Good Interview Questions


Sometimes I wonder what is the purpose of asking problem solving questions in an interview ? Some of the interesting questions I came across in the recent past are as follows. I have solutions to some. Do let me know if you have an effiicient solution.

1) Given an array of integers randomly selected from [1,n], what is the average number of comparison to be made in finding the minimum integer ?

2) What is the complexity of merging two lists of numbers ? How will you improve the complexity if one list is very large compared to other ? What if the numbers are distributed uniformly in [1,n] in both the lists ?

3) Given a circular list of integers (some of which could be -ve), find an index i such that sum of integers from index i to index j is never < 0. First find out if such an i exists.

4) Given n sets and each set consists of characters. Let the sets be S1, S2, S3, .., Sn. Given a string denoted by x1..xk. Find out if the string x1..xk can be constructed from S1, S2, ..., Sn by first looking at S1 and then S2 and finally Sn in an efficient manner. You can look at any set only once and you need to follow the ordering for looking at the sets. In one case, assume that you can skip a set. In another case, assume that no set can be skipped.