Choosing data structures, and what it costs

Part of the free Low-Level Design course on LogicWiz, in the chapter: Code that survives review. The class-diagram exercises run in the app.

Choosing data structures, and what it costs

"It works. But for every order you walk through every slot. What happens on Diwali night?"

Priya, reading a pull request

A loop inside a loop

SwiftKart has 500 delivery slots and, on a busy night, 10,000 orders. Arjun reserves a slot for each order. To find the slot, he walks the list until the id matches.

for (Order order : orders) {                     // 10,000 orders
    Slot slot = null;
    for (Slot s : slots) {                       // up to 500 slots each time
        if (s.id().equals(order.slotId())) { slot = s; break; }
    }
    slot.reserve(order);
}

In the worst case this makes 500 × 10,000, which is 5,000,000 comparisons. Here is the same job with a map, built once before the loop.

Map<String, Slot> slotById = new HashMap<>();
for (Slot s : slots) slotById.put(s.id(), s);    // 500 steps, once

for (Order order : orders) {
    slotById.get(order.slotId()).reserve(order); // one lookup per order
}

That is 500 steps to build the map and 10,000 lookups: about 10,500 steps. Both versions reserve the same slots, but one does 500 times more work.

To talk about this, we need a measure. Time complexity says how the number of steps grows when the input grows. We write it with Big O notation, such as O(n), where n is the size of the input. In plain words:

• O(1), constant. The steps do not depend on n. A map lookup takes the same steps with 10 entries or 10 million.
• O(n), linear. The steps grow in step with n. Scanning 1,000 coupons takes up to 1,000 checks, and 2,000 coupons take up to 2,000.
• O(log n), logarithmic. Each step discards half of what is left, so doubling n adds only one step. Count how often you can halve 1,000 before reaching 1: ten times. So about 10 steps cover 1,000 entries, and about 20 cover 1,000,000.
• O(n log n). An O(log n) job done n times, as in sorting. Sorting 1,000 items takes about 10,000 steps.

A loop inside a loop multiplies the two sizes, which is how we got 5,000,000. Big O describes growth, not seconds. For 20 slots any structure is fast, so choose the clearest one. It matters when n is large or the code sits inside a loop.

Choose by the question you are asking. Here are the common answers, with the costs from the Java documentation.

"On average" means hash structures rely on hash codes spreading entries evenly, as in the equality lesson. Collisions are rare, so you can plan with O(1).

Look it up and evict: HashMap and LinkedHashMap

A HashMap finds a value by its key without scanning. It promises no order when you loop over it. A HashSet answers "have I seen this id?" the same way. Keys follow the rules from the equality lesson: equal keys need equal hash codes, and a key must not change while it is in the map. A LinkedHashMap is a HashMap with a linked list through its entries that remembers an order. By default that is the order of insertion. With a flag, it is the order of last access.

That gives an LRU cache, short for least recently used. When it is full, it throws away the entry that was used longest ago. SwiftKart can use it to keep the prices of the last 1,000 products viewed.

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        super(16, 0.75f, true);              // true: order by last access
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

The three numbers in super are the starting size, the load factor (both usual defaults) and the access-order flag. After every put, the map calls removeEldestEntry. If it returns true, the eldest entry, the least recently used, is removed. With capacity 2, we put milk and eggs, read milk, then put rice. Eggs goes, and the keys are [milk, rice].

The limits matter in an interview:

• Not thread-safe. In access-order mode even get changes the structure, so two readers at once can corrupt it. Wrap it with Collections.synchronizedMap or use a lock.
• Count only. It evicts by number of entries. It cannot expire entries after 10 minutes or limit memory.
• A hidden idea. Interviewers often say "now write it without LinkedHashMap". The answer is a HashMap from key to node plus a doubly linked list. Move a node to the front on each use and drop the tail when full. Mention the shortcut, but be ready to build the real thing.

Order it, and find the next one

A customer wants a slot at 6:30 pm. A HashMap cannot answer "the nearest slot", because it has no order. A TreeMap keeps its keys sorted, so it can. We use minutes after midnight as the key, so 18:30 is 1110.

TreeMap<Integer, Slot> byStart = new TreeMap<>();
for (Slot s : slots) byStart.put(s.startMinute(), s);

byStart.ceilingEntry(1110);                    // first slot at or after 6:30 pm
byStart.floorEntry(1110);                      // last slot at or before 6:30 pm
byStart.subMap(12 * 60, true, 21 * 60, false); // slots from 12:00 up to, not including, 21:00

