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

Find Next Larger no. Using Same Digits

Posted: September 12, 2012 in Amazon

Q. The input of the problem is a number. (Say 43652). You have to compute a number using same digits such that new number is greater than original number and out of all such options, its should be closest to the original number. Answer for Example –  45236

A.

  • Examine digits starting from zeroth place and move towards higher order. Stop at the point where current digit is less than previous one. Say this location is j. In example 4365, the digit is ‘3’.
  • If no such element met and all digits occurred in ascending order, throw error saying that number is maximum possible with given digits.
  • The digits examined so far (from 0th position to j-1) are sorted. Do binary search on same window and spot the element just greater than digit at location j. In example, its ‘5’.
  • Swap these digits (Example: 45632)
  • Examined digits (from 0th position to j-1) is still sorted. Change the order by reversing the sequence. (Example: sorted 45 ‘236’)
  • The resulting number is the answer 🙂

Complexity O(n).

Spotting the element takes O(logn) as its binary search.

Sorting takes O(n) because we are just reversing the digits sequence.

Q. You are given a 2D array sorted horizontally as well as vertically. Find kth smallest element.

A. Maintain a min heap of size n. A location pointer will be maintained for checked elements in each row.

Drop 1st element from each row, move the location pointer then 2nd row.

Pull out the minimum element, note the row from which it belonged and put the next element from the same row in the heap.

Repeat the process K times. Kth smallest element will occur at that stage.

 

Reverse the Words in the String

Posted: August 23, 2012 in Uncategorized

Q. Update the string in place such that words in the strings are reversed.

Eg. “Harsh is awesome!” should be reversed to “awesome! is Harsh”.

 

A. The trick here is to handle the spaces. The best solution I could think of was to reverse all the characters and than reverse each individual word.

Step 1 – !emosewa si hsrah

Step 2 – awesome! is harsh

Q: You are given an array of integers. For each element x find a suitable y such that
1. Val(Y) < Val(x)
2. Position(Y) < Position(X)
3. Position of Y should be maximum as possible
4. If there is no such Y, set it to null

Try to achieve complexity better than O(n^2).

A: Use a doubly linked list with following insertion and maintenance rules –
1. Linked starts with null and at any point, parent node is the value of Y for operational element. The prints of Y happens at the time of element insertion.
2. For each element X, Start with the tail of the linked list.
> If its null node, add a node X as its successor.
> If linked list node element is less than X, add a new node as its successor.
> If node element is greater equals X, delete that node(including its tail) and re-do comparison with its parent.

Sample run
Say for array 7, 1, 4, 8, 5, 6, 2

Operational Element Linked List Operation taken Printed Result (X, Y)
7 null -> 7 Added node 7 7, Null
1 null -> 1 Deleted node 7 and added node 1 1, Null
4 null -> 1 -> 4 Added node 4 4,1
8 null -> 1 -> 4 -> 8 Added node 8 8,4
5 null -> 1 -> 4 -> 5 Deleted 8 and added 5 5,4
6 null -> 1 -> 4 -> 5 -> 6 Added Node 6 6,5
2 null -> 1 -> 2 Deleted 6, then 5, then 4 while traversal from tail and added 2 2,1

 

PS: We do complete traversal of linked list from right to left. We can have a step further by maintaining the linked list in such a manner, that we can do binary search on it (by storing position index separately). It can be more optimized by using binary search as linked list is always sorted.

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.