Skip to main content

Interview Questions (and answers) by Aviad Ezra

Search This Blog

Link: The Great Tree-List Recursion Problem

Get link
Facebook
X
Pinterest
Email
Other Apps

Here's a link to the article: http://cslibrary.stanford.edu/109/TreeListRecursion.pdf

Get link
Facebook
X
Pinterest
Email
Other Apps

Comments

Post a Comment

Popular Posts

Practice depth first traversals

Interviewers love to ask questions that include depth first traversals in some shape or form, these questions are much easier to solve when you have a good example of a tree and you’ve fully internalized the route of the traversals. This post includes a quick introduction to the most common depth first traversals ( in-order , pre-order and post-order) and a practice. In-order traversal: L-N-R ( L eft, Current N ode, R ight) in-order traversal starts from the left most node, move to the current node, and to the rights node. Given the tree below, in-order traversal will visit the nodes in an alphabetical order. A, B, C, D, E, F, G, H, I. Here’s the recursive implementation private static void getInorderRecursive( BinaryTreeNode<Character> node, List<BinaryTreeNode<Character>> result) { if (node == null) { return; } // Go left all the way getInorderRecursive(node.getLeft(), result); // Visit current node result.add(no...

Find First Ancestor

Given a binary tree, find the first (i.e. lowest) ancestor of two node. We can solve this inpalce by iterating depth first (solution 1), or by storing the path from root to each node into two Stacks, and popping items from both stacks until we find a mismatch (solution 2). Tests public class AncestorFinderTest { private static final Boolean USE_ARRAY = true; @Test public void findFirstAncestor_ancestorIsRoot() throws Exception { AncestorFinder ancestorFinder = createFinder(); BinaryTreeNode tree = createTree(); final BinaryTreeNode ancestor = ancestorFinder.findFirstAncestor(tree, 9, 11); assertEquals(1, ancestor.data); } @Test public void findFirstAncestor_ancestorIsSecond() throws Exception { AncestorFinder ancestorFinder = createFinder(); BinaryTreeNode tree = createTree(); final BinaryTreeNode ancestor = ancestorFinder.findFirstAncestor(tree, 10, 11); assertEquals(2, ancestor.data); ...

Boggle - find words in matrix of letters

Given a collection of words, find which of the words exist in a matrix of letters. You can move downwards, to the left and diagonally. Example: Given the matrix bellow, find the words “ALL” and “LOL” A G H N U L O A N M L K L B V M Approach (Brute Force) The brute force is to iterate over all possible word combinations, and look up the input worlds in every possible word combination. If you know how to iterate recursively though a grid that’s fairly straight forward, but it’s also inefficient. Iterate through all the cells For each cell, Call FindWordRecursive, injecting the cell’s row , column and a new empty buffer (StringBuilder) (Base Case) Break if the cell’s row , column outside the matrix FindWordRecursive clones the input buffer and adds the char located at row, column Check if the string composed by the new input buffer appears in the in the given collection of words, if yes, add the word the result (Optimization of stopping poi...

Powered by Blogger