Interviews with other companies!

Following are the questions that I and some of my friends had faced in different interviews, some time back.

Q1. Given a sorted array, how do you find the index of the first occurrence of a given number, x? For example, consider the sorted array, 1 2 3 3 4 5 and the index of the first occurrence of the number 3 (=x) is 2 (assuming that the array begins with 0 index).


This can be solved by slightly modifying the binary search algorithm. Perform binary search for number x in the array and if you find a match, recursively perform binary search on the left sub-array for the number x, to check whether the match found is the first occurrence or not. Running time complexity is O(lg n).


Q2. Given two arrays A and B of same size 'n', find if there exists a set of pairs (a_i, b_i), such that a_i belongs to A and b_i belongs to B and a_i+b_i = S, for all 1 < i < n. Note that, an element a_i (or b_i) can only appear in exactly one pair, in the entire set.


Sort the two arrays, one in non-increasing order and the other in non-decreasing order. If there exists such a set, then the set will be formed only with the pairs obtained by combining the first elements of the two sorted arrays. For example, let a₁....a_n be one sorted array (in non-increasing order) and b₁....b_n be the other sorted array (in non-decresing order). Then the required set, if at all exists, is (a₁, b₁), ...... (a_n, b_n) (Think why??).


Q3. (Interviewed for: Software Development Engineer)Given an array of 'n' numbers and a number 'k' (< n), compute the numbers which are obtained by computing the smallest number in the window of size 'k' with starting index i (varying from 0 to n-k).


Hint: Use heap :)


Q4. Write a code to perform breadth first search in a binary tree.


This is nothing but level-order traversal.

Q5. Write a code to convert a decimal number to a binary number.


Following are a set of simple puzzles.


Puzzle-1: There are three baskets with one having apples in it, the other having oranges in it and the third basket having both oranges and apples. Each of the basket have labels on them, saying what is contained in each of the basket. However, all the three baskets have been labeled WRONGLY. That is, not even one basket bears the correct label on it. A trial is defined as choosing a basket and drawing a fruit from it, observing it and replacing it in the basket. How many minimum trials are needed to label each basket correctly.


Answer to this puzzle is 1 (Find out how??).


Puzzle-2: There are 25 horses with a race track, in which only 5 horses can run at a time. How many races need to be conducted to identify the top 5 fastest running horses.


Answer is 7 (how??).

Puzzle-3: The classic puzzle of 2 eggs and 100 floors problem (google for the exact question).