1. Given n non overlapping intervals and an element. Find the interval into which this element falls.

Answer :

We can extend binary search to intervals.(Assuming the intervals are sorted)

consider interval [a,b].
if (a-x)(b-x) <=0
then x belongs to [a,b].
else
if x>a

Element can be present only in the intervals to its right.
so select the middle interval among them to it's right and repeat the procedure.
else
element can be present only in the intervals to its left.
so select the middle interval among them to it's left and repeat the procedure.

The complexity of this problem is log(N) where N is the number of sorted non-overlapping intervals.

Worst case is take all intervals one at a time and see whether the element lies in the interval or not.It will take O(n).

2. Given two sorted arrays A and B.  Find the intersection of these arrays A and B.

Answer :   The intersection can be found by using a variation of merge routine of the merge sort.

3. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Answer :

1. There is only one cheat husband

If it is so then 99 wives knew it before. So the cheated wife got the idea from queen that her husband is cheating. So she will kill him. Next morning every wife will know there is no cheat husbands anymore.

2. There are more than one cheat husbands

 In this case, all of the wives already had the idea prior to queen's information. Its just that the cheated wives knew the count which is one less than what the non-cheated wives' knew - thats all. i.e. if there were 2 cheat husbands then their wives knew the count is 1 and others knew its 2. So the queen just repeated the info saying "at least 1". Same goes to 2,3,4...100 cheat husbands. So in this case no wife kills her husband.

4. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

Answer :

Let’s suppose there are a set of attributes of each shirt you are interested in: e.g. sleeve length, color, buttons (no buttons, fully button, partially buttoned from collar to chest level).

Let’s say the closet is a simple wall closet with a single closet rod running the entire length of closet. On the left you put all the short sleeve shirts, and on the right the long sleeve shorts. You separate then long and short sleeve sides with a specially marked coat hanger. Then you separate each group into no buttonoed, partially buttoned, and fully button, using more specially marked hangers. Then each sub group is separated into colored and monochrome sub-sub-groups (specially marked hangers aren’t needed for separators unless you are color blind) Then each colored group is sorted left to right according to the color spectrum: ROYGBIV: red, orange, yellow, green, blue, indigo, violet. Each monochrome ggroup is sorted left to right: white on the left, black on the right, and shades of grey in the middle, the darker greys on the right, the lighter on the left.

5. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

Answer :

Choose 6 balls and weigh 3 against 3

- if they weigh the same, you have another weighing for the remaining 2 balls and you can find the heavier one
- if they don’t weigh the same, from the group of 3 which was heavier, choose any 2 balls and weigh them
- if they weigh the same, the remaining ball is the heavier one; otherwise you just found the heavier one by weighing the 2 chosen balls.

6. Write the code for finding the min of n number. Given that n numbers are from random sampling how many times (probability) does the line (i) be executed

Answer :

min = a[0];

for(i=0;i<n;i++)

{  

     if( a[i]<min )  

{        

       min = a[i] ---- eq(i)  

}}

Once the variable min is initialized, the probability of a[i] < min is 1/2. So the expected number of occurances of equation i is (n-1)/2 .

7. Now given that the n intervals are overlapping then how do you solve? The interviewer was concentrating more on the complexities (running, memory ..)

Answer :

If the above intervals are overlapping ,then they can be merged in O(N) and then the exact intervals can be resolved later.Otherwise ,we can identify one correct interval and then linear search on its left and right neighbourhood to find the other solutions.

8. In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. If they have a boy, they stop. what is the proportion of boys to girls in the country?

Answer :    From pure probability, we get the expected number of girls born to be 1/2 with that of boys being 1.So the ratio is 2:1

9. You have to get from point A to point B. You don’t know if you can get there. What would you do?

Answer :

Utilizing a “learn as you go” approach and applying collected knowledge and data along the way is the best way to proceed. Let’s break this down farther.

Determine the amount of time you have to go from point A to point B. Spend the initial 20% of that time making a 360° search with the largest circumference possible with the in the time you have allowed.

During that time, ask people, look for maps, clues, collect data, and knowledge. At the end of the initial 360° search take an objective look at all the information you have obtained and you calculate the risk of failure you are willing to live with. Create a plan and a strategy based on your assessment of where you believe point B to be. Then you proceed on implementing your plan with predetermined intervals of reassessment and strategy improvements.

This is the best chance you have reaching point B if you don’t know if you can get there.

10. Give an example of one permutation that this data structure cannot generate.

For Example: 1234 is input. First push all 1,2,3,4 on to stack and pop all. Output will be 4321. It means that this data structure can generate 4321.

Answer :    3124