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

Question

xy · Accepted Answer

O(n^2lgn) is easy to come up with, and with a little tweak is O(n^2).

O(n^2lgn) solution:

vector vals = {1,-2,8,5,9,4,-10,7};
multi_set sorted_vals(vals.begin(), vals.end());
for (auto it = sorted_vals.begin(); it != sorted_vals.end(); it++)
for (auto it2 = sorted_vals.begin(); it2 != sorted_vals.end(); it2++) if (it != it2)
for (auto it3 = sorted_vals.lower_bound(-*it-*it2), it3_upper = sorted_vals.upper_bound(-*it-*it2); it3 != it3_upper; it3++) if (it3 != it && it3 != it2) { cout << *it << ' ' << *it2 << ' ' << *it3; return 0; }

unnamed · Answer

Python, O(n^2 logN):

import bisect

lst = [-3, 2, 4, 1, 1]

lst = sorted(lst)
for i in xrange(len(lst)):
    for j in xrange(i + 1, len(lst)):
        rest = -(lst[i] + lst[j])
        idx = bisect.bisect_left(lst, rest, j + 1)
        while idx == i or idx == j:
            idx += 1
        if idx < len(lst) and lst[idx] == rest:
            print lst[i], lst[j], lst[idx]
            exit(0)

Ragnarok · Answer

// it took about O(n^2 + n*lg(n))
// at worst case it compare almost every two elements

public void find3Element(int [] a)
	{
		Hashtable h= new Hashtable();
		Arrays.sort(a);
		for(int i=0; i 0 || a[a.length-1]  i;j-- )
			{
				if( a[j] > -2 * a[i]  )
				{
					break;
				}
				int t = 0 - a[i] - a[j];
				if( h.containsKey( t ) && h.get(t) > i && h.get(t) < j )
				{
					System.out.println("get " + i + " " + j + " " + h.get(t));
					System.out.println("so  " + a[i] + " " + a[j] + " " + a[h.get(t)]);
				}
			}
		}
	}

Anon · Answer

Ragnarok, what if the input is int[] input = { -2,-1,3,4,6 };

someone · Answer

Sort the array, and start summing from left to right. When sum() > 0 - stop the iteration and go to next. 
Given:
sorted([a, b, c, d])

if a+b+c > 0, there is no chance for a+b+d = 0(sorted values), so a+b+d = a+b+c+x... . Just a little optimization to the algo.

Jerry · Answer

To above: the best we can do it O(n^2)
your 2nd map has the order of O(n^2) entries because it contains the sum of any two. so generating the map takes quadratic time...

Sebastien · Answer

My attempt in PHP (works):

#!/usr/bin/env php
list = $ls;
	}
	
	public function computeSum() {
		$y = 1;
		$z = 2;
		
		if (count($this->list) list)-3) as $it1) {
			
			$y = ($it1 == $y) ? $y+1 : $y;
			$z = $y + 1;
			foreach(range($y,count($this->list)-2) as $it2) {
				
				$z = ($it2 == $z) ? $z+1 : $z;
				foreach(range($z,count($this->list)-1) as $it3) {
					
					if(($this->list[$it1] + $this->list[$it2] + $this->list[$it3]) == 0) {
						print($this->list[$it1]." + ".$this->list[$it2]." + ".$this->list[$it3]." = 0
");
						return null;
					}
					
				}
				
			}
			
		}
		
		print ("No subset found
");
		return null;
	}
}

$arraytest = array(1,-2,8,5,9,4,-10,7);
$test = new ThreeSubset($arraytest);
$test->computeSum();

Sigiloso · Answer

Why not just O(n) by dynamic programming? Keep two hash_map.
1) hash_map, the first is the value, and the second is the position of this number in the array
2) hash_map >, the first value is the sum of two integers.. and pairs contains the position info for the number.. 

For each number in the array, update the two hash_map, once we found a 0, stop.

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas