Frontend School

Category Spending Tracker

DSA
hard

Category Spending Tracker

Hard
Heap
Priority Queue
Map
Data Structure Design
Financial

Overview

Intuit's financial products help millions manage their money. A core feature for many users is understanding where their money goes. One common requirement is to identify top spending categories over time. This problem challenges you to design a system that dynamically tracks spending across categories, allowing transactions to be added, updated, or voided, and efficiently provides the top K spending categories at any given moment.

What you need to do / Task

You are tasked with implementing a CategorySpendingTracker class that supports the following operations:

  1. constructor(k: number): Initializes the tracker with a specified k, representing the maximum number of top spending categories to retrieve.
  2. recordTransaction(transactionId: string, category: string, amount: number): Records a financial transaction. If transactionId already exists, it implies an update to an existing transaction (its category or amount might change). If it's a new transactionId, it's added.
  3. voidTransaction(transactionId: string): Removes a previously recorded transaction identified by transactionId. If the transactionId does not exist, this operation should do nothing.
  4. getTopKCategories(): string[]: Returns a list of strings, representing the k categories with the highest total spending. The categories should be ordered by their total spending in descending order. If fewer than k categories have positive spending, return all such categories.

Input & output

Class: CategorySpendingTracker

constructor(k: number)

  • k: An integer representing the maximum number of top categories to return.

recordTransaction(transactionId: string, category: string, amount: number)

  • transactionId: A unique string identifier for the transaction.
  • category: A string representing the spending category (e.g., "Groceries", "Rent").
  • amount: A number representing the transaction amount. Always positive.
  • Returns: void

voidTransaction(transactionId: string)

  • transactionId: The unique string identifier of the transaction to be removed.
  • Returns: void

getTopKCategories(): string[]

  • Returns: An array of strings, where each string is a category name. The categories are sorted by total spending in descending order. If two categories have the same total spending, their relative order does not matter.

Clarifications

  • All amount values will be positive integers.
  • Category names are case-sensitive strings.
  • transactionId values are unique string identifiers.
  • If getTopKCategories() is called and there are no recorded transactions with positive spending, an empty array should be returned.
  • Categories with zero or negative total spending should not be included in the getTopKCategories() result.

Examples

1

Example 1

Input:

operations = ["CategorySpendingTracker","recordTransaction","recordTransaction","recordTransaction","getTopKCategories","recordTransaction","getTopKCategories"], params = [[2],["t1","Groceries",100],["t2","Rent",1000],["t3","Utilities",50],[],["t4","Groceries",200],[]]

Output:

[null,null,null,null,["Rent","Groceries"],null,["Rent","Groceries"]]

Note:

  1. Tracker initialized with k=2.
  2. "t1" (Groceries, 100) recorded. Category totals: {Groceries: 100}.
  3. "t2" (Rent, 1000) recorded. Category totals: {Groceries: 100, Rent: 1000}.
  4. "t3" (Utilities, 50) recorded. Category totals: {Groceries: 100, Rent: 1000, Utilities: 50}.
  5. getTopKCategories() returns ["Rent", "Groceries"] as Rent (1000) and Groceries (100) are the top 2.
  6. "t4" (Groceries, 200) recorded. This is a new transaction, adding to Groceries. Category totals: {Groceries: 300, Rent: 1000, Utilities: 50}.
  7. getTopKCategories() returns ["Rent", "Groceries"] as Rent (1000) and Groceries (300) are now the top 2.
2

Example 2

Input:

operations = ["CategorySpendingTracker","recordTransaction","recordTransaction","recordTransaction","getTopKCategories","voidTransaction","getTopKCategories"], params = [[1],["txA","Food",500],["txB","Transport",200],["txC","Food",100],[],["txA"],[]]

Output:

[null,null,null,null,["Food"],null,["Transport"]]

Note:

  1. Tracker initialized with k=1.
  2. "txA" (Food, 500) recorded. Category totals: {Food: 500}.
  3. "txB" (Transport, 200) recorded. Category totals: {Food: 500, Transport: 200}.
  4. "txC" (Food, 100) recorded. Category totals: {Food: 600, Transport: 200}.
  5. getTopKCategories() returns ["Food"] (600).
  6. "txA" voided. Category totals: {Food: 100 (600-500), Transport: 200}.
  7. getTopKCategories() returns ["Transport"] (200), as Food is now only 100.
3

Example 3

Input:

operations = ["CategorySpendingTracker","recordTransaction","recordTransaction","getTopKCategories","recordTransaction","getTopKCategories"], params = [[2],["id1","Books",50],["id2","Food",150],[],["id1","Books",200],[]]

Output:

[null,null,null,["Food","Books"],null,["Books","Food"]]

Note:

  1. Tracker initialized with k=2.
  2. "id1" (Books, 50) recorded. Category totals: {Books: 50}.
  3. "id2" (Food, 150) recorded. Category totals: {Books: 50, Food: 150}.
  4. getTopKCategories() returns ["Food", "Books"].
  5. "id1" updated to (Books, 200). Old "id1" (Books, 50) is effectively removed, and new "id1" (Books, 200) is added. Category totals: {Books: (50-50)+200 = 200, Food: 150}.
  6. getTopKCategories() returns ["Books", "Food"].

Constraints

Constraints & assumptions

  • 1 <= k <= 1000
  • 1 <= transactionId.length, category.length <= 50
  • 1 <= amount <= 10^9
  • Total number of recordTransaction calls will not exceed 10^5.
  • Total number of voidTransaction calls will not exceed 10^5.
  • Total number of getTopKCategories calls will not exceed 10^4.
  • The sum of amounts for any single category will fit within a standard 64-bit integer type (e.g., JavaScript number is sufficient).

What interviewers evaluate

  • Correctness: Does the solution correctly handle all operations, including updates and removals, and produce the accurate top K categories?
  • Efficiency: Is the chosen approach performant enough to handle the given constraints, particularly for frequent updates and queries? (Hint: Think about O(log N) or O(K log N) for queries/updates).
  • Data Structure Selection: Appropriate use of data structures (e.g., Maps, Priority Queues) to manage transaction details, category sums, and top K elements.
  • Code Quality: Clean, readable, and well-organized code with proper error handling/edge case consideration.

Loading editor...