Amazon Interview Question: Given some array such as {4, ... | Glassdoor

Interview Question

Software Developer Engineer I Full Time Interview(Student Candidate) Seattle, WA

Given some array such as {4, 2, 5, 3}, write a function

  that would take in the array and a number that would return how many pairs add up to the number.
Answer

Interview Answer

2 Answers

1

The interviewer first asked what you would do in this situation and how you would solve the problem, and if it would be constant time, linear, or quadratic, etc. I explained the only way I could think of doing it would take quadratic time. When asked why I would be quadratic, I explained, and the interviewer explained that it would be order n squared, to which I agreed and explained that's why I said it was quadratic. The interviewer then asked me what quadratic meant, and I said it was n squared. The interviewer said he didn't think that was true, but he was also skeptical. The interviewer should have known the meaning of quadratic. Anyway, he then asked me what could I do if the list was sorted. He said there was a way to do this in linear time if it was sorted. This threw me off since sorting is nlogn, and then you still have to do at least n calculations. Towards the end, he threw me the hint to use a map as a way of "sorting". One mistake I made was that I assumed the numbers would be positive.

Interview Candidate on Apr 14, 2012
0

You have an array and the target number, say N. Iterate through the array and for each number n put N-n into a hashmap. Now iterate through the array again and count how many number collide with a number in the hashmap. This work because if m collides with something in the hashmap we have m = N-n for some m and n in the array, moving n to the other side we get m + n = N.

Pavel on May 24, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.