I've been going over previous tech interviews I've had (got another one coming up).
The problem
Anyway, one question I had was...
Given 2 unsorted arrays how would you find all of the common objects between them?
Say I have array A and B. Worst case A and B are both of size n.
Initial thought
Initially my thought was to iterate A and do a linear search through B.
The complexity for this is O(n) * O(n) = O(n^2)
.
Sorting first
However, I was wondering if it would be better to sort B first.
Using a quick sort (or merge sort) on B is O(n log(n))
. This is done once.
Now you can iterate A O(n)
and do a binary search on B O(log(n))
for each A.
So the complexity is (sort) O(n log(n)) + (iterate A) O(n) * (search B) O(log(n))
which simplifies down to O(n log(n))
.
My question is. Am I right with this? I am very new to complexity analysis so wanted to check that I'm not doing anything stupid.
Best solution
Is the best solution then to sort one array first before iterating the other? You could sort both arrays and then iterate but you're not improving O(n log(n).
Is there another better way of approaching this?