Interview Questions

  • View all interview questions
  • blank
  • Two sum problem
    The two sum problem is a common interview question, and it is a variation of the subset sum problem. There is a popular dynamic programming solution for the subset sum problem, but for the two sum problem we can actually write an algorithm that runs in O(n) time. The challenge is to find all the pairs of two integers in an unsorted array that sum up to a given S. For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.

    Naive solution

    A naive approach to this problem would be to loop through each number and then loop again through the array looking for a pair that sums to S. The running time for the below solution would be O(n2) because in the worst case we are looping through the array twice to find a pair.


    You need to be a premium member to see the rest of this question and code.

    mrdaniel published this on 11/9/15 | subset, bootcamp, hash, search, array, Google, Facebook, Amazon, Fullstack Academy
    Comments
  • +
  • 9
  • -
  • why do you have to convert, .toString()?
  • +
  • 1
  • -
  • How do i get the brackets to show up in my browser, when I run the code it shows up like this 5,2,-4,11, instead of [[5,2],[-4,11]]
  • +
  • 1
  • -
  • @df5890, in JavaScript hash tables, the keys cannot be integers. JavaScript will automatically convert the number to a string, but I just did it explicitly in the code above. http://stackoverflow.com/questions/2002923/javascript-using-integer-as-key-in-associative-array
  • +
  • 0
  • -
  • Can you guys give code/comments for the ArrayAdditionI version of this classic problem, ie. returns true if there is a subset of any number of elements (not just two) adding up to the largest element? The solutions provided don't have comments for the most part. Thanks.
  • +
  • 0
  • -
  • To display code include the following tags:
    code goes here
    what if there are duplicates in the given array?
    Login to submit a comment