Frontend School

FlightDelayNotificationQueue

DSA
easy

FlightDelayNotificationQueue

Easy
Queue
Data Structure Design

Overview

At Ixigo, providing timely and relevant flight information is crucial. Our flight tracking system generates numerous notifications for flight delays. To efficiently manage these and ensure users receive the most recent updates without overwhelming our infrastructure, we need a specialized buffer. This buffer will temporarily store a fixed number of the latest flight delay notifications, automatically discarding the oldest ones as new notifications arrive. This ensures we always maintain a window of the most current information.

What you need to do / Task

You are tasked with implementing a FlightDelayNotificationQueue class that simulates this buffering mechanism. Your implementation should adhere to the following specifications:

  1. constructor(capacity: number): Initializes the queue with a specified maximum capacity. This capacity determines how many notifications the buffer can hold at any given time.
  2. addNotification(notificationId: number): Adds a new notificationId to the end of the queue.
    • If the queue is currently at its maximum capacity, the oldest notification must be removed from the front of the queue before the new notification is added.
    • The new notification is always added to the end, becoming the newest.
  3. getNotifications(): Returns an array of all notificationIds currently present in the queue. The order should reflect their age, from the oldest notification at the beginning of the array to the newest at the end.
  4. getOldestNotification(): Returns the notificationId of the oldest notification currently in the queue, without removing it. Returns null if the queue is empty.
  5. getNewestNotification(): Returns the notificationId of the newest notification currently in the queue, without removing it. Returns null if the queue is empty.
  6. getSize(): Returns the current number of notifications in the queue.

Input & output

Class Name: FlightDelayNotificationQueue

Constructor:

  • capacity: number - The maximum number of notifications the queue can hold.

Methods:

  • addNotification(notificationId: number):
    • notificationId: number - The ID of the flight delay notification to add.
    • Returns: void
  • getNotifications():
    • Returns: number[] - An array of notification IDs from oldest to newest.
  • getOldestNotification():
    • Returns: number | null - The oldest notification ID, or null if the queue is empty.
  • getNewestNotification():
    • Returns: number | null - The newest notification ID, or null if the queue is empty.
  • getSize():
    • Returns: number - The current number of notifications in the queue.

Clarifications

  • An empty queue should return null for getOldestNotification() and getNewestNotification(), and an empty array for getNotifications().
  • The capacity will always be a positive integer.

Examples

1

Example 1

Input:

operations = ["FlightDelayNotificationQueue","addNotification","addNotification","addNotification","getNotifications","getOldestNotification","getNewestNotification","getSize","addNotification","getNotifications","getOldestNotification"] params = [[3],[101],[102],[103],[],[],[],[],[104],[],[]]

Output:

[null,null,null,null,[101,102,103],101,103,3,null,[102,103,104],102]

Note:

Initializes with capacity 3. Adds 101, 102, 103. Queue is [101, 102, 103]. Oldest is 101, newest is 103, size is 3. Adding 104 evicts 101. Queue becomes [102, 103, 104]. Oldest is now 102.

2

Example 2

Input:

operations = ["FlightDelayNotificationQueue","getOldestNotification","getNewestNotification","getSize","addNotification","getNotifications","addNotification","getNotifications"] params = [[1],[],[],[],[501],[],[502],[]]

Output:

[null,null,null,0,null,[501],null,[502]]

Note:

Initializes with capacity 1. Queue is empty, so oldest/newest return null, size is 0. Adds 501. Queue is [501]. Adds 502, 501 is evicted. Queue becomes [502].

3

Example 3

Input:

operations = ["FlightDelayNotificationQueue","getNotifications","getOldestNotification","getNewestNotification","getSize","addNotification","addNotification","addNotification","getNotifications","getOldestNotification","getNewestNotification","getSize"] params = [[2],[],[],[],[],[201],[202],[203],[],[],[],[]]

Output:

[null,[],null,null,0,null,null,null,[202,203],202,203,2]

Note:

Initializes with capacity 2. Empty queue returns expected values. Adds 201, 202. Queue [201, 202]. Adds 203, 201 is evicted. Queue [202, 203]. Oldest is 202, newest is 203, size is 2.

Constraints

Constraints & assumptions

  • 1 <= capacity <= 1000
  • 1 <= notificationId <= 10^9
  • The total number of operations (constructor calls + method calls) will not exceed 1000.
  • You can assume notificationIds are unique for the purpose of identifying distinct notifications, but the problem does not require unique storage (i.e., if notificationId 1 is added, then 1 is added again, it acts as a new notification pushing out the oldest if capacity is full). This simplifies it from a true LRU.
  • The system should be efficient enough for the given constraints.

What interviewers evaluate

  • Correctness: Does the class correctly implement all specified methods, handling edge cases like empty queues and full capacity?
  • Data Structure Choice: Is an appropriate data structure chosen to efficiently manage the queue operations (add, remove oldest, peek oldest/newest)?
  • Time and Space Complexity: Are the operations implemented with reasonable time and space complexity given the constraints?
  • Code Clarity and Readability: Is the code well-structured, easy to understand, and maintainable?

Loading editor...