Complexity analysis, discussion about best solution

Question

Utilisateur anonyme · Accepted Answer

you should pay attention to what is being asked and how you communicate your answer. The fact of writing code in paper is quite slow and tense, as the interviewer is just waiting on the phone for you to finish.

In summary, a good experience. Close to Google's standard of interview.

Pavel · Answer

Given 2 arrays of numbers and a number, find 1 number from each array that sum up to the 3rd given input:

You have two arrays, array1 and array2, and you want a in array1 and b in array2 such that a + b = c. The trick is to rewrite this as b = c - a. We transform each element a in array1 to c - a, then check for collisions in the two arrays. We can do this via a hash map or by sorting the two arrays and stepping through them much like in the merge part of merge sort.

Python code:

def main(array1, array2, c):
    mem = dict()
    for a in array1:
        mem[c - a] = True
    for b in array2:
        if b in mem:
            return c - b, b
    return None

Amazon

Question d’entretien chez Amazon

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois