LLD Series: DSA and Java Basics for LLD Interviews: A Gentle Primer for Beginners

Overview

• 1. Who this is for
• 2. Big-O in five minutes
• 3. The eight structures you will actually use
• 4. Concurrency 101 (the part LLD interviews love)
• 5. Money rule: never use double
• 6. How to read a class diagram
• 7. The 60-minute plan you should follow in every round
• 8. What to read next

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Who this is for

You are a working software developer, but data structures and algorithms (DSA) were never your strongest area. Good news: LLD (low-level design) rounds need far less DSA than coding rounds. You need about eight structures, a feel for Big-O, and a clear idea of what happens when two threads touch the same data. That is this whole post.

Any dotted-underline word in this series is a hover-hint from the glossary. Click it, or open the Glossary page and search, for the plain-English meaning (QPS, L4, L7, CAS, TTL and so on).

2. Big-O in five minutes

Big-O answers one question: if my input becomes 1000 times bigger, how much slower does my code get?

Rule of thumb: for n = 1,000,000, O(log n) is about 20 steps, O(n) is a million, O(n^2) is a trillion (too slow). In interviews you simply say "this lookup is O(1) because it is a hash map" or "this is O(log n) because it is a heap".

3. The eight structures you will actually use

3.1 HashMap and HashSet (the workhorse)

A hash map stores key to value pairs. A hash function turns the key into a bucket number, so get/put are O(1) on average. A hash set is the same but stores only keys, perfect for "have I seen this before?".

Used in the series for: active tickets by id (parking lot), idempotency keys (wallet, gateway), cache lookup (LRU), balances per user (Splitwise).

3.2 Queue and Stack

A queue is a line (first in, first out). A stack is a pile of plates (last in, first out). In Java use ArrayDeque for both.

Used for: request queues, undo, elevator requests, notification queues.

3.3 Heap (PriorityQueue)

A heap always hands you the smallest (or largest) item quickly: peek is O(1), insert/remove O(log n). Java's PriorityQueue is a heap.

Used for: "settle the biggest debtor with the biggest creditor" (Splitwise simplify debts), scheduling, top-k.

3.4 TreeMap and skip list (sorted structures)

Keep keys in sorted order and answer "what is the next key greater than x?" in O(log n). ConcurrentSkipListSet is a sorted set that many threads can use safely.

Used for: the nearest free parking spot, elevator stops above/below the current floor.

3.5 Doubly linked list

Nodes that point both ways. If you already hold a node you can remove it in O(1). Combine it with a HashMap and you have an LRU cache: the map finds the node, the list reorders it.

3.6 Greedy, DP and graphs (just enough)

• Greedy: always pick the best-looking choice now (largest note first for ATM cash). Fast, but not always optimal; say so out loud.
• Dynamic programming (DP): remember answers to small sub-problems so you never recompute them. The safe fallback when greedy fails (change-making with limited coins).
• Graph: things (nodes) connected by links (edges). BFS/DFS are two ways to walk it. Barely needed here except as vocabulary.

3.7 See them run

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class Primer {
    public static void main(String[] args) throws Exception {
        // 1. HashMap: count words, O(1) per update on average
        Map<String, Integer> counts = new HashMap<>();
        for (String w : "to be or not to be".split(" ")) counts.merge(w, 1, Integer::sum);
        System.out.println("HashMap counts: " + new TreeMap<>(counts));

        // 2. HashSet: remove duplicates / "have I seen this?"
        Set<String> seen = new HashSet<>();
        System.out.println("first add: " + seen.add("KA01") + ", second add: " + seen.add("KA01"));

        // 3. Queue (FIFO) and Stack (LIFO)
        Deque<Integer> queue = new ArrayDeque<>(List.of(1, 2, 3));
        System.out.println("queue poll (oldest): " + queue.pollFirst());
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1); stack.push(2); stack.push(3);
        System.out.println("stack pop (newest): " + stack.pop());

        // 4. Heap / PriorityQueue: always gives the biggest debt first
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.addAll(List.of(30, 90, 10, 60));
        System.out.println("max-heap poll order: " + maxHeap.poll() + ", " + maxHeap.poll());

        // 5. TreeMap: sorted keys, "give me the next key >= x"
        TreeMap<Integer, String> floors = new TreeMap<>(Map.of(1, "lobby", 5, "cafe", 9, "gym"));
        System.out.println("first floor >= 4: " + floors.ceilingKey(4));

        // 6. A race condition, and its fix
        int[] unsafe = {0};
        AtomicInteger safe = new AtomicInteger();
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) fs.add(pool.submit(() -> {
            for (int i = 0; i < 100_000; i++) { unsafe[0]++; safe.incrementAndGet(); }
        }));
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        System.out.println("expected 800000 | unsafe counter lost updates: " + (unsafe[0] < 800_000) + " | atomic counter: " + safe.get());

        // 7. Money: why double is dangerous
        System.out.println("0.1 + 0.2 as double = " + (0.1 + 0.2));
        long paise = 10 + 20;
        System.out.println("10 paise + 20 paise as long = " + paise);
    }
}

Output:

HashMap counts: {be=2, not=1, or=1, to=2}
first add: true, second add: false
queue poll (oldest): 1
stack pop (newest): 3
max-heap poll order: 90, 60
first floor >= 4: 5
expected 800000 | unsafe counter lost updates: true | atomic counter: 800000
0.1 + 0.2 as double = 0.30000000000000004
10 paise + 20 paise as long = 30

4. Concurrency 101 (the part LLD interviews love)

A thread is one running path of code. Real servers run thousands at once. Trouble starts when two threads read-modify-write the same variable: both read 5, both write 6, one update vanishes. That is a race condition. In the program above the plain int counter loses updates while the AtomicInteger does not.

Your toolbox, from simplest to most advanced:

1. Immutable objects: if nothing can change, nothing can race. Prefer them.
2. synchronized / ReentrantLock: one thread at a time in a critical section. Simple and correct; can be slow if the lock is too big. Choosing how big the lock is = lock granularity.
3. Concurrent collections (ConcurrentHashMap, ConcurrentSkipListSet): ready-made thread-safe structures with atomic operations like putIfAbsent.
4. Atomics and CAS: "change the value only if it is still what I last saw". No locking, retry on failure.
5. Ordered locking: when you need two locks (transfer A to B), always take them in the same order (say by id) to avoid deadlock.

Golden rules used throughout the series:

• Check-then-act must be ONE atomic step (check balance and debit together).
• Never call slow or foreign code (network, SMS, listeners) while holding a lock.
• Always say why you chose your lock size.

5. Money rule: never use double

0.1 + 0.2 is 0.30000000000000004 in floating point. Store money as an integer number of the smallest unit (paise) in a long, or use BigDecimal. Every design in this series does that.

6. How to read a class diagram

 +----------------+   has many    +-------------+
 |    Floor       |-------------->| ParkingSpot |
 +----------------+               +-------------+
         ^
         | implements          <<interface>> = a contract, no code
 +----------------+
 | SomeStrategy   |
 +----------------+

• A box is a class; <<interface>> is a contract.
• Plain arrow = "uses / has"; hollow arrow up = "implements / extends".
• Do not obsess about UML syntax. Boxes, arrows and clear names are enough.

7. The 60-minute plan you should follow in every round

8. What to read next

Start with the OOP and SOLID post, then the design patterns post, then the concurrency post. After that pick any design, beginning with the Parking Lot. See the series index post for the full list.