How to prepare for an interview - 3

Today I will solve a new set of technical interview questions, as you may know this is the third post in the How to prepare for an interview. If you have not study the last post please read it here.

Remember you should discuss these solutions with me, and refer if there are mistakes or other good solutions.

Problems

21. Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree Avoid storing additional nodes in a data structure NOTE: This is not  necessarily a binary search tree.

22. You have two very large binary trees: T1, with Millions of node, and T2 with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

23. Given a binary tree, in which each node contains a value. Design an algorithm to print all paths that sums to that value. Note that it can be any path in the tree - it doesn't have to start at the root.

24. You are given two 32 bit numbers N and M, and two bit positions i, and j. Write a method to set all bits between i and j in N to M.

(e.g., M becomes a substring of N located at i and starting at j).

Example:

Input: N = 10000000000, M = 10101, i = 2, j = 6

Output: N = 10001010100

25. Write a method to generate the nth Fibonacci number.

26. Imagine a robot sitting on the upper left hand corner of N*N grid. The robot can only move in two directions: Right and Down How many possible paths are there for the robot.

27. Same problem at 26, but if there are some blocks in some cells, print out how many paths are there.

28. Write a method that returns all subsets of a set.

29. Write a method to compute all permutations of a string.

30. Implement an algorithm to print all valid (properly opened, closed) combinations of parentheses.

Example:

Input: 3

Output: ()()(), ()(()), (())(), ((()))

31. Implement the paint-fill function that one might see on many image editing programs. That is, given a screen (represented by 2 dimension array of colors), a Point, and a new color, Fill in the surrounding area until you hit a border of that color.

Now we have solved all today's problems. I know it were harder than the previous one, But i'm sure you will enjoy solving them, read the next post here.