Counting the Layers of a Sandwich - codepath/compsci_guides GitHub Wiki

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

Problem 1: Counting the Layers of a Sandwich

You're working at a deli, and need to count the layers of a sandwich to make sure you made the order correctly. Each layer is represented by a nested list. Given a list of lists sandwich where each list [] represents a sandwich layer, write a recursive function count_layers() that returns the total number of sandwich layers.

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 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 layers in a sandwich, where each layer is represented by a nested list.
  • Q: What should the function return if the list is empty?
    • A: The function should return 0 since there are no layers.
HAPPY CASE
Input: ["bread", ["lettuce", ["tomato", ["bread"]]]]
Output: 4
Explanation: The sandwich has four layers: "bread", "lettuce", "tomato", and another "bread".

Input: ["bread", ["cheese", ["ham", ["mustard", ["bread"]]]]]
Output: 5
Explanation: The sandwich has five layers: "bread", "cheese", "ham", "mustard", and another "bread".

EDGE CASE
Input: []
Output: 0
Explanation: An empty list has no layers, so the count is 0.

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 layer.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • The number of layers in a sandwich can be counted by considering each list as one layer and then recursively counting the layers within it.

Recursive Approach:

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

⚠️ Common Mistakes

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

4: I-mplement

Implement the code to solve the algorithm.

def count_layers(sandwich):
    if not sandwich:  # Base case: if the sandwich is empty
        return 0
    return 1 + count_layers(sandwich[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_layers function with the input ["bread", ["lettuce", ["tomato", ["bread"]]]]. The function should return 4 after recursively counting each nested list.
  • Test the function with an edge case like []. The function should return 0, correctly identifying that there are no layers.

6: E-valuate

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

Time Complexity:

  • Time Complexity: O(N) where N is the number of layers in the sandwich. The function processes each layer exactly once.
  • Space Complexity: O(N) due to the recursion stack. The depth of recursion is proportional to the number of layers in the sandwich.

Discussion:

  • The recursive approach effectively handles the nested structure of the sandwich, ensuring that each layer is counted correctly.
  • This solution is straightforward and aligns well with the problem's recursive nature, making it both intuitive and efficient for the given task.