Intersection of Two Lists [Amazon Python Interview Question]

Write a function to get the intersection of two lists.

For example, if A = [1, 2, 3, 4, 5], and B = [0, 1, 3, 7] then you should return [1, 3].

p.s. this is the same as question 9.1 in Ace the Data Science Interview.

The simplest way to check for intersecting elements of two lists is to use a for-loop to iterate over one array and check if each element in the first list is contained in the other list using the operator.

A cleaner way to write this using a list comprehension is as follows:

However, this leads to a time complexity of O(N*M) where N is the length of A, and M is the length of B.

A better approach is to use sets (which utilizes a hash map implementation underneath) since the runtime time is O(1) for each lookup operation. Then we can do the series of lookups over the larger set (resulting in a O(min(N, M)) total runtime):

While the Python set's do have a built-in function called , coding interviews typically don't allow you to use that – they are trying to see you solve the problem from first-principles, not see if you memorized some lesser-known command.

However, if you want to be cheeky, this would be the code to use:

Remember to cast the set back into a list using the command!