Frontend School

Simulate Task Processing with Undo

DSA
medium

Simulate Task Processing with Undo

Medium
Stack
Queue
Data Structures
Simulation

Overview

Flipkart's order fulfillment system processes various tasks, but sometimes errors or changes require rolling back recent operations. This problem simulates a simplified task processing system that handles incoming tasks in order, and allows for undoing the most recently completed task. Your task is to implement the core logic for this system.

What you need to do / Task

Implement the simulateProcessingSystem function that takes an array of operations. The system should maintain an internal state to handle these operations:

  1. ADD <task_id>: Adds a task identified by task_id to a queue for pending processing.
  2. PROCESS: Takes the next available task from the pending queue and marks it as completed. This completed task should be available for an UNDO operation.
  3. UNDO: Reverts the last PROCESS operation. If an UNDO occurs, the task that was just processed is "un-processed" and effectively removed from the "completed" state. If there are no completed tasks to undo, this operation has no effect.

The function should return an array of results, where each result corresponds to an operation in the input array.

Input & output

Function Signature: function simulateProcessingSystem(operations: string[]): (string | null)[]

Input:

  • operations: An array of strings. Each string represents an operation.
    • "ADD <task_id>": task_id is a string identifier for the task (e.g., "T101").
    • "PROCESS": No additional parameters.
    • "UNDO": No additional parameters.

Output:

  • (string | null)[]: An array of results corresponding to each operation.
    • For "ADD <task_id>": Return null.
    • For "PROCESS": Return the task_id of the processed task. If the pending queue is empty, return null.
    • For "UNDO": Return the task_id of the task that was undone. If there are no tasks available to undo, return null.

Clarifications

  • Tasks are identified by unique string task_ids.
  • PROCESS operations always take from the front of the pending queue (FIFO).
  • UNDO operations always revert the last task that was PROCESSed (LIFO).
  • If PROCESS is called on an empty queue, it processes nothing and returns null. This "null processing" itself cannot be undone.
  • If UNDO is called when no tasks have been PROCESSed or all processed tasks have been undone, it does nothing and returns null.

Examples

1

Example 1

Input:

operations = ["ADD T1", "ADD T2", "PROCESS", "PROCESS", "UNDO", "PROCESS"]

Output:

[null,null,"T1","T2","T2",null]

Note:

  1. "ADD T1": Queue: [T1], Processed Stack: []. Returns null.
  2. "ADD T2": Queue: [T1, T2], Processed Stack: []. Returns null.
  3. "PROCESS": Takes T1. Queue: [T2], Processed Stack: [T1]. Returns "T1".
  4. "PROCESS": Takes T2. Queue: [], Processed Stack: [T1, T2]. Returns "T2".
  5. "UNDO": Undoes T2. Queue: [], Processed Stack: [T1]. Returns "T2".
  6. "PROCESS": Queue is empty. Returns null.
2

Example 2

Input:

operations = ["PROCESS", "UNDO", "ADD T1", "PROCESS", "UNDO", "UNDO"]

Output:

[null,null,null,"T1","T1",null]

Note:

  1. "PROCESS": Queue empty. Returns null.
  2. "UNDO": Processed stack empty. Returns null.
  3. "ADD T1": Queue: [T1]. Returns null.
  4. "PROCESS": Takes T1. Queue: [], Processed Stack: [T1]. Returns "T1".
  5. "UNDO": Undoes T1. Queue: [], Processed Stack: []. Returns "T1".
  6. "UNDO": Processed stack empty. Returns null.
3

Example 3

Input:

operations = ["ADD A", "PROCESS", "ADD B", "ADD C", "PROCESS", "UNDO", "PROCESS", "UNDO", "UNDO"]

Output:

[null,"A",null,null,"B","B","C","C","A"]

Note:

  1. "ADD A": Q:[A], S:[]. Res: null
  2. "PROCESS": Q:[], S:[A]. Res: "A"
  3. "ADD B": Q:[B], S:[A]. Res: null
  4. "ADD C": Q:[B,C], S:[A]. Res: null
  5. "PROCESS": Q:[C], S:[A,B]. Res: "B"
  6. "UNDO": Q:[C], S:[A]. Res: "B" (B is undone)
  7. "PROCESS": Q:[], S:[A,C]. Res: "C" (C is processed)
  8. "UNDO": Q:[], S:[A]. Res: "C" (C is undone)
  9. "UNDO": Q:[], S:[]. Res: "A" (A is undone)

Constraints

Constraints & assumptions

  • 1 <= operations.length <= 10^5
  • task_id will be a non-empty string, consisting of alphanumeric characters.
  • Each task_id mentioned in an ADD operation will be unique within the context of tasks currently awaiting processing or recently processed.
  • The system starts with an empty pending queue and an empty processed history.
  • The time complexity for each operation should ideally be O(1) on average.

What interviewers evaluate

  • Correctness: Does the solution correctly implement the logic for ADD, PROCESS, and UNDO operations, handling edge cases like empty queues/stacks?
  • Data Structure Choice: Appropriate use of Stacks and Queues to manage pending and processed tasks.
  • Time and Space Complexity: Efficiency of the solution, aiming for optimal performance (e.g., O(1) per operation).
  • Code Readability & Maintainability: Clarity of code, variable naming, and overall structure.

Loading editor...