Amazon Interview Question: Given an array and a sum, det... | Glassdoor

Interview Question

Senior Software Engineer 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.
Answer

Interview Answer

3 Answers

1

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

needajob on Feb 22, 2012
4

This will return a list of the two numbers that add up to the sum

        public List GetNumbers(int sum, List array)
        {
            var hashSet = new HashSet();
            foreach (int i in array)
            {
                if (hashSet.Contains(sum - i))
                    return new List {i, sum - i};

                hashSet.Add(i);
            }

            throw new Exception("not in here");
        }

Anonymous on Aug 13, 2012
0

"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.