How to Ace a Google Coding Interview: A Complete Breakdown

import random

class RandomizedSet:
    def __init__(self):
        self.data = set()

    def insert(self, val: int) -> bool:
        if val in self.data:
            return False
        self.data.add(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.data:
            return False
        self.data.remove(val)
        return True

    def get_random(self) -> int:
        # THIS IS THE PROBLEM
        return random.choice(list(self.data))  (1)

import random
from collections import defaultdict

class RandomizedSetWithDuplicates:
    def __init__(self):
        # val -> set of indices in self.vals
        self.val_to_indices: dict[int, set[int]] = defaultdict(set)
        self.vals: list[int] = []

    def insert(self, val: int) -> bool:
        self.vals.append(val)
        self.val_to_indices[val].add(len(self.vals) - 1)
        return True                          (1)

    def remove(self, val: int) -> bool:
        if val not in self.val_to_indices or not self.val_to_indices[val]:
            return False

        # Pick any index where val lives (use pop for O(1))
        idx = next(iter(self.val_to_indices[val]))  (2)
        last_val = self.vals[-1]

        # Move last element into the vacated slot
        self.vals[idx] = last_val
        self.val_to_indices[last_val].add(idx)
        self.val_to_indices[last_val].discard(len(self.vals) - 1)  (3)

        self.val_to_indices[val].discard(idx)

        self.vals.pop()

        if not self.val_to_indices[val]:
            del self.val_to_indices[val]

        return True

    def get_random(self) -> int:
        return random.choice(self.vals)      (4)


# ----- Verification -----
rs = RandomizedSetWithDuplicates()
rs.insert(1)
rs.insert(1)
rs.insert(1)
rs.insert(2)
print("vals:", rs.vals)  # [1, 1, 1, 2]

# Simulate probability
counts = {1: 0, 2: 0}
for _ in range(10000):
    counts[rs.get_random()] += 1
print(f"1 appeared {counts[1]/100:.1f}% (expected ~75%)")
print(f"2 appeared {counts[2]/100:.1f}% (expected ~25%)")

rs.remove(1)
rs.remove(1)
rs.remove(1)
assert rs.get_random() == 2
print("Remove duplicates: OK")

vals: [1, 1, 1, 2]
1 appeared 74.8% (expected ~75%)
2 appeared 25.2% (expected ~25%)
Remove duplicates: OK

# Thread A and Thread B both call remove(val) simultaneously
idx = self.val_to_idx[val]     # Thread A reads idx = 2
# -- context switch --
# Thread B also removes val, changes the list, corrupts idx = 2
self.vals[idx] = last_val      # Thread A writes to wrong slot — CORRUPTION

import random
import threading

class ThreadSafeRandomizedSet:
    def __init__(self):
        self.val_to_idx: dict[int, int] = {}
        self.vals: list[int] = []
        self._lock = threading.Lock()          (1)

    def insert(self, val: int) -> bool:
        with self._lock:                        (2)
            if val in self.val_to_idx:
                return False
            self.vals.append(val)
            self.val_to_idx[val] = len(self.vals) - 1
            return True

    def remove(self, val: int) -> bool:
        with self._lock:
            if val not in self.val_to_idx:
                return False
            idx = self.val_to_idx[val]
            last_val = self.vals[-1]
            self.vals[idx] = last_val
            self.val_to_idx[last_val] = idx
            self.vals.pop()
            del self.val_to_idx[val]
            return True

    def get_random(self) -> int:
        with self._lock:                        (3)
            return random.choice(self.vals)


# ----- Stress test: concurrent inserts -----
rs = ThreadSafeRandomizedSet()

def insert_many(start, count):
    for i in range(start, start + count):
        rs.insert(i)

threads = [threading.Thread(target=insert_many, args=(i * 100, 100))
           for i in range(10)]
for t in threads:
    t.start()
for t in threads:
    t.join()

print(f"Inserted 1000 values concurrently. Stored: {len(rs.vals)}")
assert len(rs.vals) == 1000, "Race condition detected!"
print("Thread safety verified.")

Inserted 1000 values concurrently. Stored: 1000
Thread safety verified.

clarifying_questions = [
    "What are the input types? (int, str, float?)",
    "What's the scale? (10 ops? 10M ops?)",
    "Can inputs be duplicates / null / negative?",
    "Are all operations equally frequent, or is one dominant?",
    "What should I return on invalid input?",
]
# Ask all that are relevant. Then CONFIRM your understanding:
# "So to restate: I need to build X that does Y, optimized for Z. Correct?"

def think_aloud_template():
    # 1. Naive approach
    print("Naive: [data structure]. Insert: O(?), Remove: O(?), get_random: O(?)")

    # 2. Identify the bottleneck
    print("Bottleneck: [operation X] is O(N) because [reason]")

    # 3. State what property the optimal solution needs
    print("To fix this, I need [property]. [Data structure] provides that.")

    # 4. State the optimal approach
    print("Optimal: [data structure combination]. All ops: O(1) because [reason]")

# Trace through a minimal example manually, updating state as a comment:
# insert(1): vals=[1], map={1:0}
# insert(2): vals=[1,2], map={1:0, 2:1}
# remove(1): swap 1 with last(2), pop -> vals=[2], map={2:0}
# get_random() -> must return 2

complexity_summary = {
    "insert":     ("O(1) amortized", "O(1)"),
    "remove":     ("O(1)",           "O(1)"),
    "get_random": ("O(1)",           "O(1)"),
    "overall":    ("—",              "O(N) for N stored elements"),
}
for op, (time, space) in complexity_summary.items():
    print(f"{op:12s} | Time: {time:15s} | Space: {space}")