Frontend School

Dynamic Financial Event Prioritization

DSA
hard

Dynamic Financial Event Prioritization

Hard
Heap
Priority Queue
Sliding Window
Data Structures

Overview

Intuit's financial analytics platform processes a real-time stream of financial events, such as transactions, alerts, or customer interactions. To ensure timely attention to critical issues, the system needs to continuously monitor and prioritize these events. This problem focuses on maintaining a live view of the most critical events within a rolling time window, reflecting the dynamic nature of financial data.

What you need to do / Task

Your task is to implement a system that processes a sequence of financial events. For each incoming event, you must identify and return the IDs of the K most critical events that are currently active within a specified time window. An event's criticality is determined by a derived score: severity / processingCost. Higher criticality scores indicate more urgent events.

Specifically, for each event in the input list (processed sequentially by their timestamp):

  1. Calculate its criticality score (severity / processingCost).
  2. Add this new event to the pool of active events.
  3. Remove any events from the active pool whose timestamp falls outside the current rolling window. The window is defined as [current_event.timestamp - W, current_event.timestamp] (inclusive at both ends).
  4. From the remaining active events, identify the K most critical ones.
  5. Return their ids as a list. If there are fewer than K active events, return all of them. The output list for each event must be sorted first by criticality (descending), then by id (ascending) for ties.

Input & output

Input:

  • events: An array of Event objects. Each Event has the following structure:
    • id: number (a unique identifier for the event)
    • timestamp: number (the time in seconds when the event occurred; events are guaranteed to be in strictly increasing order of timestamp)
    • severity: number (an integer from 1 to 10, indicating urgency)
    • processingCost: number (a positive integer representing the effort/time to process the event)
  • K: number (the maximum number of most critical events to return)
  • W: number (the width of the rolling time window in seconds)

Output:

  • number[][]: An array of arrays. Each inner array contains the ids of the K most critical events for the corresponding input event, sorted as specified in the task.

Clarifications

  • Criticality scores can be floating-point numbers. Use standard floating-point comparisons.
  • Events arrive in chronological order of timestamp.
  • The ids are unique across all events.
  • processingCost is guaranteed to be positive, so no division by zero will occur.

Examples

1

Example 1

Input:

events = [{"id":1,"timestamp":1,"severity":5,"processingCost":1},{"id":2,"timestamp":2,"severity":10,"processingCost":2},{"id":3,"timestamp":3,"severity":3,"processingCost":1}], K = 2, W = 1

Output:

[[1],[1,2],[2]]

Note:

  1. Event 1 (ts=1): crit=5/1=5. Window [1-1,1]=[0,1]. Active: {1}. Output: [1]
  2. Event 2 (ts=2): crit=10/2=5. Window [2-1,2]=[1,2]. Active: {1,2}. Crit: 1(5), 2(5). Output: [1,2] (crit=5 for both, sort by ID)
  3. Event 3 (ts=3): crit=3/1=3. Window [3-1,3]=[2,3]. Event 1 (ts=1) expires (1 < 3-1). Active: {2,3}. Crit: 2(5), 3(3). Top 2: [2]. Output: [2]
2

Example 2

Input:

events = [{"id":10,"timestamp":10,"severity":8,"processingCost":2},{"id":20,"timestamp":12,"severity":9,"processingCost":3},{"id":30,"timestamp":15,"severity":6,"processingCost":1},{"id":40,"timestamp":16,"severity":10,"processingCost":5}], K = 2, W = 5

Output:

[[10],[10,20],[30,10],[30,20]]

Note:

  1. Event 10 (ts=10): crit=8/2=4. Window [10-5,10]=[5,10]. Active: {10}. Output: [10]
  2. Event 20 (ts=12): crit=9/3=3. Window [12-5,12]=[7,12]. Active: {10,20}. Crit: 10(4), 20(3). Output: [10,20]
  3. Event 30 (ts=15): crit=6/1=6. Window [15-5,15]=[10,15]. Active: {10,20,30}. Crit: 10(4), 20(3), 30(6). Top 2: [30,10]. Output: [30,10]
  4. Event 40 (ts=16): crit=10/5=2. Window [16-5,16]=[11,16]. Event 10 (ts=10) expires (10 < 16-5). Active: {20,30,40}. Crit: 20(3), 30(6), 40(2). Top 2: [30,20]. Output: [30,20]
3

Example 3

Input:

events = [{"id":1,"timestamp":10,"severity":10,"processingCost":1},{"id":2,"timestamp":11,"severity":5,"processingCost":1},{"id":3,"timestamp":12,"severity":10,"processingCost":2}], K = 3, W = 1

Output:

[[1],[1,2],[2,3]]

Note:

  1. Event 1 (ts=10): crit=10/1=10. Window [10-1,10]=[9,10]. Active: {1}. Output: [1]
  2. Event 2 (ts=11): crit=5/1=5. Window [11-1,11]=[10,11]. Active: {1,2}. Crit: 1(10), 2(5). Output: [1,2]
  3. Event 3 (ts=12): crit=10/2=5. Window [12-1,12]=[11,12]. Event 1 (ts=10) expires (10 < 12-1). Active: {2,3}. Crit: 2(5), 3(5). Top K=3: [2,3] (fewer than K items). Output: [2,3] (tie break by ID)

Constraints

Constraints & assumptions

  • 1 <= events.length <= 10^5 (denoted as N)
  • 1 <= K <= 100
  • 1 <= W <= 10^9
  • 1 <= event.id <= 10^9
  • 1 <= event.timestamp <= 10^9
  • 1 <= event.severity <= 10
  • 1 <= event.processingCost <= 1000
  • events are sorted by timestamp in strictly increasing order.

What interviewers evaluate

  • Correctness: Does the solution correctly identify the top K critical events within the sliding window, handling ties and sorting requirements?
  • Efficiency: Does the solution manage the sliding window and top K elements efficiently, achieving optimal time complexity for the given constraints?
  • Data Structure Usage: Appropriate and effective use of priority queues (heaps) and other data structures for managing dynamic data.
  • Code Quality: Readability, modularity, and maintainability of the code.

Loading editor...