Zettabyte·Frontend Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Zettabyte is a GPU cloud company and they threw a pretty involved memory allocator problem at me for a frontend role, which I did not see coming. The problem had real depth to it and the data structure discussion went longer than I expected.

Questions Asked (1)

Design a GPU slot allocator with N slots (indexed 0 to N-1). Implement allocate(customerId, count) using best-fit strategy, release(customerId) with adjacent block merging, and getUsage() returning a map of customer slot counts.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This was way more involved than I expected for a frontend screen.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then outline a data structure that supports efficient best-fit allocation and adjacent block merging. Explain the algorithms for allocate, release, and getUsage, and discuss trade-offs between time and space complexity. Finally, walk through an example to demonstrate correctness.

Pro tip: Mention that best-fit can be implemented with a balanced BST or segment tree to achieve O(log N) allocation, and that merging adjacent free blocks is crucial to prevent fragmentation. Also, note that getUsage can be maintained incrementally to avoid O(N) scans.

1. Clarify requirements and constraints

Ask about expected number of slots, frequency of operations, and whether allocations can be split or must be contiguous. Confirm that release frees all slots for a customer and that merging is required.

2. Choose data structures

Propose a data structure for free blocks (e.g., balanced BST keyed by start index or size) and a map from customerId to allocated blocks. Consider a segment tree for efficient best-fit queries.

3. Design allocate algorithm

Describe how to find the smallest free block that fits the requested count using best-fit. If found, split the block if larger, update free blocks and customer allocation, and update usage.

4. Design release and merge algorithm

Explain how to free all blocks for a customer, then merge adjacent free blocks to combat fragmentation. Update the free block structure and usage map accordingly.

5. Analyze complexity and trade-offs

Discuss time and space complexity of each operation, and compare best-fit with first-fit or worst-fit. Mention potential optimizations like lazy merging or using a doubly linked list for free blocks.

Key Points to Mention

Best-fit strategy: choose the smallest free block that fits to minimize wasted space.
Data structures: balanced BST or segment tree for free blocks to achieve O(log N) allocation.
Adjacent block merging: coalesce free blocks on release to reduce fragmentation.
getUsage: maintain a map of customerId to total allocated slots, updated on allocate and release.
Edge cases: allocation failure when no block fits, releasing non-existent customer, and handling zero-count allocations.
Trade-offs: best-fit vs first-fit in terms of fragmentation and speed; overhead of maintaining sorted free blocks.

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