Design order stream with state transitions

Implement an in-memory order stream service with operations: add(order), delete(order_id), pause(order_id), resume(order_id); follow-up: delete_all_by_user(user_id). Define the order schema and valid state transitions, ensure operations are idempotent, and support efficient lookups by order_id and by user_id. Describe chosen data structures, expected time/space complexity, and provide example tests. Discuss how you would extend it for persistence and concurrency if required.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Part 1: In-Memory Order Stream with State Transitions

Implement an in-memory order stream simulator. The service starts empty and processes operations in order. Assumptions: each order has schema order_id, user_id, and state; order_id and user_id are strings and do not contain ':' or ','; order IDs are globally unique and cannot be reused after deletion. Valid states are ACTIVE, PAUSED, and DELETED. Valid transitions are: add creates ACTIVE; pause changes ACTIVE to PAUSED and is an idempotent no-op on PAUSED; resume changes PAUSED to ACTIVE and is an idempotent no-op on ACTIVE; delete changes ACTIVE or PAUSED to DELETED and is an idempotent no-op for missing or already deleted orders. Deleted orders remain as tombstones for order_id lookup and idempotency, but they do not appear in user lookups. Use hash maps for efficient lookup by order_id and by user_id.

Constraints

• 0 <= len(operations) <= 200000
• order_id and user_id are non-empty strings of length at most 64
• order_id and user_id do not contain ':' or ','
• All operation names are valid and each operation has the correct number of fields
• At most 200000 distinct order IDs and 200000 distinct user IDs appear

Examples

Example 1

Input: ([['add', 'o1', 'u1'], ['get_order', 'o1'], ['pause', 'o1'], ['get_order', 'o1'], ['resume', 'o1'], ['get_user_orders', 'u1']],)
Output: ['OK', 'o1:u1:ACTIVE', 'OK', 'o1:u1:PAUSED', 'OK', 'o1:ACTIVE']

Explanation: A single order is added, paused, resumed, and then found through the user index.

Example 2

Input: ([['add', 'o1', 'u1'], ['add', 'o1', 'u1'], ['pause', 'o1'], ['pause', 'o1'], ['add', 'o1', 'u2'], ['get_user_orders', 'u1']],)
Output: ['OK', 'OK', 'OK', 'OK', 'INVALID', 'o1:PAUSED']

Explanation: Duplicate add with the same user and duplicate pause are idempotent. Reusing the same order_id for another user is invalid.

Hints

1. Keep one dictionary from order_id to the order record, and another dictionary from user_id to the set of currently non-deleted order IDs.
2. Deletion should update both indexes, but keep a tombstone in the order_id dictionary so repeated deletes and later get_order calls are well-defined.

Part 2: In-Memory Order Stream with Bulk Delete by User

Extend the in-memory order stream from Part 1 with delete_all_by_user(user_id). The service starts empty and supports all previous operations plus bulk deletion. Assumptions: each order has schema order_id, user_id, and state; order_id and user_id are strings and do not contain ':' or ','; order IDs are globally unique and cannot be reused after deletion. delete_all_by_user marks every currently non-deleted order for that user as DELETED, removes those orders from the user index, and returns the number of orders newly deleted. Repeating delete_all_by_user for the same user is idempotent and returns zero if no non-deleted orders remain. Keep tombstones in the order_id dictionary.

Constraints

• 0 <= len(operations) <= 200000
• order_id and user_id are non-empty strings of length at most 64
• order_id and user_id do not contain ':' or ','
• All operation names are valid and each operation has the correct number of fields
• At most 200000 distinct order IDs and 200000 distinct user IDs appear

Examples

Example 1

Input: ([['add', 'o1', 'u1'], ['add', 'o2', 'u1'], ['pause', 'o2'], ['add', 'o3', 'u2'], ['delete_all_by_user', 'u1'], ['get_user_orders', 'u1'], ['get_order', 'o2'], ['get_user_orders', 'u2']],)
Output: ['OK', 'OK', 'OK', 'OK', 'DELETED 2', 'EMPTY', 'o2:u1:DELETED', 'o3:ACTIVE']

Explanation: Bulk delete removes both ACTIVE and PAUSED orders for u1 without affecting u2.

Example 2

Input: ([['add', 'o1', 'u1'], ['delete', 'o1'], ['delete_all_by_user', 'u1'], ['delete_all_by_user', 'u1'], ['get_order', 'o1']],)
Output: ['OK', 'OK', 'DELETED 0', 'DELETED 0', 'o1:u1:DELETED']

Explanation: An individually deleted order is already absent from the user index, so bulk delete has nothing new to delete.

Hints

1. The user_id index should contain only currently non-deleted orders, so bulk deletion can iterate exactly the affected orders.
2. Convert the affected set to a list before mutating or deleting the set from the index.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Implement an in-memory order stream service with operations: add(order), delete(order_id), pause(order_id), resume(order_id); follow-up: delete_all_by_user(user_id). Define the order schema and valid state transitions, ensure operations are idempotent, and support efficient lookups by order_id and by user_id. Describe chosen data structures, expected time/space complexity, and provide example tests. Discuss how you would extend it for persistence and concurrency if required.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.