Groupon Interview Question Software Engineer / Developers
0of 0 votesfind a Min Value in an array
Country: United States
Interview Type: Phone Interview
The approach #2 will require Log(N) size additional storage, where N is the count of the original elements. On the other hand, if we are to find ONLY 1 minimum value, the approach #1 should do it quite ok.
@ashot madatyan
That's a valid concern. In approach #2, If we think further, we can get rid of the lg(N) additional space by using the following technique. In each round of tournament, if we are comparing elements at locations i and j (where i < j), if a[j] < a[i], then swap a[i] with a[j].
For ex: in the first round, the comparison would be between elements that are 1 location apart as follows:
(1,2)(3,4)(5,6)(7,8)..etc
If we suppose that a[1]<a[2] & a[5]<a[6], but a[3]>a[4] & a[7]>a[8] then swap a[3] with a[4] and also a[7] with a[8] so in the next round we compare:
(1,3)(5,7)... etc.. [Here the elements that need to be compared are 2 locations apart. Again if i<j and a[i]>a[j] swap a[i] with a[j]]
In the next round we will compare elements that are 4 locations apart as below:
(1,5)(9,13)... etc and this process goes on until only one element (i.e, the first element remains)
This ways, we will eliminate the need to have extra space and the minimum element at the end would always be the first element.
I think it's important to note that if you receive a question like this that the interviewer is looking for the interviewee to resolve ambiguity and discuss multiple approaches to solving the problem. Anyone with basic understanding of coding and data structures recognizes that this is a trivial problem. As such, I believe a good way to approach this problem would be to ask questions like "How big is the array, can we hold all of the data on one machine?", "Where is this data coming from, what is the type of data does the array hold?" see here that the array could hold a string and the min value of a string is not explicitly defined (it could be size or lexicographical ordering).
there are 2 approaches, both involve n-1 comparisons
- Murali Mohan June 29, 20131. Pick first element as the minimum. Compare the minimum with the rest of the n-1 elements, each time updating it if the new element compared is less than the current minimum
2. Use a tournament type of approach, where adjacent elements are compared and min of the two is selected. Among the first set of minimum elements do the tournament-type comparison again. Repeat the steps until the minimum is found.