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.

    Become a Premium Member

    With our large collection of challengs, tutorials, and solutions, we make it easy for you to become a better coder, prepare for interviews, and learn new skills from more experienced coders.

    “I have my final coding interview with Fullstack Academy tomorrow, and Coderbyte has been an invaluable tool to help me progress as a
    developer.” ― Josh Aharonoff
    • 200+ Coding Challenges
    • Mock Interview Questions
    • 500,000+ Code Solutions
    • Algorithm Tutorials
    • Interview Prep Courses
    mrdaniel published this on 11/9/15 | subset, bootcamp, hash, search, array, Google, Facebook, Amazon, Fullstack Academy
    Comments
  • +
  • 10
  • -
  • 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