enzeart
BAN USERDynamic programming version of my previous answer:
// We want to branch the string at every valid character and count the
// fully form string permutations indicated by when we reach a point where
// we can go no further, i.e. a full permutation has been calculated.
function branchAndCount(string, index, twoDigits, lookup) {
var sub;
// If we've fallen off the end of the string, and there was a string
// to begin with, we know that we have traversed a full permutation
// of one of the result strings and should count it in the final result;
if(index == string.length) {
return (string.length > 0 && !twoDigits) ? 1 : 0;
}
if(twoDigits) {
// We check the two-digit case including the digit from the previous iteration
// of the function. If this two digit number in the range 1 - 26 then we explore
// it further as it is a valid path.
sub = string.substring(index -1, index + 1);
// Dynamic programming version. The number of permutations rooted
// at this index has already been stored by the one-digit case.
// Look it up and reuse it.
return (sub >= '1' && sub <= '26') ?
lookup[index] : 0;
} else {
// The one-digit case is always valid, so we branch here in order to explore the
// succeeding one-digit and two-digit cases.
return (lookup[index] = branchAndCount(string, index + 1, false, lookup))
+ branchAndCount(string, index + 1, true, lookup);
}
}
// Wrapper function to invoke the main processing function correctly.
function countPermutations(string) {
var lookup;
lookup = [];
return branchAndCount(string, 0, false, lookup);
}
// Invoke
console.log(countPermutations('111'));
The interviewer is testing your understanding of the lower-level implementation of these things. There's no way of knowing how to proceed without knowledge of the following:
1. Is the matrix notation implemented with a contiguously allocated backing array such that
a[][] = new matrix[5][5]; is structurally similar to a[] = new array[25]; but supports special matrix manipulation operators at the higher level?
2. What is the size of the elements in the matrix, including any alignment overhead etc.
3. Assuming address 0 is reserved for 'null' and the size of the elements has been given. Does the derived address seem valid or does it need further cross-examination.
psuedocode:
int RIGHT_SIDE = 0;
int LEFT_SIDE = 1;
int ROOT = 2;
int left_sum(node, side) {
// Base case.
if(node == null) {
return 0;
}
// Calculate the sum on the left side and add it to this node's value.
node.val += left_sum(node.left, LEFT_SIDE);
// If this node is the right child of its parent, we need to add the value of its parent
// because it is on the left side of the child. The left-sum of each node is always
// finalized before invoking the function on the right side of the node so the parent
// value is always in the proper state.
if(side == RIGHT_SIDE) node.val += node.parent.val;
// Safely calculate the left-sum on the right side of the tree after the current node
// has been fully evaluated.
left_sum(node.right, RIGHT_SIDE);
// Return the newly calculated value in case this is a left child and the parent is
// listening for a result. The right side is always ignored
return node.val;
}
// Example invocation.
void main() {
tree example_tree = new tree();
left_sum(tree.root, ROOT);
}
1. Get the coordinates of all zeros in the input matrix.
2. Populate an output matrix of the same dimensions with all cells initialized with infinity.
3. For each set of zero-coordinates recorded in step 1, iterate through the output matrix and calculate the distance with the following formula:
distance = abs(x_coordinate_of_zero - x) + abs(y_coordinate_of_zero - y)
4. If the calculated distance is less than the recorded minimum, replace the recorded minimum with the calculated distance.
Time complexity:
Where 'n' is the total number of elements in the input matrix, and 'm' is the number of zeros in the input matrix.
1. n
2. n
3. n * m
n + n + (n * m)
Runtime = O(n*m)
My code doesn't have to work in that case: "Given the level order traversal of a COMPLETE binary tree in an array...". The input tree is always complete so the format will never be messed up. Although none of this matter since my answer violates the "in-place" constraint of the question which I now know means O(1) space utilization.
- enzeart July 06, 2013import java.util.Arrays;
public class InOrderTraversal {
public static int[] fromLevelToInorder(int[] levelOrder) {
int numNodes = levelOrder.length;
int[] inOrder = new int[numNodes];
int currentNodeIndex = 0;
int currentLevel = 0;
int nodesInLevel;
int nodesPerQuadrant;
int currentLowerBound;
int currentUpperBound; /* Will always contain 1 more than the valid index, don't forget to decrement. */
while(currentNodeIndex < numNodes) { //While there are still nodes to process
nodesInLevel = (int)Math.pow(2, currentLevel); //Get the number of nodes/quadrants in this level
nodesPerQuadrant = numNodes/nodesInLevel; //Get the number of nodes in each quadrant
currentLowerBound = 0; //Initialize the lower bound
for(int i = 0; i < nodesInLevel; i++) {
currentUpperBound = currentLowerBound + nodesPerQuadrant; //Initialize the upper bound
/* Place the node in the center of the current quadrant */
inOrder[currentLowerBound + (((currentUpperBound - 1) - currentLowerBound)/2)] = levelOrder[currentNodeIndex];
currentLowerBound = currentUpperBound + 1;
currentNodeIndex++;
}
currentLevel++;
}
return inOrder;
}
public static void main(String[] args) {
int[] result;
//int[] input = {2, 1, 3};
//int[] input = {50, 25, 75, 1, 26, 52, 100};
int[] input = {70, 35, 105, 17, 50, 81, 200, 1, 18, 40, 60, 75, 90, 106, 205};
result = fromLevelToInorder(input);
System.out.println(Arrays.toString(result));
}
}
PLEASE NOT THAT I HAVE TAKEN 'IN-PLACE' TO MEAN 'CAN THE FINAL POSITION OF THE NODES BE DETERMINED FROM THEIR INITIAL POSITION IN LEVEL-ORDER FORM("[...]without building up the tree")'
1. Process the nodes level by level.
2. Each node is the center of its own quadrant.
3. For each level break the output space into 1 quadrant per node in that level.
4. Center each node in its quadrant iteratively for the current level.
5. The outer loop runs as long as there are nodes still left to be process.
6. The inner loop just iterates on the nodes in the current level.
7. The total number of iterations is {nsub0 + nsub1 + . . . . .+ nsubx} which is the sum of the nodes in all levels. This will sum up to n(the total number of nodes in the tree). The worst case running time is O(n).
1. All objects are subclasses of java.lang.Object.
- enzeart August 15, 20142. Reflexive, symmetric, transitive, consistent, and type aware, as mentioned above by Prince
are important attributes of an equals function. The equals method is closely related to the hashCode method in that they both speak about the identity of the object in question. If you override the equals method it is a good practice to override the hashCode method as well to ensure that two equal object return the same hashCode output.
3. The equals method should be implemented with the nature of the object in mind. An immutable object with hundreds of fields can have an optimized equals method which involves the object creating a hash-based id of itself upon initialization and comparing that value between two target objects when the equals method is invoked. For increasingly write-heavy objects a similar approach can be taken where hashes are generated for the more stable set of fields to optimize the average cost of comparison.