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.

Question

Anónimo · Accepted Answer

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.

Pavel · Answer

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.

Amazon

Pregunta de entrevista de Amazon

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo