I've been going over previous tech interviews I've had (got another one coming up).
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.
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).
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
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.
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?