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 medium 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.

Find User Airport at a Time | Ramp Coding Question

Find User Airport at a Time

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of flight records. Each record contains: - `user_id`: the traveler identifier - `departure_airport`: the airport where the flight starts - `arrival_airport`: the airport where the flight ends - `departure_time`: the flight departure time - `arrival_time`: the flight arrival time You will receive queries of the form `(user_id, query_time)`. For each query, return the airport where that user is located at `query_time`. Rules: 1. If the user is currently in the air, return an empty string `""`. 2. If the user is between two flights, return the arrival airport of the most recent completed flight. 3. If `query_time` is before the user's first recorded departure, return the departure airport of the user's first flight. 4. If `query_time` is after the user's last recorded arrival, return the arrival airport of the user's last flight. 5. Treat a user as in the air during the interval `[departure_time, arrival_time)`. At exactly `arrival_time`, the user is considered to be at the arrival airport. 6. The input flight list may contain records for multiple users and may not be sorted. Design and implement an efficient data structure or function to answer many such queries.

Quick Answer: This question evaluates the ability to model and query time-interval flight data for multiple users, testing skills in data structures, sorting and search algorithms, interval semantics, and handling temporal edge cases and performance trade-offs.

You are given a list of flight records for many users. Each flight record is a 5-tuple `(user_id, departure_airport, arrival_airport, departure_time, arrival_time)`. You are also given a list of queries, where each query is a 2-tuple `(user_id, query_time)`. For each query, return the airport where that user is located at `query_time`. Rules: 1. If the user is currently in the air, return an empty string `""`. 2. If the user is between two flights, return the arrival airport of the most recent completed flight. 3. If `query_time` is before the user's first recorded departure, return the departure airport of the user's first flight. 4. If `query_time` is after the user's last recorded arrival, return the arrival airport of the user's last flight. 5. Treat a user as in the air during the interval `[departure_time, arrival_time)`. At exactly `arrival_time`, the user is considered to be at the arrival airport. 6. The flight list may contain records for multiple users and may not be sorted. 7. If a queried user has no flight records, return `""` for that query. Implement `solution(flights, queries)` and return the answers for all queries in the same order.

Constraints

0 <= len(flights), len(queries) <= 200000
Each flight has `departure_time < arrival_time`
For the same user, flights do not overlap; after sorting by departure time, a flight's arrival time is less than or equal to the next flight's departure time
The input flight records are not guaranteed to be sorted

Examples

Input: ([('u1','LAX','JFK',15,20), ('u2','SEA','DEN',5,9), ('u1','SFO','LAX',10,12), ('u1','JFK','BOS',25,26)], [('u1',9), ('u1',10), ('u1',12), ('u1',14), ('u1',15), ('u1',20), ('u1',24), ('u1',30), ('u2',7), ('u2',9)])

Expected Output: ['SFO', '', 'LAX', 'LAX', '', 'JFK', 'JFK', 'BOS', '', 'DEN']

Explanation: After sorting u1's flights, the queries cover before the first flight, during flights, exact arrival times, between flights, and after the final flight. For u2, time 7 is in the air and time 9 is exactly at arrival.

Input: ([('a','ORD','MIA',100,130)], [('a',99), ('a',100), ('a',130), ('a',200), ('b',50)])

Expected Output: ['ORD', '', 'MIA', 'MIA', '']

Explanation: A single flight shows the boundary behavior: before departure the user is at ORD, at departure they are in the air, at arrival and after arrival they are at MIA. User b has no records, so the answer is an empty string.

Input: ([], [('x',1), ('x',10)])

Expected Output: ['', '']

Explanation: With no flight records at all, every query returns an empty string.

Hints

Group flight records by user first, then sort each user's flights by departure time.
For each query, binary search for the last flight whose departure time is less than or equal to the query time.

Quick Overview

This question evaluates the ability to model and query time-interval flight data for multiple users, testing skills in data structures, sorting and search algorithms, interval semantics, and handling temporal edge cases and performance trade-offs.