Interview 1

1. You have a C-style string containing some spaces. Move the spaces to the start of the string. Do this in place in one iteration.
2. You have a bit pattern and an infinite stream of bits coming in. You need to raise an alarm whenever the given pattern occurs. Storing the stream is not allowed.

Interview 2

1. You have an array of size N. Implement a queue using this.
2. A sorted array has been rotated. You need to find the point of inflection, i.e., the position at which the smallest element of the array is present. (I did this in log N time). For example, if the array is [6,7,8,9,1,2,3,4,5], the output should be 4.

Interview 3

1. You have a BST and an integer value (take it to be variable val). You need to print out all possible paths in the BST which sum to val. These paths may or may not start at the root.
2. You are given a dictionary and two strings, a and b. You need to convert string a to b such that only one alphabet is changed at a time, and after each change, the transformed string is in the dictionary. You need to do this in the minimum number of transformations. For example, the transformation from cat to boy can be done as follows: cat → bat → bot → boy (if the dictionary contains bat and bot).

Interview 4

1. You have been given a tree (not binary; it can have any number of children) in an array. The ith entry of the array is the parent of the ith node. For the root node, this entry is -1. You need to find the height of this tree (an O(N) solution was asked for). For example, the array [2,6,3,6,3,6,-1] represents the tree below. The height of the tree is 4 (the path from 6 to 0).

                                                       6
                                                    /  |   \
                                                  1   3   5 
                                                      /  \
                                                     2   4
                                                    /
                                                   0
   

You are given an array of numbers. Your task is to print the length of the maximum continuous sequence that you encounter.

For example, if the input is [3, 8, 10, 1, 9, 6, 5, 7, 2], the continuous sequences are {1, 2, 3} and {5, 6, 7, 8, 9, 10}. The latter is the longest one, so the answer becomes 6.

An O(n) solution was requested, assuming you have a hash map that supports O(1) insertion and fetching operations.