1st round (coding) :



There is a drought situation in Agrabah.King got worried and called



Aladdin for helping him out. As he is a modern Aladdin he took



printouts of places around Agrabah from google maps.For analyzing the



map properly, he converted the map into a M x N grid. Each point is



represented by either ?0? or ?1?.



?1? represents the unit area of water and ?0? represents the unit area



of land. King told him to find the largest continuous patch of water



so that he can send his people over there.



As our Aladdin is modern, but not a good programmer, he wants your



help. Help him out by printing out the largest area water patch



available on map.



 





2nd round (Phone interview) :



1)There are three types of balls arranged linearly in a random order



Red, Green and Blue. Now your job is to sort them so that the Red



balls are in front follwed by the Green balls and the Blue balls are



pushed to the bask.



 



This problem was the same as sorting the array of 0, 1 and 2. we  can



do this in o(n) using two pointers.



2)Given an n x n matrix, where every row and column is sorted in



increasing order. Given a number x, how to decide whether this x is in



the matrix. The designed algorithm should have linear time complexity.



 



a) Start with top right element



 



b) Loop: compare this element e with x



 



i) if they are equal then return its position



 



ii) e < x then move it to down (if out of bound of matrix then break



return false)



 



iii) e > x then move it to left (if out of bound of matrix then break



return false)



 



c) repeat the i), ii) and iii) till you find element or returned false



3)In the same matrix mentioned above find the kth maximum element.



   I said that we just need to compare the last K x K sub matrix and



to find the Kth element.



4)Given a set of integers, Display the non-empty subsets whose sum is



zero. For example, given the set { −7, −3, −2, 5, 8}, the answer is



the subset { −3, −2, 5} which  sums to zero.



   This is the special case of knapsack problem and hence it is NP-



Complete so i said we cannot find the solution in polynomial time.We



consider all the subsets with k elements. Then check how many of these



sets have a sum of 0. This is an exponential time algorithm.



 



5)Create a data structure where inserting, deleting and finding the



minimum element all have O(1) time.



   i said we can use augmented stack where with each element we can



augment the minimum element along with its actual value.Then he said



?what if you cannot create any new data structure but have to use only



the previously available data structures?? I replied that then we can



use two stacks one to store the actual data and other to store the



minimum values.



 



That was all and i was out...

HAVE YOUR SAY...