Google Interview - Matching Pair Equals Sum

using System;

using System.Collections.Generic;

using System.Linq;

// Problem: take a collection of numbers where a matching pair equals a sum that is provided

// inputs: array: [1,2,3,4], sum: 8

// brute force approach is log(n^2)

class MainClass {

static void Main() {

Console.WriteLine(MatchingPairEqualsQuadratic(new int[] {1,2,3,9}, 8));

Console.WriteLine(MatchingPairEqualsQuadratic(new int[] {-5,-3,4,11}, 8));

Console.WriteLine(MatchingPairEqualsLinear(new int[] {1,2,3,9}, 8));

Console.WriteLine(MatchingPairEqualsLinear(new int[] {-5,-3,4,11}, 8));

}

static bool MatchingPairEqualsQuadratic(int[] arry, int sum) {

if (arry.Length == 1) return false;

for (int i=0; i < arry.Length; i++) {

for (int j=1; j < arry.Length; j++) {

if (arry[i] + arry[j] == sum) return true;

}

}

return false;

}

// assuming a sorted list of numbers

// the number starting at the beginning index is the smallest number and the number at the ending index is the largest number

// which defines the range. When summing the largest and smallest if the sum is smaller than the target number then move the index

// of the smaller number and of the sum is larger then move the index of the larger number

static bool MatchingPairEqualsLinear(int[] arry, int sum) {

if (arry.Length == 1) return false;

int startIndex = 0;

int endIndex = arry.Length - 1;

int currentSum = arry[startIndex] + arry[endIndex];

if (currentSum == sum) return true;

while ( currentSum != sum) {

if (currentSum < sum) {

startIndex++;

} else {

endIndex--;

}

if (startIndex >= endIndex) break;

currentSum = arry[startIndex] + arry[endIndex];

}

return currentSum == sum;

}

}