Interview Question for Software Engineer at Facebook:

My attempt in PHP (works):

#!/usr/bin/env php
<?php
ini_set('memory_limit', '1024M');

class ThreeSubset {

    private $list;

    function __construct($ls) {
        $this->list = $ls;
    }

    public function computeSum() {
        $y = 1;
        $z = 2;

        if (count($this->list) < 3) {
            print("Table too short\n");
            return null;
        }

        foreach(range(0,count($this->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\n");
                        return null;
                    }

                }

            }

        }

        print ("No subset found\n");
        return null;
    }
}

$arraytest = array(1,-2,8,5,9,4,-10,7);
$test = new ThreeSubset($arraytest);
$test->computeSum();

O(n^2lgn) is easy to come up with, and with a little tweak is O(n^2).

O(n^2lgn) solution:

vector<int> vals = {1,-2,8,5,9,4,-10,7};
multi_set<int> 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; }

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)

// it took about O(n^2 + n*lg(n))
// at worst case it compare almost every two elements

public void find3Element(int [] a)
    {
        Hashtable<Integer,Integer> h= new Hashtable<Integer,Integer>();
        Arrays.sort(a);
        for(int i=0; i<a.length ; i++)
        {
            h.put(a[i], i);
        }
        if( a[0] > 0 || a[a.length-1] < 0 )
        {
            return;// impossible
        }
        for(int i=0;i<a.length/2;i++)
        {
            for( int j=a.length-1; j > 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)]);
                }
            }
        }
    }

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

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, as d = c +x, where x >= 0(sorted values), so a+b+d = a+b+c+x... . Just a little optimization to the algo.