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

IntermediatePrefer not to say

Jun 2026

Summary

Bloomberg SWE coding round, one meaty design-and-implement question that took up the whole session. More involved than a typical LeetCode problem since you had to think through data structure choices, edge cases, and write actual tests.

Questions Asked (1)

Build an in-memory LRU cache where each entry has a variable byte size. The cache supports get, set, delete, and resize operations. Capacity is a byte budget, not an item count. Evictions happen on insert and resize. A single entry larger than the capacity should be rejected. Aim for O(1) amortized on reads and writes, and write unit tests covering size-changing updates, eviction ordering, edge deletions, and capacity reduction.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one had a lot of moving parts and I underestimated the resize case early on.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a design using a hash map for O(1) lookups and a doubly linked list for O(1) eviction ordering, with a running total of bytes. Explain how each operation maintains the byte budget and handles edge cases like oversized entries and resizing, then outline unit tests for the specified scenarios.

Pro tip: Emphasize that the byte budget changes the eviction logic: you must evict until the total size fits, and a single entry larger than capacity must be rejected outright. Also, mention that resizing may trigger multiple evictions and that you should update the total size atomically to avoid inconsistencies.

1. Clarify requirements and constraints

Confirm that capacity is a byte budget, entries have variable sizes, and operations must be O(1) amortized. Ask about concurrency, persistence, and whether resizing can increase or decrease capacity.

2. Design data structures

Propose a hash map (key -> node) for O(1) access and a doubly linked list to track recency (most recently used at head). Maintain a running total of bytes used.

3. Define operations and eviction policy

For get: move node to head. For set: if key exists, update size and adjust total, then move to head; if new, reject if size > capacity, else insert at head and evict from tail until total <= capacity. For delete: remove node and update total. For resize: update capacity and evict from tail until total <= new capacity.

4. Handle edge cases and complexity

Discuss oversized entries, zero-size entries, resizing to smaller than current total, and deleting non-existent keys. Confirm O(1) amortized for all operations except resize which may evict multiple items.

5. Outline unit tests

List tests for size-changing updates (e.g., updating an entry to a larger size triggers evictions), eviction ordering (LRU order maintained), edge deletions (delete head, tail, only item), and capacity reduction (resize triggers evictions).

Key Points to Mention

Use a hash map for O(1) key lookup and a doubly linked list for O(1) recency updates and eviction.
Maintain a running total of bytes to avoid O(n) size calculations.
Eviction policy: remove least recently used (tail) until total size <= capacity.
Reject entries larger than capacity immediately.
Resize operation may require multiple evictions and should update capacity before evicting.
Unit tests should cover: updating an entry to a larger size, eviction order, deleting head/tail/only node, and resizing to a smaller capacity.

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