# Java 26 Interview Questions & Answers

> A comprehensive Q&A guide covering collections, concurrency, JVM, design patterns, system design, and more — aligned with Java 26 (LTS) features.

---

## Table of Contents

1. [ArrayList vs LinkedList](#1-arraylist-vs-linkedlist)
2. [Vector vs ArrayList](#2-vector-vs-arraylist)
3. [HashMap Internals](#3-hashmap-internals)
4. [LinkedHashMap](#4-linkedhashmap)
5. [TreeMap](#5-treemap)
6. [Hash Collision](#6-hash-collision)
7. [equals() vs hashCode()](#7-equals-vs-hashcode)
8. [HashSet](#8-hashset)
9. [LinkedHashSet](#9-linkedhashset)
10. [TreeSet](#10-treeset)
11. [PriorityQueue](#11-priorityqueue)
12. [ArrayDeque](#12-arraydeque)
13. [Queue vs Deque](#13-queue-vs-deque)
14. [Comparable vs Comparator](#14-comparable-vs-comparator)
15. [Collections.sort()](#15-collectionssort)
16. [Binary Search](#16-binary-search)
17. [Reverse HashMap](#17-reverse-hashmap)
18. [Merge Maps](#18-merge-maps)
19. [Frequency Counter](#19-frequency-counter)
20. [Remove Duplicates](#20-remove-duplicates)
21. [Top-K Elements](#21-top-k-elements)
22. [LRU Cache (3 implementations)](#22-lru-cache-3-implementations)
23. [WeakHashMap](#23-weakhashmap)
24. [IdentityHashMap](#24-identityhashmap)
25. [EnumMap](#25-enummap)
26. [EnumSet](#26-enumset)
27. [CopyOnWriteArrayList](#27-copyonwritearraylist)
28. [ConcurrentHashMap](#28-concurrenthashmap)
29. [BlockingQueue](#29-blockingqueue)
30. [Interview MCQs](#30-interview-mcqs)
31. [JUnit 5 Tests](#31-junit-5-tests)
32. [Real FAANG/Banks Interview Questions](#32-real-faangbanks-interview-questions)
33. [Immutable Collections](#33-immutable-collections)
34. [Collections / Arrays / Strings](#34-collections--arrays--strings)
35. [HashMap & Set](#35-hashmap--set)
36. [Streams](#36-streams)
37. [Recursion & Backtracking](#37-recursion--backtracking)
38. [Linked List / Stack & Queue](#38-linked-list--stack--queue)
39. [Trees / Graphs](#39-trees--graphs)
40. [Dynamic Programming](#40-dynamic-programming)
41. [Concurrency](#41-concurrency)
42. [CompletableFuture](#42-completablefuture)
43. [JVM Internals](#43-jvm-internals)
44. [Design Patterns](#44-design-patterns)
45. [Low-Level Design](#45-low-level-design)
46. [System Design](#46-system-design)
47. [Spring Boot](#47-spring-boot)
48. [Redis](#48-redis)
49. [Kafka](#49-kafka)
50. [Kubernetes](#50-kubernetes)
51. [Microservices](#51-microservices)
52. [CodeSignal Medium / Hard](#52-codesignal-medium--hard)
53. [Mock Interview](#53-mock-interview)

---

## 1. ArrayList vs LinkedList

**Q: What is the core difference between `ArrayList` and `LinkedList`?**

**A:** `ArrayList` is backed by a dynamically resizing array; `LinkedList` is backed by a doubly-linked list.

| Operation | ArrayList | LinkedList |
|---|---|---|
| `get(i)` | O(1) | O(n) |
| `add(e)` (end) | O(1) amortized | O(1) |
| `add(0, e)` | O(n) | O(1) |
| `remove(i)` | O(n) | O(n) to find, O(1) to unlink |
| Memory | Contiguous, less overhead | Node objects with prev/next pointers |
| Iteration | Fast (CPU cache friendly) | Slower (pointer chasing) |

```java
List<Integer> arr = new ArrayList<>(List.of(1, 2, 3));
List<Integer> lnk = new LinkedList<>(List.of(1, 2, 3));
```

**Q: When would you choose LinkedList?**
**A:** Rarely in modern Java. Only when you frequently insert/remove at both ends *and* rarely index by position. Even then, `ArrayDeque` is usually faster.

---

## 2. Vector vs ArrayList

**Q: How does `Vector` differ from `ArrayList`?**

**A:**
- `Vector` is **synchronized** (thread-safe but slow); `ArrayList` is not.
- `Vector` doubles its capacity (2x); `ArrayList` grows by ~1.5x.
- `Vector` is a legacy class from Java 1.0; `ArrayList` was introduced in Java 1.2.
- Prefer `Collections.synchronizedList(new ArrayList<>())` or `CopyOnWriteArrayList` over `Vector`.

**Q: Is `Vector` completely deprecated?**
**A:** Not deprecated, but discouraged. Its `Enumeration` iterator (`elements()`) is legacy; use `Iterator` instead.

---

## 3. HashMap Internals

**Q: Explain the internal structure of `HashMap` in Java 8+.**

**A:** HashMap uses an array of buckets (default 16). Each bucket holds:
- A single entry (or null)
- A linked list if collisions occur
- A **balanced tree (red-black)** when a bucket exceeds `TREEIFY_THRESHOLD` (8) and the array is ≥ `MIN_TREEIFY_CAPACITY` (64)

**Q: What is the put flow?**
**A:**
1. Compute `hash = (key == null) ? 0 : h = key.hashCode() ^ (h >>> 16)` (perturbation to spread bits).
2. `index = (n - 1) & hash` — bucket index (bitwise AND, since n is power of 2).
3. If bucket empty → place node.
4. If hash + key match existing → replace value.
5. Else traverse list/tree, append, treeify if needed.
6. If `size > threshold (capacity * loadFactor, 0.75)` → resize (double capacity, rehash).

**Q: Why is capacity always a power of 2?**
**A:** So `(n - 1) & hash` replaces the slower `%` and distributes bits evenly.

**Q: What is the default load factor and initial capacity?**
**A:** 0.75 and 16. Threshold = 12.

---

## 4. LinkedHashMap

**Q: What does `LinkedHashMap` add over `HashMap`?**
**A:** It maintains a **doubly-linked list** running through all entries, preserving **insertion order** (or access order if `accessOrder=true`).

```java
LinkedHashMap<Integer, String> lhm = new LinkedHashMap<>(16, 0.75f, true); // access order
```

**Q: How do you build an LRU cache with it?**
**A:** Override `removeEldestEntry`:
```java
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cap;
    LRUCache(int cap) { super(cap, 0.75f, true); this.cap = cap; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) {
        return size() > cap;
    }
}
```

---

## 5. TreeMap

**Q: What is `TreeMap`'s underlying structure?**
**A:** A **Red-Black Tree**. Keys must be `Comparable` or a `Comparator` must be supplied.

**Q: Time complexities?**
**A:** `get`, `put`, `remove`, `containsKey` are all **O(log n)**. Iteration is in **sorted key order**.

**Q: Useful methods?**
**A:** `firstKey()`, `lastKey()`, `headMap(k)`, `tailMap(k)`, `subMap(from, to)`, `ceilingKey(k)`, `floorKey(k)`.

---

## 6. Hash Collision

**Q: What is a hash collision?**
**A:** When two distinct keys produce the same bucket index (same `hashCode()` or same `(n-1) & hash`).

**Q: How does HashMap handle collisions?**
**A:**
- Java 7: chaining via linked list → O(n) worst case.
- Java 8+: if a bucket's list exceeds 8 entries and capacity ≥ 64, it converts to a **balanced tree** → O(log n).

**Q: Can two different keys have the same hashCode but be unequal?**
**A:** Yes. `equals()` distinguishes them. That's why both methods must be consistent: equal objects → same hash; same hash ≠ equal objects.

---

## 7. equals() vs hashCode()

**Q: State the contract.**
**A:**
1. **Reflexive**: `a.equals(a)` is true.
2. **Symmetric**: `a.equals(b)` ⇒ `b.equals(a)`.
3. **Transitive**: `a.equals(b)` and `b.equals(c)` ⇒ `a.equals(c)`.
4. **Consistent**: repeated calls return the same result.
5. `a.equals(null)` is false.

**Q: The hashCode contract?**
**A:**
- If `a.equals(b)`, then `a.hashCode() == b.hashCode()`.
- If not equal, hashCodes *may* still be equal (collision).
- Consistent across invocations.

**Q: Why must you override both together?**
**A:** If you override `equals` but not `hashCode`, two "equal" objects may land in different HashMap buckets → duplicates appear. `Objects.equals` + `Objects.hash` is the idiomatic implementation:

```java
@Override public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Person p)) return false;
    return Objects.equals(name, p.name) && age == p.age;
}
@Override public int hashCode() { return Objects.hash(name, age); }
```

---

## 8. HashSet

**Q: How is `HashSet` implemented?**
**A:** It wraps a `HashMap` — elements are stored as **keys** with a dummy `PRESENT` value.

**Q: Time complexities?**
**A:** `add`, `remove`, `contains` are **O(1)** average, O(log n) worst (treeified bucket).

**Q: Does it preserve order?**
**A:** No. Use `LinkedHashSet` for insertion order, `TreeSet` for sorted order.

---

## 9. LinkedHashSet

**Q: What distinguishes `LinkedHashSet`?**
**A:** It's a `HashSet` backed by `LinkedHashMap` — maintains **insertion order** with O(1) operations. Slightly more memory due to the linked list pointers.

---

## 10. TreeSet

**Q: What is `TreeSet`?**
**A:** A `NavigableSet` backed by a `TreeMap` (Red-Black Tree). Elements are **sorted**, no duplicates, O(log n) operations.

```java
TreeSet<Integer> ts = new TreeSet<>(List.of(5, 1, 3));
ts.ceiling(2); // 3
ts.floor(4);   // 3
```

**Q: Does it allow `null`?**
**A:** No — comparing `null` throws `NullPointerException` (since it relies on `compareTo`).

---

## 11. PriorityQueue

**Q: What is `PriorityQueue`?**
**A:** An unbounded, **heap-based** queue (binary min-heap by default). The head is the **least** element per natural ordering or a `Comparator`.

**Q: Complexities?**
**A:** `offer`/`poll` are O(log n); `peek` is O(1); iteration is **not ordered**.

```java
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap
```

**Q: Is it thread-safe?**
**A:** No. Use `PriorityBlockingQueue` for concurrency.

---

## 12. ArrayDeque

**Q: What is `ArrayDeque`?**
**A:** A resizable-array implementation of `Deque` — faster than `Stack` and `LinkedList` for stack/queue use. **No capacity restrictions**, does **not** allow `null`.

**Q: Why prefer it over `Stack`?**
**A:** `Stack` is synchronized (slow) and extends `Vector` (legacy). `ArrayDeque` is unsynchronized and faster.

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

---

## 13. Queue vs Deque

**Q: Difference?**
**A:**
- `Queue` is FIFO: `offer`, `poll`, `peek` at one end.
- `Deque` (Double-Ended Queue) supports both ends: `addFirst`, `addLast`, `removeFirst`, `removeLast`, `peekFirst`, `peekLast`.

`Deque` extends `Queue` — so a `Deque` can be used as a Queue (FIFO via `addLast`/`removeFirst`) or a Stack (LIFO via `push`/`pop`).

---

## 14. Comparable vs Comparator

**Q: Compare the two.**
**A:**

| | Comparable | Comparator |
|---|---|---|
| Package | `java.lang` | `java.util` |
| Method | `compareTo(T)` | `compare(T, T)` |
| Count | One natural ordering | Many external orderings |
| Usage | Modify the class itself | Separate sorting logic |

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

// Comparator
Comparator<Employee> bySalaryDesc = Comparator.comparingInt(Employee::salary).reversed();
```

---

## 15. Collections.sort()

**Q: What algorithm does `Collections.sort()` use?**
**A:** A **modified mergesort** (Timsort) — stable, O(n log n), O(n) auxiliary space. Java 8+ `List.sort()` delegates to `Arrays.sort` for objects.

**Q: Difference between `sort()` and `parallelSort()`?**
**A:** `Arrays.parallelSort` splits the array across multiple ForkJoin pools — faster for large arrays (≥ ~8192 elements), overhead otherwise.

---

## 16. Binary Search

**Q: How do you binary search in Java?**
**A:** Use `Collections.binarySearch(list, key)` or `Arrays.binarySearch(arr, key)`. The collection **must be sorted**. Returns index or `-(insertion point) - 1`.

```java
int idx = Collections.binarySearch(List.of(1,3,5,7), 5); // 2
```

**Q: Implement binary search by hand.**
**A:**
```java
int bs(int[] a, int t) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoid overflow
        if (a[mid] == t) return mid;
        if (a[mid] < t) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
```

---

## 17. Reverse HashMap

**Q: Reverse a `Map<K, V>` into `Map<V, List<K>>` (since values may repeat).**
**A:**
```java
Map<String, Integer> src = Map.of("a", 1, "b", 2, "c", 1);
Map<Integer, List<String>> rev = src.entrySet().stream()
    .collect(Collectors.groupingBy(Map.Entry::getValue,
        Collectors.mapping(Map.Entry::getKey, Collectors.toList())));
```

---

## 18. Merge Maps

**Q: Merge two maps, summing values for common keys.**
**A:**
```java
Map<String, Integer> m1 = Map.of("a", 1, "b", 2);
Map<String, Integer> m2 = Map.of("b", 3, "c", 4);

Map<String, Integer> merged = new HashMap<>(m1);
m2.forEach((k, v) -> merged.merge(k, v, Integer::sum));
// {a=1, b=5, c=4}
```

**Q: Using Streams?**
```java
Stream.of(m1, m2).flatMap(m -> m.entrySet().stream())
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, Integer::sum));
```

---

## 19. Frequency Counter

**Q: Count word frequencies.**
**A:**
```java
Map<String, Long> freq = Arrays.stream(text.split("\\s+"))
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
```

**Q: Imperative version.**
```java
Map<String, Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);
```

---

## 20. Remove Duplicates

**Q: Remove duplicates from a list while preserving order.**
**A:**
```java
List<Integer> uniq = list.stream().distinct().toList(); // Java 16+ toList()
// or
List<Integer> linked = new ArrayList<>(new LinkedHashSet<>(list));
```

---

## 21. Top-K Elements

**Q: Find the K most frequent elements.**
**A:** Use a min-heap of size K:
```java
List<Integer> topK(int[] nums, int k) {
    Map<Integer, Integer> f = new HashMap<>();
    for (int n : nums) f.merge(n, 1, Integer::sum);
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(f::get));
    for (int n : f.keySet()) {
        pq.add(n);
        if (pq.size() > k) pq.poll();
    }
    return new ArrayList<>(pq);
}
```
**Time:** O(n log k). **Space:** O(n + k).

**Alternative (quickselect)** for O(n) average.

---

## 22. LRU Cache (3 implementations)

### (a) LinkedHashMap
```java
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cap;
    LRUCache(int cap) { super(cap, 0.75f, true); this.cap = cap; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > cap; }
}
```

### (b) HashMap + Doubly Linked List
```java
class LRUCache {
    static class Node { int k, v; Node p, n; Node(int k, int v){this.k=k;this.v=v;} }
    private final int cap;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0,0), tail = new Node(0,0);
    LRUCache(int cap){ this.cap=cap; head.n=tail; tail.p=head; }

    public int get(int key){
        if(!map.containsKey(key)) return -1;
        Node n = map.get(key); moveToHead(n); return n.v;
    }
    public void put(int key, int val){
        if(map.containsKey(key)){ Node n=map.get(key); n.v=val; moveToHead(n); return; }
        Node n = new Node(key, val); map.put(key, n); addHead(n);
        if(map.size() > cap){ Node t = tail.p; remove(t); map.remove(t.k); }
    }
    private void addHead(Node n){ n.n=head.n; n.p=head; head.n.p=n; head.n=n; }
    private void remove(Node n){ n.p.n=n.n; n.n.p=n.p; }
    private void moveToHead(Node n){ remove(n); addHead(n); }
}
```

### (c) ConcurrentHashMap + VarHandle (lock-free, advanced)
Use `ConcurrentHashMap` for the map and a CAS-based doubly-linked list with `VarHandle` for atomic pointer swaps. This is the basis of Caffeine-style caches. Generally interviewers accept (a) or (b).

---

## 23. WeakHashMap

**Q: What is `WeakHashMap`?**
**A:** A `Map` whose keys are **weakly referenced** — entries are automatically removed when the key is no longer referenced elsewhere (garbage collected). Useful for **metadata/auxiliary caches** attached to objects.

**Q: When to use?**
**A:** When you want to associate data with an object's lifetime without preventing its GC. Example: `ClassLoader`-specific caches.

---

## 24. IdentityHashMap

**Q: What is `IdentityHashMap`?**
**A:** A `Map` that uses **reference equality** (`==`) instead of `equals()` for key comparison, and `System.identityHashCode` for hashing. Useful for graph traversal, serialization, proxy frameworks.

```java
IdentityHashMap<Object, Object> m = new IdentityHashMap<>();
m.put(new String("a"), 1); m.put(new String("a"), 2); // size = 2
```

---

## 25. EnumMap

**Q: What is `EnumMap`?**
**A:** A specialized `Map` for enum keys — backed by a fixed-size array indexed by `enum.ordinal()`. **O(1)** operations, very compact, no hashing.

```java
enum Day { MON, TUE, WED }
EnumMap<Day, String> m = new EnumMap<>(Day.class);
m.put(Day.MON, "Work");
```

---

## 26. EnumSet

**Q: What is `EnumSet`?**
**A:** A specialized `Set` for enum elements, internally a **bit vector** (regular/long flags). Extremely fast union/intersection. Not synchronized.

```java
EnumSet.of(Day.MON, Day.WED);
```

---

## 27. CopyOnWriteArrayList

**Q: How does `CopyOnWriteArrayList` work?**
**A:** Every mutation (`add`, `set`, `remove`) **copies the entire backing array**. Reads are lock-free and fast. Best for **read-heavy, write-rare** event-listener scenarios.

**Q: Iterator semantics?**
**A:** It's a **snapshot** — never throws `ConcurrentModificationException`, doesn't reflect subsequent modifications, and doesn't support `remove()`.

---

## 28. ConcurrentHashMap

**Q: How is it different from `HashMap` with synchronization?**
**A:** It uses **bucket-level locking** (striped locks in Java 7; per-node CAS + `synchronized` on the first node in Java 8+). Reads are fully lock-free.

**Q: Null keys/values?**
**A:** **Not allowed** — avoids ambiguity in concurrent reads (can't distinguish "absent" from "value being computed").

**Q: What is `computeIfAbsent`?**
**A:** Atomic insert-if-absent — commonly used for concurrent memoization:
```java
map.computeIfAbsent(key, k -> expensive(k));
```

---

## 29. BlockingQueue

**Q: What is a `BlockingQueue`?**
**A:** A `Queue` that **blocks** producers when full and consumers when empty — used for producer-consumer patterns.

| Implementation | Behavior |
|---|---|
| `ArrayBlockingQueue` | Bounded, array-backed, FIFO |
| `LinkedBlockingQueue` | Optionally bounded, linked nodes |
| `PriorityBlockingQueue` | Unbounded, heap-ordered |
| `SynchronousQueue` | Zero-capacity handoff |
| `DelayQueue` | Elements available after a delay |

```java
BlockingQueue<Task> q = new ArrayBlockingQueue<>(100);
q.put(task);      // blocks if full
Task t = q.take(); // blocks if empty
```

---

## 30. Interview MCQs

**Q1. Which is thread-safe?**
a) HashMap  b) TreeMap  c) ConcurrentHashMap  d) LinkedHashMap
**Ans:** c

**Q2. Default initial capacity of HashMap?**
a) 8  b) 16  c) 32  d) 64
**Ans:** b

**Q3. Which collection allows null key and values?**
a) Hashtable  b) ConcurrentHashMap  c) HashMap  d) TreeMap (one null key)
**Ans:** c (TreeMap allows one null key only if using natural ordering of a Comparable that supports it — but generally discouraged)

**Q4. `PriorityQueue` is based on?**
a) Sorted array  b) Binary heap  c) Red-black tree  d) Linked list
**Ans:** b

**Q5. Which is ordered by insertion?**
a) HashSet  b) LinkedHashSet  c) TreeSet  d) EnumSet
**Ans:** b

**Q6. `ArrayDeque` does NOT allow?**
a) duplicates  b) null  c) generics  d) iteration
**Ans:** b

**Q7. `Collections.synchronizedList` returns a list that is synchronized on?**
a) itself  b) the original list  c) a private lock  d) the iterator
**Ans:** a — it synchronizes on the wrapper object.

**Q8. `TreeMap`'s underlying structure?**
a) AVL tree  b) Red-black tree  c) B-tree  d) Trie
**Ans:** b

---

## 31. JUnit 5 Tests

**Q: Write a JUnit 5 test for a `Stack`.**
```java
import org.junit.jupiter.api.*;
import static org.junit.jupiter.api.Assertions.*;

class StackTest {
    Deque<Integer> s;
    @BeforeEach void setUp(){ s = new ArrayDeque<>(); }

    @Test void pushPop(){
        s.push(1); s.push(2);
        assertEquals(2, s.pop());
        assertEquals(1, s.pop());
    }

    @Test void emptyPopThrows(){
        assertThrows(NoSuchElementException.class, s::pop);
    }

    @ParameterizedTest
    @ValueSource(ints = {1, 5, 100})
    void pushIncreasesSize(int n){
        s.push(n);
        assertEquals(1, s.size());
    }
}
```

**Q: Key JUnit 5 annotations?**
**A:** `@Test`, `@BeforeEach`, `@AfterEach`, `@BeforeAll`, `@AfterAll`, `@ParameterizedTest`, `@DisplayName`, `@Nested`, `@Disabled`, `@Tag`.

---

## 32. Real FAANG/Banks Interview Questions

### Top K Elements
**Q (Amazon):** Given a non-empty array of integers, return the K most frequent elements.
**A:** See §21.

### LRU Cache
**Q (Google, Microsoft):** Design and implement an LRU cache with O(1) get/put.
**A:** See §22.

### Immutable Collections
**Q (JPMorgan):** Why use `List.copyOf()`? Can you mutate it?
**A:** `List.copyOf` returns an **unmodifiable** snapshot. Mutator calls throw `UnsupportedOperationException`. Useful for sharing internal state safely.

---

## 33. Immutable Collections

**Q: How do you create immutable collections in Java 9+?**
**A:**
```java
List<Integer> l = List.of(1, 2, 3);
Set<String>  s = Set.of("a", "b");
Map<String,Integer> m = Map.of("a", 1, "b", 2);
Map.Entry<String,Integer> e = Map.entry("c", 3);
Map<String,Integer> m2 = Map.ofEntries(e);
```
**Q: Java 10+ `List.copyOf`?**
**A:** Returns an unmodifiable copy of an existing collection.

**Q: Are these truly immutable?**
**A:** Shallowly — the collection itself is unmodifiable, but contained objects may still mutate.

---

## 34. Collections / Arrays / Strings

**Q: Convert array to List and back.**
```java
List<Integer> l = Arrays.asList(1,2,3);          // fixed-size
List<Integer> l2 = new ArrayList<>(Arrays.asList(arr));
Integer[] arr = l.toArray(new Integer[0]);
```

**Q: Reverse a string.**
```java
new StringBuilder(s).reverse().toString();
// or
String r = "";
for (int i = s.length()-1; i >= 0; i--) r += s.charAt(i);
```

**Q: Check anagram.**
```java
boolean anagram(String a, String b){
    if (a.length() != b.length()) return false;
    char[] x = a.toCharArray(), y = b.toCharArray();
    Arrays.sort(x); Arrays.sort(y);
    return Arrays.equals(x, y);
}
```

---

## 35. HashMap & Set

**Q: Count distinct pairs with a given sum.**
```java
int countPairs(int[] a, int target){
    Set<Integer> seen = new HashSet<>();
    int c = 0;
    for (int x : a){
        if (seen.contains(target - x)) c++;
        seen.add(x);
    }
    return c;
}
```

---

## 36. Streams

**Q: Top 3 salaries per department.**
```java
Map<String, List<Employee>> top3 = employees.stream()
    .collect(Collectors.groupingBy(
        Employee::dept,
        Collectors.collectingAndThen(
            Collectors.toList(),
            l -> l.stream().sorted(Comparator.comparingInt(Employee::salary).reversed())
                 .limit(3).toList())));
```

**Q: Group by + average.**
```java
Map<String, Double> avg = employees.stream()
    .collect(Collectors.groupingBy(Employee::dept,
        Collectors.averagingDouble(Employee::salary)));
```

**Q: Partition even/odd.**
```java
Map<Boolean, List<Integer>> p = nums.stream()
    .collect(Collectors.partitioningBy(n -> n % 2 == 0));
```

---

## 37. Recursion & Backtracking

**Q: Generate all subsets.**
```java
List<List<Integer>> subsets(int[] a){
    List<List<Integer>> r = new ArrayList<>();
    bt(a, 0, new ArrayList<>(), r);
    return r;
}
void bt(int[] a, int i, List<Integer> cur, List<List<Integer>> r){
    if (i == a.length){ r.add(new ArrayList<>(cur)); return; }
    bt(a, i+1, cur, r);                 // exclude
    cur.add(a[i]); bt(a, i+1, cur, r);  // include
    cur.remove(cur.size()-1);
}
```

**Q: Permutations.**
```java
void perm(int[] a, int idx, List<List<Integer>> r){
    if (idx == a.length){ r.add(toList(a)); return; }
    for (int i = idx; i < a.length; i++){
        swap(a, i, idx); perm(a, idx+1, r); swap(a, i, idx);
    }
}
```

---

## 38. Linked List / Stack & Queue

**Q: Reverse a singly linked list.**
```java
ListNode rev(ListNode h){
    ListNode prev = null;
    while (h != null){ ListNode n = h.next; h.next = prev; prev = h; h = n; }
    return prev;
}
```

**Q: Detect cycle.**
```java
boolean hasCycle(ListNode h){
    ListNode s = h, f = h;
    while (f != null && f.next != null){
        s = s.next; f = f.next.next;
        if (s == f) return true;
    }
    return false;
}
```

**Q: Valid parentheses using stack.**
```java
boolean valid(String s){
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()){
        if ("({[".indexOf(c) >= 0) st.push(c);
        else if (st.isEmpty() || !match(st.pop(), c)) return false;
    }
    return st.isEmpty();
}
```

---

## 39. Trees / Graphs

**Q: Inorder traversal (iterative).**
```java
void inorder(TreeNode r){
    Deque<TreeNode> st = new ArrayDeque<>();
    while (r != null || !st.isEmpty()){
        while (r != null){ st.push(r); r = r.left; }
        r = st.pop(); visit(r); r = r.right;
    }
}
```

**Q: BFS shortest path.**
```java
int bfs(Map<Integer, List<Integer>> g, int src, int dst){
    Deque<Integer> q = new ArrayDeque<>(); q.offer(src);
    Set<Integer> seen = new HashSet<>(Set.of(src));
    int d = 0;
    while (!q.isEmpty()){
        for (int sz = q.size(); sz > 0; sz--){
            int u = q.poll();
            if (u == dst) return d;
            for (int v : g.getOrDefault(u, List.of()))
                if (seen.add(v)) q.offer(v);
        }
        d++;
    }
    return -1;
}
```

---

## 40. Dynamic Programming

**Q: Climbing stairs.**
```java
int climb(int n){
    if (n < 3) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++){ int c = a + b; a = b; b = c; }
    return b;
}
```

**Q: Longest common subsequence.**
```java
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()];
}
```

---

## 41. Concurrency

**Q: Create a thread-safe singleton.**
```java
class Singleton {
    private static volatile Singleton inst;
    private Singleton(){}
    public static Singleton get(){
        if (inst == null) synchronized (Singleton.class){
            if (inst == null) inst = new Singleton();
        }
        return inst;
    }
}
```

**Q: Producer-consumer with `BlockingQueue`.**
```java
BlockingQueue<Integer> q = new LinkedBlockingQueue<>(10);
Runnable prod = () -> { while(true){ q.put(produce()); } };
Runnable cons = () -> { while(true){ consume(q.take()); } };
```

**Q: `synchronized` vs `ReentrantLock`.**
**A:** `ReentrantLock` supports fairness, tryLock with timeout, interruptible locks, and multiple condition variables. `synchronized` is simpler and releases automatically.

---

## 42. CompletableFuture

**Q: Compose two async calls.**
```java
CompletableFuture<Integer> f1 = CompletableFuture.supplyAsync(() -> fetchA());
CompletableFuture<Integer> f2 = CompletableFuture.supplyAsync(() -> fetchB());
CompletableFuture<Integer> sum = f1.thenCombine(f2, Integer::sum);
```

**Q: Pipeline with error handling.**
```java
CompletableFuture.supplyAsync(() -> load(id))
    .thenApply(this::enrich)
    .thenAccept(this::save)
    .exceptionally(ex -> { log.error(ex); return null; });
```

**Q: Wait for all / any.**
```java
CompletableFuture.allOf(f1, f2, f3).join();
CompletableFuture.anyOf(f1, f2, f3).join();
```

---

## 43. JVM Internals

**Q: JVM memory areas?**
**A:** Method area (metaspace), heap, stack, PC register, native method stack.

**Q: Describe the class loading process.**
**A:** Loading → Linking (verify, prepare, resolve) → Initialization. Classloaders follow **parent delegation**.

**Q: Garbage collection algorithms?**
**A:** Serial, Parallel, G1 (default since Java 9), ZGC (low-latency, sub-ms pauses in Java 21+), Shenandoah.

**Q: Difference between `==` and `equals()`?**
**A:** `==` compares references (for objects) or primitive values; `equals()` compares logical content (overridable).

---

## 44. Design Patterns

**Q: Singleton, Builder, Factory, Strategy, Observer — give one-line each.**
- **Singleton**: one instance, global access.
- **Builder**: step-by-step construction of complex objects.
- **Factory Method**: define an interface for creating objects, let subclasses decide.
- **Strategy**: interchangeable algorithms behind a common interface.
- **Observer**: subjects notify subscribers of state changes.

**Q: Example — Strategy for sorting.**
```java
interface Sorter { void sort(List<Integer> l); }
class BubbleSort implements Sorter { ... }
class QuickSort implements Sorter { ... }
class Context { private Sorter s; Context(Sorter s){this.s=s;} void run(List<Integer> l){ s.sort(l);} }
```

---

## 45. Low-Level Design

**Q: Design a Parking Lot.**
**A:**
- Classes: `ParkingLot`, `Level`, `ParkingSpot`, `Vehicle`, `Ticket`, `Payment`.
- Spot types: `Motorcycle`, `Compact`, `Large`.
- Vehicle enters → `findSpot()` → issue ticket → on exit, compute fee → pay.
- Use `enum` for spot type and vehicle type; `Strategy` for pricing.

**Q: Design an Elevator system.**
**A:** `Elevator`, `Floor`, `Request`, `Dispatcher` (strategy: FCFS, SCAN, LOOK). State machine for `Door`, `Moving`, `Idle`.

---

## 46. System Design

**Q: Design URL Shortener (TinyURL).**
**A:**
- API: `POST /shorten` → returns short URL; `GET /{code}` → 302 redirect.
- ID generation: base62 of a counter (or hash + collision check).
- Storage: `short_code → long_url, metadata` in a KV store (DynamoDB/Cassandra).
- Cache: Redis for hot URLs.
- Scale: sharded by code prefix; CDN for redirects.

**Q: Design Twitter/News Feed.**
**A:**
- Fan-out on write vs fan-out on read (hybrid for celebrities).
- Timeline service + Tweet service + User graph service.
- Push to Redis list per user; pull on demand for large accounts.

---

## 47. Spring Boot

**Q: What is auto-configuration?**
**A:** Spring Boot inspects the classpath and beans, then registers sensible defaults via `@ConditionalOnClass`, `@ConditionalOnMissingBean`, etc. Configured in `META-INF/spring/org.springframework.boot.autoconfigure.AutoConfiguration.imports`.

**Q: Key annotations?**
**A:** `@SpringBootApplication` (= `@Configuration` + `@EnableAutoConfiguration` + `@ComponentScan`), `@RestController`, `@RequestMapping`, `@Service`, `@Repository`, `@Configuration`, `@Bean`.

**Q: Difference between `@Component`, `@Service`, `@Repository`, `@Controller`?**
**A:** All are stereotypes detected by component scan. `@Repository` adds persistence exception translation; `@Controller` is for MVC; `@Service` is a marker for service-layer beans.

**Q: How do you handle transactions?**
**A:** `@Transactional` (rollback for `RuntimeException` by default; propagation `REQUIRED`).

---

## 48. Redis

**Q: Common data types?**
**A:** String, List, Hash, Set, Sorted Set (ZSet), Stream, Bitmap, HyperLogLog.

**Q: Use cases?**
**A:** Cache, session store, rate limiter (INCR + EXPIRE), leaderboards (ZSet), pub/sub, distributed locks (Redlock).

**Q: Cache penetration / avalanche / breakdown?**
- **Penetration**: queries for non-existent keys → use bloom filter or cache null.
- **Avalanche**: many keys expire at once → stagger TTLs.
- **Breakdown**: hot key expires, stampede → mutex lock or "never expire" + async refresh.

---

## 49. Kafka

**Q: Core concepts?**
**A:** Producer, Consumer, Broker, Topic, Partition, Offset, Consumer Group, Replica, ISR.

**Q: How does Kafka achieve high throughput?**
**A:** Sequential disk I/O, zero-copy send, partitioned parallelism, batched/compressed messages.

**Q: At-least-once vs exactly-once?**
**A:** Default is at-least-once. Exactly-once requires idempotent producer + transactional consumer (`isolation.level=read_committed`).

**Q: How to order messages?**
**A:** Use a single partition per key — same key always goes to the same partition, preserving order within that key.

---

## 50. Kubernetes

**Q: Core objects?**
**A:** Pod, Deployment, Service, ConfigMap, Secret, Ingress, StatefulSet, DaemonSet, Job, CronJob.

**Q: Service types?**
**A:** ClusterIP (default, internal), NodePort, LoadBalancer, ExternalName, Headless.

**Q: Liveness vs Readiness vs Startup probes?**
- **Liveness**: restart container if failed.
- **Readiness**: remove pod from service endpoints if failed.
- **Startup**: gate liveness/readiness until app is up (slow-start apps).

**Q: How does a Deployment roll out?**
**A:** Creates a new ReplicaSet, scales it up while scaling down the old one — configurable via `maxSurge` and `maxUnavailable`.

---

## 51. Microservices

**Q: Key patterns?**
**A:** API Gateway, Service Discovery, Circuit Breaker (Resilience4j), Saga (choreography/orchestration), CQRS, Event Sourcing, BFF, Sidecar.

**Q: How do services communicate?**
**A:** REST (synchronous), gRPC (high-perf RPC), async messaging (Kafka/RabbitMQ).

**Q: How do you handle distributed transactions?**
**A:** Avoid 2PC across services. Use **Saga** with compensating transactions, or outbox pattern for reliable event publishing.

**Q: Observability triad?**
**A:** Logs (ELK), Metrics (Prometheus + Grafana), Traces (OpenTelemetry, Jaeger).

---

## 52. CodeSignal Medium / Hard

### Medium — First Not Repeating Character
```java
char firstNonRepeating(String s){
    int[] c = new int[26];
    for (char x : s.toCharArray()) c[x - 'a']++;
    for (char x : s.toCharArray()) if (c[x - 'a'] == 1) return x;
    return '_';
}
```

### Medium — Sum of Two
```java
boolean sumOfTwo(int[] a, int[] b, int v){
    Set<Integer> s = new HashSet<>();
    for (int x : a) s.add(v - x);
    for (int y : b) if (s.contains(y)) return true;
    return false;
}
```

### Hard — Smallest Missing Positive (cycle sort)
```java
int firstMissingPositive(int[] a){
    for (int i = 0; i < a.length; i++)
        while (a[i] > 0 && a[i] <= a.length && a[a[i]-1] != a[i])
            swap(a, i, a[i]-1);
    for (int i = 0; i < a.length; i++) if (a[i] != i+1) return i+1;
    return a.length + 1;
}
```

---

## 53. Mock Interview

**Scenario (45 min, Senior Java Backend):**

> "Design an in-memory rate limiter library that supports token bucket and sliding window algorithms, thread-safe, pluggable storage."

**Discussion outline:**
1. **Requirements**: per-user limits, multiple algorithms, low latency, thread-safe, extensible.
2. **API**: `RateLimiter limiter = RateLimiter.builder().algorithm(Algorithm.TOKEN_BUCKET).capacity(100).refillPerSec(10).build(); boolean allow = limiter.tryAcquire("user-1");`
3. **Design**:
   - `RateLimiter` interface → `tryAcquire(key)`.
   - `TokenBucketLimiter`, `SlidingWindowLimiter` implementations (Strategy pattern).
   - `Storage` interface → `InMemoryStorage` (ConcurrentHashMap), `RedisStorage` for distributed.
   - Use `ConcurrentHashMap<String, AtomicLong>` or `synchronized` per key for thread safety.
4. **Edge cases**: clock drift, hot keys, cold start, distributed coordination.
5. **Testing**: JUnit 5 with `@ParameterizedTest` over algorithms; concurrency test with `CountDownLatch` + `ExecutorService`.
6. **Follow-ups**: how to scale to 1M QPS? → Redis + Lua script for atomic check-and-decrement.

**Sample skeleton:**
```java
public interface RateLimiter {
    boolean tryAcquire(String key);
    static Builder builder(){ return new Builder(); }
}

public class TokenBucketLimiter implements RateLimiter {
    private final int capacity, refillPerSec;
    private final Storage store;
    // ... constructor ...
    public boolean tryAcquire(String key){
        return store.tokenBucket(key, capacity, refillPerSec);
    }
}
```

**Closing tip:** Always clarify requirements (single vs distributed, hard vs soft limits, burst tolerance) before coding — interviewers reward this.

---

### End of Guide

> Compiled for Java 26 LTS. Practice by re-implementing each snippet from memory — that's the fastest path to fluency.