Given array find 3 elements that sum up to 0.

Question

maddy · Accepted Answer

cant we generate permutations of three numbers and use it to get the answer?

Duy Nguyen · Answer

The complexity depends on the sorting algorithm you are using. I think the above answer is correct.

Duy Nguyen · Answer

Sorry, the solution above is not correct. for example, if you have a set [-7, -5, -4, 0, 1, 2, 3, 4], the algorithm is not right. Am I missing anything?

Anónimo · Answer

It's correct.
When i=7 (assume that index starting from 1) and left = 0, right = 8 we get right answer -7 + 3 + 4
Pseudo algo:

For each i = 1..length do
  left = 0, right = length
  While lefti do
     if values[left] + values[i] + values[right] == 0
       >> Got solution here
    if values[left] + values[i] + values[right] > 0
      # means that right border should be moved
      right--
   else 
     # moving left border
      left++

Anónimo · Answer

Sort. Fix one element i of array and move to it from left and right of array depending on value of values[left]+values[i]+values[right]
Complexity O(N^2)

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo