Uber interview question
The interviewer asked to arrange elements into n buckets with equal or close to equal sum. discussed 2 approaches with the interviewer, and implemented both, however, both approaches yielded the wrong answers. The interviewer looked rigid and did not consider the alternate implementations as a solution or possible solution. Seems the make-or-break criteria was to get the answer correctly, and not how you are approaching the problem.
Interview Answer
Anonymous
Sorted items in ascending order, took the average, and divided them by 'n' buckets, to get the bucket sum target. looped through all items and if items were close to average made a bucket out of it (I took the 7% range as the base parameter to define closeness). The second approach I tried was to brute force the sum (and backtrack if the sum is not present) and if desired buckets were found return the result. Both of these solutions are incorrect, Correct solution: sort the array in descending order and put elements into a bucket with the lowest total. Implemented this solution after the interviewer gave away the trick, but I guess that wasn't enough to clear the interview. I would say to avoid Uber, as I felt from the discussion (both with HR and with the Interviewer from the USA) that the team in the USA is actively trying to avoid hiring. And things are not going well as they look.