guilhebl
BAN USERThat's right, please check the new fixed version of the algorithm, I tested with both scenarios: balanced and unbalanced tree, both is working, let me know if you find any other bug, please also notice the statement doesn't explicitly tell it's a binary tree, so assuming a N-ary tree
- guilhebl February 18, 2014the idea is:
1) build a Map<K,V> where K = char present in String, V = num. of occurrences of char
2) validate if palindrome can be generated by rule: all counts for each char must be even, except 1 char that can have an odd count of occurences.
3) if palindrome can be generated, build a new string distributing each group of chars at the start and end of string, if there is an odd count of a specific char C place C at the middle of String, and distribute the remaining.
4) return resulting string.
Solution in Java:
import java.util.*;
public class Solution {
public static String getPalindromeIfPresent(String s) {
// Basic validation
if (s == null || s.length() < 2 || s.equals("") ) {
return null;
}
Map<Character, Integer> mapChars = new HashMap<Character, Integer>();
char[] chars = s.toCharArray();
// Build map of each char and count occurences in String
for (int i = 0; i < chars.length; i++) {
if (mapChars.containsKey(chars[i])) {
Integer val = mapChars.get(chars[i]);
mapChars.put(chars[i], val+1);
} else {
mapChars.put(chars[i], 1);
}
}
// Validate String if possible to form palindrome rule is:
// must have all chars count even, except middle char which can be odd
int oneCharCount = 0;
for (Map.Entry<Character, Integer> entry : mapChars.entrySet()) {
if (entry.getValue() % 2 != 0) {
oneCharCount++;
if (oneCharCount > 1) {
return null;
}
}
}
int sLen = s.length();
int middle = sLen/2;
Character midChar = null;
StringBuilder s1 = new StringBuilder();
// rearrange each group of chars distributing them at the start and end of string
for (Map.Entry<Character, Integer> entry : mapChars.entrySet()) {
int charCount = entry.getValue();
Character c = entry.getKey();
if (charCount % 2 != 0) {
midChar = c;
}
int i = charCount / 2;
while (i > 0) {
s1.append(c);
s1.insert(0, c);
i--;
}
}
// if middle Char exists from odd count, place it otherwise ignore
if (midChar != null) {
s1.insert(middle, midChar);
}
return s1.toString();
}
public static void main(String[] args) {
String test = "abb";
System.out.println(getPalindromeIfPresent(test));
String test2a = "bbaa";
System.out.println(getPalindromeIfPresent(test2a));
String test2 = "nvreeodorevdne";
System.out.println(getPalindromeIfPresent(test2));
String test3 = "earth1earth";
System.out.println(getPalindromeIfPresent(test3));
}
}
Improved solution: performing less number of comparisons per iteration, also checks if the current Max Count can be covered:
(sLen - i > maxCount) will avoid additional comparisons.
Solution in Java:
public static Character findLongestRepeatingChar(String s) {
if (s == null || s.length() == 0 || s.equals("")) {
System.out.println("Error, invalid input String!");
return null;
}
char[] chars = s.toCharArray();
char maxChar = chars[0];
char curChar = chars[0];
int count = 1;
int maxCount = 0;
int sLen = s.length();
for (int i = 1; i < sLen && (sLen - i > maxCount); i++) {
if (chars[i] == curChar) {
count++;
} else {
if (count > maxCount) {
maxCount = count;
maxChar = curChar;
}
count = 1;
curChar = chars[i];
}
}
return new Character(maxChar);
}
public static void main(String[] args) {
String test = "aabbbcccdddeeefffgggghhhjjjiiklllmmnnopqrstuvxz";
System.out.println(findLongestRepeatingChar(test));
}
public class Solution {
public static void reverseKNodesLinkedList(List<Integer> list, int k) {
int len = list.size();
int i = 0;
int k1 = 0;
int kTemp = 0;
while ( i + k <= len) {
k1 = i + k - 1;
kTemp = i + k;
while (i < kTemp && i < k1) {
Integer temp = list.get(i);
list.set(i, list.get(k1));
list.set(k1, temp);
i++;
k1--;
}
if (i < kTemp) {
i = kTemp;
}
}
}
public static void main(String[] args) {
List<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
reverseKNodesLinkedList(list, 5);
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + ",");
}
}
}
Fixed Solution:
import java.util.*;
public class PrintAllNodesDistanceKFromLeaves {
class Node {
private List<Node> childs;
private String data;
public String getData() {
return data;
}
public void setData(String d) {
this.data = d;
}
public List<Node> getChilds() {
return childs;
}
public void addChild(Node child) {
if(childs == null) {
childs = new ArrayList<Node>();
}
childs.add(child);
}
@Override
public String toString() {
return data;
}
}
/**
* Winds back to K from leaf node until it reaches a node which diff from K is 0
*
* @param root
* @param k
* @return diff from K
*/
public int getDistanceKFromLeaf(Node root, int k) {
// is leaf
if (root == null || root.getChilds() == null || root.getChilds().isEmpty()) {
return k-1;
}
int distKMin = Integer.MAX_VALUE;
boolean printed = false;
if (root.getChilds() != null && !root.getChilds().isEmpty()) {
for (Node child : root.getChilds()) {
int distK = getDistanceKFromLeaf(child, k);
if (distK == 0 && !printed) {
System.out.println(root.getData());
}
if (distK > 0 && distK < distKMin) {
distKMin = distK;
}
}
}
return distKMin - 1;
}
/*
* 1) Test scenario 1: balanced tree
*
* Sample Tree:
* 1
2 3 4
a b c d e
*/
public Node buildTestTree() {
Node root = new Node();
root.setData("1");
Node n2 = new Node();
n2.setData("2");
Node n3 = new Node();
n3.setData("3");
Node n4 = new Node();
n4.setData("4");
root.addChild(n2);
root.addChild(n3);
root.addChild(n4);
Node na = new Node();
na.setData("a");
Node nb = new Node();
nb.setData("b");
n2.addChild(na);
n2.addChild(nb);
Node nc = new Node();
nc.setData("c");
n3.addChild(nc);
Node nd = new Node();
nd.setData("d");
Node ne = new Node();
ne.setData("e");
n4.addChild(nd);
n4.addChild(ne);
return root;
}
/*
* 1) Test scenario 2: unbalanced tree
*
* Sample Tree:
* 1
2 3 4
a b c d e
a1 c1 c2
c11 c12
*/
public Node buildTestTree2() {
Node root = new Node();
root.setData("1");
Node n2 = new Node();
n2.setData("2");
Node n3 = new Node();
n3.setData("3");
Node n4 = new Node();
n4.setData("4");
root.addChild(n2);
root.addChild(n3);
root.addChild(n4);
Node na = new Node();
na.setData("a");
Node nb = new Node();
nb.setData("b");
n2.addChild(na);
n2.addChild(nb);
Node na1 = new Node();
na1.setData("a1");
na.addChild(na1);
Node nc = new Node();
nc.setData("c");
n3.addChild(nc);
Node nd = new Node();
nd.setData("d");
Node ne = new Node();
ne.setData("e");
n4.addChild(nd);
n4.addChild(ne);
Node nc1 = new Node();
nc1.setData("c1");
nc.addChild(nc1);
Node nc2 = new Node();
nc2.setData("c2");
nc.addChild(nc2);
Node nc11 = new Node();
nc11.setData("c11");
nc1.addChild(nc11);
Node nc12 = new Node();
nc12.setData("c21");
nc1.addChild(nc12);
return root;
}
public void execute() {
Node root = buildTestTree();
getDistanceKFromLeaf(root, 2);
System.out.println(" \n------------------\n ");
Node root2 = buildTestTree2();
getDistanceKFromLeaf(root2, 2);
}
public static void test() {
PrintAllNodesDistanceKFromLeaves solution = new PrintAllNodesDistanceKFromLeaves();
solution.execute();
}
}
Solution using difference of sum is nice but as pointed by samuel: what if the you have lots of elements and the numbers are big, we will get overflow error
proposed solution is:
1) Create a HashMap<K, V> where K = number and V = count occurences of number
2) loop through both arrays at the same time adding values and counts to Map
3) iterate over HashMap and print those elements where count = 1
Implementation in Java:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public static void printMissingElems(int[] a, int[] b) {
Map<Integer, Integer> mapCount = new HashMap<Integer, Integer>();
int i = 0;
int aLen = a.length;
int bLen = b.length;
int lenBiggest = aLen > bLen ? aLen : bLen;
while (i < lenBiggest) {
if (i < aLen) {
addNum(mapCount, a[i]);
}
if (i < bLen) {
addNum(mapCount, b[i]);
}
i++;
}
printDiffNums(mapCount);
}
public static void printDiffNums(Map<Integer, Integer> mapCount) {
for(Map.Entry<Integer, Integer> entry : mapCount.entrySet()){
if (entry.getValue() == 1) {
System.out.println(entry.getKey());
}
}
}
public static void addNum(Map<Integer, Integer> mapCount, int num) {
if (!mapCount.containsKey(num)) {
mapCount.put(num, 1);
} else {
int count = mapCount.get(num);
mapCount.put(num, count + 1);
}
}
public static void runSampleTests() {
int[] a = {1, 4, 8, 3, 15, 33, 92, 145, 25, 22, 29, 38, 73, 66, 71};
int[] b = {1, 4, 8, 3, 15, 19, 33, 92, 145, 25, 22, 29, 38, 44, 73, 66, 71};
printMissingElems(a, b);
}
public static void main(String args[]) {
runSampleTests();
}
}
import java.util.ArrayList;
import java.util.List;
public class Solution {
public static char[][] fillMatrix0(char[][] m) {
int rows = m.length;
int cols = m[0].length;
char[][] ret = new char[rows][cols];
List<String> posList = new ArrayList<String>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (m[i][j] == 'O' && ret[i][j] != 'X') {
posList.clear();
posList.add(i + "," + j);
if (isSurroundedByX(posList, m, i, j)) {
// mark X for all found in block
for (String string : posList) {
// expecting format i,j
int posI = Integer.parseInt(string.substring(0, 1));
int posJ = Integer.parseInt(string.substring(2, 3));
ret[posI][posJ] = 'X';
}
} else {
ret[i][j] = 'O';
}
} else {
ret[i][j] = 'X';
}
}
}
return ret;
}
public static boolean isSurroundedByX(List<String> positionList, char[][] m, int i, int j) {
if (m == null || m.length == 0) {
return false;
}
int rows = m.length;
int cols = m[0].length;
// test boundary
if (i == 0 || i == rows - 1) {
return false;
}
if (j == 0 || j == cols - 1) {
return false;
}
// check up,
if (m[i - 1][j] == 'O' && !positionList.contains((i - 1) + "," + j)) {
positionList.add( (i - 1) + "," + j);
if (!isSurroundedByX(positionList, m, i - 1, j)) {
return false;
}
}
// check right
if (m[i][j + 1] == 'O' && !positionList.contains((i) + "," + (j + 1))) {
positionList.add( (i) + "," + (j + 1) );
if (!isSurroundedByX(positionList, m, i, j + 1)) {
return false;
}
}
// check down
if (m[i + 1][j] == 'O' && !positionList.contains((i + 1) + "," + j)) {
positionList.add( (i + 1) + "," + j );
if (!isSurroundedByX(positionList, m, i + 1, j)) {
return false;
}
}
// check left
if (m[i][j - 1] == 'O' && !positionList.contains(i + "," + (j - 1))) {
positionList.add( i + "," + (j - 1) );
if (!isSurroundedByX(positionList, m, i, j - 1)) {
return false;
}
}
return true;
}
public static void printMatrixResults(char[][] ret) {
int rows = ret.length;
int cols = ret[0].length;
// print results
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
System.out.print(ret[i][j] + " ");
}
System.out.println();
}
}
public static void runSampleTests() {
/*
X X X X X
X X O O X
X X O O X
O X X X X
*/
char[][] m = new char[4][5];
m[0][0] = 'X';
m[0][1] = 'X';
m[0][2] = 'X';
m[0][3] = 'X';
m[0][4] = 'X';
m[1][0] = 'X';
m[1][1] = 'X';
m[1][2] = 'O';
m[1][3] = 'O';
m[1][4] = 'X';
m[2][0] = 'X';
m[2][1] = 'X';
m[2][2] = 'O';
m[2][3] = 'O';
m[2][4] = 'X';
m[3][0] = 'O';
m[3][1] = 'X';
m[3][2] = 'X';
m[3][3] = 'X';
m[3][4] = 'X';
char[][] ret = fillMatrix0(m);
printMatrixResults(ret);
/*
X X X X X
X X O O X
X X O O O
O X X X X
*/
m = new char[4][5];
m[0][0] = 'X';
m[0][1] = 'X';
m[0][2] = 'X';
m[0][3] = 'X';
m[0][4] = 'X';
m[1][0] = 'X';
m[1][1] = 'X';
m[1][2] = 'O';
m[1][3] = 'O';
m[1][4] = 'X';
m[2][0] = 'X';
m[2][1] = 'X';
m[2][2] = 'O';
m[2][3] = 'O';
m[2][4] = 'O';
m[3][0] = 'O';
m[3][1] = 'X';
m[3][2] = 'X';
m[3][3] = 'X';
m[3][4] = 'X';
char[][] ret1 = fillMatrix0(m);
System.out.println();
printMatrixResults(ret1);
}
public static void main(String args[]) {
runSampleTests();
}
}
public class Solution {
public static boolean isSubsetSum(int set[], int n, int sum)
{
// The value of subset[i][j] will be true if there is a subset of set[0..j-1]
// with sum equal to i
boolean[][] subset = new boolean[sum+1][n+1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0][i] = true;
// If sum is not 0 and set is empty, then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
// Fill the subset table in botton up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i][j] = subset[i][j-1];
if (i >= set[j-1])
subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
}
}
boolean found = subset[sum][n];
// printing values found
if (found) {
for (int i = sum; i > 0; i--) {
for (int j = n; j > 0; j--) {
while (subset[i][j] == false) {
if (i >= set[j]) {
i = i - set[j];
System.out.println("[" + i + "," + j + "]" + "--->"
+ set[j]);
}
while (i > 0 && j > 0 && subset[i][j] != false) {
j--;
}
}
}
}
}
return found;
}
public static void printSubsetSum(int[] set, int sum) {
int n = set.length;
if (isSubsetSum(set, n, sum) == true) {
System.out.println("Found SubsetSum");
}
else {
System.out.println("No combination matches");
}
}
public static void main(String args[]) {
int set[] = {1, 2, 3, 5, 7, 10};
int sum = 15;
printSubsetSum(set, sum);
int set2[] = {1, 2, 3, 5, 7, 10};
int sum2 = 9;
printSubsetSum(set2, sum2);
int set3[] = {1, 2, 3, 5, 7, 10};
int sum3 = 100;
printSubsetSum(set3, sum3);
}
}
an implementation based on comment of Nascent:
import java.util.*;
public class Solution {
class TreeNode {
private TreeNode leftNode;
private TreeNode rightNode;
private int value;
public TreeNode(int value) {
super();
this.value = value;
leftNode = null;
rightNode = null;
}
public TreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public void addNode(int val) {
if (value == val) {
System.out.println("Error duplicate element: " + value + " = " + val);
}
if (value > val) {
if (leftNode != null) {
leftNode.addNode(val);
} else {
leftNode = new TreeNode(val);
}
}
if (value < val) {
if (rightNode != null) {
rightNode.addNode(val);
} else {
rightNode = new TreeNode(val);
}
}
}
}
private static TreeNode btreeToListUtil(TreeNode root){
if( root == null) {
return null;
}
if(root.getLeftNode() != null){
TreeNode leftTreeNode = btreeToListUtil(root.getLeftNode());
while(leftTreeNode.getRightNode() != null){
leftTreeNode = leftTreeNode.getRightNode();
}
leftTreeNode.setRightNode(root);
root.setLeftNode(leftTreeNode);
}
if(root.getRightNode() != null){
TreeNode rightTreeNode = btreeToListUtil(root.getRightNode());
while(rightTreeNode.getLeftNode() != null){
rightTreeNode = rightTreeNode.getLeftNode();
}
rightTreeNode.setLeftNode(root);
root.setRightNode(rightTreeNode);
}
return root;
}
public static TreeNode btreeToList(TreeNode root){
TreeNode head = btreeToListUtil(root);
while(head.getLeftNode() != null){
head = head.getLeftNode();
}
return head;
}
public static List<Integer> btreeToValueList(TreeNode root){
TreeNode head = btreeToList(root);
List<Integer> returnList = new ArrayList<Integer>();
returnList.add(head.getValue());
while(head.getRightNode() != null){
head = head.getRightNode();
returnList.add(head.getValue());
}
return returnList;
}
public static void printPairsSumK(List<Integer> vals, int k) {
int start = 0;
int end = vals.size() -1;
int sum = 0;
while (start < end) {
sum = vals.get(start) + vals.get(end);
if (sum == k) {
System.out.println(vals.get(start) + " + " + vals.get(end) + " = " + k);
start++;
} else if (sum < k) {
start++;
} else if (sum > k) {
end--;
}
}
}
public void runSolution(TreeNode root, int sum) {
// 1. Convert Binary Tree to list
List<Integer> valueList = btreeToValueList(root);
// 2. print pairs which sum up to K
printPairsSumK(valueList, sum);
}
public void runTests() {
TreeNode root = new TreeNode(1);
root.addNode(2);
root.addNode(3);
root.addNode(4);
root.addNode(5);
root.addNode(6);
root.addNode(7);
root.addNode(8);
int sum = 6;
// should print 1 + 5 = 6, 2 + 4 = 6
runSolution(root, sum);
TreeNode root2 = new TreeNode(2);
root2.addNode(34);
root2.addNode(56);
root2.addNode(23);
root2.addNode(12);
root2.addNode(6);
root2.addNode(78);
root2.addNode(33);
root2.addNode(11);
root2.addNode(20);
root2.addNode(24);
root2.addNode(14);
root2.addNode(30);
int sum2 = 44;
// should print 33 + 11 = 44, 20 + 24 = 44, 14 + 30 = 44
runSolution(root2, sum2);
TreeNode root3 = new TreeNode(3);
root3.addNode(-1230);
root3.addNode(2230);
root3.addNode(-500);
root3.addNode(1500);
root3.addNode(6500);
root3.addNode(8000);
root3.addNode(8100);
root3.addNode(500);
root3.addNode(2510);
root3.addNode(1510);
root3.addNode(490);
root3.addNode(510);
root3.addNode(8750);
root3.addNode(-6750);
int sum3 = 1000;
// should print -1230 + 2230 = 1000, -500 + 1500 = 1000, 490 + 510 = 1000
runSolution(root3, sum3);
}
public static void main(String args[]) {
Solution sol = new Solution();
sol.runTests();
}
}
initialize an array of int[10] from 0 .. 9
for each i in N keep getting reminder of i / 10 and increment array for each value found.
public static void getNumberOfOcurrencesOfDigits(int n) {
int[] sums = new int[10];
for (int i = 0; i < 10; i++) {
sums[i] = 0;
}
sums[0]++;
for (int i = 1; i <= n; i++) {
int rem = i % 10;
int div = i / 10;
sums[rem]++;
while (div > 0) {
rem = div % 10;
div = div / 10;
sums[rem]++;
}
}
for (int i = 0; i < sums.length; i++) {
System.out.println(i + " = " + sums[i]);
}
}
RepI am randy, 29 year old and I am doing a job. I am doing a job as a plant ...
I just tested with case: matchStrings("faceboooook", "f.ceb..o*k")
- guilhebl February 18, 2014should print true, but it prints false