Google

 I decided to apply to a PhD internship at Google as soon as possible, i.e. as soon as my research permits me. I'm preparing for the interviews using this platform https://algodaily.com/

They send you daily emails with coding problems. I thought I'd document my journey and post my solution here every day:-)

The first problem is to find the intersection of two lists. NB! The lists can have duplicates.

The brute force solution is a double for loop with a quadratic time complexity. I came up with an n*log(n) solution involving two pointers. The complexity of my solution is dominated by the necessity to sort the two arrays and optimal sorting algorithms are n*log(n). 

So you first sort the arrays (for instance in decreasing order) and then lay one beneath the other. You keep a pointer at the first index of the top array and the first index of the bottom array. You start by comparing the two numbers to which these indices are pointing. If the top number is larger than the bottom number you increment the bottom pointer and that's that for that number. If the top number is smaller than the bottom number you increment the top pointer, that's the only hope you have for finding a twin. If the two numbers are equal you initialize a solutions array and insert one of the numbers into the array and increment both pointers. No matter what you do, you now have a pair of new pointers pointing to the same numbers and you can repeat the exact same logic, except for the small caveat that if you should check the last member of your solutions list before adding an element if it is equal to the new element to be added in order to avoid adding duplicates, because the intersection of two lists is a set. Also, you reach the end of any array, you stop.

The solution is here https://github.com/mariakesa/Algorithms/blob/master/AlgoDaily/AlgorithmsPractice.ipynb

 

Edit: My friend came up with a better solution. Turn one list into a hash table where lookups are constant and iterate over the other list checking for each member whether it is in the hash table. That's a linear time algorithm, which beats my n*log(n).