techInterview Discussion

I was interview for a Test lead. There were 6 round in total and all the rounds were as expected and question which were asked were as expected, like given a scenario how would you test.
This algo question I was not able t crack so, posting it.
There is an array (with +ve integer) we need to sort the array ONLY with the help of the following function.
Flip(Array a, int size, int flipPos)
so if the array is
a = 3,2,6,8,1,9
and i call
Flip(a, 6, 3)
then a = 6,2,3,8,1,9.
Any ideas in how to proceed.
He told me that you can find the largest or smallest element on o(n) time and then go ahead wth that.
Thanks.

http://en.wikipedia.org/wiki/Pancake_sorting

My attempt was O(n^2) (insertion sort).

so one doubt please : we are discussing linear time sorting approach, but assuming that we are "able to find the maximum of a range of consecutive numbers in constant time."

So, doesn't "consecutive numbers" simplifies the OPs problem.
And if the input is not a set of consecutive numbers then can the above assumption be ever met.

I went through the link, but could not understand how real applications would implement such an approach.

They wouldn't. The idea is to test how well applicants deal with a dumb interface.

finding the largest no.
for(i=0;i<n;i++)
{
 if( A[1] < A[i])
 {
  flip(A,6,i);
 }
}

assuming tht flip(A,n,i) swaps elements A[1] and A[i] for an array of given size n.

This is quite funny for a MS interview question, as it uses the algorithm from the only paper Bill Gates ever published to solve it.