gistfile1.txt

given an array of size n in which every number is between 1 and n, determine if there are any duplicates.

ask dumb questions:
are they ints, is it sorted, are there any restrictions. Can you use additional space. Can it be empty.

go with brute force question (make sure it's rock solid)




given a tree print out all paths to the leaves.

How are these paths represented? (print out node contents followed by ,)

Draw out the tree

What is the interface, do you have any classes?

You have a left and right pointers and value

Use DFS for the solution




Given a tree, print out all paths to the leaves.

(threading the tree) what about parent pointers



can I asssume this input is not null?
public static void printStuffWrapper(Node root){
 if(node == null){
  System.out.println("wat");
 }
 LinkedList<Character> pathString = new LinkedList<Character>();

 printStuff(node, pathString);
}


public static void printStuff(Node root, LinkedList<Character> pathString){
 pathString.add(root.data); 
 if(root.isLeaf()){
  printPath(pathString);
  return;
 }

 if(root.left != null){
  printStuff(root.left, pathString);
  pathString.removeLast(); 
 }

 if(root.right != null){
  printStuff(root.right, pathString);
  pathString.removeLast();
 }

 
}

public static void printPath(LinkedList<Character> pathString){
 StringBuilder sb = new StringBuilder();
 LinkedListNode<Character> lln = pathString.getFirst();
 for(int i = 0; i < pathString.size(); i++){
  sb.append(lln.data);
  lln = lln.next;
 }

 System.out.println(sb.toString());

}


printThings(Node root, String path){
 path +=root.value;
 if(root.isLeaf()){
  print(path);
  return;
 }

 if(root.left != null){
  printThings(root.left, path);
 }

 if(root.right != null){
  printThings(root.right, path);
 }
}

O(n) time
O(n^2) space (aren't you just creating one string for each node)?




BFS

printThings(Node root, String path){
 Queue<Entry> q = new ....
 q.add(new Entry(


}

How does he save 

Space(2^N)
time(N)




talk out your algorithm first then wait for the ok?