← Google Interview Insights

Google·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say
Jul 2026

Summary

Google SWE design round focused entirely on a single data structure problem. The question sounds simple but the follow-up on concurrency is where things get real.

Questions Asked (2)

Q1

Design a data structure called FancySet that supports add, delete, and getRandom, all in amortized O(1) time. What happens when getRandom is called on an empty set, and how do you handle edge cases like deleting the last element or repeated inserts?

Algorithms & Data StructuresSystem Design
Author's notes

The core trick is pairing a hashmap with a dynamic array.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a dynamic array to store elements and a hash map to track each element's index, enabling O(1) add, delete, and getRandom. For delete, swap the target element with the last element, update the hash map, and pop the last element. For getRandom, return a random element from the array, handling the empty set case by throwing an exception or returning a sentinel.

Pro tip: Clarify upfront that elements are unique and that getRandom on an empty set should throw an exception (e.g., IllegalStateException) to avoid ambiguity. Mention that this design is the same as LeetCode 380 (Insert Delete GetRandom O(1)), showing familiarity with common problems.

1. Clarify requirements and edge cases

Ask if elements are unique, what getRandom should do on an empty set, and whether duplicates are allowed. Confirm that all operations must be amortized O(1).

2. Choose data structures

Select a dynamic array (e.g., ArrayList in Java, list in Python) for O(1) random access and a hash map for O(1) index lookup. Explain why this combination works.

3. Implement add and delete

For add, append to the array and record the index in the map. For delete, swap the element with the last element, update the map for the swapped element, remove the last element, and delete the entry from the map.

4. Implement getRandom and handle edge cases

For getRandom, generate a random index and return the element at that index. If the set is empty, throw an exception or return a sentinel. Handle deleting the last element by ensuring the swap logic works when the element is already at the end.

5. Analyze complexity and discuss trade-offs

Explain that all operations are amortized O(1) due to array resizing and hash map operations. Mention that space complexity is O(n). Discuss potential issues like hash collisions and resizing overhead.

Key Points to Mention

  • Use a dynamic array for O(1) random access and a hash map for O(1) index lookup.
  • For delete, swap the target with the last element, update the map, and pop the last element.
  • Handle empty set in getRandom by throwing an exception (e.g., IllegalStateException) or returning a sentinel.
  • Ensure repeated inserts are handled by checking if the element already exists (if uniqueness required).
  • Deleting the last element works seamlessly with the swap logic; no special case needed if implemented correctly.
  • Amortized O(1) is achieved because array resizing happens infrequently and hash map operations are constant time on average.

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

Q2

How would you make FancySet thread-safe under concurrent access? Walk through at least two different locking strategies and discuss the trade-offs between them.

System DesignTechnical Trade-offs
Author's notes

Knew this was coming but still felt a little underprepared.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints of FancySet, then present two locking strategies (e.g., coarse-grained and fine-grained) with clear trade-offs. Conclude by discussing how to choose based on expected workload and scalability needs.

Pro tip: Mention that thread-safety is not just about locks—consider lock-free approaches and the impact on performance, but always tie back to the specific use case and Google's scale.

1. Clarify Requirements

Ask about the expected operations, concurrency level, and performance goals to tailor your answer.

2. Strategy 1: Coarse-Grained Locking

Describe using a single lock for the entire set, ensuring simplicity but limiting concurrency.

3. Strategy 2: Fine-Grained Locking

Explain partitioning the set (e.g., by buckets) with separate locks, increasing concurrency but adding complexity.

4. Trade-offs Analysis

Compare the strategies on performance, scalability, complexity, and potential for contention.

5. Recommendation and Extensions

Suggest the best approach for the given context and mention alternatives like read-write locks or lock-free structures.

Key Points to Mention

  • Coarse-grained locking: simplicity vs. contention bottleneck
  • Fine-grained locking: concurrency vs. overhead and deadlock risks
  • Read-write locks: optimizing for read-heavy workloads
  • Lock-free or optimistic concurrency: using atomic operations and CAS
  • Performance metrics: throughput, latency, and scalability
  • Real-world examples: Java's ConcurrentHashMap or Google's internal libraries

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