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

IntermediatePrefer not to say

May 2026

Summary

Google coding round, pretty focused on data structure design. One question but it had a lot of layers and the follow-up about heaps came out of nowhere.

Questions Asked (1)

Design a Bookshelf class that supports adding a book, moving a book to a different position, and deleting a book. Handle edge cases like out-of-range indices, duplicate titles, and moving a book to its current position. Then discuss how you'd swap out the underlying structure for a priority heap if ordering by some priority became a requirement.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I went straight to an array with splice and felt pretty good about it until they started poking at edge cases.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and choosing a data structure (e.g., dynamic array) that supports O(1) add, O(n) move/delete. Then walk through edge cases and how to handle them. Finally, discuss the trade-offs of switching to a priority heap, focusing on the change in operations and complexity.

Pro tip: Demonstrate awareness of real-world constraints: mention that while a heap is great for priority ordering, it doesn't support efficient arbitrary moves or deletes, so you might need a hybrid approach or a different structure like a balanced BST.

1. Clarify requirements and constraints

Ask about expected operations, frequency, and performance needs. Confirm if books are unique by title and if positions are 0-indexed.

2. Design the Bookshelf class with a dynamic array

Use a list to store books, supporting add (append), move (remove and insert), and delete (remove). Handle edge cases with checks and exceptions.

3. Address edge cases explicitly

For out-of-range indices, throw IndexOutOfBoundsException; for duplicate titles, either reject or allow based on requirements; for moving to same position, no-op.

4. Analyze time complexity and trade-offs

Discuss O(1) add, O(n) move/delete due to shifting. Mention alternative structures like linked list (O(1) move if node known) or balanced BST.

5. Discuss switching to a priority heap

Explain that a heap orders by priority, but arbitrary move/delete become inefficient (O(n) to find, O(log n) to remove). Suggest using a heap with lazy deletion or a balanced BST for full functionality.

Key Points to Mention

Choice of data structure: dynamic array vs. linked list vs. balanced BST
Edge case handling: out-of-range indices, duplicate titles, no-op moves
Time complexity of each operation in the initial design
Heap properties: O(log n) insert and extract-min/max, but no efficient arbitrary access
Trade-offs: heap is great for priority ordering but poor for positional operations
Possible hybrid solutions: heap with a hash map for quick lookups, or a balanced BST

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