Given an unsorted array of integers, find a 3-element subset that sums to zero

Question

Spaniard · Accepted Answer

def findSumValue(array, start, elements, value):
  global sols
  for i in range(start, len(array)):
    if elements > 1:
      rest = findSumValue(array, i+1, elements-1, value-array[i])
      if rest:
        rest.append(array[i])
        return rest
    elif array[i] == value:
        return [array[i]]
  return None

array = [1,4,-6,2,5,-12,3,-3,-2,5,-1,7,9]
print findSumValue(array, 0, 3, 0)

Hussein · Answer

You can loop all combinations of 2 elements in the array O(N^2) and inserting -1*(elem1+elem2) .. then search for all array elements within the BST if it does exist then return true .. if there is no such element return false.. this is a better approach wich takes O(N^2 Lg(N)) which is better tan O(N^3)..

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas