Frontend School

Top K Impactful Service Requests

DSA
medium

Top K Impactful Service Requests

Medium
Heap
Priority Queue
Sorting
custom-comparator

Overview

Urban Company processes millions of service requests daily across various verticals. To ensure efficient resource allocation and maintain high customer satisfaction, it's crucial to identify and prioritize the most impactful requests at any given time. This problem simulates a core component of that prioritization system, challenging you to select the most critical tasks from a continuous stream of incoming requests.

What you need to do / Task

You are tasked with implementing a function that identifies the K most impactful service requests from a given list. Each request has a unique ID, a priority score, and an estimated processing time. The "impact" of a request is determined by the following criteria, in descending order of importance:

  1. Higher priority_score: A request with a higher priority score is inherently more impactful.
  2. Lower estimated_processing_time: If priority scores are equal, a request with a lower estimated processing time is considered more impactful (as it frees up resources faster).
  3. Lower request_id: If both priority scores and estimated processing times are equal, a request with a lower request_id is considered more impactful. This serves as a deterministic tie-breaker.

Your function should process a list of ServiceRequest objects and return the request_ids of the K most impactful requests.

Input & output

Input:

  • requests: An array of ServiceRequest objects. Each ServiceRequest object has the following structure:
    • id: number (unique identifier for the request)
    • priority: number (priority score, higher is more urgent)
    • processingTime: number (estimated time in minutes)
  • K: number The number of most impactful requests to identify.

Output:

  • An array of numbers, representing the request_ids of the K most impactful requests. The request_ids in the output array should be sorted in descending order of impact (most impactful first). If two requests have the same impact, their request_ids should be sorted in ascending order. If fewer than K requests are available, return all available request_ids sorted by impact.

Clarifications

  • An empty requests array should result in an empty output array.
  • K will always be a positive integer.
  • All request_ids, priority scores, and processingTime values will be non-negative integers. request_ids are guaranteed to be unique.

Examples

1

Example 1

Input:

requests = [ { id: 101, priority: 5, processingTime: 20 }, { id: 102, priority: 8, processingTime: 15 }, { id: 103, priority: 5, processingTime: 10 }, { id: 104, priority: 3, processingTime: 30 } ], K = 2

Output:

[102,103]

Note:

Requests by impact: (102, 8, 15) > (103, 5, 10) > (101, 5, 20) > (104, 3, 30). (102, 8, 15) has highest priority (8). (103, 5, 10) and (101, 5, 20) have same priority (5). (103, 5, 10) has lower processing time (10 vs 20), so it's more impactful. (104, 3, 30) has lowest priority. The top 2 are 102 and 103, sorted by impact.

2

Example 2

Input:

requests = [ { id: 1, priority: 10, processingTime: 50 }, { id: 2, priority: 10, processingTime: 20 }, { id: 3, priority: 10, processingTime: 40 } ], K = 2

Output:

[2,3]

Note:

All requests have the same priority (10). (2, 10, 20) has the lowest processing time (20). (3, 10, 40) has the next lowest processing time (40). (1, 10, 50) has the highest processing time (50). The top 2 are 2 and 3, sorted by impact (lower processing time first).

3

Example 3

Input:

requests = [ { id: 500, priority: 7, processingTime: 100 }, { id: 600, priority: 7, processingTime: 100 }, { id: 400, priority: 7, processingTime: 100 } ], K = 2

Output:

[400,500]

Note:

All requests have the same priority (7) and processing time (100). Tie-breaking by request_id: lower ID is more impactful. (400, 7, 100) is more impactful than (500, 7, 100), which is more impactful than (600, 7, 100). The top 2 are 400 and 500, sorted by impact.

Constraints

Constraints & assumptions

  • 0 <= requests.length <= 10^5
  • 1 <= K (if requests.length is 0, then K effectively means 0, resulting in an empty output. If requests.length > 0, then K will not exceed requests.length).
  • 1 <= request.id <= 10^9
  • 1 <= request.priority <= 100
  • 1 <= request.processingTime <= 1000
  • Time complexity: Aim for O(N log K), where N is the number of requests.
  • Space complexity: Aim for O(K).

Out of scope

  • Handling concurrent updates to the requests list.
  • Persistence of requests across system restarts.
  • Network latency or distributed system concerns.

What interviewers evaluate

  • Correctness of algorithm: The solution must correctly identify the K most impactful requests based on the specified criteria.
  • Efficient use of data structures: Demonstrating appropriate use of heaps/priority queues to achieve optimal time and space complexity.
  • Code clarity and organization: Well-structured, readable code with meaningful variable names and comments where necessary.
  • Handling edge cases: Correctly addressing scenarios like an empty input list, K being larger than the number of requests, or all requests having identical impact.

Loading editor...