Cracking the Coding Interview Chapter 04 Java Solutions - Trees and Graphs
These days I'm seeing graph problems pop up more and more, maybe that's just the result of getting into tougher technical interviews. Still, there are the types of questions that separate the men from the boys. Nail these and you're well on your way to that dream job.
Notes:
- Graphs translate well to maps. A world map might be a collection of links and nodes all stuffed into a giant "Graph" class, but all those nodes aren't neccessarliy connected to each other.
Graphs
Breadth First Search, pretty simple. Recusivley visit all nodes as we encounter them. Only issue is we could end up traveling way down one large branch before making it to others.
private void depthFirstSearch(Node head) {
if ( head.visited ) {
return;
}
System.out.println("Visting: " + head.value);
head.visited = true;
for (Node node : head.nodes) {
depthFirstSearch(node);
}
}
Depth First Search, use a queue to up the importance of visiting nodes as you encounter them.
private void breadthFirstSearch(Node head) {
Queue queue = new ArrayBlockingQueue<>(20);
queue.add(head);
visit(head);
while (!queue.isEmpty()) {
Node r = queue.remove();
for (Node n : r.nodes) {
if (!n.visited) {
visit(n);
queue.add(n);
}
}
}
}
Ch04Ex01: Determine if a tree is balanced
Before we get into the details of this question, remembering how to determine the height of a BST is extremely important. It can be used to solve many tree questions.
private int getTreeDepth(Node tree) {
if ( tree == null ) {
return 0;
}
return 1 + Math.max(getTreeDepth(tree.left), getTreeDepth(tree.right));
}
However this question isn't about checking the depths of branch. We want to know if the branches themselfs are balanced. If you're paying attention, which I'm often not, the question defines depth and that gives us a clue. When solving this on the whiteboard, lots of examples of trees that are balanced and unbalanced would help out.
In my case I started with a node and no values, this found the base case and I built from there. Start small, work your way backwards.
private boolean isBalanced(Node head) {
if ( head == null ) {
return true;
}
int left = getTreeDepth(head.left);
int right = getTreeDepth(head.right);
if ( left == right ) {
return isBalanced(head.left) && isBalanced(head.right);
}
else {
return false;
}
}
From here we can solve this to the interviewers question of blanced by replacing left == right, with a diff of no more than one. See the book for final solution.
Output...
5
/ \
/ \
/ \
/ \
3 8
/ \ / \
/ \ / \
2 4 7 9
/
6
Is tree balanced at node 5: false
3
/ \
2 4
Is tree balanced at node 3: true
8
/ \
/ \
7 9
/
6
Is tree balanced at node 8: false
Ch04Ex02: Determine if there is a path between two nodes in a graph
For the most part pretty staight forward if you know how to traverse a graph. My solution was a depth first search, however I was tripped up when I tried to pass a Boolean into the method to be updated by ref. This won't work and I had to wrap it in a custom class. A little hacky, but not too bad.
class FoundClass {
boolean found;
}
private void isAccessible(Node current, Node end, FoundClass found) {
System.out.println("visting: " + current.value);
current.visited = true;
if ( current == end ) {
System.out.println("accessible");
found.found = true;
}
for (Node n : current.nodes) {
if ( n.visited == false ) {
isAccessible(n, end, found);
}
}
}
The books solution prefers to do this in a breadth first search. Marking the class we're looking for and attemping to mark the class we're trying to get to.
Ch04Ex03: Create a minimal height BST from an ordered array
I quickly got myself into the weeds on this project when trying to split the data up recursivley. I was more worried about one off errors than the pattern I would use to solve the problem. Although it's not as fancy, an iterative solution probably would have been easier to start with.
I had a thought while working on this one, I kept running into one off errors when splitting the array. Doing well on an interview is about plowing through these issues regardless. Can you keep pressing on despite getting confused? What can you solve concretly first? Keep pressing on, don't trash everything and start over. Anyway, here's the real solution, I believe this recursive pattern is helpful for mergesort as well.
private Node splitInsert(int[] arr, int start, int end) {
if ( end < start ) {
return null;
}
int mid = (start + end) / 2;
Node n = new Node(arr[mid]);
n.left = splitInsert(arr, start, mid - 1);
n.right = splitInsert(arr, mid + 1, end);
return n;
}
Output...
4
/ \
/ \
/ \
/ \
2 6
/ \ / \
/ \ / \
1 3 5 7
\
8
Ok let's do this iteratively.
... Damn! Coded a solution that is just flat out wrong.. Can't stress this enough, sovle on the board first, without code, then go in for the solution.
//oops! this creates a fairly large tree, another reason to go ahead and solve this by hand first, then translate to code...
private Node splitInsertIter(int[] arr) {
Node rtn = null;
if ( arr.length % 2 != 0 ) { //odd num items
rtn = Node.insert(rtn, new Node(arr[arr.length/2]));
}
int rightStart = arr.length / 2;
int leftStart = rightStart - 1;
while ( rightStart < arr.length ) {
rtn = Node.insert(rtn, new Node(arr[leftStart]));
rtn = Node.insert(rtn, new Node(arr[rightStart]));
leftStart--;
rightStart++;
}
return rtn;
}
The (incorrect) output..
4
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
3 5
/ \
/ \
/ \
/ \
2 6
/ \
/ \
1 7
\
8
Sooooo... this one sent me off on a tangent. Clearly the recursive pattern used to solve mergesort is useful here. I had to get this one under my fingers. Checkout my algorithm notes for details on implementing mergesort.
Ch04ex04: Print each layer of a tree
Ok, I haven't checked the book yet, but I solved this simply by implementing a breadth first search. Once I've cleared all the items off the stack, I'm done with a layer and can move on to the next.
private void runMe() {
Node root = Node.treeFromArray(new Integer[]);
BTreePrinter.printNode(root);
List<List> treeLayers = eachLayer(root);
for ( List layer : treeLayers ) {
System.out.println("Printing Layer");
for (Node n : layer) {
System.out.print(n.data + ", ");
}
System.out.println("");
}
}
private List<List> eachLayer(Node root) {
List<List> rtn = new ArrayList<>();
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
List levelList = new ArrayList<>();
while (!stack.isEmpty()) {
levelList.add(stack.pop());
}
for (Node n : levelList) {
if (n.left != null) {
stack.add(n.left);
}
if (n.right != null) {
stack.add(n.right);
}
}
rtn.add(levelList);
}
return rtn;
}
Output...
5
/ \
/ \
/ \
/ \
2 7
/ \ \
/ \ \
1 3 8
/
0
Printing Layer
5,
Printing Layer
7, 2,
Printing Layer
3, 1, 8,
Printing Layer
0,