View All num of num See all Photos Microsoft www.microsoft.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 9.4k Reviews 32k Salaries 4.1k Interviews Follow Add Review or Salary Follow Add Review or Salary Interview Question Software Development Engineer Interview(Student Candidate) Microsoft 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. Tags: algorithm See more , See less 8 Answer Add Tags Answer Interview Answer 1 Answer ▲ 3 ▼ 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 Interviews > Software Development Engineer > Microsoft Add Answers or Comments To comment on this, Sign In or Sign Up.