Common Cause - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Sets, Iteration

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• The function common_elements() should take two lists lst1 and lst2 and return a list of elements that are present in both lists.

HAPPY CASE
Input: lst1 = ["super strength", "super speed", "x-ray vision"], lst2 = ["super speed", "time travel", "dimensional travel"]
Expected Output: ["super speed"]

Input: lst1 = ["apple", "banana", "cherry"], lst2 = ["banana", "cherry", "date"]
Expected Output: ["banana", "cherry"]

EDGE CASE
Input: lst1 = ["super strength", "super speed", "x-ray vision"], lst2 = ["martial arts", "stealth", "master detective"]
Expected Output: []

Input: lst1 = [], lst2 = ["time travel"]
Expected Output: []

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Convert one list to a set for O(1) average time complexity checks and iterate through the other list to find common elements.

1. Convert `lst2` to a set called `set2` for faster lookups.
2. Initialize an empty list `result` to store common elements.
3. Iterate through each element in `lst1`:
   a. If the element is in `set2`, append it to `result`.
4. Return `result`

⚠️ Common Mistakes

• Not accounting for duplicates in the input lists.
• Not handling cases where one or both lists are empty.

I-mplement

Implement the code to solve the algorithm.

def common_elements(lst1, lst2):
    set2 = set(lst2)
    result = []
    for item in lst1:
        if item in set2:
            result.append(item)
    return result