Alright guys, Ive got a teaser for all of you. Yesterday, Ive attended an interview and the interviewer was testing me on various aspects in programming. In the middle of the interview, he asked me a question: There is an array whose elements are unsorted. How do you find the maximum and the next maximum elements among them? I thought about it for a few seconds and then came up with two solutions: 1) First, you run a loop and find the maximum element in ordinary way (i.e; you initialize max to element in the zeroth index and run the loop from index 1 to n-1, comparing the maxs value to the currently indexed value, and updating the max value whenever appropriate). But you also store the index of the maximum element in the array, not just the maximum value. Then run the loop again to find the next maximum element using the same approach. But this time, when you encounter the index of the maximum element, you simply skip over it and move onto other indexes. This will ensure that the next_max value will not contain the same value as max does. So, by the end of the two iterations, we have the maximum and next maximum values. 2) A more simpler solution is to use the technique that we employ in the selection sort. Run the loop once, find the maximum value and store it in the zeroth index. Then run the loop again, find the maximum value among the remaining numbers and store it in the 1st index of the array. The interviewer listened to both of these solutions, then replied Okay, both of these solutions will work. But what if you have to find something like 350 or 400 greatest elements ? Clearly, these solutions would be infeasible then!! I thought he indeed had a point. Running the loops again and again will increase the time complexity linearly. So, these 2 solutions will not address the issue he raised. I thought about it for some more time, but couldnt come up with any more solutions. Then the interview proceeded towards other questions. At the end of the interview, when I was about to leave, he said If you are still curious about that question, think about what would happen if you do repeated swappings. I left with that cliffhanger in mind andve been thinking about it. But Im not able to decipher the clue he gave me. Does anyone know of any other method which efficiently solves the problem ???
Posted on: Sat, 11 Oct 2014 06:53:16 +0000
Trending Topics
Recently Viewed Topics
© 2015