Katkat
Back

Find User Airport at a Time

RampSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently query temporal interval data for a specific user using binary search and interval manipulation.

Problem Statement

You are given a list of trips, where each trip is represented as (user_id, airport_code, start_time, end_time). A trip indicates that a user was at a specific airport_code during the inclusive time interval [start_time, end_time].

Implement a class AirportTracker that supports the following operations:

  1. __init__(self, trips): Initializes the tracker with a list of trips.
  2. get_airport(self, user_id, timestamp): Returns the airport_code where the user_id was located at a given timestamp. If the user was not at any airport at that time, return None.

Assumptions

  • A user can only be at one airport at any given time.
  • Trips for the same user do not overlap in time.
  • The number of trips can be large, so optimize for efficient query time.

Example

trips = [
    ("Alice", "JFK", 10, 20),
    ("Alice", "LAX", 30, 40),
    ("Bob", "SFO", 15, 25)
]
tracker = AirportTracker(trips)
print(tracker.get_airport("Alice", 15)) # Output: "JFK"
print(tracker.get_airport("Alice", 25)) # Output: None
print(tracker.get_airport("Bob", 20))   # Output: "SFO"

Constraints

  • start_time <= end_time.
  • user_id is a string; airport_code is a string; timestamps are integers.
  • Optimize get_airport to run faster than O(N) where N is the number of trips.

Hints

Hint 1

Group the trips by `user_id` first to reduce the search space.

Hint 2

For each user, sort their associated trips by `start_time`.

Hint 3

Use binary search (like `bisect_right`) on the sorted list of trips to locate a potential interval that covers the target timestamp.

Follow-up questions

  • How would you modify your solution if a user could be at multiple airports simultaneously?
  • What is the space complexity of your current implementation, and how would you handle a scenario where the number of trips exceeds system memory?
  • How would you handle a query if the 'timestamp' is actually a range `[t1, t2]` and you need to return all airports visited during that period?