Festival Booth Navigation

Edit PagePage History

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

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is a list clues where each element is either an integer representing a booth number or the word "back" indicating that the participant should backtrack to the previous booth.
• Q: What is the output?
  • A: The output is the final sequence of booth numbers visited, in the order they were visited.
• Q: How should the clues be processed?
  • A: Booth numbers should be added to the sequence as they are visited, and "back" should remove the most recently visited booth, simulating backtracking.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to simulate the navigation process. Each booth number is pushed onto the stack when visited, and if "back" is encountered, the last visited booth is removed from the stack.

1. Initialize an empty stack to track the sequence of booths visited.
2. Iterate through the list `clues`:
   1. If the clue is an integer (booth number), push it onto the stack.
   2. If the clue is `"back"`, pop the top element from the stack if it is not empty.
3. After processing all clues, return the stack, which contains the final sequence of booths visited.

⚠️ Common Mistakes

• Forgetting to check if the stack is empty before popping when "back" is encountered.
• Mismanaging the order of operations, leading to an incorrect sequence of booths.
• Not handling consecutive "back" commands correctly, which could result in an incorrect final sequence.

I-mplement

def booth_navigation(clues):
    stack = []

    for clue in clues:
        if clue == "back":
            if stack:
                stack.pop()
        else:
            stack.append(clue)

    return stack

# Example usage
clues = [1, 2, "back", 3, 4]
print(booth_navigation(clues))  # Output: [1, 3, 4]

clues = [5, 3, 2, "back", "back", 7]
print(booth_navigation(clues))  # Output: [5, 7]

clues = [1, "back", 2, "back", "back", 3]
print(booth_navigation(clues))  # Output: [3]