# Java Interview Preparation Guide
### Collections, DSA, Concurrency, Design & System Design — Q&A with Code

> Java version note: examples target modern Java (LTS syntax through Java 21, forward-compatible with the Java 26 preview cycle). No Java-26-specific preview APIs are relied upon unless noted.

---

## Table of Contents

1. [Collections Framework Core](#1-collections-framework-core)
2. [Collections Coding Patterns](#2-collections-coding-patterns)
3. [Specialized Collections & Concurrency Collections](#3-specialized-collections--concurrency-collections)
4. [Interview MCQs](#4-interview-mcqs)
5. [JUnit 5 Tests](#5-junit-5-tests)
6. [Real Interview Questions (FAANG / Banks)](#6-real-interview-questions-faang--banks)
7. [Immutable Collections](#7-immutable-collections)
8. [Core DSA Topics](#8-core-dsa-topics)
9. [Concurrency & CompletableFuture](#9-concurrency--completablefuture)
10. [JVM Internals](#10-jvm-internals)
11. [Design Patterns](#11-design-patterns)
12. [Low-Level Design](#12-low-level-design)
13. [System Design](#13-system-design)
14. [Spring Boot](#14-spring-boot)
15. [Redis](#15-redis)
16. [Kafka](#16-kafka)
17. [Kubernetes](#17-kubernetes)
18. [Microservices](#18-microservices)
19. [CodeSignal Practice — Medium](#19-codesignal-practice--medium)
20. [CodeSignal Practice — Hard](#20-codesignal-practice--hard)
21. [Mock Interview Script](#21-mock-interview-script)

---

## 1. Collections Framework Core

### 1.1 ArrayList vs LinkedList

**Q: When would you choose ArrayList over LinkedList and why?**

A: `ArrayList` is backed by a resizable array, giving O(1) amortized random access (`get(i)`) and O(1) amortized append, but O(n) insert/delete in the middle (elements must shift). `LinkedList` is a doubly linked list — O(1) insert/delete once you have a node/iterator reference, but O(n) random access since it must walk from head or tail. In practice, `ArrayList` wins for almost all use cases because of CPU cache locality; `LinkedList` is rarely faster in real workloads even for insert-heavy code, since pointer chasing defeats cache prefetching. Choose `LinkedList` only when you need a `Deque` with cheap head/tail operations and don't need indexed access.

```java
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

// O(1) amortized
arrayList.add(1);
// O(n) worst case (array copy on resize), O(1) amortized append
arrayList.add(0, 99); // O(n) - shifts all elements right

// O(1) if you already hold the node (not exposed publicly in java.util.LinkedList)
linkedList.addFirst(1);
linkedList.addLast(2);
```

| Operation | ArrayList | LinkedList |
|---|---|---|
| get(i) | O(1) | O(n) |
| add(end) | O(1) amortized | O(1) |
| add(i) / remove(i) | O(n) | O(n) to find + O(1) to link |
| addFirst/removeFirst | O(n) | O(1) |
| Memory overhead | Low (contiguous array) | High (2 pointers + object header per node) |

**Follow-up: Why is LinkedList rarely used in production despite O(1) insert claims?**
A: The O(1) insert only helps if you already have a reference to the node (e.g., via a `ListIterator`). Calling `add(index, val)` still costs O(n) to traverse to that index. Combined with poor cache locality (each node is a separate heap allocation), `ArrayDeque` typically outperforms `LinkedList` even as a queue/stack.

---

### 1.2 Vector vs ArrayList

**Q: What's the difference between Vector and ArrayList, and why is Vector considered legacy?**

A: Both are array-backed, resizable lists. `Vector` is synchronized on every method (`add`, `get`, etc.), making it thread-safe but slow due to lock contention even in single-threaded use. `ArrayList` is unsynchronized — faster, but not thread-safe. `Vector` predates the Collections Framework (JDK 1.0) and grows by doubling by default like ArrayList, but its "synchronize every call" approach is coarse-grained and doesn't even guarantee compound-action atomicity (e.g., check-then-act on `size()` then `get()` can still race). Modern code prefers `ArrayList` plus explicit synchronization (`Collections.synchronizedList`) or, better, `CopyOnWriteArrayList` / `ConcurrentHashMap`-style structures for concurrent access.

```java
List<String> vector = new Vector<>();      // synchronized, legacy
List<String> arrayList = new ArrayList<>(); // unsynchronized, preferred

// Thread-safe alternative to Vector, still coarse locking:
List<String> synced = Collections.synchronizedList(new ArrayList<>());
```

**Follow-up: Is Vector deprecated?**
A: Not formally deprecated, but it's a legacy class Sun/Oracle explicitly says to avoid for new code — use `ArrayList` or concurrent collections instead.


### 1.3 HashMap Internals

**Q: Explain how HashMap works internally.**

A: `HashMap<K,V>` stores entries in an array of buckets (`Node<K,V>[] table`). The bucket index is `(n - 1) & hash`, where `n` is table length (always a power of 2) and `hash` is a spread function applied to `key.hashCode()`: `hash ^ (hash >>> 16)` — this mixes high bits into low bits to reduce collisions for poor hash functions. Each bucket is a linked list of entries; on collision, new entries are appended. Since Java 8, if a bucket's linked list grows to **8 or more** nodes *and* the table has at least 64 buckets, that bucket is treeified into a **red-black tree** (O(log n) instead of O(n) for lookups in a heavily-collided bucket). Load factor (default 0.75) times capacity determines the resize threshold; on resize, capacity doubles and every entry is rehashed into the new table.

```java
Map<String, Integer> map = new HashMap<>(); // default capacity 16, load factor 0.75
map.put("a", 1);
// index = (capacity - 1) & spread(hash("a"))

// Resize trigger: size > capacity * loadFactor => capacity doubles (16 -> 32 -> 64...)
```

**Follow-up: Why must capacity be a power of 2?**
A: So `(n - 1) & hash` is a fast, correct substitute for `hash % n`, and so bits split cleanly during resize (each old bucket splits into exactly two new buckets — `index` or `index + oldCap` — avoiding a full rehash pass in older JDKs' optimized resize path).

**Follow-up: What happens on `put` for an existing key?**
A: The value is replaced and the old value returned; the key object itself is *not* replaced (equals() match keeps the original key reference).

---

### 1.4 LinkedHashMap

**Q: How does LinkedHashMap differ from HashMap, and what's the accessOrder flag for?**

A: `LinkedHashMap` extends `HashMap` and additionally maintains a doubly linked list threading through all entries, preserving iteration order. By default it's **insertion order**; passing `accessOrder=true` to the constructor switches to **access order** (most-recently-used entries move to the end), which is exactly the building block for an LRU cache via `removeEldestEntry()`.

```java
// Insertion-order (default)
Map<String, Integer> lhm = new LinkedHashMap<>();

// Access-order LRU cache, capacity 3
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3;
    }
};
lru.put("a", 1); lru.put("b", 2); lru.put("c", 3);
lru.get("a");        // "a" becomes most-recently-used
lru.put("d", 4);      // evicts "b" (least recently used)
```

**Follow-up: What's the time/space overhead vs HashMap?**
A: Slightly more memory per entry (extra `before`/`after` pointers) and slightly slower inserts (linked-list bookkeeping), but iteration is faster and predictable-order.

---

### 1.5 TreeMap

**Q: How is TreeMap implemented and what guarantees does it give?**

A: `TreeMap` implements `NavigableMap` using a **red-black tree**, keeping keys in sorted order (natural ordering via `Comparable`, or a supplied `Comparator`). All core operations — `put`, `get`, `remove`, `containsKey` — are **O(log n)**. It provides navigation methods `floorKey`, `ceilingKey`, `higherKey`, `lowerKey`, `firstKey`, `lastKey`, and range views `headMap`/`tailMap`/`subMap`.

```java
TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(5, "five"); tm.put(1, "one"); tm.put(3, "three");
tm.firstKey();        // 1
tm.ceilingKey(2);      // 3 (smallest key >= 2)
tm.floorKey(4);        // 3 (largest key <= 4)
SortedMap<Integer,String> sub = tm.subMap(1, 5); // [1,5)
```

**Follow-up: HashMap vs TreeMap vs LinkedHashMap — when would you pick each?**
A: `HashMap` for raw speed with no ordering need (O(1) avg). `LinkedHashMap` when you need predictable iteration order (insertion or LRU access order) at near-HashMap speed. `TreeMap` when you need sorted keys or range queries, accepting O(log n) operations.

---

### 1.6 Hash Collision

**Q: What is a hash collision and how does Java's HashMap handle it? Can it be exploited?**

A: A collision occurs when two different keys hash to the same bucket index. Java handles this via **chaining** (linked list, or red-black tree once a bucket exceeds 8 entries with table size ≥ 64). Historically, hash collisions were an actual **DoS vector**: an attacker submitting many keys engineered to collide (e.g., crafted `String`s) could degrade a HashMap-backed structure (like servlet parameter maps) to O(n) per operation, causing algorithmic complexity attacks. Java mitigated this with (a) the bit-spreading `hash()` function reducing the impact of poor `hashCode()` implementations, and (b) treeification, which caps worst-case bucket lookup at O(log n) even under adversarial collisions.

```java
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```

**Follow-up: How would you design a hash function to minimize collisions for custom keys?**
A: Combine all significant fields using a prime multiplier pattern (`Objects.hash(...)` or manual `31 * result + field.hashCode()`), ensure fields used in `equals()` are exactly the fields used in `hashCode()`, and avoid hashing on mutable fields for keys stored in hash-based collections.

---

### 1.7 equals() vs hashCode()

**Q: What's the contract between equals() and hashCode(), and what breaks if you violate it?**

A: The contract (from `Object`):
1. If `a.equals(b)` is true, then `a.hashCode() == b.hashCode()` **must** be true.
2. The reverse is *not* required — different objects can share a hash code (collision), that's fine.
3. `hashCode()` must be consistent across calls as long as fields used in `equals()` don't change.

If you override `equals()` but not `hashCode()` (or vice versa), hash-based collections break silently: a `HashSet.contains()` can return `false` for an "equal" object because it looks in the wrong bucket, or duplicate "equal" entries can coexist in a `HashSet`.

```java
class Point {
    int x, y;
    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }
    @Override public int hashCode() {
        return Objects.hash(x, y); // must derive from the same fields as equals()
    }
}
```

**Follow-up: Why does record class solve this cleanly?**
A: Java `record` auto-generates `equals()`, `hashCode()`, and `toString()` based on all components consistently, eliminating the manual-sync bug class entirely.

---

### 1.8 HashSet

**Q: How is HashSet implemented, and what's its relationship to HashMap?**

A: `HashSet<E>` is literally backed by a `HashMap<E, Object>` internally — every element is stored as a key, mapped to a shared dummy `PRESENT` object. So `add`, `remove`, `contains` are all O(1) average, inheriting HashMap's behavior including no ordering guarantee and reliance on correct `equals()`/`hashCode()`.

```java
Set<String> set = new HashSet<>();
set.add("x"); // internally: map.put("x", PRESENT)
set.contains("x"); // internally: map.containsKey("x")
```

**Follow-up: Does HashSet allow null?**
A: Yes, one `null` element (since it maps to `map.put(null, PRESENT)` and HashMap allows one null key).

---

### 1.9 LinkedHashSet

**Q: When would you use LinkedHashSet over HashSet?**

A: `LinkedHashSet` extends `HashSet` but is backed by a `LinkedHashMap` internally, so it preserves **insertion order** while still giving O(1) average `add`/`contains`/`remove`. Use it when you need set semantics (no duplicates) *and* predictable iteration order — e.g., deduplicating a list while preserving the first-seen order.

```java
Set<String> seen = new LinkedHashSet<>();
for (String s : List.of("b", "a", "b", "c")) seen.add(s);
// iteration order: b, a, c
```

---

### 1.10 TreeSet

**Q: How does TreeSet work and what extra capabilities does it offer over HashSet?**

A: `TreeSet<E>` is backed by a `TreeMap<E, Object>`, so elements are kept in sorted order (natural or via `Comparator`) with O(log n) operations. It implements `NavigableSet`, exposing `first()`, `last()`, `higher(e)`, `lower(e)`, `ceiling(e)`, `floor(e)`, and range views (`headSet`, `tailSet`, `subSet`).

```java
TreeSet<Integer> ts = new TreeSet<>(List.of(5, 1, 3, 9));
ts.first();      // 1
ts.higher(3);    // 5 (smallest strictly greater than 3)
ts.headSet(5);   // [1, 3]
```

**Follow-up: Can you store a custom object in TreeSet without implementing Comparable?**
A: Yes, by passing a `Comparator` to the constructor: `new TreeSet<>(Comparator.comparing(Person::getAge))`.

---

### 1.11 PriorityQueue

**Q: What data structure backs PriorityQueue, and what are its complexity characteristics?**

A: A **binary heap** (min-heap by default) stored in an array. `offer`/`add` is O(log n) (sift-up), `poll`/`remove` (removes the head, smallest element by default) is O(log n) (sift-down), `peek` is O(1). It does *not* guarantee full sorted iteration order — only that `poll()` returns elements in priority order one at a time.

```java
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // natural order, min at head
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
minHeap.poll(); // 1
```

**Follow-up: Is PriorityQueue thread-safe? What's the concurrent equivalent?**
A: No. Use `PriorityBlockingQueue` for a thread-safe unbounded blocking priority queue.

---

### 1.12 ArrayDeque

**Q: Why is ArrayDeque generally preferred over Stack and LinkedList for stack/queue use?**

A: `ArrayDeque` is a resizable circular array implementing `Deque`. It has no capacity restrictions, better cache locality than `LinkedList`, and avoids `Stack`'s legacy baggage (synchronized, extends the odd `Vector`). It's the JDK-recommended replacement for both `Stack` (use `push`/`pop`) and `LinkedList` as a `Queue`.

```java
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.pop(); // 2 (LIFO)

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2); queue.poll(); // 1 (FIFO)
```

**Follow-up: Does ArrayDeque allow null elements?**
A: No — null is used internally as a sentinel to signal "empty slot", so `add(null)` throws `NullPointerException`.

---

### 1.13 Queue vs Deque

**Q: What's the conceptual and interface difference between Queue and Deque?**

A: `Queue` supports FIFO operations at one end (`offer`/`add` at tail, `poll`/`remove` at head, `peek`). `Deque` ("double-ended queue") extends `Queue` and allows insertion/removal at **both** ends (`addFirst`/`addLast`, `removeFirst`/`removeLast`), so it can act as a `Queue`, a `Stack`, or a sliding-window buffer. Every `Deque` is-a `Queue`, but not every `Queue` implementation (e.g. `PriorityQueue`) is a `Deque`.

```java
Queue<Integer> q = new LinkedList<>();
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1); dq.addLast(2); // deque-specific
```

---

### 1.14 Comparable vs Comparator

**Q: Difference between Comparable and Comparator, and when do you use each?**

A: `Comparable<T>` is implemented **by the class itself** to define its single "natural ordering" via `compareTo()`. `Comparator<T>` is a **separate strategy object** passed to sorting methods, letting you define one or more *external*, swappable orderings without modifying the class — essential when you don't own the class, or need multiple orderings.

```java
class Employee implements Comparable<Employee> {
    int salary;
    public int compareTo(Employee o) { return Integer.compare(salary, o.salary); }
}

Comparator<Employee> byNameThenAge = Comparator
    .comparing((Employee e) -> e.name)
    .thenComparingInt(e -> e.age);

list.sort(byNameThenAge.reversed());
```

**Follow-up: Is `a.compareTo(b) == 0` required to be consistent with `a.equals(b)`?**
A: Not strictly required by the language, but strongly recommended ("consistent with equals") — otherwise sorted collections like `TreeSet`/`TreeMap` (which use `compareTo` for equality, not `equals()`) can behave surprisingly, e.g. silently dropping "unequal-by-equals but compareTo==0" elements as duplicates.

---

### 1.15 Collections.sort()

**Q: What sorting algorithm does Collections.sort() use, and what's its complexity?**

A: For object references, `Collections.sort()` (which delegates to `List.sort()` / `Arrays.sort(Object[])`) uses a variant of **TimSort** — a hybrid stable merge sort/insertion sort optimized for real-world partially-sorted data. Worst/average case O(n log n), best case O(n) for already-sorted input. It's **stable** (equal elements retain relative order), which matters for multi-key sorts (`thenComparing`). For primitive arrays, `Arrays.sort(int[])` uses a **dual-pivot Quicksort** instead (O(n log n) average, not stable, but no boxing overhead — stability doesn't matter for primitives without satellite data).

```java
List<Employee> list = ...;
Collections.sort(list); // needs Comparable
list.sort(Comparator.comparing(Employee::getSalary).reversed());
```

---

### 1.16 Binary Search

**Q: How does Collections.binarySearch / Arrays.binarySearch work, and what are the preconditions?**

A: Classic O(log n) binary search — the list/array **must already be sorted** according to the comparator used (or natural order). If not sorted, behavior is undefined. Returns the index if found; if not found, returns `-(insertion point) - 1`, letting you compute where to insert while preserving order.

```java
int[] arr = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(arr, 5); // 2
int notFound = Arrays.binarySearch(arr, 4); // -(2)-1 = -3, insertion point = 2

List<Integer> list = List.of(1, 3, 5, 7);
int i = Collections.binarySearch(list, 3); // 1
```

```java
// Manual implementation
static int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoids overflow vs (lo+hi)/2
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}
```

---

## 2. Collections Coding Patterns

### 2.1 Reverse a HashMap (swap keys and values)

**Q: Given a Map<K,V> with unique values, produce a Map<V,K>.**

```java
static <K, V> Map<V, K> reverse(Map<K, V> map) {
    Map<V, K> result = new HashMap<>();
    for (Map.Entry<K, V> e : map.entrySet()) {
        result.put(e.getValue(), e.getKey()); // last wins if values aren't unique
    }
    return result;
}

// Stream version, throws on duplicate values
static <K, V> Map<V, K> reverseStream(Map<K, V> map) {
    return map.entrySet().stream()
        .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));
}
```
**Gotcha:** if values aren't unique, information is lost — decide explicitly whether to keep first, last, or collect into `Map<V, List<K>>`.

---

### 2.2 Merge Two Maps (with conflict resolution)

```java
Map<String, Integer> m1 = new HashMap<>(Map.of("a", 1, "b", 2));
Map<String, Integer> m2 = Map.of("b", 20, "c", 3);

// sum values on key conflict
Map<String, Integer> merged = new HashMap<>(m1);
m2.forEach((k, v) -> merged.merge(k, v, Integer::sum));
// {a=1, b=22, c=3}
```
`Map.merge(key, value, remappingFn)` is the idiomatic tool: if the key is absent, it inserts `value`; if present, it applies `remappingFn(oldValue, value)`.

---

### 2.3 Frequency Counter

```java
static Map<Character, Long> charFrequency(String s) {
    return s.chars()
        .mapToObj(c -> (char) c)
        .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
}

// Manual, O(n) time, O(k) space
static Map<Character, Integer> freqManual(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    return freq;
}
```

---

### 2.4 Remove Duplicates (preserving order vs not)

```java
// Preserve first-seen order
static List<Integer> dedupeOrdered(List<Integer> nums) {
    return new ArrayList<>(new LinkedHashSet<>(nums));
}

// From a sorted array in place (classic interview Q), returns new length
static int removeDuplicatesSorted(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
        }
    }
    return slow + 1; // two-pointer, O(n) time, O(1) space
}
```

---

### 2.5 Top-K Elements

```java
// Top K frequent elements — O(n log k) using a min-heap of size k
static List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
        new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

    for (var e : freq.entrySet()) {
        minHeap.offer(e);
        if (minHeap.size() > k) minHeap.poll(); // evict smallest, keep top k
    }
    List<Integer> result = new ArrayList<>();
    while (!minHeap.isEmpty()) result.add(minHeap.poll().getKey());
    Collections.reverse(result); // largest first
    return result;
}
```
**Why a min-heap of size k, not a max-heap of size n?** Keeping only k elements bounds heap operations to O(log k), giving O(n log k) total — better than O(n log n) full sort when k << n. Alternative: **Quickselect** gives O(n) average.

---

### 2.6 LRU Cache — Three Implementations

**Implementation A: LinkedHashMap (access-order) — simplest**
```java
class LRUCacheA<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRUCacheA(int capacity) {
        super(16, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
```

**Implementation B: HashMap + manual doubly linked list — the "real" O(1) interview answer**
```java
class LRUCacheB {
    class Node { int key, val; Node prev, next; Node(int k, int v){key=k; val=v;} }
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(-1, -1), tail = new Node(-1, -1); // sentinels

    LRUCacheB(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }
    private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void insertAtFront(Node n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }
    int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n = map.get(key);
        remove(n); insertAtFront(n); // mark as most recently used
        return n.val;
    }
    void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        else if (map.size() == capacity) {
            Node lru = tail.prev;       // evict least recently used
            remove(lru); map.remove(lru.key);
        }
        Node n = new Node(key, value);
        map.put(key, n); insertAtFront(n);
    }
}
// get/put are O(1); this is what most interviewers actually want to see you derive.
```

**Implementation C: Using LinkedHashMap composition (not inheritance) — cleaner encapsulation**
```java
class LRUCacheC<K, V> {
    private final int capacity;
    private final LinkedHashMap<K, V> map;

    LRUCacheC(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true) {
            @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) {
                return size() > LRUCacheC.this.capacity;
            }
        };
    }
    V get(K key) { return map.getOrDefault(key, null); }
    void put(K key, V value) { map.put(key, value); }
}
```
**Trade-offs:** A/C are fast to write but expose (or wrap) LinkedHashMap internals and are not thread-safe. B is the canonical hand-rolled answer interviewers usually want, and generalizes to non-Java-collection environments (e.g., designing the same structure in C++). For thread safety, wrap B's methods with a single `ReentrantLock`, or use `Collections.synchronizedMap` around C.

---

## 3. Specialized Collections & Concurrency Collections

### 3.1 WeakHashMap

**Q: What problem does WeakHashMap solve?**

A: In a normal `HashMap`, keys are strongly referenced, so an entry keeps its key (and value) alive even if nothing else references the key — a classic memory-leak source for caches. `WeakHashMap` holds keys via `WeakReference`; once a key has no other strong references, the GC can reclaim it, and the entry is automatically removed (lazily, on next access) from the map. Commonly used for caches/metadata keyed by objects whose lifecycle you don't control (e.g., listener registries, class-metadata caches).

```java
Map<Object, String> cache = new WeakHashMap<>();
Object key = new Object();
cache.put(key, "metadata");
key = null; // no other strong refs
System.gc(); // entry becomes eligible for removal
```
**Gotcha:** Don't use it for a general-purpose cache expecting predictable eviction timing — GC runs are non-deterministic. For that, use a proper cache library (Caffeine) with explicit eviction policies.

---

### 3.2 IdentityHashMap

**Q: How does IdentityHashMap differ from HashMap?**

A: It uses **reference equality** (`==`) instead of `.equals()`, and `System.identityHashCode()` instead of `.hashCode()`, for both keys and values. Two distinct-but-`.equals()`-equal objects are treated as **different** keys. Used for identity-based bookkeeping, e.g., detecting cycles during object graph traversal (serialization frameworks), or when key mutability makes `.equals()` unsafe.

```java
Map<String, Integer> idMap = new IdentityHashMap<>();
String a = new String("x"), b = new String("x");
idMap.put(a, 1);
idMap.put(b, 2);
idMap.size(); // 2 — a and b are different objects even though a.equals(b)
```

---

### 3.3 EnumMap

**Q: Why use EnumMap instead of HashMap<EnumType, V>?**

A: `EnumMap` is backed internally by a simple **array** indexed by the enum constant's `ordinal()` — no hashing, no boxing of keys, extremely compact and fast (effectively O(1) with a tiny constant factor), and iterates in natural enum declaration order. Requires all keys to be from the same enum type.

```java
enum Day { MON, TUE, WED, THU, FRI, SAT, SUN }
Map<Day, String> schedule = new EnumMap<>(Day.class);
schedule.put(Day.MON, "Standup");
// iterates in MON..SUN order automatically
```

---

### 3.4 EnumSet

**Q: How is EnumSet implemented and why is it so fast?**

A: `EnumSet` is backed by a **bitvector** (a `long` for ≤64 constants — `RegularEnumSet`, or a `long[]` for more — `JumboEnumSet`). Each enum constant maps to a bit position (its ordinal). Set operations (`add`, `contains`, union, intersection) become simple bitwise operations — extremely fast, extremely compact memory footprint.

```java
enum Permission { READ, WRITE, EXECUTE, DELETE }
EnumSet<Permission> perms = EnumSet.of(Permission.READ, Permission.WRITE);
EnumSet<Permission> all = EnumSet.allOf(Permission.class);
EnumSet<Permission> none = EnumSet.noneOf(Permission.class);
perms.contains(Permission.READ); // O(1) bit check
```

---

### 3.5 CopyOnWriteArrayList

**Q: How does CopyOnWriteArrayList achieve thread safety, and when is it appropriate?**

A: Every mutating operation (`add`, `remove`, `set`) creates a **new copy** of the underlying array, and atomically swaps the reference. Reads (`get`, iteration) work off an immutable snapshot with **no locking at all**, so iterators never throw `ConcurrentModificationException` and reads are extremely fast and safe even during concurrent writes. The trade-off: writes are O(n) (full array copy) and memory-churny. Ideal for **read-heavy, write-rare** scenarios — e.g., a list of event listeners, or configuration that's read constantly and updated occasionally.

```java
List<String> listeners = new CopyOnWriteArrayList<>();
listeners.add("l1");
for (String l : listeners) { // iterates a stable snapshot, safe even if another thread adds
    // ...
}
```
**Anti-pattern:** using it for write-heavy workloads (e.g., a queue processed by many producers) — each write copies the whole backing array, causing O(n²) total cost across n writes.

---

### 3.6 ConcurrentHashMap

**Q: How does ConcurrentHashMap achieve high-concurrency thread safety, and how has its internal locking evolved?**

A: Pre-Java 8, `ConcurrentHashMap` used **segment-based locking** — the table was divided into ~16 segments, each independently lockable, so up to 16 threads could write concurrently without contention. Since Java 8, segments were dropped in favor of **per-bucket (per-node) locking** using `synchronized` on the first node of a bin, combined with **CAS (compare-and-swap)** operations for bin-head insertion — finer-grained than segment locking, so concurrency scales with the number of buckets, not a fixed 16. Reads are largely **lock-free** (volatile reads of `Node` fields). Like `HashMap`, buckets treeify past a threshold. It never allows `null` keys or values (unlike `HashMap`) because `null` would be ambiguous with "key absent" in a concurrent context — you can't distinguish "no mapping" from "mapping to null" when another thread might be modifying concurrently.

```java
Map<String, Integer> chm = new ConcurrentHashMap<>();
chm.put("a", 1);
chm.compute("a", (k, v) -> v == null ? 1 : v + 1); // atomic read-modify-write
chm.putIfAbsent("b", 2);                            // atomic
chm.forEach(1, (k, v) -> System.out.println(k + "=" + v)); // parallel-capable bulk op
```

**Follow-up: Why does HashMap allow null but ConcurrentHashMap doesn't?**
A: In single-threaded `HashMap`, `map.get(key) == null` is ambiguous (key absent vs. mapped to null), resolved by a follow-up `containsKey()` check. In a concurrent map, that two-step check-then-act isn't atomic — another thread could mutate the map between the calls — so Doug Lea (its author) disallowed null entirely to remove the ambiguity.

---

### 3.7 BlockingQueue

**Q: What is BlockingQueue and what are the common implementations?**

A: `BlockingQueue<E>` extends `Queue` with blocking semantics for producer-consumer patterns: `put(e)` blocks if the queue is full (for bounded queues), `take()` blocks if the queue is empty, until space/an element becomes available. It's the standard building block for thread pools and work queues.

| Implementation | Backing structure | Notes |
|---|---|---|
| `ArrayBlockingQueue` | Fixed-size circular array | Bounded, single lock |
| `LinkedBlockingQueue` | Linked nodes | Optionally bounded, two locks (put/take) for higher throughput |
| `PriorityBlockingQueue` | Binary heap | Unbounded, priority order, no blocking on put |
| `SynchronousQueue` | None — direct handoff | Zero capacity; put blocks until a take is ready, and vice versa |
| `DelayQueue` | Heap ordered by delay | Elements only become available after their delay expires |

```java
BlockingQueue<Runnable> workQueue = new LinkedBlockingQueue<>(100);

// Producer
workQueue.put(task); // blocks if full

// Consumer
Runnable task = workQueue.take(); // blocks if empty

// This is exactly what ThreadPoolExecutor uses internally to hold pending tasks.
ExecutorService pool = new ThreadPoolExecutor(
    4, 8, 60, TimeUnit.SECONDS, new LinkedBlockingQueue<>(100));
```

---

## 4. Interview MCQs

1. **What is the initial default capacity of a `HashMap`?**
   a) 10 b) 16 c) 32 d) 0
   **Answer: b) 16** — default capacity is 16 with load factor 0.75, resize threshold = 12.

2. **Which collection permits duplicate elements but maintains insertion order and is NOT a `List`?**
   a) `TreeSet` b) `ArrayDeque` (as a list-like structure) c) None — insertion-order + duplicates is the definition of a `List`
   **Answer: c)** — trick question; any structure allowing duplicates + insertion order is functionally a `List`.

3. **What does `HashMap.get()` return if the key maps to `null` vs the key is absent?**
   **Answer:** Both return `null` — use `containsKey()` or `getOrDefault()` to disambiguate.

4. **Which of these throws `UnsupportedOperationException` on `add()`?**
   a) `new ArrayList<>(List.of(1,2))` b) `Arrays.asList(1,2)` c) `new LinkedList<>(List.of(1,2))`
   **Answer: b)** — `Arrays.asList` returns a fixed-size list backed by the array; `set()` works but `add`/`remove` don't.

5. **What's the time complexity of `TreeMap.floorKey()`?**
   **Answer: O(log n)** — red-black tree traversal.

6. **True or False: `ConcurrentHashMap` allows `null` values.**
   **Answer: False.**

7. **What's the load factor's effect on a HashMap?**
   **Answer:** Higher load factor = fewer resizes, more memory-efficient, but more collisions (slower lookups). Lower = more memory, fewer collisions, faster lookups. 0.75 is the classic time/space compromise.

8. **Which method must be overridden together with `equals()` to safely use a class as a `HashMap` key?**
   **Answer: `hashCode()`.**

9. **What happens if you modify a `List` while iterating with a for-each loop (not using the iterator's own remove)?**
   **Answer:** `ConcurrentModificationException`, via the iterator's fail-fast `modCount` check.

10. **Which is faster for a stack: `java.util.Stack` or `ArrayDeque`?**
    **Answer: `ArrayDeque`** — `Stack` extends `Vector` and synchronizes every call.

11. **What's the Big-O of `PriorityQueue.offer()`?**
    **Answer: O(log n)**.

12. **Does `Collections.unmodifiableList()` create a deep copy?**
    **Answer: No** — it's a live read-only *view*; mutations to the underlying list are still visible through it.

13. **What's the difference between `List.of(...)` and `Arrays.asList(...)`?**
    **Answer:** `List.of()` is truly immutable (throws on any mutation, including `set()`) and disallows `null` elements. `Arrays.asList()` is fixed-size but allows `set()`, and permits `null`.

14. **What sort does `Arrays.sort(int[])` use vs `Arrays.sort(Object[])`?**
    **Answer:** Dual-pivot Quicksort for primitives; TimSort (stable merge sort) for objects.

15. **Is `String` a good HashMap key? Why?**
    **Answer:** Yes — immutable (safe hash caching; `String.hashCode()` is cached after first computation), well-distributed `hashCode()`, correct `equals()`.

---

## 5. JUnit 5 Tests

```java
import org.junit.jupiter.api.*;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.ValueSource;
import static org.junit.jupiter.api.Assertions.*;

class LRUCacheBTest {

    private LRUCacheB cache;

    @BeforeEach
    void setUp() {
        cache = new LRUCacheB(2);
    }

    @Test
    @DisplayName("put then get returns the stored value")
    void putThenGet() {
        cache.put(1, 100);
        assertEquals(100, cache.get(1));
    }

    @Test
    @DisplayName("get on missing key returns -1")
    void getMissingKey() {
        assertEquals(-1, cache.get(42));
    }

    @Test
    @DisplayName("exceeding capacity evicts least recently used entry")
    void evictsLeastRecentlyUsed() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // 1 is now MRU, 2 is LRU
        cache.put(3, 3);     // evicts 2
        assertEquals(-1, cache.get(2));
        assertEquals(1, cache.get(1));
        assertEquals(3, cache.get(3));
    }

    @Test
    void updatingExistingKeyRefreshesRecency() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(1, 10);    // 1 becomes MRU
        cache.put(3, 3);      // evicts 2, not 1
        assertEquals(10, cache.get(1));
        assertEquals(-1, cache.get(2));
    }

    @ParameterizedTest
    @ValueSource(ints = {1, 5, 100})
    void capacityIsRespected(int capacity) {
        LRUCacheB c = new LRUCacheB(capacity);
        for (int i = 0; i < capacity + 10; i++) c.put(i, i);
        // only the last `capacity` keys should remain
        for (int i = 10; i < capacity + 10; i++) {
            assertNotEquals(-1, c.get(i));
        }
    }
}

class TopKFrequentTest {
    @Test
    void returnsCorrectTopKByFrequency() {
        int[] nums = {1, 1, 1, 2, 2, 3};
        List<Integer> result = topKFrequent(nums, 2);
        assertEquals(List.of(1, 2), result);
    }

    @Test
    void handlesKEqualToDistinctCount() {
        int[] nums = {4, 4, 5, 5, 6};
        assertEquals(3, topKFrequent(nums, 3).size());
    }
}

class HashMapEqualsHashCodeTest {
    record Point(int x, int y) {}

    @Test
    void recordsWithSameFieldsAreEqualAndHashSame() {
        Point p1 = new Point(1, 2);
        Point p2 = new Point(1, 2);
        assertEquals(p1, p2);
        assertEquals(p1.hashCode(), p2.hashCode());

        Set<Point> set = new HashSet<>();
        set.add(p1);
        assertTrue(set.contains(p2)); // proves the equals/hashCode contract holds
    }
}
```

**Follow-up: What's the difference between `@BeforeEach` and `@BeforeAll`?**
A: `@BeforeEach` runs before every test method (new instance per test by default in JUnit 5). `@BeforeAll` runs once before all tests in the class and must be `static` (unless the class uses `@TestInstance(Lifecycle.PER_CLASS)`).

---

## 6. Real Interview Questions (FAANG / Banks)

These are patterns commonly reported from Amazon, Google, Meta, Goldman Sachs, JPMorgan, and similar interview loops.

**Q1 (Amazon, OOD/coding hybrid): Design a rate limiter using a sliding window, backed by a data structure discussed above.**
> Approach: `ArrayDeque<Long>` per client, storing request timestamps. On each request, pop timestamps older than `now - windowSize` from the front (O(1) each), then check if `deque.size() < limit`. Push `now` if allowed. Amortized O(1) per request.

**Q2 (Google): Given a stream of integers, design a class that supports adding numbers and finding the median in O(log n) per operation.**
> Approach: two heaps — a max-heap for the lower half, a min-heap for the upper half, kept balanced in size (differ by at most 1). Median is the top of the larger heap, or the average of both tops if equal size. This is the canonical use of `PriorityQueue` with a custom comparator on one side.

**Q3 (Meta): Why might `HashMap` iteration order change between two runs of the same program with the same insertions?**
> Answer: Iteration order follows bucket order, and bucket index depends on `hashCode()`. If `hashCode()` isn't overridden (default `Object.hashCode()`, often derived from memory address/identity), it can vary across JVM runs due to ASLR/heap layout — so don't rely on HashMap order for anything observable; use `LinkedHashMap` if order matters.

**Q4 (Goldman Sachs — Java/low-latency desk): Why is `ConcurrentHashMap` preferred over `Collections.synchronizedMap(new HashMap<>())` in high-throughput trading systems?**
> Answer: `synchronizedMap` wraps every method in a single global lock — one thread at a time, regardless of key. `ConcurrentHashMap` uses fine-grained per-bin locking/CAS, allowing many threads to read and write different keys concurrently with minimal contention — critical when tracking order books or position caches under high request rates.

**Q5 (JPMorgan): You have millions of transaction objects; equals()/hashCode() are based on transaction ID. What breaks if the ID field is mutable and someone changes it after inserting into a HashSet?**
> Answer: The object's bucket location was computed from the *old* hash. After mutation, `hashCode()` returns a different value, but the object still lives in its original bucket. Subsequent `contains()`/`remove()` calls compute the *new* hash, look in the *wrong* bucket, and silently fail to find the entry — a classic "lost" object bug. Lesson: never mutate fields used in `hashCode()`/`equals()` while the object is a live key/element in a hash-based collection; prefer immutable keys.

**Q6 (Amazon, OA-style): Two Sum — given an array and a target, return indices of two numbers that add up to target.**
```java
static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>(); // value -> index
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) return new int[]{seen.get(complement), i};
        seen.put(nums[i], i);
    }
    throw new IllegalArgumentException("no solution");
}
// O(n) time, O(n) space — the canonical HashMap warm-up question at nearly every FAANG loop.
```

**Q7 (Meta / Bloomberg): Detect if a LinkedList has a cycle.**
```java
static boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true; // Floyd's cycle detection ("tortoise and hare")
    }
    return false;
}
// O(n) time, O(1) space
```

---

## 7. Immutable Collections

**Q: What are the ways to create immutable collections in modern Java, and how do they differ?**

A:
- `List.of(...)`, `Set.of(...)`, `Map.of(...)` (Java 9+) — truly immutable, fixed-size, disallow `null` elements/keys/values, throw `UnsupportedOperationException` on any mutation attempt.
- `Collections.unmodifiableList(list)` — a **live wrapper/view**; the underlying list can still change (via the original reference), and those changes show through the wrapper. Not truly immutable, just externally read-only.
- `Collections.emptyList()`, `singletonList(x)` — special-cased immutable instances for 0/1-element cases.
- `List.copyOf(existing)` — snapshot copy, immutable, decouples from the source.

```java
List<Integer> immutable = List.of(1, 2, 3);
immutable.add(4); // throws UnsupportedOperationException

List<Integer> mutable = new ArrayList<>(List.of(1, 2));
List<Integer> view = Collections.unmodifiableList(mutable);
mutable.add(3);
view.get(2); // 3 — the "immutable" view just changed, because it's a live wrapper
```

**Follow-up: Why prefer immutable collections in general?**
A: Thread-safety without synchronization (safe to share across threads freely), no defensive-copy needed when exposing internal state via getters, and they prevent an entire class of bugs where a caller mutates a collection you didn't expect them to touch.

---

## 8. Core DSA Topics

### 8.1 Arrays

**Q: Find the maximum subarray sum (Kadane's Algorithm).**
```java
static int maxSubArray(int[] nums) {
    int maxSoFar = nums[0], maxEndingHere = nums[0];
    for (int i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}
// O(n) time, O(1) space
```

**Q: Rotate an array right by k steps in-place.**
```java
static void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}
static void reverse(int[] a, int lo, int hi) {
    while (lo < hi) { int t = a[lo]; a[lo++] = a[hi]; a[hi--] = t; }
}
// O(n) time, O(1) space — the "triple reversal" trick
```

---

### 8.2 Strings

**Q: Check if two strings are anagrams.**
```java
static boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] counts = new int[26];
    for (char c : s.toCharArray()) counts[c - 'a']++;
    for (char c : t.toCharArray()) if (--counts[c - 'a'] < 0) return false;
    return true;
}
// O(n) time, O(1) space (fixed alphabet)
```

**Q: Longest substring without repeating characters (sliding window).**
```java
static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int start = 0, maxLen = 0;
    for (int end = 0; end < s.length(); end++) {
        char c = s.charAt(end);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= start) {
            start = lastSeen.get(c) + 1; // shrink window past the duplicate
        }
        lastSeen.put(c, end);
        maxLen = Math.max(maxLen, end - start + 1);
    }
    return maxLen;
}
// O(n) time, O(min(n, alphabet)) space
```

**Q: Why is `StringBuilder` preferred over `String` concatenation in loops?**
A: `String` is immutable — each `+` creates a new object, so concatenating in a loop is O(n²). `StringBuilder` mutates an internal resizable `char[]`/`byte[]` buffer, giving O(n) amortized total for n appends.

---

### 8.3 HashMap & Set (algorithmic use)

**Q: Group anagrams together.**
```java
static List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars); // canonical form is the map key
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}
// O(n * k log k) time where k = avg string length
```

**Q: Longest consecutive sequence in an unsorted array — O(n) solution.**
```java
static int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int longest = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) { // only start counting from sequence heads
            int length = 1;
            while (set.contains(n + length)) length++;
            longest = Math.max(longest, length);
        }
    }
    return longest;
}
// O(n) — each number is visited at most twice total
```

---

### 8.4 Streams

**Q: Common Stream operations and their laziness.**
```java
List<String> names = List.of("Alice", "Bob", "Charlie", "Dan");

// filter + map + collect (intermediate ops are lazy; nothing runs until a terminal op)
List<Integer> lengths = names.stream()
    .filter(n -> n.length() > 3)
    .map(String::length)
    .collect(Collectors.toList());

// groupingBy + downstream collector
Map<Integer, List<String>> byLength = names.stream()
    .collect(Collectors.groupingBy(String::length));

// reduce
int totalChars = names.stream().mapToInt(String::length).sum();

// parallel stream — use with caution, only for CPU-bound, stateless, large datasets
long count = names.parallelStream().filter(n -> n.startsWith("A")).count();
```

**Follow-up: When should you avoid parallelStream()?**
A: For small collections (fork/join overhead exceeds benefit), I/O-bound operations (no CPU parallelism benefit, and can exhaust the shared ForkJoinPool used by other parallel streams / CompletableFutures app-wide), and operations with side effects or ordering dependencies.

---

### 8.5 Recursion & Backtracking

**Q: Generate all permutations of an array.**
```java
static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
    return result;
}
static void backtrack(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current)); // must copy — current is mutated after this
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        current.add(nums[i]);
        backtrack(nums, current, used, result);
        current.remove(current.size() - 1); // undo — the core backtracking step
        used[i] = false;
    }
}
// O(n * n!) time
```

**Q: N-Queens (classic backtracking with pruning).**
```java
static int totalNQueens(int n) {
    return solve(n, 0, new HashSet<>(), new HashSet<>(), new HashSet<>());
}
static int solve(int n, int row, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
    if (row == n) return 1;
    int count = 0;
    for (int col = 0; col < n; col++) {
        int d1 = row - col, d2 = row + col;
        if (cols.contains(col) || diag1.contains(d1) || diag2.contains(d2)) continue;
        cols.add(col); diag1.add(d1); diag2.add(d2);
        count += solve(n, row + 1, cols, diag1, diag2);
        cols.remove(col); diag1.remove(d1); diag2.remove(d2); // backtrack
    }
    return count;
}
```

---

### 8.6 Linked List

**Q: Reverse a singly linked list, iteratively and recursively.**
```java
static ListNode reverseIterative(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev; // O(n) time, O(1) space
}

static ListNode reverseRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead; // O(n) time, O(n) space (call stack)
}
```

**Q: Merge two sorted linked lists.**
```java
static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1), tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
        else { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next; // O(n+m) time, O(1) extra space
}
```

---

### 8.7 Stack & Queue

**Q: Valid Parentheses.**
```java
static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    for (char c : s.toCharArray()) {
        if (pairs.containsValue(c)) stack.push(c);
        else if (pairs.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
        }
    }
    return stack.isEmpty();
}
// O(n) time, O(n) space
```

**Q: Implement a Queue using two Stacks.**
```java
class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();

    void push(int x) { in.push(x); }

    int pop() {
        transferIfNeeded();
        return out.pop();
    }
    int peek() {
        transferIfNeeded();
        return out.peek();
    }
    private void transferIfNeeded() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
    }
    // amortized O(1) per operation — each element moves from `in` to `out` exactly once
}
```

---

### 8.8 Trees

**Q: Level-order (BFS) traversal.**
```java
static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result; // O(n) time, O(n) space
}
```

**Q: Lowest Common Ancestor in a binary tree.**
```java
static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left != null && right != null) return root; // p and q found in different subtrees
    return (left != null) ? left : right;
}
// O(n) time, O(h) space (recursion stack, h = height)
```

**Q: Validate a Binary Search Tree.**
```java
static boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}
static boolean validate(TreeNode node, Integer lower, Integer upper) {
    if (node == null) return true;
    if (lower != null && node.val <= lower) return false;
    if (upper != null && node.val >= upper) return false;
    return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
}
```

---

### 8.9 Graphs

**Q: BFS and DFS on an adjacency-list graph.**
```java
static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(start); visited.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (visited.add(neighbor)) queue.offer(neighbor); // add() returns false if already present
        }
    }
    return order; // O(V + E)
}

static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, List<Integer> order) {
    if (!visited.add(node)) return;
    order.add(node);
    for (int neighbor : graph.getOrDefault(node, List.of())) dfs(graph, neighbor, visited, order);
}
```

**Q: Detect a cycle in a directed graph (using 3-color / recursion-stack DFS).**
```java
static boolean hasCycle(Map<Integer, List<Integer>> graph, int n) {
    int[] state = new int[n]; // 0 = unvisited, 1 = in progress, 2 = done
    for (int i = 0; i < n; i++) {
        if (state[i] == 0 && dfsCycle(graph, i, state)) return true;
    }
    return false;
}
static boolean dfsCycle(Map<Integer, List<Integer>> graph, int node, int[] state) {
    state[node] = 1;
    for (int neighbor : graph.getOrDefault(node, List.of())) {
        if (state[neighbor] == 1) return true;        // back edge -> cycle
        if (state[neighbor] == 0 && dfsCycle(graph, neighbor, state)) return true;
    }
    state[node] = 2;
    return false;
}
```

**Q: Dijkstra's shortest path (using PriorityQueue).**
```java
static int[] dijkstra(Map<Integer, List<int[]>> graph, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); // [node, dist]
    pq.offer(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int node = cur[0], d = cur[1];
        if (d > dist[node]) continue; // stale entry, skip
        for (int[] edge : graph.getOrDefault(node, List.of())) {
            int next = edge[0], weight = edge[1];
            if (dist[node] + weight < dist[next]) {
                dist[next] = dist[node] + weight;
                pq.offer(new int[]{next, dist[next]});
            }
        }
    }
    return dist; // O((V + E) log V)
}
```

---

### 8.10 Dynamic Programming

**Q: Fibonacci — from exponential to O(n) to O(1) space.**
```java
// Naive recursion: O(2^n)
static int fibNaive(int n) { return n <= 1 ? n : fibNaive(n-1) + fibNaive(n-2); }

// Memoized (top-down): O(n) time, O(n) space
static int fibMemo(int n, Map<Integer, Integer> memo) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, result);
    return result;
}

// Bottom-up, O(1) space
static int fibIterative(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}
```

**Q: 0/1 Knapsack.**
```java
static int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w]; // don't take item i
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity]; // O(n * capacity) time and space (can be reduced to O(capacity))
}
```

**Q: Longest Common Subsequence.**
```java
static int lcs(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            dp[i][j] = (a.charAt(i-1) == b.charAt(j-1))
                ? dp[i-1][j-1] + 1
                : Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[a.length()][b.length()]; // O(n*m) time and space
}
```

---

## 9. Concurrency & CompletableFuture

**Q: What's the difference between `synchronized`, `ReentrantLock`, and `volatile`?**

A: `synchronized` provides mutual exclusion + a memory-visibility barrier via intrinsic monitor locks — simple, JVM-managed, but can't be interrupted while waiting and can't try-lock with a timeout. `ReentrantLock` (java.util.concurrent.locks) offers the same mutual exclusion but adds `tryLock()`, `lockInterruptibly()`, fairness policies, and multiple `Condition` objects per lock (vs. one implicit wait-set per `synchronized` object). `volatile` guarantees **visibility** (writes are immediately visible to other threads, no CPU-cache staleness) and **ordering** (via happens-before), but **not atomicity** — `volatile int counter; counter++;` is still a race (read-modify-write is 3 separate operations).

```java
class Counter {
    private volatile boolean flag; // visibility only, not for compound ops
    private int count;
    private final ReentrantLock lock = new ReentrantLock();

    void increment() {
        lock.lock();
        try { count++; } finally { lock.unlock(); } // always unlock in finally
    }

    synchronized void incrementSync() { count++; } // equivalent, simpler
}
```

**Q: Explain the Java Memory Model's "happens-before" relationship briefly.**
A: It defines when one thread's writes are guaranteed visible to another thread's reads, without which the JIT/CPU are free to reorder or cache values per-thread. Key happens-before edges: unlocking a monitor happens-before a subsequent lock of the same monitor; a `volatile` write happens-before a subsequent `volatile` read of the same field; a thread's actions before `Thread.start()` happen-before the new thread's actions; a thread's actions happen-before another thread observes it via `Thread.join()`.

**Q: What's a race condition vs a deadlock vs livelock?**
A: **Race condition** — outcome depends on non-deterministic thread interleaving (e.g., unsynchronized `count++`). **Deadlock** — two+ threads each hold a lock the other needs, waiting forever (classic: lock A then B in thread 1, lock B then A in thread 2 — fix by consistent lock ordering). **Livelock** — threads actively respond to each other (e.g., both back off and retry in lockstep) but make no progress, unlike deadlock where they're blocked/idle.

**Q: CompletableFuture — chaining, combining, and exception handling.**
```java
CompletableFuture<Integer> future = CompletableFuture
    .supplyAsync(() -> fetchUserId())              // runs on ForkJoinPool.commonPool() by default
    .thenApply(id -> id * 2)                         // sync transform
    .thenApplyAsync(id -> id + 1, customExecutor)     // async transform on a named executor
    .exceptionally(ex -> {                             // recover from any upstream failure
        System.err.println("failed: " + ex.getMessage());
        return -1;
    });

// Combining two independent futures
CompletableFuture<String> nameF = CompletableFuture.supplyAsync(() -> fetchName());
CompletableFuture<Integer> ageF = CompletableFuture.supplyAsync(() -> fetchAge());
CompletableFuture<String> combined = nameF.thenCombine(ageF, (name, age) -> name + " is " + age);

// Waiting for all of several futures
CompletableFuture<Void> all = CompletableFuture.allOf(nameF, ageF);
all.join(); // blocks until both complete

// Timeout (Java 9+)
future.orTimeout(2, TimeUnit.SECONDS)
      .handle((result, ex) -> ex != null ? -1 : result);
```
**Follow-up: `thenApply` vs `thenApplyAsync` — what's the difference?**
A: `thenApply` runs the callback on whichever thread completes the previous stage (could be the calling thread if already complete, or the worker thread that finished the async task). `thenApplyAsync` (no executor arg) always submits the callback to `ForkJoinPool.commonPool()`; with an executor arg, it runs there — giving explicit control over which thread pool does the work, important to avoid starving the common pool with blocking work.

---

## 10. JVM Internals

**Q: Describe the JVM memory areas.**

A:
- **Heap** — shared across all threads; holds all objects and arrays. Divided generationally by most collectors: **Young Generation** (Eden + two Survivor spaces, for short-lived objects, collected by fast "minor GC") and **Old Generation** (long-lived/promoted objects, collected by slower "major/full GC").
- **Metaspace** (replaced PermGen in Java 8+) — stores class metadata, method bytecode, constant pool; grows into native memory, not bounded by `-Xmx`.
- **Stack** — one per thread; holds stack frames (local variables, operand stack, partial results) for method calls. `StackOverflowError` when exceeded.
- **PC Register** — one per thread; tracks the current executing instruction.
- **Native Method Stack** — for JNI/native calls.

**Q: How does Garbage Collection generally work (generational hypothesis)?**
A: Most objects die young ("weak generational hypothesis"), so the heap is split so young objects are collected frequently and cheaply (Eden fills up, live objects copied to a Survivor space, repeat; objects surviving several cycles get **promoted** to Old Gen). Old Gen is collected less often but more expensively, since it typically requires scanning more live data. Modern collectors like **G1** (default since Java 9) divide the heap into many equal-sized regions instead of fixed contiguous generations, prioritizing collection of regions with the most garbage ("garbage first") to hit pause-time targets. **ZGC** and **Shenandoah** are low-pause concurrent collectors designed for multi-GB-to-TB heaps with sub-millisecond pause targets, doing almost all work concurrently with application threads.

**Q: What's the difference between `==` and `.equals()` for objects, and why does `String s1 = "a"; String s2 = "a"; s1 == s2` return `true`?**
A: `==` compares references (identity) for objects; `.equals()` compares logical/value equality (if overridden). String literals are interned in the **String Pool** (part of the heap since Java 7, previously PermGen) — the compiler/JVM reuses the same `String` object for identical literals, so `s1 == s2` is true here. But `new String("a") == "a"` is `false` (explicit heap allocation bypasses the pool) unless you call `.intern()`.

**Q: Class loading — what are the three built-in class loaders and the delegation model?**
A: **Bootstrap** (loads core `java.*` classes, native code, no Java parent) → **Platform/Extension** (JDK-supplied extensions) → **Application/System** (your classpath). Each loader delegates to its parent first (**parent delegation model**) — a class is only loaded by the child if the parent can't find it — preventing user code from shadowing core classes like `java.lang.String`.

**Q: What's escape analysis and how does it enable stack allocation of objects?**
A: The JIT compiler analyzes whether an object reference "escapes" its allocating method (is it returned, stored in a field, passed elsewhere?). If it provably doesn't escape, the JIT can perform **scalar replacement** — decompose the object into its primitive fields and allocate them on the stack (or even in registers) instead of the heap, avoiding allocation and GC pressure entirely, and can also elide `synchronized` locks on objects proven to be thread-local.

---

## 11. Design Patterns

**Q: Singleton — thread-safe lazy initialization, three approaches.**
```java
// 1. Enum singleton — simplest, serialization-safe, reflection-attack-proof (JVM guarantees single instantiation)
enum Singleton { INSTANCE; void doWork() { } }

// 2. Double-checked locking — lazy, thread-safe, minimal synchronization overhead after first init
class DCLSingleton {
    private static volatile DCLSingleton instance; // volatile prevents reordering of partially-constructed object being visible
    private DCLSingleton() {}
    static DCLSingleton getInstance() {
        if (instance == null) {
            synchronized (DCLSingleton.class) {
                if (instance == null) instance = new DCLSingleton();
            }
        }
        return instance;
    }
}

// 3. Initialization-on-demand holder idiom — lazy, thread-safe via classloader guarantees, no synchronization needed
class HolderSingleton {
    private HolderSingleton() {}
    private static class Holder { static final HolderSingleton INSTANCE = new HolderSingleton(); }
    static HolderSingleton getInstance() { return Holder.INSTANCE; } // Holder class loads (and initializes) only on first access
}
```

**Q: Strategy pattern — with lambdas replacing boilerplate classes.**
```java
interface DiscountStrategy { double apply(double price); }

class PricingContext {
    private DiscountStrategy strategy;
    PricingContext(DiscountStrategy s) { this.strategy = s; }
    double price(double base) { return strategy.apply(base); }
}

// Old-style: implement classes. Modern: lambdas
PricingContext regular = new PricingContext(price -> price);
PricingContext vip = new PricingContext(price -> price * 0.8);
```

**Q: Builder pattern.**
```java
class Pizza {
    private final String size;
    private final List<String> toppings;
    private Pizza(Builder b) { this.size = b.size; this.toppings = b.toppings; }

    static class Builder {
        private String size = "medium";
        private final List<String> toppings = new ArrayList<>();
        Builder size(String size) { this.size = size; return this; }
        Builder topping(String t) { toppings.add(t); return this; }
        Pizza build() { return new Pizza(this); }
    }
}
Pizza p = new Pizza.Builder().size("large").topping("cheese").topping("olives").build();
```

**Q: Observer pattern.**
```java
interface Observer { void update(String event); }

class EventBus {
    private final List<Observer> observers = new CopyOnWriteArrayList<>(); // safe under concurrent notify+subscribe
    void subscribe(Observer o) { observers.add(o); }
    void publish(String event) { observers.forEach(o -> o.update(event)); }
}
```

**Q: Factory Method vs Abstract Factory — what's the distinction?**
A: **Factory Method** — a single method (often overridden in subclasses) that creates one type of product, deferring instantiation logic to subclasses. **Abstract Factory** — an interface/class that creates a **family of related products** (e.g., `GUIFactory` producing matching `Button` + `Checkbox` for a given OS theme), ensuring the products it creates are compatible with each other.

---

## 12. Low-Level Design

**Q: Design a Parking Lot system (class-level).**
```java
enum VehicleType { MOTORCYCLE, CAR, BUS }

abstract class Vehicle {
    final String licensePlate;
    final VehicleType type;
    Vehicle(String plate, VehicleType type) { this.licensePlate = plate; this.type = type; }
}

class ParkingSpot {
    final int spotNumber;
    final VehicleType supportedType;
    Vehicle parkedVehicle;
    boolean isAvailable() { return parkedVehicle == null; }
    void park(Vehicle v) { this.parkedVehicle = v; }
    void vacate() { this.parkedVehicle = null; }
    ParkingSpot(int n, VehicleType t) { spotNumber = n; supportedType = t; }
}

class ParkingFloor {
    final int floorNumber;
    final Map<VehicleType, List<ParkingSpot>> spotsByType = new EnumMap<>(VehicleType.class);

    Optional<ParkingSpot> findAvailableSpot(VehicleType type) {
        return spotsByType.getOrDefault(type, List.of()).stream()
            .filter(ParkingSpot::isAvailable)
            .findFirst();
    }
    ParkingFloor(int floorNumber) { this.floorNumber = floorNumber; }
}

class ParkingLot { // Singleton in a real system
    private final List<ParkingFloor> floors = new ArrayList<>();
    private final Map<String, ParkingSpot> activeTickets = new ConcurrentHashMap<>(); // plate -> spot

    Optional<ParkingSpot> parkVehicle(Vehicle v) {
        for (ParkingFloor floor : floors) {
            Optional<ParkingSpot> spot = floor.findAvailableSpot(v.type);
            if (spot.isPresent()) {
                spot.get().park(v);
                activeTickets.put(v.licensePlate, spot.get());
                return spot;
            }
        }
        return Optional.empty(); // lot full
    }
    void unparkVehicle(String licensePlate) {
        ParkingSpot spot = activeTickets.remove(licensePlate);
        if (spot != null) spot.vacate();
    }
}
```
**Key design decisions to call out in interview:** `EnumMap` for type-segregated spot lookup (fast, natural ordering), `ConcurrentHashMap` for the active-ticket registry (multiple entry/exit gates operate concurrently), `Optional` to express "may not find a spot" without null checks, and strategy-pattern potential for pricing (`PricingStrategy` per vehicle type/duration).

**Q: Design a Rate Limiter (Token Bucket).**
```java
class TokenBucketRateLimiter {
    private final long capacity;
    private final long refillTokensPerSecond;
    private double availableTokens;
    private long lastRefillTimestamp;

    TokenBucketRateLimiter(long capacity, long refillTokensPerSecond) {
        this.capacity = capacity;
        this.refillTokensPerSecond = refillTokensPerSecond;
        this.availableTokens = capacity;
        this.lastRefillTimestamp = System.nanoTime();
    }

    synchronized boolean allowRequest() {
        refill();
        if (availableTokens >= 1) {
            availableTokens -= 1;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        double secondsElapsed = (now - lastRefillTimestamp) / 1_000_000_000.0;
        availableTokens = Math.min(capacity, availableTokens + secondsElapsed * refillTokensPerSecond);
        lastRefillTimestamp = now;
    }
}
```

---

## 13. System Design

**Q: Design a URL shortener (e.g., bit.ly) — high-level.**

A: **Core flow:** `POST /shorten {longUrl}` → generate a short code → store `(code -> longUrl)` → return `short.ly/{code}`. `GET /{code}` → look up → HTTP 301/302 redirect.

- **Code generation:** Base62-encode an auto-incrementing distributed ID (from a service like Snowflake or a pre-allocated ID range per app server, to avoid a single DB counter bottleneck), or hash the long URL (MD5/SHA-256) and take the first 6-8 chars, retrying on collision.
- **Storage:** A key-value store (DynamoDB, Cassandra) fits the read-heavy, simple-lookup access pattern well; a relational DB with an index on `code` also works at moderate scale.
- **Caching:** Redis/Memcached in front of the DB for hot URLs — reads vastly outnumber writes (typical ratio 100:1+), so cache hit rate dominates latency.
- **Scaling reads:** CDN/edge caching for redirect responses where staleness is tolerable; read replicas for the DB.
- **Analytics (click tracking):** Don't write synchronously on the read path — publish a click event to a queue (Kafka) and aggregate asynchronously, keeping redirect latency low.
- **Expiration/cleanup:** TTL on entries if short links expire; a background job or DB TTL feature to reap.

**Q: Design a distributed cache — what are the key considerations?**
A: **Partitioning** (consistent hashing to distribute keys across nodes and minimize reshuffling when nodes join/leave), **replication** (for availability — leader/follower per shard, or quorum-based), **eviction policy** (LRU/LFU per node — this is where your earlier LRU cache design plugs in directly), **consistency model** (usually eventual consistency is acceptable for a cache; strong consistency adds latency), and **cache invalidation** strategy (write-through, write-behind, or TTL-based expiry — "there are only two hard things in Computer Science: cache invalidation and naming things").

**Q: How would you design a notification system that fans out to millions of users?**
A: Producer (event source, e.g., "new post") publishes to a message queue (Kafka topic). Consumer workers pull from the queue, look up each recipient's notification preferences/device tokens (from a fast KV store), and push to the appropriate channel (APNs/FCM for mobile push, SMTP relay for email, SMS gateway). Use **fan-out-on-write** (precompute each follower's feed/notification at write time — good for read-heavy, moderate fan-out) vs **fan-out-on-read** (compute at read time — better for celebrities with millions of followers, avoiding a write storm) as a hybrid based on follower count. Rate-limit per user to avoid notification storms; use a dead-letter queue for failed deliveries with retry/backoff.

**Q: CAP theorem — explain briefly and give a database example for each trade-off.**
A: In a distributed system experiencing a network **P**artition, you must choose between **C**onsistency (every read sees the latest write) and **A**vailability (every request gets a response, possibly stale). **CP** systems (e.g., HBase, ZooKeeper, MongoDB in certain configs) reject requests rather than serve stale data during a partition. **AP** systems (e.g., Cassandra, DynamoDB) always respond, accepting eventual consistency. Outside of an actual partition, most systems tune the C/A trade-off via read/write quorums.

---

## 14. Spring Boot

**Q: What is dependency injection and how does Spring implement it?**

A: Dependency Injection (DI) is a pattern where an object's dependencies are provided by an external container rather than constructed internally, decoupling components and enabling easier testing (mocking) and configuration swapping. Spring's `ApplicationContext` (IoC container) scans for `@Component`/`@Service`/`@Repository`/`@Controller`-annotated classes, instantiates them as **beans**, resolves their dependencies (via constructor, setter, or field injection), and wires them together.

```java
@Service
class OrderService {
    private final PaymentGateway paymentGateway; // constructor injection — preferred: immutable, testable, fails fast if missing
    OrderService(PaymentGateway paymentGateway) { this.paymentGateway = paymentGateway; }
}

@Component
class StripeGateway implements PaymentGateway { /* ... */ }
```
**Follow-up: Why prefer constructor injection over field injection (`@Autowired` on a field)?**
A: Constructor injection makes dependencies explicit and immutable (`final` fields), fails fast at startup if a dependency is missing (rather than a `NullPointerException` at first use), and makes the class trivially testable without a Spring context (`new OrderService(mockGateway)`). Field injection hides dependencies, requires reflection to set (harder to unit test without Spring or reflection hacks), and allows circular dependencies to silently "work" in ways that hide design problems.

**Q: What are the default bean scopes, and when would you use `prototype`?**
A: Default is **singleton** — one shared instance per Spring container. **prototype** creates a new instance every time the bean is requested/injected — appropriate for stateful, non-thread-safe beans (e.g., a per-request builder or a bean wrapping a mutable in-progress computation).

**Q: Explain `@Transactional` and a common pitfall with self-invocation.**
A: `@Transactional` wraps a method in a database transaction via a Spring AOP **proxy** — commit on success, rollback on a `RuntimeException` (by default; checked exceptions don't trigger rollback unless configured). **Pitfall:** if a `@Transactional` method is called from *within the same class* (`this.otherTransactionalMethod()`), the call bypasses the proxy entirely (proxies only intercept external calls through the bean reference), so the transactional behavior silently doesn't apply.

```java
@RestController
@RequestMapping("/orders")
class OrderController {
    private final OrderService orderService;
    OrderController(OrderService orderService) { this.orderService = orderService; }

    @PostMapping
    ResponseEntity<Order> create(@RequestBody @Valid OrderRequest req) {
        Order order = orderService.create(req);
        return ResponseEntity.status(HttpStatus.CREATED).body(order);
    }
}
```

**Q: What's the Spring Boot auto-configuration mechanism at a high level?**
A: `@SpringBootApplication` bundles `@EnableAutoConfiguration`, which scans `META-INF/spring/org.springframework.boot.autoconfigure.AutoConfiguration.imports` (or the legacy `spring.factories`) for conditional configuration classes. Each is gated by `@ConditionalOnClass`, `@ConditionalOnMissingBean`, `@ConditionalOnProperty`, etc. — so, e.g., adding the `spring-boot-starter-data-jpa` dependency on the classpath triggers `DataSourceAutoConfiguration` and `HibernateJpaAutoConfiguration` automatically, unless you've defined your own conflicting beans (which take precedence via `@ConditionalOnMissingBean`).

---

## 15. Redis

**Q: What data structures does Redis support and when would you pick each?**

A: Redis is an in-memory key-value store, but values can be rich structures, not just strings:
- **String** — simple cache values, counters (`INCR`), distributed locks (`SET key val NX PX 30000`).
- **Hash** — object-like records (`HSET user:1 name "Alice" age 30`) — more memory-efficient than storing each field as a separate top-level key.
- **List** — ordered, used as a simple queue (`LPUSH`/`RPOP`) or recent-activity feed.
- **Set** — unique unordered members, fast membership tests, set operations (union/intersect for tag-based filtering).
- **Sorted Set (ZSET)** — members with scores, O(log n) insert/range queries — ideal for leaderboards, rate limiters (sliding window via timestamp scores), priority queues.
- **Stream** — append-only log structure, consumer groups — like a lightweight Kafka for simpler use cases.

```
SET session:abc123 "userdata" EX 3600      # string with TTL, e.g. session cache
ZADD leaderboard 1500 "player1"            # sorted set for a leaderboard
ZREVRANGE leaderboard 0 9 WITHSCORES        # top 10 players
```

**Q: How would you implement a distributed lock with Redis?**
A: `SET lock:resource1 <unique-token> NX PX 30000` — `NX` (only set if not exists) makes acquisition atomic, `PX` sets an expiry so a crashed holder doesn't lock forever. Release must check the token matches before deleting (via a Lua script for atomicity) to avoid one client releasing another's lock after its own lock expired. For stronger guarantees across a Redis cluster, the **Redlock** algorithm acquires the lock across a majority of independent Redis instances.

**Q: Cache-aside vs write-through vs write-behind — how do they differ?**
A: **Cache-aside** (lazy loading) — app checks cache first; on miss, reads DB and populates cache; writes go to DB and invalidate/update the cache entry. Most common pattern. **Write-through** — writes go to the cache, which synchronously writes to the DB — simpler consistency, higher write latency. **Write-behind** (write-back) — writes go to the cache and are asynchronously flushed to the DB later — lowest write latency, risk of data loss if the cache crashes before flush.

---

## 16. Kafka

**Q: Explain Kafka's core architecture: topics, partitions, brokers, consumer groups.**

A: A **topic** is a logical event stream, split into **partitions** for parallelism — each partition is an ordered, append-only, immutable log. Messages within a partition are strictly ordered; ordering across partitions is *not* guaranteed. **Brokers** are the servers storing partition data, with each partition replicated across brokers for fault tolerance (one **leader** handles reads/writes, **followers** replicate). **Producers** write to a partition (chosen by key hash, or round-robin if no key). **Consumers** in a **consumer group** each own a disjoint subset of partitions — Kafka guarantees at most one consumer per partition *within* a group, enabling horizontal scaling of consumption up to the partition count; different groups independently re-read the same topic.

```
Topic "orders" with 4 partitions
Consumer Group "billing-service" with 4 consumer instances -> each gets exactly 1 partition
Consumer Group "analytics-service" (separate group) -> independently reads all 4 partitions from its own offset
```

**Q: How does Kafka provide ordering and delivery guarantees?**
A: Ordering is guaranteed **only within a partition** — if you need strict ordering for a given entity (e.g., all events for `orderId=123`), use that entity's ID as the partition key so all its events land on the same partition. Delivery semantics: **at-most-once** (commit offset before processing — risk of loss on crash), **at-least-once** (commit offset after processing — risk of duplicate processing on crash/retry, most common default), **exactly-once** (via idempotent producers + transactional writes across producer and consumer offset commits — Kafka's transactional API, more overhead).

**Q: What's a consumer offset and how does rebalancing work?**
A: The offset is the position (an integer) of the next message to consume in a partition; Kafka stores committed offsets in an internal `__consumer_offsets` topic, so a consumer can resume where it left off after a restart. **Rebalancing** happens when group membership changes (a consumer joins/leaves/crashes) — the group coordinator reassigns partitions among remaining consumers, briefly pausing consumption; frequent/expensive rebalances are a common Kafka operational pain point, mitigated by tuning `session.timeout.ms`, using **cooperative sticky** assignment strategy (incremental rebalancing instead of stop-the-world), or Kafka's newer **KIP-848** consumer group protocol.

---

## 17. Kubernetes

**Q: Explain the relationship between Pod, Deployment, Service, and Ingress.**

A: A **Pod** is the smallest deployable unit — one or more tightly-coupled containers sharing network/storage, usually ephemeral. A **Deployment** manages a set of identical Pod replicas via a ReplicaSet, handling rolling updates, rollbacks, and self-healing (restarting crashed Pods, rescheduling on node failure). A **Service** provides a stable virtual IP/DNS name that load-balances traffic across the currently-live Pods matching a label selector (Pods' IPs change as they're recreated; Services abstract that away). An **Ingress** sits in front of Services, providing HTTP(S) routing (host/path-based), TLS termination, at the cluster edge — routing external traffic in.

```yaml
apiVersion: apps/v1
kind: Deployment
metadata: { name: order-service }
spec:
  replicas: 3
  selector: { matchLabels: { app: order-service } }
  template:
    metadata: { labels: { app: order-service } }
    spec:
      containers:
        - name: order-service
          image: myrepo/order-service:1.4.0
          resources:
            requests: { cpu: "250m", memory: "256Mi" }
            limits: { cpu: "500m", memory: "512Mi" }
          livenessProbe: { httpGet: { path: /health, port: 8080 }, initialDelaySeconds: 10 }
          readinessProbe: { httpGet: { path: /ready, port: 8080 }, initialDelaySeconds: 5 }
---
apiVersion: v1
kind: Service
metadata: { name: order-service }
spec:
  selector: { app: order-service }
  ports: [{ port: 80, targetPort: 8080 }]
```

**Q: Liveness vs readiness probes — what's the difference?**
A: **Liveness** probe determines if a container is *alive*; if it fails, Kubernetes **kills and restarts** the container (recovering from deadlocks/hangs). **Readiness** probe determines if a container is *ready to serve traffic*; if it fails, the Pod is removed from the Service's load-balancing endpoints (traffic stops routing to it) **without** restarting it — useful during slow startup (loading caches, warming connection pools) or temporary overload, letting the Pod recover and rejoin without a disruptive restart.

**Q: What happens during a rolling update, and how do you control its blast radius?**
A: The Deployment controller gradually replaces old-version Pods with new ones, governed by `maxSurge` (how many extra Pods above `replicas` can be created during the rollout) and `maxUnavailable` (how many can be down at once). Combined with the readiness probe, Kubernetes won't route traffic to a new Pod until it reports ready, and won't proceed replacing more old Pods until enough new ones are healthy — giving a controlled, zero-downtime rollout that automatically pauses/can be rolled back (`kubectl rollout undo`) if new Pods keep failing readiness.

---

## 18. Microservices

**Q: What's the difference between orchestration and choreography for inter-service communication?**

A: **Orchestration** — a central coordinator (an orchestrator service, or a workflow engine like Camunda/Temporal) explicitly directs each step of a business process, calling services in sequence and handling compensation on failure. Easier to reason about and debug (one place to see the whole flow), but introduces a central point of coordination/failure and coupling. **Choreography** — each service reacts to events published by others (via a message broker) with no central coordinator; more loosely coupled and scalable, but the overall business process becomes implicit, spread across many services' event handlers, making it harder to trace/debug end-to-end (often needs distributed tracing to reconstruct).

**Q: What is the Saga pattern and why is it needed?**
A: In a monolith, a multi-step transaction (e.g., "reserve inventory, charge payment, create shipment") can use a single ACID database transaction. Across microservices with separate databases, that's not possible — so a **Saga** breaks the transaction into a sequence of local transactions, each with a defined **compensating action** to undo it if a later step fails (e.g., "charge payment" fails → trigger "release inventory reservation"). Implemented via **choreography** (each service listens for the prior step's success/failure event) or **orchestration** (a saga coordinator explicitly calls each step and its compensations).

**Q: How do you handle service-to-service resilience (a downstream service is slow/down)?**
A: **Circuit breaker** (e.g., Resilience4j) — after a failure threshold, stop calling the failing service for a cooldown period, failing fast instead of piling up latency/threads; periodically allow a trial request through to test recovery ("half-open" state). **Timeouts** on every network call (never rely on defaults). **Retries with exponential backoff + jitter** for transient failures — but only for idempotent operations, and bounded to avoid retry storms. **Bulkheads** — isolate resource pools (thread pools/connection pools) per downstream dependency so one slow dependency can't exhaust resources needed by calls to healthy dependencies.

```java
@CircuitBreaker(name = "inventoryService", fallbackMethod = "fallbackReserve")
@Retry(name = "inventoryService")
@TimeLimiter(name = "inventoryService")
CompletableFuture<ReservationResult> reserve(String sku, int qty) {
    return CompletableFuture.supplyAsync(() -> inventoryClient.reserve(sku, qty));
}
ReservationResult fallbackReserve(String sku, int qty, Throwable t) {
    return ReservationResult.deferred(sku, qty); // queue for later instead of failing the whole request
}
```

**Q: How do you achieve distributed tracing across microservices?**
A: Propagate a **trace ID** (and per-hop **span ID**) through request headers (W3C Trace Context standard: `traceparent` header) across every service call; each service emits spans tagged with that trace ID to a collector (Jaeger, Zipkin, or an OpenTelemetry-compatible backend), which stitches spans into a single end-to-end trace showing latency per hop — essential for debugging cross-service performance issues that logs alone can't reconstruct.

---

## 19. CodeSignal Practice — Medium

**Q1: `firstDuplicate` — return the first value that occurs twice when scanning left to right, or -1.**
```java
static int firstDuplicate(int[] a) {
    Set<Integer> seen = new HashSet<>();
    for (int x : a) {
        if (!seen.add(x)) return x; // add() returns false if already present
    }
    return -1;
} // O(n) time, O(n) space
```

**Q2: `isCryptSolution` — verify a cryptarithmetic puzzle like SEND+MORE=MONEY.**
```java
static boolean isCryptSolution(String[] crypt, char[][] solution) {
    Map<Character, Character> map = new HashMap<>();
    for (char[] pair : solution) map.put(pair[0], pair[1]);

    long[] values = new long[3];
    for (int i = 0; i < 3; i++) {
        String word = crypt[i];
        StringBuilder digits = new StringBuilder();
        for (char c : word.toCharArray()) digits.append(map.get(c));
        if (digits.length() > 1 && digits.charAt(0) == '0') return false; // no leading zeros
        values[i] = Long.parseLong(digits.toString());
    }
    return values[0] + values[1] == values[2];
} // O(n) over total input length
```

**Q3: `sudoku2` — validate a partially filled 9x9 board (each row/col/3x3 box has no repeated digits).**
```java
static boolean sudoku2(char[][] grid) {
    Set<String> seen = new HashSet<>();
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char val = grid[r][c];
            if (val == '.') continue;
            String row = "r" + r + val, col = "c" + c + val, box = "b" + (r/3) + (c/3) + val;
            if (!seen.add(row) || !seen.add(col) || !seen.add(box)) return false;
        }
    }
    return true;
} // O(1) — fixed 9x9 board, but generalizes to O(n^2)
```

**Q4: `areFollowingPatterns` — check words follow the same equivalence pattern as a pattern array.**
```java
static boolean areFollowingPatterns(String[] strings, String[] patterns) {
    Map<String, String> strToPat = new HashMap<>();
    Map<String, String> patToStr = new HashMap<>();
    for (int i = 0; i < strings.length; i++) {
        String s = strings[i], p = patterns[i];
        if (strToPat.containsKey(s) && !strToPat.get(s).equals(p)) return false;
        if (patToStr.containsKey(p) && !patToStr.get(p).equals(s)) return false;
        strToPat.put(s, p);
        patToStr.put(p, s); // must check both directions for a true bijection
    }
    return true;
} // O(n)
```

---

## 20. CodeSignal Practice — Hard

**Q1: `minimumCostFlowerDelivery` (interval scheduling / greedy with heap).**
> Given delivery windows, minimize total wait — pattern: sort by start time, use a min-heap keyed by end time to track earliest-freeing resource, classic **interval partitioning** (also used for "minimum meeting rooms").
```java
static int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
    PriorityQueue<Integer> endTimes = new PriorityQueue<>(); // min-heap of room end times
    for (int[] interval : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll(); // reuse the room that freed up earliest
        }
        endTimes.offer(interval[1]);
    }
    return endTimes.size(); // O(n log n)
}
```

**Q2: `alienDictionary` — derive character ordering from a sorted word list (topological sort).**
```java
static String alienOrder(String[] words) {
    Map<Character, Set<Character>> graph = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();
    for (String w : words) for (char c : w.toCharArray()) { graph.putIfAbsent(c, new HashSet<>()); inDegree.putIfAbsent(c, 0); }

    for (int i = 0; i < words.length - 1; i++) {
        String w1 = words[i], w2 = words[i + 1];
        int minLen = Math.min(w1.length(), w2.length());
        boolean foundDiff = false;
        for (int j = 0; j < minLen; j++) {
            char c1 = w1.charAt(j), c2 = w2.charAt(j);
            if (c1 != c2) {
                if (graph.get(c1).add(c2)) inDegree.merge(c2, 1, Integer::sum);
                foundDiff = true;
                break;
            }
        }
        if (!foundDiff && w1.length() > w2.length()) return ""; // invalid: prefix must come first
    }

    Queue<Character> queue = new ArrayDeque<>();
    inDegree.forEach((c, deg) -> { if (deg == 0) queue.offer(c); });
    StringBuilder result = new StringBuilder();
    while (!queue.isEmpty()) {
        char c = queue.poll();
        result.append(c);
        for (char next : graph.get(c)) {
            if (inDegree.merge(next, -1, Integer::sum) == 0) queue.offer(next);
        }
    }
    return result.length() == inDegree.size() ? result.toString() : ""; // "" means a cycle exists
} // O(C) where C = total characters across all words — Kahn's algorithm for topological sort
```

**Q3: `wordLadderLength` — shortest transformation sequence length (BFS over implicit graph).**
```java
static int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) return 0;
    Queue<String> queue = new ArrayDeque<>();
    queue.offer(beginWord);
    int steps = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            if (word.equals(endWord)) return steps;
            char[] chars = word.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[j] = c;
                    String next = new String(chars);
                    if (dict.remove(next)) queue.offer(next); // remove = visited, avoids revisiting
                }
                chars[j] = original;
            }
        }
        steps++;
    }
    return 0;
} // O(M^2 * N) where M = word length, N = word list size — BFS gives shortest path in an unweighted graph
```

---

## 21. Mock Interview Script

A self-run 45-minute mock interview structure you can practice against:

**Phase 1 — Warm-up (5 min):** "Tell me about a time you had to choose between two data structures for a performance-sensitive path. What did you pick and why?" — *practice explaining an ArrayList-vs-LinkedList or HashMap-vs-TreeMap trade-off from real experience, tying it to measured impact, not just textbook Big-O.*

**Phase 2 — Coding (20 min):** Pick one cold, without looking at the answer first:
1. Implement an LRU cache from scratch (expect to derive Implementation B above unaided, in ~15 min, then discuss thread-safety as a follow-up).
2. Given a stream of numbers, return the running median.
3. Given a list of intervals, merge overlapping ones.

*Self-grading rubric:* Did you (a) clarify constraints/edge cases before coding (empty input, duplicates, capacity 0)? (b) state complexity before and after writing code? (c) test with a manual trace, not just "looks right"? (d) discuss at least one alternative approach and why you didn't pick it?

**Phase 3 — System/LLD (10 min):** "Design a URL shortener" or "Design a parking lot" — practice narrating your design out loud: requirements clarification → high-level components → data model → scaling bottleneck → how you'd address it. Interviewers weight the *reasoning process* far more than arriving at "the" correct architecture.

**Phase 4 — Behavioral + Deep-dive (10 min):** Be ready to go two levels deep on anything on your resume: "You mentioned Kafka — walk me through what happens when a consumer in your group crashes mid-processing. What guarantees do you have about redelivery, and how did your code handle idempotency?" *If you can't answer a natural follow-up to your own resume line, don't put that line on your resume.*

**Closing tip:** For every "compare X vs Y" question in this guide (ArrayList vs LinkedList, HashMap vs TreeMap, orchestration vs choreography, etc.), practice answering in the same three-part shape: **(1) what each does differently under the hood, (2) the concrete complexity/behavior consequence, (3) a rule of thumb for when you'd pick one over the other.** That structure is what separates a memorized answer from a demonstrated understanding — and it's the same shape used throughout this guide.

---

*End of guide. Good luck!*