matthewrobertwalters
BAN USERHere is a solution in java. The hard part of this algorithm is communicating the count of visited nodes between recursive calls. It would be trivial if there was some out-of-scope variable, but that is ugly and not needed. Java is pass by value, so using the primitive java int does not retain its value between recursive calls, however an Integer object wrapper will, because all we are doing is passing a copy of the reference to the integer object, which any recursive call can mutate.
Node findNthInOrderNode(Node root, Integer n){
if(n < 0){ throw new IllegalArgumentException(); }
if(root != null){
Node left = findNthInOderNode(root.left(), n);
if(left != null){ return left; }
if(n == 0){ return root; }
n--;
Node right = findNthInOrderNode(root.right, n);
if(right != null){ return right; }
}
return null;
}
Can you provide the code for this? Remember you are given a String[], you cannot magically transform it into a trie. I believe that this would take O(nlog(a)) to construct where n is the size of the array and a is the average string size. Why not just do linear search?
- matthewrobertwalters August 31, 2012Assuming that 4GB can fit into memory all at once may or may not be appropriate. Here is a solution in java that runs in O(n) where n is the size of the list:
void printKLargestKInt(File file, int k){
Scanner scanner = new Scanner(file);
PriorityQueue<Integer> queue = new PriorityQueue<>(k,
new Comparator<Integer>(){
public int compare(Integer x, Integer y){
if(x == y){ return 0; }
else if(x > y) { return 1; }
else{ return -1; }
}
});
while(scanner.hasNext()){
queue.add(scanner.next());
while(queue.size() > k) queue.poll();
}
scanner.close(); // should probably do this in finally clause
return queue.poll();
}
so lets look at the normal BFS algo for the this tree first:
and the algo:
assuming that process delegates to System.out.print(), then we will print:
1234567
if we instread enqueue the right child before the left, like this
this will print:
1327654
which is our goal but revered... so we can use a stack to reverse it:
This gives the correct answer, namely
- matthewrobertwalters September 06, 20124567231