This exercise is based on the solution found at Google Life's YouTube channel. Admittedly, I was pulling my hair out for a bit on this one.
The question asks the programmer to find an efficient way to find two numbers in a sequence that add up to a number.
Following along in my mind the solution was similar to what was proposed by the interviewee except instead of using the HASH table I used an associative array. Instead of finding all the compliments until I found one that was missing. It made sense to simply add the compliment as the key in the array and if I found a value plus the compliment. Then I would know I had found the answer.
<?php $result = hasPairWithSum([1,2,4,8,12,15,6,5],20); if(false === $result) { print "No results found \n"; }else{ print $result[0]." : ".$result[1]."\n"; } echo "\n"; /** * hasPairWithSum * [1,2,3,9] ?= 8 * [1,2,4,4] ?= 8 * @param array * @param integer * * @return variant boolean / array * */ function hasPairWithSum($set,$sum) { // initialize an array to compare against that will contain a list of complementary numbers $comp = []; // get the length of our set $l = count($set); // loop the set for($i=0; $i<$l; $i++) { // have i seen this before? if(isset($comp[$set[$i]])) { // if i have seen this number before does its compliment result in our target sum? if(($comp[$set[$i]] + $set[$i]) == $sum) return array($comp[$set[$i]],$set[$i]); // yes,...then return that value } // add the current test result to our hash set $comp[($sum - $set[$i])] = $set[$i]; } // didn't find it...? return false; }
Once I found my answer I began adding larger numbers to search for in larger sets by passing some random logic before running the function:
<?php $set = array(); $sum = floor(rand(1000,10000)); $set_length = 20000; $set_lengths = array(); for($i=0; $i<$set_length; $i++) { $set[] = floor(rand(1,$set_length)); } $result = hasPairWithSum($set,$sum); print "sum = ".$sum."\n"; if(false === $result) { print "No results found \n"; }else{ print $result[0]." : ".$result[1]."\n"; } echo "\n";
Eventually I hit an out of memory error. To fix this issue I began dropping parts of the set that were no longer necessary by adding this to the loop:
// have i seen this before? if(isset($comp[$set[$i]])) { // if i have seen this number before does its compliment result in our target sum? if(($comp[$set[$i]] + $set[$i]) == $sum) { return array($comp[$set[$i]],$set[$i]); // yes,...then return that value }else{ // we don't need this anymore, so get rid of it unset($comp[$set[$i]]); } }
By doing this I was able to find numbers up to a million with a set length of up to two million...(Maybe more I just haven't pushed it).
The program only takes a few seconds to run.
I think I will build a version to chunk out the task to multiple computers. That should be interesting.
Meanwhile here is the final test code:
<?php $set = array(); $sum = floor(rand(1000,1000000)); $set_length = 2000000; $set_lengths = array(); for($i=0; $i<$set_length; $i++) { $set[] = floor(rand(1,$set_length)); } $result = hasPairWithSum($set,$sum); print "sum = ".$sum."\n"; if(false === $result) { print "No results found \n"; }else{ print $result[0]." : ".$result[1]."\n"; } echo "\n"; /** * hasPairWithSum * [1,2,3,9] ?= 8 * [1,2,4,4] ?= 8 * @param array * @param integer * * @return variant boolean / array * */ function hasPairWithSum($set,$sum) { // initialize an array to compare against that will contain a list of complimentary numbers $comp = []; // get the length of our set $l = count($set); // loop the set for($i=0; $i<$l; $i++) { // have i seen this before? if(isset($comp[$set[$i]])) { // if i have seen this number before does its compliment result in our target sum? if(($comp[$set[$i]] + $set[$i]) == $sum) { return array($comp[$set[$i]],$set[$i]); // yes,...then return that value }else{ // we don't need this anymore, so get rid of it unset($comp[$set[$i]]); } } // add the current test result to our hash set $comp[($sum - $set[$i])] = $set[$i]; } // didn't find it...? return false; }