Archive for the ‘Uncategorized’ Category

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