Frontend School

Oyo Room Assignment Log

DSA
medium

Oyo Room Assignment Log

Medium
Stack
Arrays
String Parsing

Overview

At Oyo, efficiently managing room assignments is crucial for smooth hotel operations and guest satisfaction. As part of a new internal tool, we need to process a historical log of room assignment changes to determine the final state of assigned rooms. This problem simulates processing such a log, which involves adding assignments, removing the most recent ones, swapping recent assignments, and batch-unassigning multiple rooms.

What you need to do / Task

Implement a function processAssignmentLog that takes an array of strings representing room assignment operations and returns the final ordered list of assigned rooms. The operations are processed sequentially.

The operations can be one of the following:

  1. Room Number: A string consisting of digits (e.g., "101", "205") or specific identifiers (e.g., "VIP", "SUITE"). This indicates a new room has been assigned and should be added to the log.
  2. "UNASSIGN": This operation indicates that the most recently assigned room (that has not yet been unassigned) should be freed up. If there are no assigned rooms, this operation does nothing.
  3. "SWAP": This operation indicates that the two most recently assigned rooms should have their positions swapped in the log. If there are fewer than two assigned rooms, this operation does nothing.
  4. "BATCH_UNASSIGN_K": This operation indicates that the K most recently assigned rooms should be freed up. K will be an integer embedded in the string (e.g., "BATCH_UNASSIGN_3" means unassign the 3 most recent rooms). If there are fewer than K assigned rooms, all currently assigned rooms are freed up.

The final list of assigned rooms should be returned in the order they were originally assigned, from oldest to newest.

Input & Output

  • Input:
    • operations: string[] - An array of strings, where each string represents an operation as described above.
  • Output:
    • string[] - An array of strings representing the final list of assigned rooms, ordered from oldest to newest.

Clarifications

  • Room numbers/identifiers are unique strings. You don't need to validate their format beyond assuming they are valid room identifiers or specific keywords.
  • "BATCH_UNASSIGN_K" will always have a valid integer K after the underscore. K will be a positive integer.
  • Operations are processed strictly in the given order.
  • The "log" of assigned rooms should behave like a stack for operations like UNASSIGN, SWAP, and BATCH_UNASSIGN_K, where operations affect the "top" (most recent) elements. The final output, however, should reflect the order of assignment from oldest to newest.

Examples

1

Example 1

Input:

operations = ["101", "201", "UNASSIGN", "301", "SWAP"]

Output:

["301", "101"]

Note:

  1. [] -> ["101"] (Assign 101)
  2. ["101"] -> ["101", "201"] (Assign 201)
  3. ["101", "201"] -> ["101"] (Unassign 201)
  4. ["101"] -> ["101", "301"] (Assign 301)
  5. ["101", "301"] -> ["301", "101"] (Swap 101 and 301) Final assigned rooms: ["301", "101"].
2

Example 2

Input:

operations = ["VIP", "SUITE", "105", "BATCH_UNASSIGN_2", "200", "UNASSIGN", "SWAP", "UNASSIGN"]

Output:

[]

Note:

  1. [] -> ["VIP"] (Assign VIP)
  2. ["VIP"] -> ["VIP", "SUITE"] (Assign SUITE)
  3. ["VIP", "SUITE"] -> ["VIP", "SUITE", "105"] (Assign 105)
  4. ["VIP", "SUITE", "105"] -> ["VIP"] (BATCH_UNASSIGN_2: removes 105, SUITE)
  5. ["VIP"] -> ["VIP", "200"] (Assign 200)
  6. ["VIP", "200"] -> ["VIP"] (UNASSIGN: removes 200)
  7. ["VIP"] -> ["VIP"] (SWAP: only one room, no change)
  8. ["VIP"] -> [] (UNASSIGN: removes VIP) Final assigned rooms: [].
3

Example 3

Input:

operations = ["R1", "R2", "R3", "R4", "BATCH_UNASSIGN_1", "BATCH_UNASSIGN_5", "R5"]

Output:

["R5"]

Note:

  1. [] -> ["R1"]
  2. ["R1"] -> ["R1", "R2"]
  3. ["R1", "R2"] -> ["R1", "R2", "R3"]
  4. ["R1", "R2", "R3"] -> ["R1", "R2", "R3", "R4"]
  5. ["R1", "R2", "R3", "R4"] -> ["R1", "R2", "R3"] (BATCH_UNASSIGN_1: removes R4)
  6. ["R1", "R2", "R3"] -> [] (BATCH_UNASSIGN_5: removes all 3 rooms, since 3 < 5)
  7. [] -> ["R5"] Final assigned rooms: ["R5"].

Constraints

Constraints & assumptions

  • 1 <= operations.length <= 10^5
  • Each string in operations will have a length between 1 and 10 characters.
  • Room identifiers (e.g., "101", "VIP") will consist of alphanumeric characters.
  • K in "BATCH_UNASSIGN_K" will be an integer 1 <= K <= 10^5.
  • The number of concurrently assigned rooms will not exceed 10^5.
  • The total number of push/pop operations will not lead to memory exhaustion beyond typical limits for 10^5 elements.

What interviewers evaluate

  • Correctness: The solution correctly handles all specified operations and edge cases (e.g., empty stack, insufficient elements for SWAP/BATCH_UNASSIGN_K).
  • Algorithm Design: Efficient use of appropriate data structures (e.g., a stack) to manage room assignments and process operations.
  • Code Quality: Readability, maintainability, and proper handling of different operation types.
  • Time and Space Complexity: An optimal solution should aim for O(N) time complexity where N is the number of operations, and O(M) space complexity where M is the maximum number of concurrently assigned rooms.

Loading editor...