Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Amazon SWE interview with a pretty involved parking lot problem that had three escalating parts. The last subproblem was the one that really made me sweat.

Questions Asked (3)

Given an unsorted list of parking lot log entries in the form [carId, time, eventType], where eventType is either 'entry' or 'exit', compute the maximum number of cars simultaneously in the lot. Treat all exits at a given timestamp as happening just before any entries at that same timestamp.

Algorithms & Data Structures

Author's notes

Classic sweep line problem once you see it that way.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Extract all events into a list of (time, delta) pairs, where entry is +1 and exit is -1. Sort by time, and for ties, process exits before entries. Then sweep through the sorted events, maintaining a running count and tracking the maximum.

Pro tip: Clarify the tie-breaking rule upfront and confirm whether the lot can go negative (invalid logs). Also, mention that you can avoid sorting by using a hash map if timestamps are bounded, but sorting is generally simpler and O(n log n).

1. Parse and transform events

Convert each log entry into a tuple (time, delta), where delta = +1 for 'entry' and -1 for 'exit'.

2. Sort events with tie-breaking

Sort the list by time ascending. For equal timestamps, ensure exits (delta = -1) come before entries (delta = +1) to satisfy the problem's rule.

3. Sweep and track maximum

Initialize current_count = 0 and max_count = 0. Iterate through sorted events, add delta to current_count, and update max_count if current_count exceeds it.

4. Return result and discuss edge cases

Return max_count. Mention handling of empty input, invalid logs (e.g., exit without entry), and potential optimizations.

Key Points to Mention

Time complexity: O(n log n) due to sorting, where n is number of log entries.
Space complexity: O(n) for storing the transformed events (or O(1) extra if sorting in-place).
Tie-breaking rule: exits before entries at the same timestamp.
Sweep-line algorithm: maintain running count and update maximum.
Edge cases: empty list, all entries, all exits, negative counts (invalid logs).
Alternative: use a hash map for counting if timestamps are small integers, but sorting is more general.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Using the same parking lot logs, find all maximal time intervals during which the number of parked cars equals the maximum occupancy from the previous part. Return each interval as [startTime, endTime).

Algorithms & Data Structures

Author's notes

This tripped me up more than it should have.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, compute the maximum occupancy from the previous part (or assume it's given). Then, sweep through the sorted event times (entry/exit) to track the current occupancy, and whenever it equals the maximum, start an interval; when it drops below, close the interval. Collect all such intervals and return them as [start, end).

Pro tip: Clarify whether the logs are already sorted by time and whether the maximum occupancy is provided; if not, mention that you would compute it first. Also, handle edge cases like multiple events at the same timestamp and empty logs.

1. Understand the input and requirements

Confirm the format of the parking lot logs (e.g., list of (timestamp, car_id, action)) and whether the maximum occupancy is given or must be computed. Clarify that intervals are half-open [start, end).

2. Compute or obtain maximum occupancy

If not provided, compute the maximum occupancy by sweeping through the logs, tracking the count of parked cars. This can be done by sorting events by time and processing entries before exits at the same timestamp.

3. Sweep to find intervals

Iterate through the sorted events, maintaining the current occupancy. When occupancy becomes equal to the maximum, record the start time; when it drops below, record the end time and add the interval to the result.

4. Handle edge cases and finalize

Ensure intervals are maximal (merge adjacent intervals if needed) and handle cases where occupancy remains at maximum until the last event. Return the list of intervals.

Key Points to Mention

Sorting events by timestamp and processing entries before exits at the same time to correctly reflect occupancy.
Using a sweep line algorithm to track current occupancy and identify intervals where it equals the maximum.
Handling multiple events at the same timestamp to avoid missing or incorrectly splitting intervals.
Ensuring intervals are maximal by merging consecutive intervals where occupancy stays at maximum.
Considering edge cases: empty logs, no cars, maximum occupancy zero, and intervals that start or end at the boundaries.
Time complexity: O(n log n) due to sorting, and space complexity O(n) for storing events and intervals.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Now suppose some exit events are missing from the logs but all entry events are present. The lot has a policy that no car stays longer than 2 hours. For cars with missing exit records, the actual exit time is unknown but must satisfy entryTime < actualExitTime <= entryTime + 2. Design an algorithm to find the time interval(s) during which the parking lot could have the largest possible simultaneous occupancy, assuming exit times for cars with missing logs are chosen to maximize the peak. Return the interval(s) as [startTime, endTime).

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where things got genuinely hard.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model each car with missing exit as an interval that can extend up to 2 hours after entry, and treat known exits as fixed. Use a sweep-line algorithm with events, but for missing exits, consider them as flexible intervals that can be 'stretched' to maximize overlap. Compute the maximum possible overlap by allowing missing-exit cars to exit at the latest possible time (entry+2) to maximize peak occupancy, then identify intervals where this peak is achieved.

Pro tip: Clarify that the policy allows exit at exactly entry+2, and that maximizing peak occupancy may require aligning multiple missing-exit cars to exit at their latest times, potentially creating a plateau. Also, mention that if multiple intervals achieve the same maximum, return all.

1. Parse and categorize events

Separate cars into those with known exit times (fixed intervals) and those with missing exits (flexible intervals with entry time and max possible exit = entry+2).

2. Determine worst-case (maximizing) exit times

For each missing-exit car, set its exit time to entry+2 to maximize its duration and potential overlap with other cars.

3. Sweep-line to compute occupancy

Create events: +1 at entry, -1 at exit. Sort events by time, and sweep to compute occupancy over time. For missing-exit cars, use entry+2 as exit.

4. Find intervals of maximum occupancy

Track the maximum occupancy value during the sweep and record all time intervals where occupancy equals this maximum. Output as [start, end).

5. Handle edge cases and validate

Consider cars with zero duration (entry=exit) if allowed, and ensure intervals are half-open. Verify that the chosen exit times are valid (<= entry+2).

Key Points to Mention

Sweep-line algorithm with event sorting (O(n log n) time).
Flexible intervals: missing exits can be set to entry+2 to maximize peak.
Half-open intervals [start, end) and handling of simultaneous events.
Maximum occupancy may occur over multiple disjoint intervals.
Policy constraint: actual exit time must be > entry and <= entry+2.
Trade-off: assuming worst-case (latest exit) for missing logs gives an upper bound on peak occupancy.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.