Solve Four Interview Coding Problems

Part 1: Itinerary Reconstruction

Given a list of flight tickets represented as [from, to] pairs, reconstruct an itinerary that uses every ticket exactly once. If multiple valid itineraries exist, return the one that is lexicographically smallest. If no such itinerary exists, return an empty list.

def find_itinerary(tickets: list[list[str]]) -> list[str]

Part 2: Time-Sorted Search

Design a class to store values associated with timestamps. The class must support put(key, value, timestamp) and get(key, timestamp), where get returns the value for a key at or immediately before the given timestamp.

class TimeMap: ...

Part 3: Ray Grid Traversal

Given an N x M grid where each cell is either 0 (empty) or 1 (block), a ray starts at (r, c) moving in direction (dr, dc). When it hits a 1, it reflects 90 degrees clockwise. Return the path of the ray as a list of coordinates until it enters an infinite loop or exits the grid.

Part 4: High-Performance Leaderboard

Design a system to track scores for players. Support:

• update_score(player_id, score): Update a player's score.
• top_k(k): Return the IDs of the top K players.
• Assume N=1,000,000 players and high write frequency.

Examples

Part 2: tm.put('foo', 'bar', 1) tm.get('foo', 3) -> returns 'bar' tm.get('foo', 0) -> returns None

Constraints

• Part 1: Tickets length up to 10,000.
• Part 2: Timestamps are strictly increasing for each key.
• Part 4: top_k must be optimized for sub-linear time complexity.