Google SDE VO (September), Two Rounds: Kth Largest in a Stream + Top K from Massive Data + Longest Consecutive Sequence

Overview

Google's interviews are challenging. The pace was fast with no wasted time, and it really tested coding fundamentals and thinking on your feet.

Round 1: Behavioral + coding

Behavioral

1. Tell me about a time you disagreed with a teammate on a technical decision. How did you resolve it?
2. Describe a project where your initial plan failed. What did you learn and how did you pivot?
3. Tell me about a time you proactively improved an existing system or process. What impact did you make?

Coding: Kth largest element in a stream

Implement a class whose constructor takes k and an initial array nums, and whose add(val) adds a value and returns the current kth largest element.

Approach: keep a min-heap of size K holding the K largest numbers; its top is the kth largest. Push on init and on add, and pop the top whenever the size exceeds K.

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k, self.heap = k, []
        for x in nums:
            self.add(x)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

Complexity: O(n log K) to initialize, O(log K) per add.

Round 2: Pure coding

Q1: The K closest pairs from massive data

Approach: a huge stream of star_id + distance records, N very large and K much smaller than N; pick the K smallest distances.

• Sorting is O(N log N), and heapifying everything is no better for massive data.
• Keep a max-heap of size K: once it's full, compare each new item with the top and replace the top if it's smaller — O(N log K).
• We also discussed edge cases: K = 0, K > N, duplicate distances.

import heapq

def k_closest_stars(stars, k):
    """stars: iterable of (star_id, distance); returns the k closest, sorted by distance"""
    if k <= 0:
        return []
    heap = []                          # max-heap of (-distance, star_id)
    for sid, dist in stars:
        if len(heap) < k:
            heapq.heappush(heap, (-dist, sid))
        elif dist < -heap[0][0]:
            heapq.heapreplace(heap, (-dist, sid))
    return [(sid, -nd) for nd, sid in sorted(heap, reverse=True)]

Q2: Longest consecutive sequence

Problem: given an array with no duplicates, return the length of the longest run of consecutive numbers. For example [100,4,200,1,3,2] returns 4.

Approach: put every number into a hash set. A number whose num - 1 isn't in the set starts a sequence; count forward from it and track the maximum — O(n) overall. We also discussed empty arrays and single elements, and all test cases passed.

def longest_consecutive(nums):
    s, best = set(nums), 0
    for x in s:
        if x - 1 not in s:             # start of a sequence
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best