david wong

Hey! I'm David, cofounder of zkSecurity and the author of the Real-World Cryptography book. I was previously a crypto architect at O(1) Labs (working on the Mina cryptocurrency), before that I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

Find all the pairs in a list that are summing to a known number posted May 2014

I got asked this question in an interview. And I knew this question beforehands, and that it had to deal with hashtables, but never got to dig into it since I thought nobody would asked me that for a simple internship.

I didn't know how to answer, in my mind I just had a simple php script that would have looked like this:

$arr = array(-5, 5, 3, 1, 7, 8);
$target = 8;

for($i = 0; $i < sizeof($arr) - 1; $i++)
{
    for($j = $i + 1; $j < sizeof($arr); $j++)
    {
    if($arr[$i] + $arr[$j] == $target)
        echo "pair found: ${arr[i]}, ${arr[j]}";
    }    
}

But it's pretty slow, it's mathematically correct, but it's more of a CS-oriented question. How to implement that quickly for machines? The answer is hash tables. Which are implemented as arrays in PHP (well, arrays are like super hash tables) and as dictionaries in Python.

I came up with this simple example in python:

arr = (-5, 5, 3, 1, 7, 8)
target = 8

dic = {}

for i, item in enumerate(arr):
    dic[item] = i

    if dic.has_key(target - item) and dic[target - item] != i:
        print item, (target - item)
  1. iterate the list
  2. assign the hash of the value to the index of the value in the array
  3. to avoid finding a pair twice, we do this in the same for loop:
    we do the difference of the target sum and the number we're on, we hash it, if we find that in the hash table that's good!
  4. but it could also be the number itself, so we check for its index, and it has to be different than its own index.

VoilĂ ! We avoid the n-1! additions and comparisons of the first idea with hash tables (I actually have no idea how fast they are but since most things use hash tables in IT, I guess that it is pretty fast).

Well done! You've reached the end of my post. Now you can leave a comment or read something else.

Comments

leave a comment...