First part: Given a sorted array that was "shifted", e.g., [1, 2, 3, 4] --- [2, 3, 4, 1], write an algorithm that finds the maximum value in the array. Second part: Improve the time complexity using parallel computing.

Question

First part: Given a sorted array that was "shifted", e.g., [1, 2, 3, 4] ---> [2, 3, 4, 1], write an algorithm that finds the maximum value in the array. Second part: Improve the time complexity using parallel computing.

Anonymous · Accepted Answer

You can do a binary search where in step you choose the part where the first element is greater than the last element in that part. That way you can achieve log(n) time complexity.

Joe · Answer

The first answer is actually incorrect - Consider the case of an array sorted from top to bottom then you actually need to check if the first element and last element of a part is bigger then both the last and first of the 2n'd part and then move

Anonymous · Answer

If the shif is always by 1 we can do it in a simple way like that with o(1) I guess he was looking for that answer 
IndexOfmax=list.size()-2;
Lisit.get(IndexOfmax);//4

Microsoft

Microsoft Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches