Quick Overview

This question evaluates a candidate's ability to perform efficient data aggregation, use associative data structures (maps/dictionaries), and reason about time and space complexity when processing large collections of records.

Aggregate expenses by person, trip, and category

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem You are given a list of expense records. Each record has: - `employee_id` (string) - `trip_id` (string) - `category` (string, e.g., `MEAL`, `HOTEL`, `TRANSPORT`) - `amount` (integer) Implement functions to compute aggregated totals: 1) **Per-employee total** - Return total spend for each `employee_id`. 2) **Per-trip breakdown (for one employee)** - Given an `employee_id`, return total spend per `trip_id`. 3) **Per-category breakdown (for one employee)** - Given an `employee_id`, return total spend per `category`. ## Input/Output expectations - Input: an array/list of expense records. - Output: maps/dictionaries for each query type. ## Constraints - Up to 10^6 expense records. - Aim for efficient time complexity; avoid re-scanning the full list for every query.

Quick Answer: This question evaluates a candidate's ability to perform efficient data aggregation, use associative data structures (maps/dictionaries), and reason about time and space complexity when processing large collections of records.

Part 1: Aggregate Total Expenses Per Employee

You are given a list of expense records. Each record is a 4-item tuple: (employee_id, trip_id, category, amount). Compute the total amount spent by each employee across all of their expense records. If an employee appears in multiple records, sum all of their amounts together. Your solution should run efficiently for large inputs.

Constraints

  • 0 <= len(records) <= 10^6
  • Each record has exactly 4 fields: (employee_id, trip_id, category, amount)
  • employee_id, trip_id, and category are strings
  • 0 <= amount <= 10^9

Examples

Input: ([('E1', 'T1', 'MEAL', 50), ('E2', 'T2', 'HOTEL', 120), ('E1', 'T3', 'TRANSPORT', 30), ('E2', 'T2', 'MEAL', 20)],)

Expected Output: {'E1': 80, 'E2': 140}

Explanation: E1 has 50 + 30 = 80. E2 has 120 + 20 = 140.

Input: ([],)

Expected Output: {}

Explanation: Edge case: no expense records means no totals.

Hints

  1. A hash map/dictionary is a natural way to accumulate totals by employee_id.
  2. You only need to scan the records once.

Part 2: Aggregate Expenses Per Trip for One Employee

You are given a list of expense records. Each record is a 4-item tuple: (employee_id, trip_id, category, amount). Given a target employee_id, compute how much that employee spent on each trip. Only include trips that belong to the target employee. If the employee has no records, return an empty dictionary.

Constraints

  • 0 <= len(records) <= 10^6
  • Each record has exactly 4 fields: (employee_id, trip_id, category, amount)
  • employee_id, trip_id, and category are strings
  • 0 <= amount <= 10^9

Examples

Input: ([('E1', 'T1', 'MEAL', 50), ('E1', 'T1', 'HOTEL', 70), ('E1', 'T2', 'TRANSPORT', 30), ('E2', 'T1', 'MEAL', 10)], 'E1')

Expected Output: {'T1': 120, 'T2': 30}

Explanation: For E1, trip T1 has 50 + 70 = 120, and T2 has 30.

Input: ([('E2', 'T1', 'MEAL', 10)], 'E1')

Expected Output: {}

Explanation: Edge case: the target employee has no matching records.

Hints

  1. Ignore records whose employee_id does not match the target.
  2. For matching records, accumulate amounts using trip_id as the dictionary key.

Part 3: Aggregate Expenses Per Category for One Employee

You are given a list of expense records. Each record is a 4-item tuple: (employee_id, trip_id, category, amount). Given a target employee_id, compute how much that employee spent in each category. Only include categories that belong to the target employee. If the employee has no records, return an empty dictionary.

Constraints

  • 0 <= len(records) <= 10^6
  • Each record has exactly 4 fields: (employee_id, trip_id, category, amount)
  • employee_id, trip_id, and category are strings
  • 0 <= amount <= 10^9

Examples

Input: ([('E1', 'T1', 'MEAL', 50), ('E1', 'T2', 'MEAL', 20), ('E1', 'T2', 'HOTEL', 100), ('E2', 'T1', 'MEAL', 999), ('E1', 'T3', 'TRANSPORT', 30)], 'E1')

Expected Output: {'MEAL': 70, 'HOTEL': 100, 'TRANSPORT': 30}

Explanation: For E1, MEAL is 50 + 20, HOTEL is 100, and TRANSPORT is 30.

Input: ([('E2', 'T1', 'MEAL', 10)], 'E1')

Expected Output: {}

Explanation: Edge case: the target employee has no matching records.

Hints

  1. You do not need to group by trip here; only by category.
  2. A single pass with a dictionary is enough.

Loading coding console...