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.

    mrdaniel published this on 2/5/16 | subset, array, matrix, Microsoft, Google
    Comments
  • +
  • 11
  • -
  • @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.
  • +
  • 10
  • -
  • dude, the video is not clear. I normally love your stuff but this one is an anomaly.
  • +
  • 5
  • -
  • 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.
  • +
  • 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
  • -
  • Is this a legitimate question to expect for a coding bootcamp interview? Asking because it's on coderbyte's preparatory coursework for Makersquare.
  • +
  • 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
  • -
  • @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
  • -
  • 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
  • -
  • Could anyone translate the last updated solution to JavaScript? I don't know python.
  • +
  • 0
  • -
  • 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