Archive for the ‘Puzzles’ Category

Get The Hiker Down

Posted: May 4, 2014 in J P Morgan, Puzzles

Q. Hiker has reached a cliff of 200 meters height. This cliff has hooks at top, 200 meters, and at middle, 100 meters. Hiker plans to get down using hooks and his rope. But he realizes that his rope is only of 150 meters length. He also forgot to bring any additional hooks but luckily brought a knife with him. How can use his rope wisely and reach the ground safely ?

A. I couldn’t solve this question at the first shot. My proposal for hiker was to come down to 100 m hook, tie the rope at 100 m point, climb back to top and untie other end of rope. Since, we know hook is in middle, he can tie this other end to himself do a bungee jump to reach the ground 😀

Interviewer gave me some hints: No jumping risk required. Bring knife to equation. We can ignore rope used for tying knots.

Gradually, reached to a workable solution.

Right Answer:

1) Divide the rope in 100m, 50m parts. For doing this, hiker can go down to middle point, mark the rope and come back on top. Use knife for making parts.

Objective: From the middle point, we need to use 100m part. Challenge is to reach middle point, and still have hold of 100m rope.

2) Tie one end of 50m rope to topmost cliff, and make a hanging knot at other end.

Hanging Knot

 

 

 

Hanging Knot

 

3) Fold 100 m rope to two stripes of 50m (don’t cut). Pass the hanging knot through the fold. At the end, middle of 100 m part should be touching knot point, both ends are kept together.

Hook1———————-()================Hook2

200m                             150m                                100m

4). Hiker has to hold both ends of 100m part. The length of assembly is 100m. He can reach to Hook2.

5). At hook 2, release one end of the rope and keep pulling from the other end. Since, 100m part is not tied tightly, it will come out of the knot and hiker will get this 100 m part to cover rest distance.

6) Use 100 m part to get down from middle point.

 

 

 

Advertisements

Get The Job

Posted: November 21, 2011 in Microsoft, Puzzles

Q. A company plan to recruit people. But, ends up finding many more than eligible people including you :). So, they plan a strategy to cut short the people to their suit the headcount of their requirement.

People will be lined up in a queue 1, 2, 3… N.  At first phase, people at odd locations will be eliminated. Same thing will apply for next phase.

For example,

Round 1: 1, 2, 3, 4, 5, 6….N

Round 2:  2, 4, 5.. N  (People at odd locations eliminated)

Round 3: 4, 6… N (People at odd locations eliminated)

 

Y0u look charming. So, you get a choice for your position. Given the value of N, where will you position yourself to take up the job ??

 

A. I would choose position is the last power of 2 within N

for example, if N=17, the last power of 2 is 16 (2^4). Why ?? Think and tell me 🙂

Choose The Right Door

Posted: November 10, 2011 in Puzzles

Q. The king placed him in a dungeon with two doors, each guarded by a giant guard, and said: “One is the door to freedom, the other to death. One guard tells the truth, the other doesn’t. You are allowed to ask only one question from any one of these two guards; and based on the response, you may figure out which door to choose.” What is the question to be asked ?

A.  One guard says truth and other lies. If we take cumulative result, we’ll always get a lie (as atleast one of them lies). So, I will ask to guard “Will the other guard say if this door is correct ?”. One of these two guys will definitely lie which makes right door is exactly opposite to the question’s answer.

Save the Prisoners

Posted: February 13, 2011 in Algorithms, Microsoft, Puzzles

Q. There are 10 prisoners and jailer said he will play a game with them next morning. He will make all of them stand in a row and put either of black or white hat on their head. Since, they are standing in a row, they can see the hats in front of them but not the one their head or heads behind them.

Starting from the last, jailer will ask each prisoner what is the color of his own hat. If prisoner gives wrong answer, he will shoot him right at that moment.

Prisoners have to come up with a strategy such that maximum of them can be saved.

A.

The last prisoner will say black if there are odd number of black hats in front of him. For simplicity, lets assume they are in odd number.

  • Second last prisoner can count the black hats in front of him. If he gets odd number, he can conclude the hat on his head is white and black otherwise.
  • Third last prisoner, will keep his ear open on the previous answer and then he’ll calculate of total black hats in front of him and behind him. That way he can decide if total is a odd number and can predict his hat’s color.
  • Using this technique, n-1 prisoners can be guaranteed to be saved.

 

Q. You have an array of integers. Device an algorithm that can return all possible pythagorean triplets within them.

Example, (a,b,c) is a valid answer if    ”  a sq  + b sq  = c sq ”

A. My answer takes O(n sq) time.

  • Square all elements and keep them in an array. Time taken – O(n).
  • Our problem is simplified get numbers (a,b,c) such that to a + b = c.
  • Sort the array. Time taken O(nlogn)
  • Keep a as first element and c as last element. Try to find last b where a+b <=c
  • Store the index of that last b. Because a+b will be > c for further elements.
  • Now, search for the sum a+b within [b+1, c]. Binary search can be used.
  • If no triplet is found, increment a to next location and repeat the process.
  • Time complexity O(n sq).

Since O(n sq) is the most dominating its the overall time taken in this process.

Interviewer was looking for a solution that takes O(nlogn) and I am still thinking about it. 🙂

Find The Average

Posted: February 12, 2011 in Algorithms, CA, data structures, HomeShop, Puzzles

Q. Given a set of n numbers (data type long). Write an algorithm to get the average.

  • It should work if one of the contributing number is the maximum possible number of type long.
  • Casting it to other data types is not allowed.

A. This question made me thing alot as we can’t use addition for getting the average. If we do, first constraint might not get incorporated. Finally, I came up with an equation.

Keep looping till you hit the last number. Counter is the index variable for the loop that increments by one at each iteration.

average = average + (nextNumber – average)/counter

We have to round of everytime we hit an uneven divide and there is a loss of precision.

Design LRU Cache

Posted: February 12, 2011 in Algorithms, CA, HomeShop, Java, Puzzles

Q.  You have to design a LRU cache such that all operations can be done in O(1) – read, write and insert.

  • In case, cache is full, you have to remove an element which was read/written last.
  • Each read should update the timestamp of these elements.
  • Read request of the element contains a key which is not the location of the element.

A.  Assuming hashmap has retrieval complexity of O(1), we can do this using a doubly link list and a Hashmap

  • Doubly link list will be used to store indexes sorted by date/timestamp information.
  • Keep track of first and last node.
  • No sorting effort is needed as each new node will have latest timestamp.
  • The Hashmap will retrieve the node searched by key. It will also contain pointer to its respective doubly link list node.

READ –

  • Search the node by key. Retrieve the node value and index for doubly linklist.
  • Delete the node from doubly linked list and add it with the updated date value at the starting of the list.
  • Complexity of deleting a node in doubly link list is O(1) as we can reach to it without traversing the list.

INSERT –

  • Add the new node in the hashmap and the doubly linked list.
  • If the cache is full, use the pointer to the last node in the doubly linked list and delete that node. Set the delete pointer appropriately.
  • Inserting at the start of linked list is operation with time O(1).

UPDATE –

  • Update operation will need similar operation as READ in terms of accessing the data structure. Hence, similar time complexities apply.

DELETE –

  • Deleting the node from the doubly-linked list and hashmap can be done in O(1).

 

I was asked to write the java code for implementing the same. It took a lot of effort.

Used multidimensional array for implementing the doubly-linked list and maintained the pointers for previous and next nodes.