Solving Google Interview Questions

· 6 mins read Edit Post
Part 2.

Another technical algorithm question asked at Google interviews, is coined ‘Two Sum’, taken from a user on Glassdoor.

Question:

Given an array of integers, return 
indices of the two numbers such that
they add up to a specific target.
You may assume that each input would
have exactly one solution and
you may not use the same element twice.

Input: array e.g. [2, 7, 11, 15], and a target sum, e.g. 9 Output: print [0, 1] because the values at these indexes add up to 9, e.g. array[0] is 2 and array[1] is 7, 2 + 7 = 9, the target.

Example Input

[2, 7, 11, 15]
9

Example Output

[0, 1]

Worst Case

The question assumes there is only 1 solution, therefore we can call return [i, j] straight away, however, if there can be more than one solution, we need to initialise an array before the first for loop and instead of calling return [i,j] we push these elements onto our initialised array, then return that array at the end of the function, instead of using return [].

Setup Code

var input = [3, 2, 4];
var target = 6;
console.log(twoSum(input, target));

Algorithm

var twoSum = function(nums, target) {
    for(var i = 0; i < nums.length; i++) {
        for(var j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] == target) {
                return [i, j];
            }
        }
    }
    return [];
};

Complexity:

O(2^n), where N is the size of the array.

The positives and negatives of this solution are:

Pros:

Cons:

Better Case

To find a solution that is better than O(2^N), we need to use a lookup table, so we only have to navigate through the array once.

We want to have a HashMap of all elements that are on the way to being summed. So when we reach another element, if it is in the hash map, we know we can reach the target!

Algorithm

var twoSumsHashMaps = function(nums, target) {
  var map = new Map();
  for(var i = 0; i < nums.length; i++) {
    if(map.get(nums[i]) === undefined) {
      map.set(target - nums[i], i);
    } else {
      return [map.get(nums[i]), i];
    }
  }
};

Pros

Cons

Complexity

O(N), where N is the size of the array. This algorithm runs in Linear time as to lookup a hashmap only costs O(1) and looping through an array costs O(N), therefore O(N + 1) = O(N).

Comparing Computations

When counting the amount of computations both of the algorithms perform, it is clear that the better case does a lot less when the input is greater.

Worst Case

var twoSum = function(nums, target) {
    for(var i = 0; i < nums.length; i++) { ct += 2;
        for(var j = i + 1; j < nums.length; j++) { ct += 3;
            if(nums[i] + nums[j] == target) { ct += 2;
                return [i, j];
            }
        }
    }
    return [];
};

Better Case

var twoSumsHashMaps = function(nums, target) {
  var map = new Map(); ct++;
  for(var i = 0; i < nums.length; i++) { ct += 2;
    if(map.get(nums[i]) === undefined) { ct += 2;
      map.set(target - nums[i], i); ct += 2;
    } else {
      ct += 1;
      return [map.get(nums[i]), i];
    }
  }
};

For example:

Input:  [3, 2, 4, 7, 10]
Target: 17

Worst Case : 40
Better Case: 28

However, when the input is small, the computations very similar, and actually the one with Hashmaps performs slightly more:

Input:  [3, 2, 4]
Target: 6

Worst Case : 15
Better Case: 16

Final Solution

var twoSums = function(nums, target) {
  var map = new Map();
  for(var i = 0; i < nums.length; i++) {
    if(map.get(nums[i]) === undefined) {
      map.set(target - nums[i], i);
    } else {
      return [map.get(nums[i]), i];
    }
  }
};

Suggested

return home