Interview Question

Software Development Engineer Interview(Student Candidate)

Given an array of integers, define an algorithm that

  deduces whether a given sum can be attained by adding two numbers in the array without using data structures.

Interview Answer

1 Answer


There's the naive way (O(n^2)) that doesn't warrant an explanation. There's also a method to use a hash table and finish it in O(n) time, but the recruiter asked to not use data structures. The most efficient solution is to sort the array first, and stick a pointer at the beginning and the end of the array. In a loop, sum up the values of the pointers. If the sun matches the value, return true. Otherwise, if the sum is less than the one we want, increment the left pointer. If the sum is more than the one we want, decrement the right pointer. Continue the loop until the pointers equal each other (i.e. are pointing to the same place). If you get out of the loop, return false.

Interview Candidate on Jul 29, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.