How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Ramp.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Ramp during technical interviews.

Track Users From Flight History | Ramp Coding Question

Track Users From Flight History

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an unsorted list of flight records. Each record contains `departure_airport`, `departure_time`, `arrival_airport`, `arrival_time`, and `user_id`. Assume: - Timestamps are ISO-8601 UTC strings. - Flights for the same user do not overlap. - A user's status at a given time is: - `unknown` before their first recorded departure, - `in_transit(departure_airport, arrival_airport)` between departure and arrival, - the airport where they most recently landed or are waiting to depart between two flights. Implement two functions: 1. `get_user_with_most_flights(flights)`: return the `user_id` with the largest number of flight records. If multiple users tie, return any one of them. 2. `get_user_locations(flights, time)`: given a timestamp, return the location or travel status of every user at that time. Your solution should handle large inputs efficiently.

Quick Answer: This question evaluates competency in processing and aggregating temporal event data, including time-interval reasoning, counting/grouping per user, and designing efficient data structures and algorithms for large datasets.

Part 1: User With Most Flights

You are given an unsorted list of flight records. Each record is a dictionary with keys 'departure_airport', 'departure_time', 'arrival_airport', 'arrival_time', and 'user_id'. Return the 'user_id' that appears in the largest number of flight records. If multiple users tie for the maximum, you may return any one of them. If the input list is empty, return None.

Constraints

0 <= len(flights) <= 200000
Each flight record contains all required keys.
user_id is a non-empty string when a record exists.
If several users have the same maximum count, any one of them is acceptable.

Examples

Input: ([{'departure_airport': 'SFO', 'departure_time': '2024-01-01T08:00:00Z', 'arrival_airport': 'LAX', 'arrival_time': '2024-01-01T09:00:00Z', 'user_id': 'u1'}, {'departure_airport': 'LAX', 'departure_time': '2024-01-01T11:00:00Z', 'arrival_airport': 'LAS', 'arrival_time': '2024-01-01T12:00:00Z', 'user_id': 'u1'}, {'departure_airport': 'SEA', 'departure_time': '2024-01-01T07:00:00Z', 'arrival_airport': 'DEN', 'arrival_time': '2024-01-01T10:00:00Z', 'user_id': 'u2'}, {'departure_airport': 'LAS', 'departure_time': '2024-01-01T13:00:00Z', 'arrival_airport': 'PHX', 'arrival_time': '2024-01-01T14:00:00Z', 'user_id': 'u1'}, {'departure_airport': 'JFK', 'departure_time': '2024-01-01T06:00:00Z', 'arrival_airport': 'BOS', 'arrival_time': '2024-01-01T08:00:00Z', 'user_id': 'u3'}, {'departure_airport': 'BOS', 'departure_time': '2024-01-01T09:00:00Z', 'arrival_airport': 'IAD', 'arrival_time': '2024-01-01T10:30:00Z', 'user_id': 'u3'}],)

Expected Output: 'u1'

Explanation: u1 has 3 flights, u3 has 2, and u2 has 1.

Input: ([{'departure_airport': 'ORD', 'departure_time': '2024-03-10T15:00:00Z', 'arrival_airport': 'ATL', 'arrival_time': '2024-03-10T17:00:00Z', 'user_id': 'solo'}],)

Expected Output: 'solo'

Explanation: With a single record, that user must be the answer.

Input: ([],)

Expected Output: None

Explanation: Edge case: no flights means there is no user to return.

Input: ([{'departure_airport': 'A', 'departure_time': '2024-05-01T01:00:00Z', 'arrival_airport': 'B', 'arrival_time': '2024-05-01T02:00:00Z', 'user_id': 'b'}, {'departure_airport': 'C', 'departure_time': '2024-05-01T03:00:00Z', 'arrival_airport': 'D', 'arrival_time': '2024-05-01T04:00:00Z', 'user_id': 'c'}, {'departure_airport': 'E', 'departure_time': '2024-05-01T05:00:00Z', 'arrival_airport': 'F', 'arrival_time': '2024-05-01T06:00:00Z', 'user_id': 'a'}, {'departure_airport': 'G', 'departure_time': '2024-05-01T07:00:00Z', 'arrival_airport': 'H', 'arrival_time': '2024-05-01T08:00:00Z', 'user_id': 'b'}, {'departure_airport': 'I', 'departure_time': '2024-05-01T09:00:00Z', 'arrival_airport': 'J', 'arrival_time': '2024-05-01T10:00:00Z', 'user_id': 'c'}, {'departure_airport': 'K', 'departure_time': '2024-05-01T11:00:00Z', 'arrival_airport': 'L', 'arrival_time': '2024-05-01T12:00:00Z', 'user_id': 'b'}, {'departure_airport': 'M', 'departure_time': '2024-05-01T13:00:00Z', 'arrival_airport': 'N', 'arrival_time': '2024-05-01T14:00:00Z', 'user_id': 'b'}],)

