Arrange Guest Arrival Order - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Advanced (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 string arrival_pattern consisting of the characters 'I' (indicating increasing order) and 'D' (indicating decreasing order).
• Q: What is the output?
  • A: The output is a string guest_order of length n + 1 that represents the order of guest arrivals, satisfying the conditions of the arrival_pattern.
• Q: What does lexicographically smallest mean?
  • A: Lexicographically smallest means that if there are multiple valid guest_order strings, the one that appears first in dictionary order should be returned.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to build the guest_order string by pushing digits as you iterate through the arrival_pattern. When you encounter an 'I' or reach the end, pop elements from the stack to ensure the correct order.

1. Initialize an empty list `guest_order` to store the final order of guests.
2. Initialize an empty stack to help manage the digits as we process the `arrival_pattern`.
3. Iterate through the `arrival_pattern` from `0` to `n`, where `n` is the length of `arrival_pattern`:
   1. Push the digit `i + 1` onto the stack.
   2. If the current pattern character is `'I'` or we've reached the end of the pattern:
      1. Pop all elements from the stack and append them to `guest_order`.
4. Convert the `guest_order` list to a string and return it.

⚠️ Common Mistakes

• Misunderstanding the use of the stack to reverse the order when needed.
• Not correctly managing the transitions between 'I' and 'D' in the arrival_pattern.
• Forgetting to append the last digit after the loop completes.

I-mplement

def arrange_guest_arrival_order(arrival_pattern):
    n = len(arrival_pattern)
    guest_order = []
    stack = []

    for i in range(n + 1):
        stack.append(str(i + 1))
        if i == n or arrival_pattern[i] == 'I':
            while stack:
                guest_order.append(stack.pop())

    return ''.join(guest_order)

# Example usage
print(arrange_guest_arrival_order("IDID"))  # Output: "13254"
print(arrange_guest_arrival_order("III"))   # Output: "1234"
print(arrange_guest_arrival_order("DDI"))   # Output: "3214"