vincethecoder
BAN USER@IntwPrep.MS usually strings can be composed of ASCII or Unicode values for instance. During an interview, it is ideal to clarify the kind of strings we are dealing with and probably proceed to determine whether we would use 128 or 256 characters.
- vincethecoder December 20, 2013@guest, most certainly. I just realized I omitted the linear as part of my sentence. I updated my response. It's a linear logarithmic complexity O(N log N). That said, we can achieve a balanced tree using this approach.
- vincethecoder December 20, 2013String is an immutable object. "in place" modification is not possible!
- vincethecoder December 19, 2013PS: @Gaurav, I can send you a link to download my entire source code so that you can run tests on the logic in your desired IDE. Recursion can be a challenge to comprehend without seeing it in action. Let me know man. Cheers.
- vincethecoder December 19, 2013@Gaurav, you are mistaken, although you were close to identifying the position of 4.
Firstly the root will be 2: my code logic sets the root to the mid of the array and then slices left and right of the array until we have completely exhausted the contents of the array {1, 4, 2, 5, 3}
This is what I mean:
int mid = (start + end) / 2;
TreeNode n = new TreeNode(arr[mid]);
So there is no WAY, the value 1 will be the root of the tree.
Yes 4 will be in the right position of 1 - which is correct, and the formed tree is valid according to the definition of a balanced tree. A balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.
Here is the tree I formed based on my logic:
/* The final tree output */
2
/ \
1 5
\ \
4 3
So the tree is clearly balanced ;)
Happy Holidays!!!
Use a recursive approach to achieve a linear logarithmic complexity. Let's see this in action:
/* Create a wrapper function*/
TreeNode createBalancedTree(int[] array) {
return createBalancedTree(array, 0, array.length - 1);
}
/* Recursive function*/
TreeNode createBalancedTree(int[] array, int min, int max) {
if (max < min) return null;
int mid = (min + max) / 2;
TreeNode node = TreeNode(array[mid]);
node.setLeftChild(createBalancedTree(array, min, mid - 1));
node.setRightChild(createBalancedTree(array, mid + 1, max));
return node;
}
PS: This also create a balanced binary search tree, so we kill 2 birds with a stone.
To use this function simply create an array as below:
int[] array = {1, 4, 2, 5, 3};
TreeNode node = createBalancedTree(array);
This can be resolved using a simple approach - no hashmaps. You can reduce your complexity to O(N) by simply using an array of size 128 characters (to represent ASCII values). This boolean array will track the characters you encounter as you iterate through the string.
Implementation below:
String removeDuplicates(String str) {
StringBuilder sb = new StringBuilder();
boolean[] char_set = new boolean[128];
for (int i = 0; i < str.length(); i++) {
int c = str.charAt(i);
if (!char_set[c]) {
sb.append((char)c);
char_set[c] = true;
}
}
return sb.toString();
}
/**
* Programming Languguage Used : Java
*
* This method will print the two numbers which form the minimum sum.
*
* @author Vincent Sam <kobesam@gmail.com>
*
* @param array of numbers
* @return void (prints the two numbers which form the minimum sum).
*
*/
public static void getMininalSum(int[] digits) {
int minSum = 0, i = 0;
int len = digits.length;
StringBuilder op1 = new StringBuilder(), op2 = new StringBuilder();
Arrays.sort(digits);
while (i < len) {
if (i%2==0) op1.append(digits[i++]);
else op2.append(digits[i++]);
}
minSum = (len > 0) ? Integer.parseInt(op1.toString()) + Integer.parseInt(op2.toString()) : 0;
System.out.printf(" The minimal sum of %s, %s = %d \n", op1.toString(), op2.toString(), minSum);
}
- vincethecoder April 01, 2016