Counting Iron Man's Suits - codepath/compsci_guides GitHub Wiki

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

Problem 1: Counting Iron Man's Suits

Tony Stark, aka Iron Man, has designed many different suits over the years. Given a list of strings suits where each string is a suit in Stark's collection, count the total number of suits in the list.

  1. Implement the solution iteratively without the use of the len() function.
  2. Implement the solution recursively.
  3. Discuss: what are the similarities between the two solutions? What are the differences?

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 15 mins
  • 🛠️ Topics: Iteration, Recursion

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?
  • Q: What is the main task in this problem?
    • A: The task is to count the total number of suits in the list using both iterative and recursive approaches.
  • Q: Can we use the len() function?
    • A: No, the problem explicitly states not to use the len() function for counting.
HAPPY CASE
Input: ["Mark I", "Mark II", "Mark III"]
Output: 3
Explanation: There are three suits in the list.

Input: ["Mark I", "Mark I", "Mark III", "Mark IV"]
Output: 4
Explanation: There are four suits in the list.

EDGE CASE
Input: []
Output: 0
Explanation: The list is empty, so the count should be 0.

Input: ["Mark I"]
Output: 1
Explanation: There is only one suit in the list.

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.

For Counting Problems, we want to consider the following approaches:

  • Iteration: Loop through the list and count each item.
  • Recursion: Use a base case and recursive calls to count the items in the list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • For the iterative solution, initialize a counter and increment it for each item in the list.
  • For the recursive solution, use the base case of an empty list returning 0, and for non-empty lists, return 1 plus the result of the recursive call on the rest of the list.

Iterative Approach:

1) Initialize a counter variable `count` to 0.
2) Loop through each item in the list `suits`.
3) For each item, increment the `count` by 1.
4) Return the `count` after the loop completes.

Recursive Approach:

1) Base case: If the list `suits` is empty, return 0.
2) Recursive case: Return 1 plus the result of a recursive call to the same function with the rest of the list (excluding the first item).

⚠️ Common Mistakes

  • Forgetting the base case in the recursive approach can lead to infinite recursion.
  • Failing to correctly initialize and update the counter in the iterative approach.

4: I-mplement

Implement the code to solve the algorithm.

# Iterative Solution:

def count_suits_iterative(suits):
    count = 0
    for suit in suits:
        count += 1
    return count

# Recursive Solution:

def count_suits_recursive(suits):
    if not suits:
        return 0
    return 1 + count_suits_recursive(suits[1:])

5: R-eview

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

  • Trace through the count_suits_iterative function with the input ["Mark I", "Mark II", "Mark III"]. The count should be incremented three times.
  • Trace through the count_suits_recursive function with the input ["Mark I", "Mark II", "Mark III"]. The function should return 3 after three recursive calls.

6: E-valuate

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

  • Time Complexity:
    • Iterative Solution: O(N) where N is the number of suits in the list.
    • Recursive Solution: O(N) where N is the number of suits in the list.
  • Space Complexity:
    • Iterative Solution: O(1) as only a counter variable is used.
    • Recursive Solution: O(N) due to the recursion stack space.