Frontend School

Top K Merchant Accounts by Transaction Volume

DSA
medium

Top K Merchant Accounts by Transaction Volume

Medium
Heap
Priority Queue
Hash Map
Sorting

Overview

Razorpay processes millions of transactions daily. Identifying top-performing merchant accounts is crucial for business intelligence, fraud detection, and targeted support. This problem challenges you to efficiently find the K merchant accounts with the highest total transaction volume from a given dataset.

What you need to do / Task

  1. Implement a function that takes a list of transactions and an integer k.
  2. Each transaction object will contain a merchantId (string) and an amount (number).
  3. Calculate the total transaction volume for each unique merchant account.
  4. Return a list of merchantIds, representing the top k merchant accounts sorted by their total transaction volume in descending order. If two merchants have the same total volume, their relative order does not matter.

Input & output

  • Input:
    • transactions: An array of Transaction objects. Each Transaction object has two properties:
      • merchantId: A string representing the unique identifier of the merchant.
      • amount: A number representing the transaction amount.
    • k: An integer representing the number of top merchant accounts to retrieve.
  • Output:
    • An array of strings, where each string is a merchantId of a top k merchant. The list should be sorted in descending order of their total transaction volume.

Clarifications

  • What if k is greater than the number of unique merchants? Return all unique merchants, sorted by volume.
  • What if transactions is empty? Return an empty array.
  • Are transaction amounts always positive? Yes, assume amount is always a positive number.
  • Can merchantId be empty or null? Assume merchantId is always a non-empty string.

Examples

1

Example 1

Input:

transactions = [{"merchantId": "M1", "amount": 100}, {"merchantId": "M2", "amount": 200}, {"merchantId": "M1", "amount": 50}, {"merchantId": "M3", "amount": 300}, {"merchantId": "M2", "amount": 100}], k = 2

Output:

["M3", "M2"]

Note:

M1 total: 100 + 50 = 150 M2 total: 200 + 100 = 300 M3 total: 300 Sorted by volume: M3 (300), M2 (300), M1 (150). Top 2 are M3, M2.

2

Example 2

Input:

transactions = [{"merchantId": "A", "amount": 10}, {"merchantId": "B", "amount": 20}, {"merchantId": "C", "amount": 30}], k = 5

Output:

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

Note:

Unique merchants: A (10), B (20), C (30). Since k=5 is greater than the number of unique merchants (3), all merchants are returned, sorted by volume.

3

Example 3

Input:

transactions = [], k = 3

Output:

[]

Note:

No transactions, so no merchants to return.

Constraints

Constraints & assumptions

  • 0 <= transactions.length <= 10^5
  • 1 <= k <= 10^5
  • 1 <= amount <= 10^9
  • merchantId length: 1 <= merchantId.length <= 50
  • The number of unique merchantIds can be up to transactions.length.
  • Time complexity: Aim for O(N + M log K) where N is transactions.length and M is the number of unique merchants.
  • Space complexity: Aim for O(M + K).

Out of scope

  • Handling negative transaction amounts or invalid merchantId formats.
  • Real-time streaming updates for transaction data.

What interviewers evaluate

  • Correctness and efficiency of the algorithm, particularly the use of appropriate data structures (Hash Map for aggregation, Min-Heap for top K).
  • Clarity and structure of the code, including variable naming and handling of edge cases (e.g., empty input, k value).
  • Ability to analyze time and space complexity and justify design choices.
  • Handling of sorting requirements for the final output.

Loading editor...