Product Array - Interview Question

Friday, December 17, 2010 by gradbot

Given an array of numbers return an array where each item is replaced by the product of all the other items in the array.

A trivial solution would be to multiply the elements repeatedly for each result giving an O(n^2) solution.

var productOfOthers = function(input) {
    var length = input.length;
    
    var result = [];
    for (var i = 0; i < length; i++) {
        result[i] = 1;
        for (var j = 0; j < length; j++) {
            if (i != j) {
                result[i] *= input[j];
            }
        }
    }
    return result;
};

You could get the total product first and then divide by each element for O(n) but you may introduce floating point error and you have to deal with dividing by zero.

var productOfOthers = function(input) {
    var length = input.length;
    
    var product = 1;
    for (var i = 0; i < length; i++) {
        product *= input[i];
    }
    
    var result = [];
    for (var i = 0; i < length; i++) {
        result[i] = product / input[i];
    }
    
    return result;
};

Taking advantage of Multiplications Associative property you can get minimal error in O(n) by making two runners, one forward and one backward, to calculate the result by result[i] = forward[i-1] * backward[i+1].

var productOfOthers = function(input) {
    var length = input.length;
    
    if (length <= 1) {
        if (length == 1) {
            return [input[0]];
        } else {
            return [];          
        }
    }
        
    var forward = [];
    var product = 1;
    for (var i = 0; i < length; i++) {
        product *= input[i];
        forward[i] = product;
    }

    var backward = [];
    var product = 1;
    for (var i = length - 1; i >= 0; i--) {
        product *= input[i];
        backward[i] = product;
    }
    
    var result = [];
    for (var i = 1; i < length - 1; i++) {
        result[i] = forward[i - 1] * backward[i + 1];
    }

    result[0] = backward[1];
    result[length - 1] = forward[length - 2];   
    
    return result;
};

Pots of Gold - Interview Question

Thursday, December 16, 2010 by gradbot

Given n pots of gold arranged in a line containing different quantities of coins. You are allowed to remove one pot of gold from either end and then another player gets to remove one. This is repeated until no pots remain. Write an algorithm to find the set of moves for collecting the most coins in a two player game. Assume your opponent also takes optimal moves.

var max_gold = function(pots) {
  var length = pots.length;
  if (length <= 1) {
    if (length == 1) {
      return {first: [pots[0]], second: []};
    } else {
      return {first: [], second: []};
    }
  }
  
  var left = max_gold(pots.slice(1));
  var right = max_gold(pots.slice(0, -1));
  
  var left_pot = pots[0]; 
  var right_pot = pots[length - 1];
  
  var left_total = left_pot + sum(left.second);
  var right_total = right_pot + sum(right.second);

  if (left_total >= right_total) {
    return {
      first: [left_pot].concat(left.second), 
      second: left.first
    };
  } else {
    return {
      first: [right_pot].concat(right.second),
      second: right.first
    };
  }
};

// sample input 
[11, 19, 18, 16, 1, 4, 7, 3, 6, 2]
// sample output
{first: [11, 18, 2, 3, 4], second: [19, 16, 6, 7, 1]}

This can be easily optimized from O(2^n) into O(n^2) by moving to array indexes and memoization. Note: I'm ignoring the cost of sum, slice and concat for BigO. If you only wanted the total then you could just keep track of it instead of an array and save a bunch of memory.

var max_gold = memoize(function(pots, start, stop) {
  if (start >= stop) {
    if (start == stop) {
      return {first: [pots[start]], second: []};
    } else {
      return {first: [], second: []};
    }
  }
  
  var left = max_gold(pots, start + 1, stop);
  var right = max_gold(pots, start, stop - 1);
  
  var left_pot = pots[start]; 
  var right_pot = pots[stop];
  
  var left_total = left_pot + sum(left.second);
  var right_total = right_pot + sum(right.second);

  if (left_total >= right_total) {
    return {
      first: [left_pot].concat(left.second), 
      second: left.first
    };
  } else {
    return {
      first: [right_pot].concat(right.second),
      second: right.first
    };
  }
});

var memoize = function(f) {
  var store = {};
  return function(pass_through, x, y) {
    var value;
    if (x in store) {
      if (y in store[x]) {
        value = store[x][y]; 
      } else {
        value = f(pass_through, x, y);
        store[x][y] = value;
      }
    } else {
      value = f(pass_through, x, y);
      store[x] = {};
      store[x][y] = value;
    }
    return value;
  }
};

You can remove the memoization with dynamic programming for extra speed at the cost of some readability.

var max_gold_dynamic = function(pots) {
  var length = pots.length;
  var gold_array = [];
  for (var start = length - 1; start >= 0; start--) {
    gold_array[start] = [];
    for (var stop = start; stop < length; stop++) {
      if (start >= stop) {
        if (start == stop) {
          gold_array[start][stop] = {first: [pots[start]], second: []};
          continue;
        } else {
          gold_array[start][stop] = {first: [], second: []};
          continue;
        }
      }
      
      var left = gold_array[start + 1][stop];
      var right = gold_array[start][stop - 1];
    
      var left_pot = pots[start]; 
      var right_pot = pots[stop];
      
      var left_total = left_pot + sum(left.second);
      var right_total = right_pot + sum(right.second);
    
      if (left_total >= right_total) {
        gold_array[start][stop] = {
          first: [left_pot].concat(left.second), 
          second: left.first
        };
      } else {
        gold_array[start][stop] = {
          first: [right_pot].concat(right.second),
          second: right.first
        };
      }
    }
  }
  return gold_array[0][length - 1];
};