Interview Questions

  • View all interview questions
  • blank
  • Subset sum problem
    The subset sum problem is an important problem in computer science. Below we'll provide two common algorithms for solving this problem. The challenge is to determine if there is some subset of numbers in an array that can sum up to some number S. These algorithms can both be implemented to solve Array Addition I and Array Addition.

    Naive solution




    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.

    “If you're able to solve Medium Coderbyte problems and have a good understanding of web development basics [...] then you are probably ready for admissions at the top schools.” ― Huntly Mayo-Malasky
    • 200+ Coding Challenges
    • Mock Interview Questions
    • 500,000+ Code Solutions
    • Algorithm Tutorials
    • Interview Prep Courses
    mrdaniel published this on 2/5/16 | subset, array, matrix, Microsoft, Google
    Comments
  • +
  • 17
  • -
  • dude, the video is not clear. I normally love your stuff but this one is an anomaly.
  • +
  • 13
  • -
  • @mrdaniel, as @SJern, @codesmith and @artykreaper noticed, the dinamic programming solution given above is not always correct if the input array contains negative numbers. For this simple case: [-1,1,2,3] returns 'false' but 1 + 2 = 3 I think the problem is that in the first for loop, labeled "#clever way to get rid of negative numbers" you are implicitly using all the negative values to obtain the total sum. A modification can be perfomed to address this issue. The complexity rises to O(Sn) with S the sum of the absolute values of the input array. A larger memoization matrix, with broader range (negative and positive) allows to calculate the current values from the preview ones when there are negative values in the input. This is what I came out with:
    def ArrayAddition(arr): 
    
      sum_positive = sum([x for x in arr if x > 0])
      sum_negative = sum([x for x in arr if x < 0])
    
      num_columns = -sum_negative + 1 + sum_positive
    
      # get largest number and remove it from array
      goal = max(arr)
      arr.remove(goal) 
      
      '''
      # clever way to get rid of negative values
      for i in xrange(0, len(arr)):
        if arr[i] < 0:
          goal -= arr[i]
          arr[i] = 0
      '''
          
      # table to track elements
      table = [[False]*num_columns for r in xrange(0, len(arr)+1)]
      
      '''
      # fill first column
      for i in xrange(0, len(arr)+1):
        table[i][0] = True
      '''
      table[0][-sum_negative] = True
        
      # dynamic programming solution
      for i in xrange(1, len(arr)+1):
        for j in xrange(num_columns):
          table[i][j] = table[i-1][j]
          if table[i][j] == False and 0 <= j - arr[i-1] and j-arr[i-1] < num_columns:
            table[i][j] = table[i][j] or table[i-1][j-arr[i-1]]
            
      if table[len(arr)][-sum_negative + goal]:
        return "true"
      else:
        return "false"
    
    print ArrayAddition([-1,1,2,3])   
    
    I am not sure if this can be further optimized.
  • +
  • 6
  • -
  • for (var i = 0; i < arr.length; i++) { 
      if (arr[i] < 0) {
        sum -= arr[i];
        arr[i] = 0;
      }
    }
    
    I think the getting rid of negative values code above wouldn't work, if any of the negative numbers did not belong to any subset of numbers in the array that can sum up to S. For example, [3,4,-1,8,12] wouldn't work I think. Am I mistaken?
  • +
  • 3
  • -
  • @SJern I believe you are correct. With the example code provide above, if you change 7 to -7 the result changes from true to false, even though you can still add 2,4, and 6 to get 12 regardless of whether 7 is positive or negative.
  • +
  • 2
  • -
  • Video is super confusing. Also negative numbers workaround does not work!
  • +
  • 2
  • -
  • Is this a legitimate question to expect for a coding bootcamp interview? Asking because it's on coderbyte's preparatory coursework for Makersquare.
  • +
  • 1
  • -
  • @mrdaniel could you provide clarification on how to handle negative numbers? as said below, subtracting the negative numbers from the max doesn't work.
  • +
  • 1
  • -
  • @Cohno, the reason we explicity set the length of sets equal to len is because we want to loop through all of the "sets" array before we start adding elements to it, which would make the length of "sets" larger.
  • +
  • 1
  • -
  • I agree with the other comments. This doesn't work for the first negative values I tried. Cool solution but it should probably be updated.
  • +
  • 1
  • -
  • Regarding the nested for loop in the first solution. Why do we need to declare len? the code does not run properly without it for (var j = 0, len = sets.length; j < len; j++) Why does that work? wouldn't this be simpler? for (var j = 0; j < sets.length; j++)
  • +
  • 0
  • -
  • It's a bit disgraceful that --on this paid service-- this solution is still up, months after it's been shown to be incorrect. Just use as input: [11, 10, 1, -2] (By the way, why isn't `sum` just a separate parameter?)
  • +
  • 0
  • -
  • Could anyone translate the last updated solution to JavaScript? I don't know python.
  • +
  • -1
  • -
  • 3:10 - "The true means you keep going up the column until you hit a false" - huh? Not an explanation. "Now you go left, now you go up" - What the heck does that even mean? This video is not an explanation. It is a description of what you are doing. Filling out a table. Where does this table add together elements of the source array to compare them to the largest #? The Trues and Falses have to relate to some sort of hard math, not 'just because'. Additionally, I thought that using .apply() was to be avoided? Given the various ways you could go about getting that largest number, why use apply at all instead of something like
     arr.sort(function(a,b){return a-b;}).pop() 
    ?
    Login to submit a comment