MTCI_Sec4_GoogleInterview
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124
using System;
using System.Collections.Generic;
using System.Linq;
class MainClass {
static void Main() {
// collection of numbers
// find a pair that is equal to a given sum
//
//ex [1,2,3,9] Sum = 8
//ex [1,2,4,4] Sum = 8
//
// inputs:
// - collection of numbers
// - in memory
// - in order
// - can be repeating elements
// - all integers, including negatives
// outputs:
// - bool
//
// example inputs
int[] input1 = new int[] { 1,2,3,9 };
int input1Sum = 8;
int[] input2 = new int[] { 1,2,4,4 };
int input2Sum = 8;
// Brute force solution
// hasPairEqualingValBF(input1, input1Sum);
// hasPairEqualingValBF(input2, input2Sum);
// O(n) Dictionary solution
// hasPairEqualingValDict(input1, input1Sum);
// hasPairEqualingValDict(input2, input2Sum);
// O(log n) solution
hasPairEqualingValLog(input1, input1Sum);
hasPairEqualingValLog(input2, input2Sum);
}
private static bool hasPairEqualingValBF(int[] inputs, int sumValue)
{
// error checking
if (inputs.Length < 2) {
Console.WriteLine("Error: inputs array must have at least 2 items.");
}
// O(n^2) solution
for (int i = 0; i < inputs.Length; i++) {
for (int j = 0; j < inputs.Length; j++) {
if (j != i && ((inputs[i] + inputs[j]) == sumValue))
{
// pair equaling the sum has been found
Console.WriteLine("Pair found: {0} + {1} = {2}", inputs[i], inputs[j], sumValue);
return true;
}
}
}
// a pair equaling the sum was not found
Console.WriteLine("Pair not found.");
return false;
}
private static bool hasPairEqualingValDict(int[] inputs, int sumValue)
{
// error checking
if (inputs.Length < 2) {
Console.WriteLine("Error: inputs array must have at least 2 items.");
}
//O(n) solution
Dictionary<int, int> inputDict = inputs
.Select((value, index) => new { value, index })
.ToDictionary(pair => pair.index, pair => pair.value);
int complement = 0;
for (int i = 0; i < inputs.Length; i++) {
complement = sumValue - inputs[i];
if (inputDict.Any(kvp => kvp.Value == complement && kvp.Key != i))
{
// pair equaling the sum has been found
Console.WriteLine("Pair found");
return true;
}
}
Console.WriteLine("Pair not found.");
return false;
}
private static bool hasPairEqualingValLog(int[] inputs, int sumValue)
{
// error checking
if (inputs.Length < 2) {
Console.WriteLine("Error: inputs array must have at least 2 items.");
}
// O(log n) solution
int left = 0;
int right = inputs.Length - 1;
while (right > left) {
int currentSum = inputs[left] + inputs[right];
if (currentSum == sumValue) {
// pair equaling the sum has been found
Console.WriteLine("Pair found");
return true;
}
if (currentSum > sumValue)
right--; // decrease right index
if (currentSum < sumValue)
left++; // increase left index
}
Console.WriteLine("Pair not found.");
return false;
}
}
Csharp
INFO