1

I was in an interview once, where I was asked to find the first common element between two sorted arrays, and I chose the following algo:

def elementMatch(a1, a2):
    '''Find first similar element in a pair of sorted arrays'''
    try:
        return sorted(set(a1) & set(a2))[0]
    except IndexError:
        return False`

The interviewer asked about another solution, and I said nested loops could work as well, but I think the set solution may be quicker. He said that he thought internally set was probably using something like a nested loop. Is that accurate? How does set work when comparing elements?

GL2014
  • 6,016
  • 4
  • 15
  • 22
  • No, that is not accurate - a set is implemented like a dictionary, i.e. based on hashing. You can see the CPython implementation [here](https://hg.python.org/cpython/file/162743b7f59b/Objects/setobject.c). – jonrsharpe Apr 08 '15 at 13:35
  • `first common element between two sorted arrays` - sorted is the key here. – thefourtheye Apr 08 '15 at 13:35
  • 2
    You don't need a nested loop. Keep advancing in the array with the lowest element, until you find a common element to both or you reach the end of one of the arrays. You can find it in O(n). – siritinga Apr 08 '15 at 13:37
  • You can slightly modify [Merge algorithm](http://en.wikipedia.org/wiki/Merge_algorithm) and solve this in O(n) – thefourtheye Apr 08 '15 at 13:42
  • So clearly my solution is more efficient than any nested for loop would be, which could be linear time in worst case. Is that correct? – GL2014 Apr 08 '15 at 14:04
  • @GL2014: Your solution involves constructing the two sets, which is expected O(n) if sets are hash tables, which I think they are. Doing a simple merge between the two ordered vectors until a common element is found is also O(n), but it will almost always be faster because in most cases it will terminate before scanning the entirety of both vectors. Also, you are using `sort` at the end (O(n log n) if the two vectors are mostly equal), instead of `min` which would be O(n). – rici Apr 08 '15 at 16:40

0 Answers0