Weta Digital interview question

How do you find the biggest number ?

Interview Answers

Anonymous

17 Nov 2015

If you sorted the list of numbers why would you have to binary search to pick it out? It should either be the first or last one in the list depending on what you past as your comparator. And sorting is slow for this kind of question, since you will be removing and inserting items to figure out which one is the biggest. What they probably wanted to hear is if they didn't want it optimized was a single for-loop with a comparator. This should get done in O(n). If they wanted it optimized, a divide and conquer strategy will find the answer in lesser number of comparisons. If you're looking for a STD solution it's "std::minmax_element(first, last);"

2

Anonymous

17 Nov 2015

You are so right ! Now I can't remember whether the question was to find a target number, or the biggest. If the latter, then for sure that would be the killer reason I failed the interview! Thanks very much for the solution.

Anonymous

15 Jan 2019

Sorting + Binary search = O(n log n) + O(log n) Linear search = O(n) ???

Anonymous

1 Sept 2015

Sort and use binary search.