Given an array of integers and size find 3 integers that sum to zero. Explain a brute force algorithm

Question

Viet Nguyen · Accepted Answer

Here a solution which requires:

log(n) for sorting
n^2 for summing all pairs * log(n) for searching for the 3rd number to bring the total to zero
=======================================================================
Total: O(n^2 x log(n))

Could probably be optimized more if we used a hashtable to perform O(1) lookups. 

  public void sumZero(int[] S) {
    sort(S);    // sort nlog(n)
    int sz = S.length;

    for(int i = 0 ; S[i] > 0; i++) {            // For all pairs, n^2
      for(int j = sz-1 ; S[j] = 0) {
          // found a match
          print(i, j, k);
        }
      }
    }
  }

  private int exists(int[] S, int n) {
    int L = 0;
    int R = S.length;
    while(L  n) {
        // number in left subtree
        R = (R+L)/2;
      } else {
        // number in right subtree
        L = (R+L)/2;
      }
    }
    return -1;
  }

Peter Ma · Answer

Ok, I've just came across here and trying it for fun, I don't work for facebook or was even interviewed there.

Sort the entire array, with negative numbers to start to biggest, since this is brute force, using a for loop for every number.

check if there is 0, if there isn't, loop the opposite of the array with conditions that number is postive.

too hard to explain

consider int[] array is given

[Sort Array] - I don't need to write down the method here

int final1, final2, final3

for(int i = 0; i = 0)
 {
  //done, nothing found
  break;
 }
 for(int j = array.length; j>0; j--)
 {
  if(array[j] 0; k--)
  {
    if(array[k] <0)
    {
      //going negative
     break;
    }
    if(array[i] == (array[j] + array[k])
    {
      final1 = array[i];
      final2 = array[j];
      final3 = array[k];
    }
  }
 }
}

This is simulating I am in real interview, which i have to finish under 3 to 5 minutes, There are ways to optimize this but this is just something I am trying to do for fun =)

Hopefully its right lol

Kunal · Answer

void find3Nos(int* array1)
{
	int final1, final2, final3;

	for(int i = 0; i < 8; i++)
	{
		for(int j = 0; j < 8; j++)
		{
			if (i==j)
				continue;
			for(int k=0; k < 8; k++)
			{
				if (i==k || j==k)
					continue;
				if ((array1[i] + array1[j] + array1[k]) == 0)
				{
					final1 = array1[i];
					final2 = array1[j];
					final3 = array1[k];
					goto finished;
				}
			}
		}
	}
finished:
	printf("%d", final1);
	printf("%d", final2);
	printf("%d", final3);
}

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas