Frontend School

Expedited Order Queue

DSA
easy

Expedited Order Queue

Easy
Queue
Data Structures

Overview

At Razorpay, efficient and reliable processing of financial transactions and customer requests is paramount. Imagine a simplified system managing incoming customer support tickets or payment dispute resolutions. These requests typically need to be processed in the order they arrive. However, sometimes a critical request might need to be fast-tracked to the front of the queue to ensure immediate attention.

This problem challenges you to implement a basic queue-like data structure that supports standard queue operations along with a special "expedite" feature, mimicking real-world scenarios where certain high-priority tasks need to bypass the regular processing order.

What you need to do / Task

Your task is to implement a class ExpeditedOrderQueue that manages a sequence of orderIds. This class should support the following operations:

  1. constructor(): Initializes an empty queue.
  2. enqueue(orderId: number): Adds a new orderId to the back of the queue.
  3. dequeue(): number | null: Removes and returns the orderId from the front of the queue. Returns null if the queue is empty.
  4. peek(): number | null: Returns the orderId at the front of the queue without removing it. Returns null if the queue is empty.
  5. expediteOrder(orderId: number): boolean: If an orderId exists in the queue, it should be moved to the very front of the queue, becoming the next order to be dequeued. If multiple identical orderIds exist, only the first occurrence (closest to the front) should be moved. If the orderId is not found, the queue remains unchanged. This method should return true if the order was found and expedited, and false otherwise.

Input & output

The input will consist of a sequence of operations to be performed on the ExpeditedOrderQueue class.

Class: ExpeditedOrderQueue

  • constructor(): No parameters.
    • Initializes the internal queue.
  • enqueue(orderId: number):
    • orderId: An integer representing a unique order identifier.
    • Returns: void.
  • dequeue(): number | null:
    • Returns: The orderId from the front of the queue, or null if the queue is empty.
  • peek(): number | null:
    • Returns: The orderId at the front of the queue (without removing it), or null if the queue is empty.
  • expediteOrder(orderId: number): boolean:
    • orderId: The integer orderId to be moved to the front.
    • Returns: true if the orderId was found and moved, false otherwise.

Clarifications

  • All orderIds will be positive integers.
  • The queue should maintain the relative order of elements that are not expedited.
  • If expediteOrder is called with an orderId that is already at the front of the queue, it should still return true but no change in queue order is necessary.

Examples

1

Example 1

Input:

operations = ["ExpeditedOrderQueue","enqueue","enqueue","peek","dequeue","peek","dequeue","peek","dequeue"], params = [[],[101],[102],[],[],[],[],[],[]]

Output:

[null,null,null,101,101,102,102,null,null]

Note:

Initializes queue. Enqueues 101, then 102. Peeks 101. Dequeues 101. Peeks 102. Dequeues 102. Peeks null. Dequeues null.

2

Example 2

Input:

operations = ["ExpeditedOrderQueue","enqueue","enqueue","enqueue","expediteOrder","peek","dequeue","peek","dequeue","expediteOrder"], params = [[],[101],[102],[103],[102],[],[],[],[],[105]]

Output:

[null,null,null,null,true,102,102,101,101,false]

Note:

Queue: [101, 102, 103]. Expedite 102. Queue becomes [102, 101, 103]. Dequeue 102. Queue: [101, 103]. Dequeue 101. Queue: [103]. Try to expedite 105 (not found).

3

Example 3

Input:

operations = ["ExpeditedOrderQueue","enqueue","enqueue","enqueue","enqueue","expediteOrder","peek","dequeue","peek","dequeue","peek"], params = [[],[10],[20],[10],[30],[10],[],[],[],[],[]]

Output:

[null,null,null,null,null,true,10,10,20,20,30]

Note:

Queue: [10, 20, 10, 30]. Expedite 10 (first occurrence, which is already at front). Queue remains [10, 20, 10, 30]. Dequeue 10. Queue: [20, 10, 30]. Dequeue 20. Queue: [10, 30]. Peek 10.

Constraints

Constraints & assumptions

  • The number of operations will be between 1 and 1000.
  • Each orderId will be an integer between 1 and 10^9.
  • The maximum number of orders in the queue at any given time will not exceed 1000.
  • Assume orderIds are not necessarily unique when initially enqueued, but expediteOrder only targets the first occurrence.
  • You should not use built-in Queue or Deque classes if your language provides them. You are expected to implement the queue functionality yourself using basic data structures like arrays or linked lists.

Out of scope

  • Concurrency or thread safety for queue operations.
  • Advanced error handling beyond returning null or false as specified.
  • Persistence of the queue state.

What interviewers evaluate

  • Correctness: All operations, especially expediteOrder, function as specified across various scenarios.
  • Data Structure Choice: Appropriate use of underlying data structures to implement the queue efficiently.
  • Edge Case Handling: Correctly handles empty queue scenarios for dequeue, peek, and expediteOrder.
  • Code Readability & Structure: Clean, well-organized code with meaningful variable names.

Loading editor...