Amazon Interview Question: Bar raiser 1. Given array of ... | Glassdoor

## Interview Question

Software Development Engineer I Interview Seattle, WA

# Bar raiser 1. Given array of numbers, find a, b, c such

that a + b = c. Can you beat O(N**2) ? 2. Difference between Quick sort and Merge sort. What modifications you make in Quick sort so that it provides O(N lg N) worst case complexity.

1

1. Solved using hash table. complexity O(N**2). Told that there exist algorithm 3SUM which beats O(N**2) - http://en.wikipedia.org/wiki/3SUM.

2. Didn't get this question even after he gave me a hint. Answer is to find median in O(N) time(yeah it is possible to find median in O(N) in an unsorted array !) and assign that as pivot in each pass of quicksort. Thus quicksort behaves like merge sort by splitting array exactly in the middle.

Interview Candidate on May 24, 2011
0

This is almost the same as 3sum problem and check http://bit.ly/2aJyjFx for full solution and all its variants.

peter on Aug 11, 2016