Working at google: answers to google job interview programming problem mentioned in https://www.youtube.com/watch?v=XKu_SEDAykw

find_pair_with_sum.md

find_pair_with_sum

Given a sorted array of integers and a number n, find a pair of numbers in the array whose sum is n.

Solution

Algorithm

Start with a pair constituted of the first and last numbers of the sorted array. At each step, compute the sum of the current pair. If the sum is larger than our objective, take following element as the first of our pair. If it's smaller, take the previous element as the second element of the pair. If it's equal, then we have our solution.

###Implementation

C

Create a struct containing two pointers. It will be used as an input of the function (pointer to the first and the last element of the array), and an output (pointer to our two elements).

Javascript

Just use array indices.

Haskell

Use Data.Sequence to handle the finite-size sorted list.

Source

Google job interview.

Working at google: answers to google job interview programming problem mentioned in https://www.youtube.com/watch?v=XKu_SEDAykw

google.c

#include <stdio.h>
#include <stdlib.h>

struct pointer_pair {
  int* start;
  int* end;
};

struct pointer_pair find_pair_with_sum(struct pointer_pair input, int objective) {
  int sum;
  while(input.start < input.end) {
    sum = *(input.start) + *(input.end);
    if (sum == objective) break;
    if (sum > objective) input.end--;
    else input.start++;
  }
  return input;
}

int main(void) {
  int input_arr[] = {1,2,3,4,5};
  struct pointer_pair input_p;
  input_p.start = input_arr;
  input_p.end = input_arr + sizeof(input_arr)/sizeof(int) - 1;
  struct pointer_pair p = find_pair_with_sum(input_p, 6);

  if (p.start < p.end) printf("(%d,%d)", *p.start, *p.end);
  else printf("no result");
  return 0;
}

google.hs

import Data.Sequence

find_pair_with_sum :: (Ord a, Num a) => Seq a -> a -> Maybe (a,a)
find_pair_with_sum input objective =
  case (viewl input, viewr input) of
    (l:<ls, rs:>r) ->
      case compare (l+r) objective of
        LT -> find_pair_with_sum ls objective
        GT -> find_pair_with_sum rs objective
        EQ -> Just (l,r)
    _ -> Nothing

main =
  print $ find_pair_with_sum (fromList [1,2,3,4,5]) 5

google.js

function find_pair_with_sum(input, objective) {
  var start = 0, end = input.length - 1;
  while (start < end) {
    var sum = input[start] + input[end];
    if (sum === objective) return [input[start], input[end]];
    if (sum < objective) start ++;
    else end--;
  }
  throw new Error("no number pair matching the given sum");
}