With slots at 8:00, 12:00, 18:00 and 21:00, ceilingEntry gives the 21:00 slot and floorEntry the 18:00 slot. Both return null when nothing qualifies, so check. Every operation is O(log n). TreeSet does the same for plain values.

A PriorityQueue hands out the next item by a rule, and SwiftKart's packers need the order with the earliest promised time. It needs to know what "earlier" means. A class can have one built-in order, written as compareTo and marked by implementing Comparable. A Comparator is a separate object that compares two items, so one class can have many orders, even if you cannot edit it. If Slot implements Comparable<Slot> by start time, a sorted structure uses that order whenever you give it no comparator.

Comparator<Order> byPromise = Comparator
    .comparingInt(Order::promisedMinute)
    .thenComparingLong(Order::placedAt);
PriorityQueue<Order> queue = new PriorityQueue<>(byPromise);

Three traps:

• Do not subtract. a.value - b.value overflows. For example, Integer.MAX_VALUE - (-1) gives −2,147,483,648, so the sign is wrong. Use Integer.compare or comparingInt.
• Add a tiebreaker. Without thenComparingLong, two orders with the same promise come out in no fixed order.
• Looping is not sorted. A queue built from 5, 1, 4, 2, 3 prints as [1, 2, 4, 5, 3]. Only poll returns items in order.

Three more structures cover most other needs. A Deque adds and removes at both ends. ArrayDeque is the usual one, and it is faster than Stack and LinkedList for these jobs. EnumMap is a map whose keys are enum values, kept in an array. HashSet holds unique items in no order, LinkedHashSet keeps insertion order, and TreeSet keeps them sorted.

Deque<String> recent = new ArrayDeque<>();     // the last 5 products viewed
recent.addFirst(sku);
if (recent.size() > 5) recent.removeLast();

EnumMap<OrderStatus, Integer> countByStatus = new EnumMap<>(OrderStatus.class);
countByStatus.merge(OrderStatus.PLACED, 1, Integer::sum);

How the choice shows in the design

A data-structure choice is a design decision. Often one structure is not enough. The packing queue must give the next order fast, and also find an order by id when a customer cancels. Two structures, one class.

public class OrderQueue {
    private final PriorityQueue<Order> queue = new PriorityQueue<>(BY_PROMISE);
    private final Map<String, Order> byId = new HashMap<>();

    public void add(Order order) {
        byId.put(order.id(), order);
        queue.add(order);
    }

    public Optional<Order> next() {
        Order order = queue.poll();
        if (order != null) byId.remove(order.id());
        return Optional.ofNullable(order);
    }

    public boolean cancel(String id) {
        Order order = byId.remove(id);
        return order != null && queue.remove(order);   // O(n)
    }
}

The map is an index: a second structure kept next to the first so one kind of lookup is fast. The price is that both must always agree. Every method updates both. Nobody outside the class touches either structure, so there is one place to keep right and one place to test. This is encapsulation doing real work.

Say the costs aloud, because interviewers ask: "next is O(log n), lookup by id is O(1), and cancel is O(n), since PriorityQueue.remove(Object) scans." If cancels are rare, that is fine. If they are common, mark the order cancelled and skip it when polling.

When you review code, look for a contains, indexOf or filter(...).findFirst() inside a loop. That is the opening mistake again. A plain ArrayList is still right when the list is small, when you only loop over it, or when position matters, such as the lines of a receipt. Do not add an index map for ten items. Add it when a lookup runs often on a large list, and say that reason aloud. Hide your structure behind methods like next(), so you can change it later without touching callers. Try it: the starter keeps orders in a plain list. Give OrderQueue a priority queue field for the next order and an index map by id.

📌 Summary: Pick the structure from the question: lookup, order, evict or next. Know the cost of each operation. When you keep two structures in sync, hide both inside one class.

What Arjun learns next

Arjun can now choose structures and defend their cost. Priya's next question is harder: how do you know the queue still works after the next change? Next: tests, and what a reviewer expects to see in them.

Check your understanding

1. For each of 20,000 orders, the code calls coupons.stream().filter(c -> c.code().equals(code)).findFirst() on a list of 5,000 coupons. What is the best fix?
2. Slots are in a TreeMap<Integer, Slot> keyed by start minute. A customer asks for the first slot that starts at or after 6:30 pm (minute 1110). Which call?
3. What does new LinkedHashMap<>(16, 0.75f, true) change, compared with the same call without the final true?
4. Arjun prints a PriorityQueue to check his comparator and sees [1, 2, 4, 5, 3]. What is true?
5. A TreeMap with 1,000,000 slots needs about 20 steps for a get. About how many steps does it need with 2,000,000 slots?