Expected Output: 'b'

Explanation: b appears 4 times, c appears 2 times, and a appears once.

Hints

You do not need to sort the flights. Count how many times each user_id appears.
While counting, keep track of the current best user so you only scan the list once.

Part 2: User Locations at a Given Time

You are given an unsorted list of flight records and a query timestamp. Each record is a dictionary with keys 'departure_airport', 'departure_time', 'arrival_airport', 'arrival_time', and 'user_id'. For every user that appears in the flight list, return that user's status at the given time. A user's status is: 'unknown' before their first recorded departure; ('in_transit', departure_airport, arrival_airport) when departure_time <= time < arrival_time; otherwise the airport where they most recently landed while waiting for the next flight or after their final recorded arrival. At exact arrival_time, the user is considered to be at the arrival airport.

Constraints

0 <= len(flights) <= 200000
Timestamps are normalized UTC strings in the same ISO-8601 format, so direct string comparison matches chronological order.
Flights for the same user do not overlap.
All records contain the required keys.

Examples

Input: ([{'departure_airport': 'LAX', 'departure_time': '2024-01-01T11:00:00Z', 'arrival_airport': 'LAS', 'arrival_time': '2024-01-01T12:00:00Z', 'user_id': 'u1'}, {'departure_airport': 'JFK', 'departure_time': '2024-01-01T08:15:00Z', 'arrival_airport': 'BOS', 'arrival_time': '2024-01-01T09:15:00Z', 'user_id': 'u2'}, {'departure_airport': 'SEA', 'departure_time': '2024-01-01T10:00:00Z', 'arrival_airport': 'DEN', 'arrival_time': '2024-01-01T13:00:00Z', 'user_id': 'u3'}, {'departure_airport': 'SFO', 'departure_time': '2024-01-01T08:00:00Z', 'arrival_airport': 'LAX', 'arrival_time': '2024-01-01T09:30:00Z', 'user_id': 'u1'}], '2024-01-01T10:30:00Z')

Expected Output: {'u1': 'LAX', 'u2': 'BOS', 'u3': ('in_transit', 'SEA', 'DEN')}

Explanation: u1 has landed in LAX and is waiting for the next flight, u2 has already arrived in BOS, and u3 is currently in the air.

Input: ([{'departure_airport': 'ATL', 'departure_time': '2024-02-01T08:00:00Z', 'arrival_airport': 'MIA', 'arrival_time': '2024-02-01T09:00:00Z', 'user_id': 'u1'}, {'departure_airport': 'DFW', 'departure_time': '2024-02-01T09:00:00Z', 'arrival_airport': 'ORD', 'arrival_time': '2024-02-01T10:00:00Z', 'user_id': 'u2'}], '2024-02-01T09:00:00Z')

Expected Output: {'u1': 'MIA', 'u2': ('in_transit', 'DFW', 'ORD')}

Explanation: At exact arrival time, u1 is already at MIA. At exact departure time, u2 is considered in transit.

Input: ([{'departure_airport': 'SFO', 'departure_time': '2024-04-10T12:00:00Z', 'arrival_airport': 'LAX', 'arrival_time': '2024-04-10T13:00:00Z', 'user_id': 'u1'}, {'departure_airport': 'JFK', 'departure_time': '2024-04-10T14:00:00Z', 'arrival_airport': 'BOS', 'arrival_time': '2024-04-10T15:00:00Z', 'user_id': 'u2'}], '2024-04-10T11:00:00Z')

Expected Output: {'u1': 'unknown', 'u2': 'unknown'}

Explanation: Edge case: before any recorded departure, every listed user is unknown.

Input: ([], '2024-06-01T00:00:00Z')

Expected Output: {}

Explanation: Edge case: no flights means there are no users to report.

Hints

Group flights by user_id, then sort each user's flights by departure_time.
For each user, find the last flight whose departure_time is <= query time. That one flight is enough to determine the answer.

Quick Overview

This question evaluates competency in processing and aggregating temporal event data, including time-interval reasoning, counting/grouping per user, and designing efficient data structures and algorithms for large datasets.