Interview Question

Interview Seattle, WA

Given an array and a sum, determine if any of the items add

  up to sum. Do a linear space solution and constant time solution.

Interview Answer

3 Answers


Tell me your constant time solution, because I am too noob to figure it out

needajob on Feb 22, 2012

This will return a list of the two numbers that add up to the sum public List<int> GetNumbers(int sum, List<int> array) { var hashSet = new HashSet<int>(); foreach (int i in array) { if (hashSet.Contains(sum - i)) return new List<int> {i, sum - i}; hashSet.Add(i); } throw new Exception("not in here"); }

Anonymous on Aug 13, 2012

"any two items" and "any of the items" are very different problems. Any two items is easy. Any subset of the items is NP-hard (if I recall)

Anonymous on Mar 25, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.