Frontend School

Livspace Smart Delivery Dispatch

DSA
hard

Livspace Smart Delivery Dispatch

Hard
Queue
Priority Queue
Simulation
Greedy

Overview

Livspace operates a sophisticated supply chain to ensure timely delivery and installation of home interior solutions. A critical bottleneck is the central dispatch system, which sequences material deliveries and installation teams for various projects. Optimizing this sequence is crucial for client satisfaction and operational efficiency, especially when dealing with varying priorities and geographical zones.

This problem challenges you to design a dispatch algorithm that prioritizes urgent deliveries while strategically grouping tasks for the same geographical zone to minimize travel time and maximize resource utilization. Your solution will simulate the dispatch process and determine the optimal sequence of delivery requests.

What you need to do / Task

Implement the getDispatchSequence function that simulates a delivery dispatch system. Given a list of DeliveryRequest objects, your function should return an array of requestIds in the order they are dispatched.

The dispatch system operates in discrete time steps (e.g., minutes) and processes one request at a time. The selection of the next request follows these rules:

  1. Availability: At any given time t, only requests with scheduledTime <= t are eligible for dispatch.
  2. Primary Priority: Among all eligible requests, always select those with the lowest priority value (e.g., 1 is more urgent than 2).
  3. Secondary Priority: If multiple eligible requests share the same lowest priority, prefer those with the earliest scheduledTime.
  4. Tertiary Rule (Strategic Zone Grouping): If there are multiple eligible requests that satisfy both Primary and Secondary rules (i.e., they form the absolute highest-priority, earliest-scheduled group): a. If the dispatch system just finished processing a request for lastProcessedZone (i.e., lastProcessedZone is not null), and at least one of these top-tier eligible requests is also for lastProcessedZone, then the dispatcher must choose one of these zone-matching requests. If multiple such requests exist, pick the one with the earliest scheduledTime (breaking ties by requestId lexicographically if scheduledTime is also identical). b. If lastProcessedZone is null (this is the very first task) or if no such zone-matching request exists among the top-tier eligible candidates, then the dispatcher picks the eligible request with the earliest scheduledTime (breaking any remaining ties by requestId lexicographically if scheduledTime is also identical).

Once a request is dispatched, it occupies the system for its estimatedCompletionTime. The system then moves to the next time step, considering new eligible requests and the remaining ones.

Input & output

Input: requests: DeliveryRequest[] An array of DeliveryRequest objects, where each object has the following structure:

interface DeliveryRequest {
    requestId: string; // Unique identifier for the request
    priority: number;  // Priority level (1 = urgent, 2 = standard, 3 = low)
    deliveryZone: number; // Geographical delivery zone (1 to N)
    estimatedCompletionTime: number; // Time in minutes required to complete this delivery
    scheduledTime: number; // Timestamp (minutes from start) when this request becomes available
}

Output: string[] An array of requestIds, representing the sequence in which the requests are dispatched by the system.

Clarifications

  • All scheduledTime values are non-negative and can be considered timestamps from the start of the dispatch operation.
  • estimatedCompletionTime values are positive integers.
  • priority values are positive integers, with lower numbers indicating higher priority.
  • deliveryZone values are positive integers.
  • The input requests array is not necessarily sorted by scheduledTime.
  • It's possible for scheduledTime to be the same for multiple requests. In such cases, the priority rule applies. If priority and scheduledTime are identical for multiple requests, the requestId can be used for arbitrary tie-breaking (e.g., lexicographically) if the zone rule doesn't apply.

Examples

1

Example 1

Input:

requests = [ { "requestId": "A", "priority": 1, "deliveryZone": 1, "estimatedCompletionTime": 5, "scheduledTime": 0 }, { "requestId": "B", "priority": 1, "deliveryZone": 2, "estimatedCompletionTime": 5, "scheduledTime": 0 }, { "requestId": "C", "priority": 2, "deliveryZone": 1, "estimatedCompletionTime": 5, "scheduledTime": 0 }, { "requestId": "D", "priority": 1, "deliveryZone": 1, "estimatedCompletionTime": 5, "scheduledTime": 10 } ]

Output:

["A","B","D","C"]

Note:

