Udemy: Master Coding Interview - Coding Problems - #55

Run Settings
LanguageC#
Language Version
Run Command
using System; using System.Collections.Generic; // Google interview question found at https://www.youtube.com/watch?v=XKu_SEDAykw // Given a collection of numbers and a given sum, find a matching pair of numbers // that add to equal the sum. // Example 1: [1,2,3,9], Sum=8 // Example 2: [1,2,4,4], Sum=8 // Initial assumption: values in arrays are sorted // Naive approach: Loop through array, then an inner loop starting from next // index, adding the two to check if equal to sum. This is slow, O(n^2) time // complexity. // Better approach: Work from outside in. If sum is greater than target sum, // decrement upper index (to get smaller sum). If sum is less than target sum, // increment lower index (to get greater sum). Stop before lower index equals // upper index. O(n) // Updated assumption: values in arrays are not guaranteed to be sorted // Naive approach: Add sort (eg, binary sort, O(n*log(n))) before main algorithm // Better approach: Traverse array, storing complement (sum-x) for each value x // in a hashset. Check if value is in hashset before adding value. O(n) class MainClass { static int[] array1 = {1, 2, 3, 9}; static int[] array2 = {1, 2, 4, 4}; static int[] array3 = {9, 1, 2, 3}; static int[] array4 = {4, 1, 2, 4}; static void Main() { Console.WriteLine("Sum in array1? " + DoTwoValuesAddToSum(array1, 8)); Console.WriteLine("Sum in array2? " + DoTwoValuesAddToSum(array2, 8)); Console.WriteLine("Sum in array3? " + DoTwoValuesAddToSum_Unsorted(array3, 8)); Console.WriteLine("Sum in array4? " + DoTwoValuesAddToSum_Unsorted(array4, 8)); } // O(n) static bool DoTwoValuesAddToSum(int[] array, int sum) { // Work from outside in. If sum is greater than target sum, // decrement upper index (to get smaller sum). If sum is less than target sum, // increment lower index (to get greater sum). Stop before lower index equals // upper index. int lo = 0; int hi = array.Length - 1; while (lo < hi) { int currentSum = array[lo] + array[hi]; if (currentSum == sum) { return true; } if (currentSum < sum) { lo++; } if (currentSum > sum) { hi--; } } return false; } static bool DoTwoValuesAddToSum_Unsorted(int[] array, int sum) { // Better approach: Traverse array, storing complement (sum-x) for each value x // in a hashset. Check if value is in hashset before adding value. HashSet<int> hash = new HashSet<int>(); for (int i = 0; i < array.Length; i++) { if (hash.Contains(array[i])) { return true; } hash.Add(sum - array[i]); } return false; } }
Editor Settings
Theme
Key bindings
Full width
Lines