Find all pairs sum to target where each element is used once. Asked in Bloomberg Junior Software Developer interview.

java.md

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Pair {

    private int l, r;

    public Pair(int l, int r) {
        this.l = l;
        this.r = r;
    }

    @Override
    public String toString() {
        return "(" + l + ", " + r + ")";
    }

    public static void main(String args[]) {
        for(Pair p : getPairs(new int[]{1, 3, 3, 4, 4, 5, 5}, 8))
            System.out.println(p);
    }

    public static List<Pair> getPairs(int ls[], int target) {
        HashMap<Integer, Integer> c = new HashMap<Integer, Integer>();
        ArrayList<Pair> res = new ArrayList<Pair>();
        for(int i : ls)
            c.put(i, 1 + (c.containsKey(i) ? c.get(i) : 0));
        for(int i : c.keySet()) {
            int j = target - i;
            if(c.containsKey(j) && c.get(j) > 0) {
                int min = Math.min(c.get(i), c.get(j));
                if(i == j) min /= 2;
                for(int k=0; k<min; k++)
                    res.add(new Pair(i, j));
                c.put(i, c.get(i) - min);
                c.put(j, c.get(j) - min);
            }
        }
        return res;
    }
}

python.md

from collections import Counter


def get_pairs(ls, target):
    c, pairs = Counter(ls), []
    for k in c.keys():
        l = target - k
        if c[l] > 0:
            i = min(c[k], c[l])
            if k == l:
                i /= 2
            pairs.extend([(k, l) for _ in xrange(i)])
            c[k], c[l] = c[k] - i, c[l] - i
    print pairs


get_pairs([1, 3, 3, 4, 4, 5, 5], 8)  # [(3, 5), (3, 5), (4, 4)]