Mapping Atlantis' Hidden Chambers - codepath/compsci_guides GitHub Wiki

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

Problem 1: Mapping Atlantis' Hidden Chambers

Poseidon, the ruler of Atlantis, has a map that shows various chambers hidden deep beneath the ocean. The map is currently stored as a nested list sections, with each section containing smaller subsections. Write a recursive function map_chambers() that converts the map into a nested dictionary, where each section and subsection is a key-value pair.

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Recursion, Dictionary Construction

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 convert a nested list representing sections of Atlantis into a nested dictionary using recursion.
  • Q: How should the sections and subsections be represented in the dictionary?
    • A: Each section should be a key, and its corresponding subsection should be its value in the dictionary.
HAPPY CASE
Input: ["Atlantis", ["Coral Cave", ["Pearl Chamber"]]]
Output: {'Atlantis': {'Coral Cave': 'Pearl Chamber'}}
Explanation: The nested list is converted into a nested dictionary, where each section is a key and its subsection is the value.

EDGE CASE
Input: ["Atlantis"]
Output: 'Atlantis'
Explanation: If there is only one section, it should simply be returned as a string.

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

  • Recursive Mapping: Recursively process each section of the list, converting it into a key-value pair in the dictionary.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • To convert the nested list into a dictionary, treat the first element as the key and the rest of the list as the value, recursively processing the value.

Recursive Approach:

1) Base case: If the list `sections` contains only one element, return that element.
2) Recursive case: Return a dictionary where the first element of `sections` is the key, and the result of recursively processing the rest of the list is the value.

⚠️ Common Mistakes

  • Not handling the base case correctly, which could lead to incorrect or incomplete dictionaries.
  • Incorrectly nesting the dictionaries, leading to unexpected structures.

4: I-mplement

Implement the code to solve the algorithm.

def map_chambers(sections):
    if len(sections) == 1:
        return sections[0]
    return {sections[0]: map_chambers(sections[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 map_chambers function with the input ["Atlantis", ["Coral Cave", ["Pearl Chamber"]]]. The function should return {'Atlantis': {'Coral Cave': 'Pearl Chamber'}} after recursively converting the list to a nested dictionary.
  • Test the function with edge cases like ["Atlantis"]. The function should return "Atlantis", correctly identifying the base case.

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 depth of the nested list. The function processes each section exactly once.
  • Space Complexity: O(N), due to the recursion stack. The depth of recursion is proportional to the depth of the nested list.

Discussion:

  • This recursive approach effectively converts the nested list into a nested dictionary, maintaining the hierarchical structure of the sections.
  • The solution is straightforward and leverages the natural recursive structure of the problem, making it both intuitive and efficient for the given task.