At time 0: A, B, C are eligible. Top candidates are A (P1,Z1,ST0) and B (P1,Z2,ST0). No lastProcessedZone. Arbitrarily pick A (e.g., by requestId). Process A (5min). lastProcessedZone=1. At time 5: B, C are eligible. Top candidate is B (P1,Z2,ST0). Process B (5min). lastProcessedZone=2. At time 10: C, D are eligible. Top candidate is D (P1,Z1,ST10). Process D (5min). lastProcessedZone=1. At time 15: C is eligible. Top candidate is C (P2,Z1,ST0). Process C (5min). lastProcessedZone=1.

2

Example 2

Input:

requests = [ { "requestId": "X", "priority": 2, "deliveryZone": 5, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "Y", "priority": 1, "deliveryZone": 3, "estimatedCompletionTime": 8, "scheduledTime": 2 }, { "requestId": "Z", "priority": 2, "deliveryZone": 5, "estimatedCompletionTime": 7, "scheduledTime": 1 } ]

Output:

["X","Y","Z"]

Note:

At time 0: Only X is eligible. Process X (10min). lastProcessedZone=5. At time 10: Current time is 10. Y (ST2) and Z (ST1) become eligible. Top candidates are Y (P1,Z3,ST2) and Z (P2,Z5,ST1). Y is higher priority (P1). Process Y (8min). lastProcessedZone=3. At time 18: Current time is 18. Only Z (P2,Z5,ST1) remains eligible. Process Z (7min). lastProcessedZone=5.

3

Example 3

Input:

requests = [ { "requestId": "P1", "priority": 1, "deliveryZone": 10, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "P2", "priority": 1, "deliveryZone": 10, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "P3", "priority": 2, "deliveryZone": 10, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "Q1", "priority": 1, "deliveryZone": 20, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "Q2", "priority": 2, "deliveryZone": 20, "estimatedCompletionTime": 10, "scheduledTime": 0 } ]

Output:

["P1","P2","Q1","Q2","P3"]

Note:

At time 0: All requests are eligible. Top candidates: P1(P1,Z10,ST0), P2(P1,Z10,ST0), Q1(P1,Z20,ST0). No lastProcessedZone. Pick P1 (arbitrary tie-break among P1, P2, Q1, e.g., by requestId). Process P1 (10min). lastProcessedZone=10. At time 10: Remaining eligible: P2, P3, Q1, Q2. Top candidates: P2(P1,Z10,ST0), Q1(P1,Z20,ST0). lastProcessedZone=10. P2 matches zone. Pick P2. Process P2 (10min). lastProcessedZone=10. At time 20: Remaining eligible: P3, Q1, Q2. Top candidates: Q1(P1,Z20,ST0). Pick Q1. Process Q1 (10min). lastProcessedZone=20. At time 30: Remaining eligible: P3, Q2. Top candidates: P3(P2,Z10,ST0), Q2(P2,Z20,ST0). lastProcessedZone=20. Q2 matches zone. Pick Q2. Process Q2 (10min). lastProcessedZone=20. At time 40: Remaining eligible: P3. Top candidate: P3(P2,Z10,ST0). Pick P3. Process P3 (10min). lastProcessedZone=10.

Constraints

Constraints & assumptions

  • 1 <= requests.length <= 1000
  • requestId is unique and consists of alphanumeric characters.
  • 1 <= priority <= 5
  • 1 <= deliveryZone <= 100
  • 1 <= estimatedCompletionTime <= 600 (10 hours)
  • 0 <= scheduledTime <= 10^5 (large enough to simulate long-running operations)
  • The system always has a task to process if there are eligible tasks.
  • Assume an efficient Priority Queue implementation is available or can be quickly implemented.

Out of scope

  • Handling concurrent dispatchers or multiple assembly lines.
  • Complex routing algorithms beyond simple zone grouping.
  • Real-time system clock synchronization; scheduledTime and estimatedCompletionTime are abstract units.

What interviewers evaluate

  • Correctness: The algorithm correctly implements all dispatch rules, especially the tertiary zone grouping logic, and produces the accurate dispatch sequence.
  • Data Structure Usage: Appropriate use of queues (specifically a Priority Queue) to manage eligible requests efficiently.
  • Algorithmic Efficiency: The solution demonstrates optimal time and space complexity for the given constraints (e.g., O(N log N) where N is the number of requests).
  • Code Quality: Clean, well-structured, and readable code with clear variable names and comments where necessary.
  • Edge Cases: Handles scenarios like an empty input list, all requests having the same priority/zone, or sparse scheduledTime values.

Loading editor...