Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round with a classic scheduling problem. Two parts to the same question, which I didn't fully expect going in.

Questions Asked (1)

Given a list of meeting time intervals, first determine whether a single person can attend all of them without any overlap, then find the minimum number of conference rooms needed to hold all meetings simultaneously.

Algorithms & Data Structures

Author's notes

The overlap-detection part I got through fine, sort by start time and check adjacent pairs.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose sorting intervals by start time to check for overlaps. For the minimum rooms, use a min-heap to track end times of ongoing meetings, incrementing the room count when a new meeting starts before the earliest end time.

Pro tip: Mention that the problem can be solved in O(n log n) time due to sorting, and that the heap approach is optimal. Also, note that the two parts are related: if no overlaps, only one room is needed.

1. Clarify and confirm

Restate the problem to ensure understanding, ask about input format, edge cases (empty list, single meeting, back-to-back meetings), and whether intervals are inclusive/exclusive.

2. Check for overlaps

Sort intervals by start time. Iterate through and check if the current meeting's start time is less than the previous meeting's end time. If any overlap, return false; otherwise true.

3. Find minimum rooms

Sort intervals by start time. Use a min-heap to store end times of ongoing meetings. For each meeting, if the heap is not empty and the earliest end time is <= current start, pop it (room freed). Then push the current end time. The heap size at the end is the minimum rooms needed.

4. Analyze complexity

Explain that sorting takes O(n log n) and heap operations take O(n log n), so overall O(n log n) time and O(n) space.

5. Test with examples

Walk through a simple example (e.g., [[0,30],[5,10],[15,20]]) to demonstrate the algorithm and verify correctness.

Key Points to Mention

Sorting intervals by start time is crucial for both parts.
Overlap condition: current.start < previous.end (assuming non-inclusive end times).
Min-heap efficiently tracks the earliest ending meeting.
Time complexity: O(n log n) due to sorting and heap operations.
Space complexity: O(n) for the heap.
Edge cases: empty input, single meeting, meetings that touch but don't overlap.

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