Counting the Castle Walls - codepath/compsci_guides GitHub Wiki

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

Problem 2: Counting the Castle Walls

In a faraway kingdom, a castle is surrounded by multiple defensive walls, where each wall is nested within another. Given a list of lists walls where each list [] represents a wall, write a recursive function count_walls() that returns the total number of walls.

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 15-20 mins
  • 🛠️ Topics: Recursion, Nested Lists

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 walls, where each wall is represented as a nested list.
  • Q: What should the function return for an empty list of walls?
    • A: The function should return 1, representing the outermost wall.
HAPPY CASE
Input: ["outer", ["inner", ["keep", []]]]
Output: 4
Explanation: The list represents four walls: "outer", "inner", "keep", and the empty list representing the innermost part.

EDGE CASE
Input: []
Output: 1
Explanation: Even an empty list represents a single wall, so the count is 1.

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 Nested Structures, we want to consider the following approaches:

  • Recursive Counting: Recursively traverse each nested list and count it as one wall.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • The number of walls can be counted by considering each list as one wall, and then recursively counting the walls within it.

Recursive Approach:

1) Base case: If the list `walls` is empty, return 1 to represent the current wall.
2) Recursive case: Return 1 (for the current wall) plus the result of the recursive call on the nested list `walls[1]`.

⚠️ Common Mistakes

  • Not correctly accounting for the base case of an empty list.
  • Incorrectly indexing into the list or misunderstanding the nested structure.

4: I-mplement

Implement the code to solve the algorithm.

def count_walls(walls):
    if not walls:
        return 1
    return 1 + count_walls(walls[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_walls function with the input ["outer", ["inner", ["keep", []]]]. The function should return 4 after recursively counting each nested list.
  • Test the function with an edge case like []. The function should return 1, representing the single outer wall.

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 depth of the nested structure. The function processes each level of nesting, leading to linear time complexity.
  • Space Complexity: O(N) due to the recursion stack. The depth of recursion is proportional to the depth of the nested list.