Frontend School

Find Top K Most Active Delivery Zones

DSA
easy

Find Top K Most Active Delivery Zones

Easy
Heap
Priority Queue
Sorting

Overview

As Zomato expands its delivery network, efficiently allocating resources (delivery partners, support staff) to the busiest areas is crucial. This problem simulates a core task: identifying the top k most active delivery zones based on their current active order counts. A quick and accurate way to get this information helps in real-time operational decisions.

What you need to do / Task

Your task is to implement a function findTopKActiveZones that takes a list of delivery zone data and an integer k. The function should return the k zone IDs that currently have the highest number of active orders. If multiple zones have the same active order count, their relative order among themselves in the output does not strictly matter, but all k zones must be present and the final list should be sorted by active order count in descending order.

Input & output

  • Input:

    • zoneOrders: [string, number][]: An array where each inner array [zoneId, activeOrderCount] represents a delivery zone. zoneId is a string (e.g., "ZoneA", "DLF_Phase_1"), and activeOrderCount is a non-negative integer representing the current number of active orders in that zone.
    • k: number: An integer representing the number of top active zones to retrieve.
  • Output:

    • string[]: An array of k zone IDs. These IDs should correspond to the zones with the highest activeOrderCount. The output array must be sorted in descending order of their active order counts. If k is greater than or equal to the total number of zones, return all available zone IDs, sorted by active order count descending.

Clarifications

  • Empty zoneOrders: If the input zoneOrders array is empty, the function should return an empty array.
  • k larger than total zones: If k is greater than or equal to the total number of unique zones provided in zoneOrders, return all zone IDs, sorted by their active order counts in descending order.
  • Tie-breaking: If two zones have the same active order count, their relative order in the final output array among themselves is not strict (either can come first), as long as they appear before zones with lower counts.

Examples

1

Example 1

Input:

zoneOrders = [["ZoneA", 100], ["ZoneB", 250], ["ZoneC", 50], ["ZoneD", 150]], k = 2

Output:

["ZoneB", "ZoneD"]

Note:

ZoneB has 250 active orders, and ZoneD has 150. These are the two highest counts.

2

Example 2

Input:

zoneOrders = [["X", 10], ["Y", 5], ["Z", 100], ["W", 20]], k = 1

Output:

["Z"]

Note:

ZoneZ has 100 active orders, which is the highest count.

3

Example 3

Input:

zoneOrders = [["P", 70], ["Q", 70], ["R", 30], ["S", 20]], k = 3

Output:

["P", "Q", "R"]

Note:

Zones P and Q both have 70 orders, R has 30. These are the top 3. The order of P and Q can vary.

Constraints

Constraints & assumptions

  • 1 <= zoneOrders.length <= 10^5
  • 0 <= activeOrderCount <= 10^9 for each zone.
  • 1 <= k <= 10^5
  • zoneId will consist of alphanumeric characters and underscores.
  • All zoneIds within the input zoneOrders array are guaranteed to be unique.

What interviewers evaluate

  • Correctness of the algorithm for identifying the top k elements.
  • Efficient use of appropriate data structures (e.g., Priority Queue/Heap).
  • Ability to handle edge cases, such as k being larger than the total number of zones or an empty input.
  • Code clarity, readability, and maintainability, reflecting good software engineering practices.

Loading editor...