Thistle Hunt

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 5 mins
• 🛠️ Topics: Lists, Loops

1: 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 locate_thistles() should take a list of strings items and return a list of the indices where the value is "thistle".

HAPPY CASE
Input: ["thistle", "stick", "carrot", "thistle", "eeyore's tail"]
Expected Output: [0, 3]

EDGE CASE
Input: ["book", "bouncy ball", "leaf", "red balloon"]
Expected Output: []

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

This problem falls under: List indexing and traversal.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Define a function that iterates through the list and records the indices where the value is "thistle".

1. Define the function `locate_thistles(items)`.
2. Initialize an empty list `indices` to store the indices.
3. Iterate through the list using a range to get both index and item.
4. For each item, check if it is equal to `"thistle"`.
5. If it is, add the index to `indices`.
6. Return the `indices` list.

⚠️ Common Mistakes

• Not correctly iterating through all elements of the input list.
• Misplacing or misidentifying the indices.

4: I-mplement

Implement the code to solve the algorithm.

def locate_thistles(items):
    # Initialize an empty list to store the indices
    indices = []
    
    # Iterate through the list using range to get both index and item
    for i in range(len(items)):
        # If the item is "thistle", add its index to the list
        if items[i] == "thistle":
            indices.append(i)
    
    # Return the list of indices
    return indices

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Call the function with the provided examples:

print(locate_thistles(["thistle", "stick", "carrot", "thistle", "eeyore's tail"]))  # Expected Output: [0, 3]
print(locate_thistles(["book", "bouncy ball", "leaf", "red balloon"]))              # Expected Output: []

Expected outputs:

[0, 3]
[]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

• Time Complexity: O(n) where n is the length of the input list items since we need to check each element.
• Space Complexity: O(k) where k is the number of times "thistle" appears in the input list, for storing the result list of indices.