Thought I would give some tips here from an interviewing standpoint. Using Question #1 as an example, in the comments I’m seeing some alternative solutions that involve leveraging built-in python specific libraries, or sorting lists and then comparing them. Unfortunately, any of these types of solutions would reflect very poorly and be an automatic fail in any technical interview.
From a technical interviewing standpoint, basic algorithms questions like this one serve two main purposes:
1) Can the interviewee solve the problem without relying on built-in language specific functions and/or libraries?
2) Does the interviewee display a basic knowledgebase in Data Structures & Algorithms, computational complexity and running-times (and hence scalability), and is capable of choosing the “best” solution to the problem that is both simple and computationally efficient?
As an example for Question #1, sorting the two lists with a built-in “sort” function and then comparing them would be an automatic fail because:
1) A built-in sorting library was used
2) Sorting the two lists and then comparing them is computationally inefficient. The asymptotic complexity of this solution is O(nln(n)). Chris’s solution with the use of hash tables (python dictionaries) has complexity O(n) and is absolutely the “correct” approach for this problem from a technical interviewing standpoint.
Most companies ask these types of questions in first-round screening interviews specifically to weed out people early. Even though a “sort and compare” approach technically solves the problem, it would be seen as naive, give the sense the interviewee has no sense of computational complexity or why it’s important, and would be an automatic fail. As frustrating as that is, that’s how the technical interviewing game works.