Frage im Vorstellungsgespräch bei Weta Digital

How do you find the biggest number ?

Antworten zu Vorstellungsgespräch

Anonym

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

Anonym

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.

Anonym

15. Jän. 2019

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

Anonym

1. Sep. 2015

Sort and use binary search.