3

I faced a question in an interview two days back regarding optimally finding the maximum element in an array and I have query regarding that.

The array as described by interviewer consists of integer values which may repeat (not necessarily in consecutive places) and it also consists of two parts (One part may be empty) : First part in non-decreasing order, and second part in non-increasing order,i.e. if a[n] is an array consisting of n integer values, then, a[i]<=a[i+1],i in [1,m] and a[j]>=a[j+1],j in [m,n] and m lies somewhere between 1 and n inclusive. Now, they asked me to find the maximum value in the array in most efficient way.

I argued that as some elements may be repeated, I cannot element a search space using divide and conquer strategy. Had all the elements been distinct, we would be able to find maximum in lg n time using binary search. But there exists at least one input sequence (possibly when all elements are same) for which we at least need to have n-1 comparison before we can tell which element is maximum.

The interviewer asked me to think if I can impose some restriction on the input so that the problem can be solved in lg n time. I was not able to solve at that time and still thinking.

It would be helpful if you can help me in thinking.

Improve this question

1 Answer 1

Reset to default
6

The interviewer was trying to see if you know about ternary search: if you require that the parts are strictly increasing and then strictly decreasing, you'd be able to get an answer in Log3(N). So the additional requirement the interviewer was looking for is probably that duplicate entries, if any, should occur on different sides of the ascending-descending switchover point.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Except ternary search requires the function to be partly strictly increasing and partly strictly decreasing.
@Shahbaz I meant to answer the "interviewer asked me to think if I can impose some restriction on the input so that the problem can be solved in lg n time" part of the question. The first part of the OP's answer is correct.
But Unimodal function unimodal function is a function that is either strictly increasing and then strictly decreasing or vice versa. And moreover, I guess, that can be done using binary search also. Using binary search I can get it in Log2(n). But if elements are repeated, then??? (Say , all elements are same)
@sarthak I'm sorry that the initial answer was not clear: you answered the first part of the question correctly, it's the second part (find an addition condition to impose on the array to make it possible to search in Log(N)) that can be addressed with ternary search. Binary search would not work, though.
@sarthak An array of 1000 2s is a counterexample that shows that if you allow repeated items on either side of the switchover point you are limited to a linear search. However, if you have something like {1, 2, 3, 4, 5, 4, 2, 0}, both 2 and 4 are repeated, but you can still find the max in Log3(N).
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.