Google Intern VO, Two Rounds: Meeting Rooms II + Convert a BST to a Sorted Circular Doubly Linked List

Overview

Two Google Intern VO rounds — not too hard overall, and both went smoothly.

Round 1: Meeting Rooms II

The interviewer was very nice. We spent 10 minutes on my resume, then went straight into the problem.

Problem: given meetings with start and end times, what's the minimum number of rooms needed to schedule them all?

Approach: a classic variant of interval merging, and a frequent question.

1. Sort meetings by start time.
2. Keep a min-heap of each room's end time.
3. For each meeting: if start >= the heap's smallest end, that room can be reused — pop it and push the new end; otherwise just push the new end.
4. The heap's final size is the answer.

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for start, end in intervals:
        if heap and start >= heap[0]:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

Time O(n log n), space O(n).

Round 2: Behavioral + BST to circular doubly linked list

This round moved quickly. The interviewer spoke fast with a noticeable accent, so I had to listen carefully, but there was nothing tricky.

Behavioral

• Mistake: tell me about a time you made a mistake. How did you fix it?
• Leadership: describe a time you took ownership and led the team to finish a task.

Coding: BST to sorted circular doubly linked list

Problem: convert a BST into a sorted circular doubly linked list in place — rewire pointers, no new nodes.

Approach: the core is in-order traversal. Recursively maintain a prev pointer to the previous node in in-order:

• When visiting the current node, set prev.right = cur and cur.left = prev.
• Record the first visited node as the head.
• After the traversal, connect the tail back to the head to close the circle.

def tree_to_doubly_list(root):
    if not root:
        return None
    head = prev = None

    def inorder(node):
        nonlocal head, prev
        if not node:
            return
        inorder(node.left)
        if prev:
            prev.right, node.left = node, prev
        else:
            head = node
        prev = node
        inorder(node.right)

    inorder(root)
    head.left, prev.right = prev, head
    return head

Time O(n), space O(h) for the recursion stack.