☕ Java Backend Interview Prep

Java Collections
Master Reference for 3-Year Experience Level
50 Questions · Basic → Intermediate → Advanced · Code Examples · Real-World Scenarios

How to Use This Document

Each card shows the question, a structured answer, runnable code, and an interviewer tip with follow-ups.
Difficulty is colour-coded:
• Basic — ArrayList internals, iteration, equals/hashCode: every candidate must know cold.
• Intermediate — HashMap internals, TreeMap, LinkedHashMap, Comparator, Collections utility.
• Advanced — WeakHashMap, EnumMap, NavigableMap, IdentityHashMap, fail-fast vs fail-safe, custom
implementations.

Section 1 — Collection Hierarchy & Core Interfaces (Q1–Q15)

These questions form the baseline. If you cannot answer them fluently, nothing else matters.

Q1 What is the Java Collections Framework? Describe the core hierarchy. [Basic] [Basic]

Answer:
The Java Collections Framework (JCF) is a unified architecture for storing and manipulating groups of
objects. It provides interfaces, implementations, and algorithms.
Core interfaces and their purpose:
Collection — root interface. Represents a group of objects (elements). Subtypes: List, Set, Queue.
List — ordered, allows duplicates. Indexed access. Implementations: ArrayList, LinkedList, Vector,
Stack.
Set — no duplicates. Models mathematical set. Implementations: HashSet, LinkedHashSet, TreeSet.
Queue — FIFO ordering. Implementations: LinkedList, PriorityQueue, ArrayDeque.
Deque — double-ended queue. Implementations: ArrayDeque, LinkedList.
Map — key-value pairs. NOT a Collection subtype. Implementations: HashMap, LinkedHashMap,
TreeMap, Hashtable.

Code Example:
// Collection hierarchy (simplified):
Collection<E>
├── List<E> → ArrayList, LinkedList, Vector
├── Set<E> → HashSet, LinkedHashSet, TreeSet
└── Queue<E> → PriorityQueue, ArrayDeque

Map<K,V> → HashMap, LinkedHashMap, TreeMap

// Iterable is above Collection — all collections support for-each

for (String s : list) { } // uses Iterator internally
💡 Interviewer Tip:
Map is NOT a Collection — it never extended Collection. Interviewers often ask 'Why does Map not
implement Collection?' Answer: because Map's nature (key-value pairs) doesn't fit the single-element
contract of [Link](E).

Q2 What is the difference between ArrayList and LinkedList? [Basic] [Basic]

Answer:
Both implement List but use completely different internal data structures with different performance
profiles.
ArrayList: backed by a dynamic array. Random access is O(1) — index directly into the array.
Insertion/deletion at arbitrary positions is O(n) — all subsequent elements must shift. Amortized O(1)
appends at the end (doubling resize: 10 → 15 → 22 → ...).
LinkedList: doubly-linked list of Node objects. No random access — traversal is O(n).
Insertion/deletion at head/tail is O(1). Insertion at arbitrary position given an iterator reference is O(1)
but finding the position is O(n).
Memory: ArrayList is more cache-friendly (contiguous memory). LinkedList has per-node overhead
(~40 bytes: data + prev + next pointers).
Rule of thumb: use ArrayList for almost everything. Use LinkedList only if you're doing frequent
insertions/deletions at the head (queue operations).

Code Example:
// ArrayList: fast indexed access
ArrayList<String> list = new ArrayList<>(16); // pre-size to avoid resizes
[Link](0); // O(1)
[Link](0, 'x'); // O(n) — shifts all elements right
[Link]('x'); // amortized O(1) — appends at end

// LinkedList: fast head/tail ops

LinkedList<String> ll = new LinkedList<>();
[Link]('x'); // O(1)
[Link]('x'); // O(1)
[Link](500); // O(n) — must traverse 500 nodes

💡 Interviewer Tip:
Common trap: 'LinkedList is faster for insertions.' Only true for insertions at known positions (head/tail).
For random insertions, you still pay O(n) to find the position. In practice, ArrayList's cache locality
makes it faster even for insertions unless the list is very large.

Q3 How does ArrayList resize internally? What is the initial capacity? [Basic] [Basic]

Answer:
ArrayList uses a backing Object[] array. When capacity is exhausted during add(), it creates a new
array of size = oldCapacity * 1.5 (specifically: oldCapacity + (oldCapacity >> 1)) and copies all
elements using [Link]() (which calls [Link]() natively).
Default initial capacity: 10. But the array is NOT allocated until the first add() when using the no-arg
constructor (lazy allocation since Java 8). Passing initial capacity of 0 allocates on first add.
Why 1.5x growth? It's a balance — 2x growth (like some other languages) wastes more memory; too
small a factor causes frequent copies. Java chose 1.5x.
Performance implication: if you know the target size, always pre-size: new
ArrayList<>(expectedSize). This avoids all intermediate array allocations and copies.

Code Example:
// Internal growth: capacity after each resize from 10
// 10 → 15 → 22 → 33 → 49 → 73 → ...

// Pre-size to avoid resize copies

ArrayList<String> list = new ArrayList<>(10_000);

// Trim excess capacity after bulk load

[Link](); // shrinks backing array to [Link]()

// Force capacity without adding elements

[Link](50_000);

💡 Interviewer Tip:
Follow-up: 'What is the growth factor?' 1.5x. Many candidates say 2x (that's Java's old Vector). The
shift operator trick (oldCapacity >> 1) achieves 1.5x without floating point. Knowing this shows you've
read the JDK source.

Q4 How does HashMap work internally? What is hashing? [Basic] [Basic]

Answer:
HashMap is backed by an array of 'buckets' (Node[] table). Each bucket is a linked list (Java 7) or
linked list that converts to a red-black tree when it grows beyond 8 entries (Java 8+).
Put operation: (1) call [Link](), (2) spread hash bits: h ^ (h >>> 16) — spreads high bits into
low bits to improve distribution, (3) compute bucket index: (n-1) & hash where n = table length (always
a power of 2), (4) if bucket empty, insert; if occupied, traverse the chain checking equals() for the same
key.
Get operation: same hash + index calculation, traverse bucket chain comparing equals().
Load factor (default 0.75): when size > capacity * loadFactor, the table rehashes — doubles capacity
and redistributes all entries. This is O(n) but amortized.
Default initial capacity: 16 (always a power of 2 for the bitwise index trick).

Code Example:
// Bucket index calculation (simplified from JDK source)
int hash = [Link]();
hash = hash ^ (hash >>> 16); // spread high bits
int index = (n - 1) & hash; // n is always power of 2

// Java 8: linked list → red-black tree at bucket size 8

// Reverts to linked list when bucket size drops below 6

// Pre-size HashMap to avoid rehashing

// For 1000 entries at 0.75 load: capacity = 1000/0.75 ≈ 1334 → next power of 2 =
2048
Map<String,Integer> map = new HashMap<>(2048);

💡 Interviewer Tip:
The Java 8 treeification (TREEIFY_THRESHOLD = 8) is a critical upgrade. It prevents O(n) worst-case
gets when many keys collide in the same bucket (hash DoS attack). Before Java 8, malicious inputs
could force all keys into one bucket, degrading HashMap to O(n).
 What are the contracts for equals() and hashCode()? Why do both matter for
Q5
HashMap? [Basic] [Basic]

Answer:
equals() contract: reflexive ([Link](x)), symmetric ([Link](y) → [Link](x)), transitive, consistent,
and [Link](null) == false.
hashCode() contract: objects that are equals() MUST have the same hashCode(). Objects with the
same hashCode() need NOT be equals() (collision is allowed).
Why both matter for HashMap: HashMap uses hashCode() to find the bucket, then equals() to find
the exact key within that bucket. If you override equals() without hashCode(), two 'equal' objects hash
to different buckets — [Link]() will return null even though the key appears to be present.
If hashCode() always returns constant: all keys collide into one bucket — HashMap degrades to
O(n). Technically correct but catastrophically slow.

Code Example:
// BROKEN: equals overridden but hashCode not — HashMap breaks
class Point {
int x, y;
@Override public boolean equals(Object o) { ... }
// No hashCode override!
}
Map<Point, String> map = new HashMap<>();
[Link](new Point(1,1), 'A');
[Link](new Point(1,1)); // returns null! Different hashCode → different bucket

// CORRECT: both overridden consistently

@Override public int hashCode() { return [Link](x, y); }
@Override public boolean equals(Object o) {
if (!(o instanceof Point p)) return false;
return x == p.x && y == p.y;
}

💡 Interviewer Tip:
Interviewers love: 'What if I only override hashCode but not equals?' Then two distinct objects that
should be equal (same content) won't match in equals() — HashMap treats them as different keys.
You'll silently insert duplicate logical keys.

Q6 What is the difference between HashSet, LinkedHashSet, and TreeSet? [Basic] [Basic]

Answer:
All three implement Set (no duplicates) but differ in ordering and performance.
HashSet: backed by a HashMap. No ordering guarantee. O(1) add/contains/remove (amortized). Null
allowed. Best general-purpose Set.
LinkedHashSet: backed by a LinkedHashMap. Maintains insertion order. O(1) operations. Slightly
higher memory than HashSet (linked list of entries). Use when you need predictable iteration order.
TreeSet: backed by a TreeMap (red-black tree). Elements stored in natural order (Comparable) or by
provided Comparator. O(log n) for all operations. No null (unless Comparator handles it). Provides
navigation methods: first(), last(), headSet(), tailSet(), floor(), ceiling().

Code Example:
// HashSet — no order
Set<String> h = new HashSet<>([Link]('C','A','B'));
// Iteration order: unpredictable
 // LinkedHashSet — insertion order
Set<String> lhs = new LinkedHashSet<>([Link]('C','A','B'));
// Iteration: C, A, B (insertion order preserved)

// TreeSet — sorted order

Set<String> ts = new TreeSet<>([Link]('C','A','B'));
// Iteration: A, B, C (natural order)
String first = [Link](); // A
Set<String> sub = [Link]('B'); // [A]
String ceil = [Link]('BB'); // C (smallest >= BB)

💡 Interviewer Tip:
TreeSet uses Comparator or Comparable for BOTH ordering AND equality. If compareTo() returns 0,
elements are considered duplicates — even if equals() returns false. This is a subtle bug source when
using custom Comparators.

What is the difference between HashMap and TreeMap? When would you use each?
Q7
[Basic] [Basic]

Answer:
HashMap: hash-based storage. O(1) average get/put. No ordering. Allows one null key, multiple null
values. Best for most key-value use cases.
TreeMap: red-black tree. O(log n) get/put. Keys stored in sorted order (Comparable or Comparator).
No null keys (throws NullPointerException). Multiple null values allowed.
TreeMap-only operations (NavigableMap interface): firstKey()/lastKey(), lowerKey()/higherKey(),
floorKey()/ceilingKey(), headMap(toKey)/tailMap(fromKey)/subMap(from,to), descendingMap().
Use HashMap for general caching, frequency counting, index lookups. Use TreeMap when you need
sorted order, range queries, or navigation (e.g., 'find all keys between A and M').

Code Example:
// HashMap: O(1), unordered
Map<String, Integer> freq = new HashMap<>();
[Link]('apple', 1, Integer::sum); // count words

// TreeMap: O(log n), sorted — use for range queries

TreeMap<Integer, String> scheduleMap = new TreeMap<>();
[Link](9, 'standup');
[Link](14, 'review');
[Link](17, 'sync');

// Find next meeting after 10am

[Link]<Integer, String> next = [Link](10);
// Returns: 14=review

// All meetings between 12 and 16

SortedMap<Integer,String> afternoon = [Link](12, 16);

💡 Interviewer Tip:
TreeMap vs sorting a HashMap: don't sort a HashMap by keys just for a one-time print. TreeMap
keeps keys sorted continuously — insert-time cost is O(log n), but you never need a manual sort. Use
TreeMap when the sorted invariant must always hold.

Q8 What is fail-fast vs fail-safe iteration? [Intermediate] [Intermediate]

Answer:
Fail-fast iterators detect structural modifications to the collection during iteration and immediately
throw ConcurrentModificationException. They track a modCount counter — incremented on every
structural change. The iterator checks modCount on each next() call.
Fail-safe iterators operate on a snapshot or use concurrent data structures. No
ConcurrentModificationException. May return stale data.
Fail-fast collections: ArrayList, HashMap, HashSet, LinkedList — all standard [Link] collections. The
iterator is 'fail-fast' to alert you of programming errors (modifying while iterating).
Fail-safe collections: CopyOnWriteArrayList (iterates a snapshot copy), ConcurrentHashMap (weakly
consistent iterator — may reflect concurrent insertions/deletions).

Code Example:
// Fail-fast: ConcurrentModificationException
List<String> list = new ArrayList<>([Link]('a','b','c'));
for (String s : list) {
[Link](s); // throws ConcurrentModificationException!
}

// Fix 1: use [Link]()

Iterator<String> it = [Link]();
while ([Link]()) {
if ([Link]().equals('b')) [Link](); // safe — iterator tracks its own mods
}

// Fix 2: use removeIf (Java 8+, preferred)

[Link](s -> [Link]('b'));

// Fail-safe: CopyOnWriteArrayList — no exception, reads snapshot

List<String> cowList = new CopyOnWriteArrayList<>([Link]('a','b','c'));
for (String s : cowList) { [Link](s); } // no exception

💡 Interviewer Tip:
Interviewers expect you to know the fix: [Link](), removeIf(), or collect-then-remove. Never
modify a fail-fast collection inside a for-each loop directly. Also: the modCount check is a 'best-effort'
detection — not a memory model guarantee — so it's possible (though rare) to miss it under
concurrency.

Q9 What is the difference between Comparable and Comparator? [Basic] [Basic]

Answer:
Comparable<T> ([Link]): a class implements this to define its natural ordering. The class itself
defines how its instances are compared. One compareTo() method. Used by [Link](),
TreeSet, TreeMap by default.
Comparator<T> ([Link]): an external strategy for comparison. Separates sorting logic from the class.
Multiple Comparators can exist for the same class (sort by name, sort by age, sort by salary). Passed
as a parameter to sort methods or collection constructors.
Java 8 Comparator additions: [Link](), thenComparing(), reversed(), naturalOrder(),
nullsFirst(), nullsLast(). These enable fluent chaining for complex sort orders.

Code Example:
// Comparable: natural ordering inside the class
class Employee implements Comparable<Employee> {
String name; int salary;
@Override public int compareTo(Employee o) {
return [Link]([Link], [Link]); // natural = by salary
 }
}
[Link](employees); // uses compareTo

// Comparator: external, flexible, composable

Comparator<Employee> byName = [Link](Employee::getName);
Comparator<Employee> bySalaryDesc =
[Link](Employee::getSalary).reversed();
Comparator<Employee> complex = Comparator
.comparing(Employee::getDepartment)
.thenComparing(Employee::getName)
.thenComparingInt(Employee::getSalary).reversed();

[Link](complex); // inline Comparator

TreeSet<Employee> ts = new TreeSet<>(byName); // TreeSet with custom order

💡 Interviewer Tip:
compareTo() must be consistent with equals() for correct TreeMap/TreeSet behaviour — if
compareTo() returns 0, TreeMap considers it a duplicate key. A common bug: Comparator that
compares by name only, then TreeSet rejects employees with same name as 'duplicates' even if
they're different people.

Q10 How does LinkedHashMap work? What are its use cases? [Intermediate] [Intermediate]

Answer:
LinkedHashMap extends HashMap and adds a doubly-linked list that runs through all entries in either
insertion order (default) or access order (flag in constructor).
Insertion order mode (default): entries iterated in the order they were inserted. Useful for
predictable/reproducible map iteration.
Access order mode (accessOrder=true): each get() or put() moves that entry to the tail of the linked
list. LRU (Least Recently Used) order — the head is the least recently accessed. Override
removeEldestEntry() to evict old entries automatically.
LRU Cache pattern: the canonical use case. When size exceeds capacity, removeEldestEntry()
returns true and LinkedHashMap automatically removes the head (LRU entry).

Code Example:
// LRU Cache using LinkedHashMap
class LRUCache<K,V> extends LinkedHashMap<K,V> {
private final int capacity;
LRUCache(int capacity) {
super(capacity, 0.75f, true); // accessOrder = true
[Link] = capacity;
}
@Override protected boolean removeEldestEntry([Link]<K,V> eldest) {
return size() > capacity; // evict LRU when over capacity
}
}

LRUCache<Integer,String> cache = new LRUCache<>(3);

[Link](1, 'A'); [Link](2, 'B'); [Link](3, 'C');
[Link](1); // access 1 — moves to tail: [2, 3, 1]
[Link](4, 'D'); // evicts LRU (2): [3, 1, 4]

💡 Interviewer Tip:
LRUCache via LinkedHashMap is a classic interview coding question. Know the constructor parameter
accessOrder=true. removeEldestEntry() is called after each put() — return true to evict. Note:
LinkedHashMap is not thread-safe; wrap with [Link]() or use Caffeine/Guava
Cache in production.

Q11 What is the difference between HashMap and Hashtable? [Basic] [Basic]

Answer:
Both implement Map but have significant differences — Hashtable is a legacy class from Java 1.0.
Synchronization: Hashtable synchronizes every method on the instance. HashMap is not
synchronized.
Null handling: HashMap allows one null key and multiple null values. Hashtable does NOT allow null
keys or values (throws NullPointerException).
Performance: Hashtable's per-method synchronization makes it a bottleneck in concurrent scenarios
— every operation locks the entire map. In modern code, use ConcurrentHashMap for thread safety.
Iteration: HashMap's Iterator is fail-fast. Hashtable's Enumerator is NOT fail-fast.
Recommendation: Never use Hashtable in new code. Use HashMap (single-threaded) or
ConcurrentHashMap (multi-threaded).

Code Example:
// Hashtable — legacy, synchronized, no nulls
Hashtable<String,String> ht = new Hashtable<>();
[Link](null, 'x'); // NullPointerException

// HashMap — modern, not synchronized, allows nulls

HashMap<String,String> hm = new HashMap<>();
[Link](null, 'x'); // OK

// Thread-safe modern alternative

Map<String,String> safe = new ConcurrentHashMap<>();
// OR: wrap HashMap (but full lock — slow under contention)
Map<String,String> syncMap = [Link](new HashMap<>());

💡 Interviewer Tip:
Hashtable vs synchronizedMap vs ConcurrentHashMap is a common progression question. Hashtable
= full lock per method. synchronizedMap = full lock per method on a wrapper. ConcurrentHashMap =
per-bucket locking (Java 8) — far higher read concurrency. Always use ConcurrentHashMap for new
concurrent code.

Q12 What is PriorityQueue? How does it maintain order? [Intermediate] [Intermediate]

Answer:
PriorityQueue is a heap-based priority queue that returns elements in natural order (min-heap by
default) or by a provided Comparator. It does NOT guarantee FIFO order for elements of equal priority.
Internal structure: a binary min-heap stored in an array. The root (array[0]) is always the smallest
element. add()/offer() inserts and sifts up. poll()/remove() removes the root and sifts down. Both
operations are O(log n). peek() is O(1).
Iteration order: iterating a PriorityQueue does NOT return elements in priority order — it returns them
in heap array order. To drain in order, repeatedly call poll().
Not thread-safe. Use PriorityBlockingQueue for concurrent use.

Code Example:
// Min-heap (default — smallest element first)
PriorityQueue<Integer> pq = new PriorityQueue<>();
 [Link](5); [Link](1); [Link](3);
[Link](); // returns 1 (minimum)
[Link](); // returns 3

// Max-heap via reverseOrder Comparator

PriorityQueue<Integer> maxPq = new PriorityQueue<>([Link]());
[Link](5); [Link](1); [Link](3);
[Link](); // returns 5 (maximum)

// Custom priority (shortest job first scheduler)

PriorityQueue<Task> tasks = new PriorityQueue<>(
[Link](Task::getPriority));

// K-th largest element (classic interview problem)

PriorityQueue<Integer> kth = new PriorityQueue<>() // min-heap of size k
// ... keep only k elements in heap

💡 Interviewer Tip:
Heap invariant: every parent <= its children (min-heap). add() and poll() sifts maintain this. Common
interview problem: 'Find k-th largest element' — maintain a min-heap of size k. Top of heap is k-th
largest. Time O(n log k). Knowing this patterns signals algorithm fluency.

What is ArrayDeque? How does it compare to LinkedList as a stack/queue?

Q13
[Intermediate] [Intermediate]

Answer:
ArrayDeque is a resizable-array implementation of Deque (double-ended queue). It supports O(1)
amortized add/remove at both head and tail.
As a Stack (LIFO): push() = addFirst(), pop() = removeFirst(), peek() = peekFirst(). Java's Stack class
is synchronized and extends Vector — avoid it. Prefer ArrayDeque as a stack.
As a Queue (FIFO): offer() = addLast(), poll() = removeFirst(). Prefer ArrayDeque over LinkedList as a
Queue — no node allocation overhead, better cache locality.
vs LinkedList: ArrayDeque is faster in practice. No per-element node allocation. Circular array gives
contiguous memory access. No null elements allowed in ArrayDeque.

Code Example:
// ArrayDeque as Stack (replaces [Link])
Deque<String> stack = new ArrayDeque<>();
[Link]('A'); // addFirst — O(1)
[Link]('B');
[Link](); // removeFirst — 'B' (LIFO)
[Link](); // peekFirst — 'A' (no remove)

// ArrayDeque as Queue (replaces LinkedList-as-Queue)

Queue<String> queue = new ArrayDeque<>();
[Link]('A'); // addLast — O(1)
[Link]('B');
[Link](); // removeFirst — 'A' (FIFO)

// Deque — both ends

Deque<Integer> dq = new ArrayDeque<>();
[Link](1); [Link](2);
[Link](); [Link]();

💡 Interviewer Tip:
The Javadoc for ArrayDeque explicitly states: 'This class is likely to be faster than Stack when used as
a stack, and faster than LinkedList when used as a queue.' Always recommend ArrayDeque over Stack
or LinkedList-as-queue in code reviews.

Q14 What does Collections utility class provide? Name important methods. [Basic] [Basic]

Answer:
[Link] provides static utility methods for collection operations:
Sorting: [Link](list) — O(n log n) stable sort (TimSort). [Link](list, comparator).
Searching: [Link](list, key) — O(log n), list must be sorted first.
Shuffling/rotating: [Link](list), [Link](list, distance).
Extremes: [Link](coll), [Link](coll), [Link](coll, element).
Wrappers: [Link]/Set/Map() — read-only view.
[Link]/Map() — synchronized wrapper. [Link](x) — immutable
single-element list.
Filling: [Link](list, value), [Link](n, element), [Link](c1, c2).

Code Example:
List<Integer> nums = new ArrayList<>([Link](3, 1, 4, 1, 5, 9));

// Sort and search

[Link](nums); // [1,1,3,4,5,9]
int idx = [Link](nums, 4); // index of 4

// Extremes
[Link](nums); // 1
[Link](nums); // 9
[Link](nums, 1); // 2

// Immutable view (throws UnsupportedOperationException on mutate)

List<Integer> readOnly = [Link](nums);

// Reverse
[Link](nums);

// Swap two elements

[Link](nums, 0, 5);

💡 Interviewer Tip:
[Link]() uses TimSort (hybrid merge+insertion sort, stable). Since Java 8 prefer
[Link](comparator) — same algorithm but cleaner API. Note: [Link]() still
requires external synchronization during iteration (unlike CopyOnWriteArrayList).

What are immutable collections in Java? How do [Link](), [Link](), [Link]() differ from
Q15
[Link]()? [Intermediate] [Intermediate]

Answer:
Java 9+ factory methods ([Link], [Link], [Link]): create truly immutable collections. No structural
changes AND no modification of elements. Implementation classes are package-private and highly
optimized (compact memory layout). Null elements/keys/values are NOT allowed.
[Link]/Set/Map(): creates a read-only VIEW over the original collection. The
underlying collection can still be modified externally, and changes are reflected through the view. Null
 elements allowed. Not truly immutable.
Guava ImmutableList/Map: immutable, allows null if explicitly added via builder, preserves insertion
order (ImmutableList/ImmutableMap), provides builder pattern for complex construction.

Code Example:
// Java 9+ factory — truly immutable, compact
List<String> immutable = [Link]('a', 'b', 'c');
[Link]('d'); // UnsupportedOperationException
[Link]('a', null); // NullPointerException!

// unmodifiableList — view, backing list still mutable

List<String> backing = new ArrayList<>([Link]('a','b'));
List<String> view = [Link](backing);
[Link]('c'); // UnsupportedOperationException
[Link]('c'); // OK — view now shows ['a','b','c']!

// [Link] — max 10 entries (use [Link] for more)

Map<String,Integer> m = [Link]('k1',1, 'k2',2);
Map<String,Integer> large = [Link](
[Link]('k1',1), [Link]('k2',2) // ... up to any size
);

💡 Interviewer Tip:
[Link]() and [Link]() do NOT guarantee iteration order. [Link]('a','b','c') could iterate in any order.
[Link]() does not preserve insertion order. If you need ordered iteration, use [Link]() or
LinkedHashMap. Also: [Link]() detects duplicate elements at creation time and throws
IllegalArgumentException.

Section 2 — HashMap Internals, Performance & Production Patterns (Q16–

Q35)
HashMap and performance questions are almost guaranteed. Know the internals cold, not just the API.

Q16 What is HashMap's load factor and when should you change it? [Intermediate]
[Intermediate]

Answer:
Load factor (default 0.75) determines when HashMap rehashes. When size > capacity * loadFactor,
the table doubles and all entries are rehashed.
Lower load factor (e.g., 0.5): less collision, faster lookups, but more memory (table is larger relative to
entries). Use when lookup performance is critical and memory is plentiful.
Higher load factor (e.g., 0.9): more entries before rehashing, less memory, but longer collision chains
— slower lookups. Use when memory is constrained and collision risk is acceptable.
Setting initial capacity: if you know you'll store N entries, set initial capacity = N / loadFactor + 1
rounded to next power of 2. This prevents any rehashing during population.

Code Example:
// Default: capacity=16, loadFactor=0.75 → rehash at 12 entries

// For 1000 entries: 1000 / 0.75 ≈ 1334 → next power of 2 = 2048

Map<String, Value> map = new HashMap<>(2048, 0.75f);

// Low-latency lookup: lower load factor = fewer collisions

 Map<String, Value> fastMap = new HashMap<>(4096, 0.5f);

// Tracking capacity:
// After 12 inserts into default HashMap: capacity doubles to 32
// After 24 inserts: doubles to 64, etc.

💡 Interviewer Tip:
The interview follow-up: 'What is the cost of rehashing?' O(n) — all entries must be re-hashed and
placed in the new table. If you insert 10,000 items into a default HashMap, you'll trigger ~10 rehashes.
Pre-sizing eliminates all of them.

What happens when two keys have the same hashCode? (Hash collision)
Q17
[Intermediate] [Intermediate]

Answer:
A hash collision means two different keys produce the same bucket index. HashMap handles this with
chaining (linked list or tree in the same bucket).
Java 7 collision handling: linked list in the bucket. get() traverses the list calling equals() at each
node. Worst case O(n) if all keys collide.
Java 8 collision handling: when a bucket's chain grows beyond TREEIFY_THRESHOLD (8 entries)
AND table capacity >= MIN_TREEIFY_CAPACITY (64), the chain converts to a red-black tree. get()
becomes O(log n) even in the worst case.
Security implication: before Java 8, an attacker could craft keys with identical hash codes to cause
O(n) gets — a DoS vector. Java 8 treeification mitigated this.

Code Example:
// All these strings (in Java) have hashCode = 0:
// 'Aa' and 'BB' have the same hashCode in Java
[Link]('Aa'.hashCode()); // 2112
[Link]('BB'.hashCode()); // 2112
// They collide into the same bucket

// [Link]() with collision:

// 1. Compute hash(key) → bucket index
// 2. Traverse chain: [Link](candidateKey) at each node
// Java 8: chain becomes tree at size 8 (TREEIFY_THRESHOLD)

// Degenerate case: if all N keys collide, Java 7 = O(N) lookup

// Java 8 with treeification: O(log N) even for all collisions

💡 Interviewer Tip:
The treeification detail (TREEIFY_THRESHOLD=8, UNTREEIFY_THRESHOLD=6,
MIN_TREEIFY_CAPACITY=64) shows you've read the JDK source. The degenerate behaviour prior to
Java 8 was a real HTTP server vulnerability — servers hashing request parameters into a HashMap
were exploitable.

Q18 How do you iterate over a Map? What are the different approaches? [Basic] [Basic]

Answer:
Four main approaches, each with different use cases:
entrySet() iteration: most efficient — gets key and value in one step. No additional lookup. Preferred
approach.
keySet() iteration: then [Link](key) for the value — costs an extra hash lookup per entry. Use only
when you need keys only.
values() iteration: when you only need values. No key access.
forEach (Java 8+): clean, uses entrySet() internally. Preferred for simple operations. Cannot use
break/continue — use return in lambda to skip.

Code Example:
Map<String, Integer> map = new HashMap<>([Link]('a',1,'b',2,'c',3));

// Best: entrySet() — one lookup per entry

for ([Link]<String, Integer> entry : [Link]()) {
[Link]([Link]() + '=' + [Link]());
}

// Bad: keySet() + get() — two lookups per entry

for (String key : [Link]()) {
Integer value = [Link](key); // extra hash lookup!
}

// Java 8 forEach — cleanest

[Link]((k, v) -> [Link](k + '=' + v));

// Streams
[Link]().stream()
.filter(e -> [Link]() > 0)
.forEach(e -> process([Link](), [Link]()));

💡 Interviewer Tip:
entrySet() iteration is preferred because [Link] gives you both key and value from the same node
— no second hash lookup. Iterating keySet() then calling get() is an O(n) extra cost across the
iteration. This is a common inefficiency in code reviews.

What are Java 8 Map API additions? (compute, merge, getOrDefault, etc.)
Q19
[Intermediate] [Intermediate]

Answer:
Java 8 added powerful atomic-ish operations to Map that eliminate common verbose patterns:
getOrDefault(key, default): returns value or default if key absent. Replaces: [Link](k) ?
[Link](k) : default.
putIfAbsent(key, value): inserts only if key not present. Returns existing value or null.
computeIfAbsent(key, fn): if key absent, applies fn to compute and insert. Atomically safe in
ConcurrentHashMap.
computeIfPresent(key, fn): applies fn only if key exists.
compute(key, fn): always applies fn(key, existingValue). If fn returns null, entry is removed.
merge(key, value, fn): if key absent, inserts value; if present, applies fn(existingValue, newValue).
Perfect for accumulation patterns.

Code Example:
Map<String, List<String>> grouping = new HashMap<>();

// OLD: verbose, race condition with ConcurrentHashMap

if () [Link](key, new ArrayList<>());
[Link](key).add(value);
 // NEW: atomic with ConcurrentHashMap, cleaner
[Link](key, k -> new ArrayList<>()).add(value);

// Word frequency counting

Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
[Link](word, 1, Integer::sum); // increment or init to 1
}

// Remove if value becomes zero

[Link]('apple', (k, v) -> (v == null || v <= 1) ? null : v - 1);

// Safe default
int count = [Link]('unknown', 0);

💡 Interviewer Tip:
merge() is the most powerful and underused method. It replaces the pattern: [Link](k,
[Link](k) ? fn([Link](k), v) : v). In ConcurrentHashMap, merge() and computeIfAbsent()
are atomic — they eliminate the check-then-act race condition of the old pattern.

Q20 What is WeakHashMap and when is it used? [Advanced] [Advanced]

Answer:
WeakHashMap uses WeakReferences for its keys. When a key is no longer referenced by any other
part of the program (only weakly reachable), the garbage collector can collect it. After GC, the
corresponding entry is automatically removed from the map.
Use case: caches where the lifecycle of cached values should match the lifecycle of their keys.
Example: cache metadata about Class objects — when the ClassLoader is unloaded and the Class is
GC'd, the metadata entry should also disappear.
NOT suitable: as a general-purpose Map — entries disappear silently at GC time, which is
unpredictable. Also: keys that are String literals or enum constants are never GC'd (they have strong
references), so WeakHashMap offers no benefit for those.
Values are NOT weakly referenced — values can prevent the associated key from being collected if
the value holds a strong reference back to the key.

Code Example:
// WeakHashMap: entries auto-removed when key is GC'd
WeakHashMap<Object, String> weakMap = new WeakHashMap<>();

Object key = new Object(); // strong reference

[Link](key, 'metadata');
[Link]([Link]()); // 1

key = null; // remove strong reference

[Link](); // suggest GC (not guaranteed immediately)
[Link](100); // allow GC to run
[Link]([Link]()); // may be 0

// Real use: ClassLoader metadata cache

// When ClassLoader is unloaded → Class GC'd → WeakHashMap auto-cleans

// WRONG: string literal keys — never GC'd

[Link]('constant', 'value'); // String literals have strong refs

💡 Interviewer Tip:
WeakHashMap is used internally by frameworks: [Link] caches BeanInfo in a
WeakHashMap keyed by Class. When a class is unloaded (e.g., in OSGi or hot-reload), the cache
entry automatically clears. Knowing this real-world internal use is impressive.

What is EnumMap and EnumSet? Why are they preferred over HashMap/HashSet for
Q21
enum keys? [Advanced] [Advanced]

Answer:
EnumMap<K extends Enum<K>, V>: backed by an array indexed by the ordinal of the enum
constant. No hashing, no collision handling — array index lookup is O(1) with zero overhead. Memory-
compact. Preserves enum natural order (declaration order).
EnumSet<E extends Enum<E>>: backed by a bitmask (long) for enums with up to 64 constants
(RegularEnumSet) or a long[] for larger enums (JumboEnumSet). Set operations (add, contains,
complement) are bitwise operations — extremely fast.
Both are NOT synchronized. Both do not allow null keys/elements (EnumMap allows null values). Both
are faster and more memory-efficient than their HashMap/HashSet counterparts for enum keys.

Code Example:
enum Day { MON, TUE, WED, THU, FRI, SAT, SUN }

// EnumMap — array-backed, O(1) no hashing

Map<Day, String> schedule = new EnumMap<>([Link]);
[Link]([Link], 'standup');
[Link]([Link], 'demo');

// EnumSet — bitmask-based, bitwise operations

EnumSet<Day> weekdays = [Link]([Link], [Link]);
EnumSet<Day> weekend = [Link](weekdays); // [SAT, SUN]
EnumSet<Day> workdays = [Link]([Link], [Link], [Link]);

// Bitwise intersection (contains all the speed of bit operations)

boolean overlap = ;

// Iteration order = enum declaration order

for (Day d : weekdays) [Link](d); // MON,TUE,WED,THU,FRI

💡 Interviewer Tip:
[Link](), noneOf(), copyOf(), range(), complementOf() are the static factory methods. EnumSet
is the canonical way to represent sets of flags (permissions, feature toggles, days of week). It's faster
than a HashSet<Enum> and more readable than a bitmask int.

What is IdentityHashMap? When does it violate the Map contract intentionally?

Q22
[Advanced] [Advanced]

Answer:
IdentityHashMap uses reference equality (==) instead of object equality (.equals()) for key comparison.
It uses [Link]() instead of [Link]().
This intentionally violates the Map contract (which requires equals-based comparison). It's designed for
specific use cases where you need to track object identity, not logical equality.
Use cases: serialization/deserialization — detect if the same object instance has been visited (cycle
detection in object graphs). Memory profilers — track object instances. Proxy implementations —
associate metadata with specific object instances.
Not synchronized. Allows null keys. Initial capacity should be larger than for HashMap (identity maps
tend to need more buckets for equivalent load).

Code Example:
// IdentityHashMap: == comparison, not .equals()
IdentityHashMap<String, Integer> idMap = new IdentityHashMap<>();

String s1 = new String('hello'); // new instance

String s2 = new String('hello'); // another new instance

[Link](s1, 1);
[Link](s2, 2);
[Link]([Link]()); // 2 — different identities!

// HashMap would show size=1 ([Link](s2))

HashMap<String, Integer> hashMap = new HashMap<>();
[Link](s1, 1); [Link](s2, 2);
[Link]([Link]()); // 1 — same logical key

// Real use: object graph traversal / serialization

IdentityHashMap<Object, Boolean> visited = new IdentityHashMap<>();
void traverse(Object obj) {
if ([Link](obj, true) != null) return; // already visited this instance
}

💡 Interviewer Tip:
Java's own serialization mechanism uses IdentityHashMap internally to detect object cycles and
shared references. Mentioning this concrete internal use — and understanding why == semantics is
correct there (you care about the same object instance, not equal objects) — demonstrates advanced
JDK knowledge.

Q23 How do you sort a List of custom objects? [Intermediate] [Intermediate]

Answer:
Three approaches, from least to most modern:
Implement Comparable: define natural ordering in the class. [Link]() or [Link]() with no
comparator uses this. Best when there's one obvious natural order.
Pass a Comparator: for alternative orderings or when you can't modify the class. [Link](list,
comparator) or [Link](comparator).
Java 8 [Link](): fluent builder API. Avoids manual compareTo() arithmetic. Handles
nulls, reversal, and chaining cleanly.

Code Example:
record Employee(String name, int salary, String dept) {}

List<Employee> emps = new ArrayList<>([Link](

new Employee('Zoe', 80000, 'Eng'),
new Employee('Alice', 90000, 'Eng'),
new Employee('Bob', 70000, 'HR')
));

// Sort by salary ascending

[Link]([Link](Employee::salary));

// Sort by salary descending

[Link]([Link](Employee::salary).reversed());

// Sort by dept then by name within dept

 [Link]([Link](Employee::dept)
.thenComparing(Employee::name));

// Null-safe sort (nulls last)

[Link]([Link](Employee::dept,
[Link]([Link]())));

// Stream-based: returns new sorted stream, original unchanged

List<Employee> sorted =
[Link]().sorted([Link](Employee::name)).toList();

💡 Interviewer Tip:
[Link]() is preferred over [Link]() for primitive int/long to avoid
boxing overhead. .reversed() creates a new Comparator — it doesn't mutate. thenComparing() chains
— first criterion, then tiebreak. These compose without manual null checks or arithmetic.

Q24 What is the difference between Iterator and ListIterator? [Basic] [Basic]

Answer:
Iterator: forward-only traversal of any Collection. Methods: hasNext(), next(), remove() (removes last
returned element).
ListIterator: extends Iterator, only for List implementations. Bidirectional traversal (hasPrevious(),
previous()). Can add elements (add()), modify elements (set()), and query current position (nextIndex(),
previousIndex()).
Both are fail-fast for ArrayList, LinkedList — throw ConcurrentModificationException if the list is
structurally modified outside the iterator.
[Link]() is the only safe way to remove elements during iteration. It does not increment
modCount (the iterator tracks its own operations).

Code Example:
List<String> list = new ArrayList<>([Link]('A', 'B', 'C', 'D'));

// Iterator — forward only

Iterator<String> it = [Link]();
while ([Link]()) {
String s = [Link]();
if ([Link]('B')) [Link](); // safe removal
}

// ListIterator — bidirectional, add, set

ListIterator<String> lit = [Link]([Link]()); // start at end
while ([Link]()) {
String s = [Link]();
if ([Link]('C')) [Link]('X'); // replace in-place
if ([Link]('A')) [Link]('Z'); // insert after A
}

// Position query
[Link](); // index of element that next() would return
[Link](); // index of element that previous() would return

💡 Interviewer Tip:
The only safe removal during iteration is [Link]() — it's the exception to the fail-fast rule. Any
direct [Link]() inside a loop using enhanced for-each (which uses an iterator internally) triggers
ConcurrentModificationException. Also: remove() can only be called once per next() call.
Q25 What is the difference between poll() and remove() in Queue? [Basic] [Basic]

Answer:
Queue defines two sets of methods for the same operations: throwing-versions and null/false-returning
versions.
Head removal: remove() throws NoSuchElementException if queue empty. poll() returns null if queue
empty. Use poll() in production — null check is safer than exception handling for empty queues.
Head peek: element() throws NoSuchElementException if empty. peek() returns null if empty. Use
peek() for safe access.
Insertion: add() throws IllegalStateException if capacity exceeded (bounded queues). offer() returns
false. Use offer() for bounded queues.
This pattern (throwing vs. special-value) is consistent across Queue, Deque, and BlockingQueue.

Code Example:
Queue<String> queue = new LinkedList<>([Link]('A','B','C'));

// Safe variants (return null/false — prefer these)

[Link](); // 'A' — no removal, null if empty
[Link](); // 'A' — removes, null if empty

// Throwing variants (throw if empty/full)

[Link](); // 'B' — no removal, throws if empty
[Link](); // 'B' — removes, throws if empty

// Offer vs add (matters for bounded queues like ArrayBlockingQueue)

ArrayBlockingQueue<Integer> bounded = new ArrayBlockingQueue<>(2);
[Link](1); // true
[Link](2); // true
[Link](3); // false — full, no exception
[Link](3); // throws IllegalStateException — full

💡 Interviewer Tip:
This two-tier API exists because Queue is used in both contexts where exceptions are appropriate
(algorithm correctness checks) and where normal control flow (empty queue = do nothing) is expected.
In most production code, always use poll() and peek() for queues to avoid exception handling
overhead.

Q26 How do you make a collection thread-safe? Compare all approaches. [Intermediate]
[Intermediate]

Answer:
Approach 1 — synchronized wrappers ([Link]): wraps every method with
synchronized on the wrapper. Full lock on every operation — readers and writers block each other.
Iteration still requires external synchronization. Simple but lowest concurrency.
Approach 2 — CopyOnWriteArrayList/CopyOnWriteArraySet: every write creates a new copy of
the underlying array. Reads are lock-free (read snapshot). Best for collections read far more than
written (e.g., event listeners). Writes are O(n) — expensive.
Approach 3 — ConcurrentHashMap/ConcurrentSkipListMap: fine-grained locking.
ConcurrentHashMap: per-bucket CAS/sync (Java 8). ConcurrentSkipListMap: lock-free skip list with
O(log n) operations, sorted. Highest read concurrency.
Approach 4 — Immutable collections ([Link] etc.): no synchronization needed — reads only. Copy-
on-write at the application level if updates needed.
Code Example:
// Approach 1: synchronized wrapper — simple, low concurrency
List<String> synced = [Link](new ArrayList<>());
synchronized(synced) { // MUST externally sync during iteration
for (String s : synced) process(s);
}

// Approach 2: CopyOnWrite — read-heavy workloads

List<EventListener> listeners = new CopyOnWriteArrayList<>();
// Reads: zero lock. Write: copies entire array

// Approach 3: Concurrent collections — high concurrency

Map<String, Value> map = new ConcurrentHashMap<>();
[Link](key, k -> load(k)); // atomic

// Sorted + concurrent
NavigableMap<String, Value> sorted = new ConcurrentSkipListMap<>();

// Approach 4: Immutable + application-level swap

volatile List<String> config = [Link]('a','b');
// To 'update': swap the reference atomically (volatile write)
config = [Link]('a','b','c'); // visible to all readers

💡 Interviewer Tip:
The concurrency level question: synchronized wrappers serialize ALL operations (including concurrent
reads). ConcurrentHashMap allows all readers to proceed in parallel and writers to different buckets in
parallel. For a read-heavy cache, this difference is orders of magnitude in throughput.

Q27 What is the difference between Vector and ArrayList? [Basic] [Basic]

Answer:
Both are List implementations backed by dynamic arrays. Vector is a legacy class from Java 1.0;
ArrayList was added in Java 1.2.
Synchronization: every Vector method is synchronized — thread-safe but slow under single-threaded
use. ArrayList is not synchronized.
Growth factor: Vector doubles its capacity (oldCapacity * 2) by default, or by a configurable
increment. ArrayList grows by 1.5x — less memory waste.
Stack: [Link] extends Vector — equally legacy, synchronized, avoid. Use ArrayDeque as a
stack.
Recommendation: never use Vector or Stack in new code. Use ArrayList (single-threaded) or
CopyOnWriteArrayList/[Link]() (multi-threaded).

Code Example:
// Vector: synchronized, 2x growth, legacy — avoid
Vector<String> v = new Vector<>(10); // initial capacity 10
[Link]('a'); // synchronized — overhead even single-threaded

// Stack: extends Vector — doubly legacy — avoid

Stack<Integer> stack = new Stack<>();
[Link](1);
[Link]();

// Modern replacements
List<String> list = new ArrayList<>(); // single-threaded
List<String> syncList = new CopyOnWriteArrayList<>(); // concurrent reads
Deque<Integer> dequeStack = new ArrayDeque<>(); // replaces Stack
 // ArrayDeque as stack (faster, not synchronized)
[Link](1); // addFirst
[Link](); // removeFirst

💡 Interviewer Tip:
Vector and Stack appear in legacy codebases but should be replaced during refactoring. The
performance overhead of synchronized methods in Vector shows up in profilers as contention even on
single-threaded code. Interviewers use this question to probe whether you know the collections history.

Q28 What is NavigableMap and NavigableSet? Name key methods. [Advanced] [Advanced]

Answer:
NavigableMap extends SortedMap with navigation methods for finding closest matches. NavigableSet
extends SortedSet similarly. TreeMap implements NavigableMap; TreeSet implements NavigableSet.
Key NavigableMap methods: lowerKey(k) — greatest key < k. floorKey(k) — greatest key <= k.
ceilingKey(k) — smallest key >= k. higherKey(k) — smallest key > k.
Entry variants: lowerEntry, floorEntry, ceilingEntry, higherEntry — return [Link] or null.
Range views: headMap(toKey, inclusive), tailMap(fromKey, inclusive), subMap(from, fromInclusive, to,
toInclusive). Views are LIVE — changes to view affect the backing map and vice versa.
Descending: descendingMap() returns a view in reverse order. pollFirstEntry()/pollLastEntry() —
remove and return first/last entry.

Code Example:
TreeMap<Integer, String> prices = new TreeMap<>([Link](
10, 'bronze', 50, 'silver', 100, 'gold', 500, 'platinum'));

// Navigation: find tier for given amount

[Link](75); // 50=silver (largest key <= 75)
[Link](75); // 100=gold (smallest key >= 75)
[Link](100); // 50 (largest key < 100)
[Link](100); // 500 (smallest key > 100)

// Range views (LIVE — mutations affect backing map)

SortedMap<Integer, String> affordable = [Link](100); // [10,50]
SortedMap<Integer, String> midRange = [Link](50, 500); // [50,100]

// Descending iteration
[Link]().forEach(k -> [Link](k)); // 500,100,50,10

// Poll (remove) extremes

[Link]<Integer,String> cheapest = [Link](); // removes 10
[Link]<Integer,String> priciest = [Link](); // removes 500

💡 Interviewer Tip:
NavigableMap/Set is perfect for range-based lookups: price tier lookup, rate limiting (find the bucket for
this timestamp), time-series data (find all events between T1 and T2). The live view behaviour of
headMap/tailMap/subMap is important — mutations propagate. Use .entrySet() of the subMap to
iterate safely.

How does [Link]() achieve stability? What algorithm does it use?

Q29
[Intermediate] [Intermediate]

Answer:
[Link]() uses TimSort — a hybrid of merge sort and insertion sort developed by Tim Peters
(Python's sort algorithm, adapted for Java by Josh Bloch).
Stability: TimSort is stable — equal elements maintain their original relative order. Critical for multi-key
sorting: sort by salary, then by name — employees with equal names maintain their salary-sort order.
TimSort mechanics: (1) finds existing natural runs (ascending or descending sequences) in the data.
(2) Extends short runs to a minimum size using insertion sort. (3) Merges runs using a merge sort
adapted to preserve the run structure.
Performance: O(n log n) worst case, O(n) for already-sorted input (detects natural runs). Best-case
much better than quicksort for nearly-sorted data (common in practice).
[Link]() for objects also uses TimSort. [Link]() for primitives uses Dual-Pivot QuickSort
(unstable, but stability is irrelevant for primitives).

Code Example:
// Stability demonstration
record Person(String name, int age) {}
List<Person> people = new ArrayList<>([Link](
new Person('Alice', 30), new Person('Bob', 25),
new Person('Alice', 25) // same name as first Alice
));

// Sort by age (stable — equal-age persons keep their original order)

[Link]([Link](Person::age));
// Result: [Bob-25, Alice-25, Alice-30]
// Alice-25 comes before Alice-30 — original relative order preserved

// [Link] for objects = TimSort (stable)

Person[] arr = [Link](Person[]::new);
[Link](arr, [Link](Person::name));

// [Link] for primitives = Dual-Pivot QuickSort (NOT stable)

int[] nums = {3,1,4,1,5}; [Link](nums); // unstable, but ints dont care

💡 Interviewer Tip:
TimSort's O(n) best case for nearly-sorted data is why it's chosen for general-purpose sorting of object
arrays. Real-world data (logs by timestamp, names in almost-alphabetical order) is often nearly sorted
— TimSort exploits this. Dual-Pivot QuickSort for primitives is faster on random data and stability
doesn't matter for primitives (no associated data to reorder).

What is the difference between subList(), subSet(), and subMap() and how do live
Q30
views work? [Advanced] [Advanced]

Answer:
subList(), subSet(), and subMap() all return LIVE views of the backing collection within a specified
range. Changes to the view affect the original, and changes to the original within the range are
reflected in the view.
[Link](from, to): returns a view of elements from index 'from' (inclusive) to 'to' (exclusive).
Supports all List operations including remove — removals are reflected in the backing list. Structural
modifications to the backing list outside the subList invalidate the view
(ConcurrentModificationException on next use).
[Link](from, to): live view of elements in [from, to) range. Both headSet(to) and
tailSet(from) are also live views.
Common use — clearing a range: [Link](from, to).clear() is the idiomatic way to remove a range
of elements from a list.
Code Example:
// subList — live view
List<Integer> list = new ArrayList<>([Link](0,1,2,3,4,5,6,7,8,9));
List<Integer> view = [Link](3, 7); // [3,4,5,6]

[Link](0, 99); // changes list[3] to 99

[Link]([Link](3)); // 99

[Link](0); // removes from backing list at index 3

[Link](list); // [0,1,2,4,5,6,7,8,9]

// Idiom: clear a range

[Link](2, 5).clear(); // removes elements at index 2,3,4

// Invalidation: structural mod outside view → CME

[Link](99); // structural mod to backing list
[Link](0); // ConcurrentModificationException!

// subMap — live view of TreeMap range

TreeMap<Integer, String> map = new TreeMap<>();
NavigableMap<Integer, String> range = [Link](10, true, 50, true);
[Link](25, 'x'); // goes into backing TreeMap

💡 Interviewer Tip:
The live view property is both a feature and a footgun. Clearing a range with subList().clear() is very
efficient — O(n) compared to O(n²) for looping and removing. But keeping a subList reference alive
after modifying the backing list is a common source of ConcurrentModificationException. Don't hold
subList references across mutations.

How would you implement a cache with max size and LRU eviction without external
Q31
libraries? [Intermediate] [Intermediate]

Answer:
Use LinkedHashMap with accessOrder=true and override removeEldestEntry(). This is the canonical
Java LRU cache implementation using only standard library classes.
For thread safety, wrap with [Link]() for simple cases, or re-implement with
ReentrantReadWriteLock for better read concurrency.
For production: use Caffeine (successor to Guava Cache) — it provides LRU/LFU eviction, expiry by
time, async loading, stats, and far better concurrency than a synchronized LinkedHashMap.

Code Example:
// Thread-unsafe LRU — interview answer
class LRUCache<K,V> extends LinkedHashMap<K,V> {
private final int maxSize;
LRUCache(int maxSize) {
super(maxSize, 0.75f, true); // accessOrder=true
[Link] = maxSize;
}
@Override protected boolean removeEldestEntry([Link]<K,V> e) {
return size() > maxSize;
}
}

// Thread-safe wrapper
Map<K,V> cache = [Link](new LRUCache<>(100));

// Production: Caffeine
Cache<String, Result> caffeineCache = [Link]()
 .maximumSize(1000)
.expireAfterWrite([Link](10))
.recordStats()
.build();
Result val = [Link](key, k -> loadFromDb(k)); // async-safe

💡 Interviewer Tip:
The interview follow-up: 'Can you implement LRU without LinkedHashMap?' Yes — use a
HashMap<K, Node<K,V>> + a doubly-linked list maintained manually. O(1) get and put. This is the
LeetCode 146 (LRU Cache) problem. Being able to implement both the LinkedHashMap shortcut and
the manual DLL version shows breadth.

Q32 What are the internal differences between HashMap and LinkedHashMap? [Advanced]
[Advanced]

Answer:
LinkedHashMap extends HashMap and adds a doubly-linked list that runs through all entries in
insertion (or access) order. Each entry in the underlying array has two additional fields: before and
after — pointers in the access/insertion order linked list.
Extra fields per entry: [Link] has: hash, key, value, next (bucket chain pointer).
[Link] additionally has: before, after (doubly-linked list for iteration order).
Memory overhead: each LinkedHashMap entry is larger than HashMap entry by two object references
(~16 bytes extra on 64-bit JVM with compressed OOPs). For millions of entries, this adds up.
Iteration: [Link]().iterator() follows the doubly-linked list — O(n) in insertion/access
order. HashMap iteration traverses the bucket array — O(capacity + size), skipping empty buckets.

Code Example:
// Conceptual structure of [Link]<K,V>
// Inherits from [Link]:
// int hash; K key; V value; Node<K,V> next; // bucket chain
// LinkedHashMap adds:
// Entry<K,V> before; // previous in access-order list
// Entry<K,V> after; // next in access-order list

// Insertion order mode (default)

LinkedHashMap<Integer, String> lhm = new LinkedHashMap<>();
[Link](3, 'three'); [Link](1, 'one'); [Link](2, 'two');
[Link]().toString(); // [3, 1, 2] — insertion order

// Access order mode

LinkedHashMap<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true);
[Link](1, 'a'); [Link](2, 'b'); [Link](3, 'c');
[Link](1); // access 1 — moves to tail
[Link](); // [2, 3, 1] — 1 is most recently used

💡 Interviewer Tip:
The before/after pointers mean every put(), get() (in access order mode), and remove() must update
the doubly-linked list — 2 extra pointer writes per operation. For pure lookup performance, use
HashMap. For predictable order, pay the LinkedHashMap overhead.

What is ConcurrentSkipListMap and when would you use it over

Q33
ConcurrentHashMap? [Advanced] [Advanced]

Answer:
ConcurrentSkipListMap is a concurrent, sorted Map backed by a lock-free skip list. It implements
NavigableMap and ConcurrentMap.
vs ConcurrentHashMap: ConcurrentHashMap provides O(1) get/put with no ordering.
ConcurrentSkipListMap provides O(log n) get/put but keeps keys sorted and supports range queries
(headMap, tailMap, subMap, ceilingKey, floorKey).
Thread safety: fully lock-free using CAS operations. Reads never block. Concurrent writes to different
parts of the skip list proceed in parallel.
Use cases: when you need a concurrent map that you also need to iterate in key order, or perform
range queries concurrently. Example: rate limiting buckets, time-ordered event logs, concurrent
leaderboard.

Code Example:
// ConcurrentSkipListMap: sorted + concurrent
ConcurrentNavigableMap<Long, Event> eventLog = new ConcurrentSkipListMap<>();

// Multiple threads safely insert events with timestamp keys

[Link]([Link](), event1); // thread 1
[Link]([Link](), event2); // thread 2

// Concurrent range queries — no locking needed

long cutoff = [Link]() - 60_000; // 1 min ago
ConcurrentNavigableMap<Long, Event> recent = [Link](cutoff);
// recent is a live concurrent view

// First / last entry atomically

[Link]<Long, Event> earliest = [Link]();
[Link]<Long, Event> latest = [Link]();

// ConcurrentSkipListSet (same idea for sets)

ConcurrentSkipListSet<String> sortedConcurrentSet = new
ConcurrentSkipListSet<>();

💡 Interviewer Tip:
ConcurrentSkipListMap is the only concurrent implementation of NavigableMap in the JDK. Skip list is
a probabilistic data structure (O(log n) expected, not guaranteed — but practically excellent). Use it
when TreeMap would be correct but you need concurrent access. ConcurrentHashMap is faster for
unordered access.

What are the performance implications of using a List as a Set? (contains on

Q34
ArrayList) [Intermediate] [Intermediate]

Answer:
[Link](x) is O(n) — it linearly scans all elements calling equals() at each step. For a
1,000,000-element list, checking membership means up to 1,000,000 equals() calls.
[Link](x) is O(1) average — hash lookup into a bucket then 1-2 equals() calls.
Using an ArrayList as a lookup set is a common performance anti-pattern. The fix is simple: convert to
a HashSet. If insertion order matters, use LinkedHashSet. If sorted order needed, use TreeSet.
Similarly: [Link](Object) is O(n) + shift. [Link](x) is O(1). For frequent removals, use a Set.

Code Example:
// O(n) per lookup — scales terribly
List<String> badSet = new ArrayList<>(loadMillionItems());
for (String query : queries) {
if ([Link](query)) process(query); // O(n) each time!
 }
// Total: O(n * queries) = potentially O(n²)

// Fix: convert to HashSet once, O(1) lookups

Set<String> goodSet = new HashSet<>(loadMillionItems()); // O(n) once
for (String query : queries) {
if ([Link](query)) process(query); // O(1) each!
}
// Total: O(n + queries)

// Deduplication: List → Set → List (preserve insertion order)

List<String> deduped = new ArrayList<>(new LinkedHashSet<>(list));

// Retain only elements in another collection (set semantics)

[Link](new HashSet<>(otherList)); // convert otherList to Set first!
// retainAll iterates list and calls contains() on the argument
// If argument is a List: O(n*m). If HashSet: O(n)

💡 Interviewer Tip:
[Link](c), removeAll(c), containsAll(c) all call [Link]() repeatedly. If c is a List, each
call is O(n). Always convert the argument to a HashSet first. This is a real production optimization —
retainAll on two large lists is O(n²) without the Set conversion.

How would you design a frequency map and find the top-K frequent elements
Q35
efficiently? [Advanced] [Advanced]

Answer:
Step 1 — Build frequency map: use HashMap<T, Integer> with merge() to count occurrences in
O(n).
Step 2 — Find top-K: several approaches of varying efficiency:
Sort all entries by frequency descending, take first K: O(n log n). Simple but wasteful if K << n.
Min-heap of size K: maintain a PriorityQueue<[Link]> of size K. For each entry, if its frequency >
min in heap, swap. Final heap contains top-K. O(n log K) — optimal for large n, small K.
Bucket sort: create an array of lists indexed by frequency (0 to n). O(n) — optimal when n is
manageable.

Code Example:
// Frequency map in one line
Map<String, Long> freq = [Link]()
.collect([Link](w -> w, [Link]()));

// OR: merge-based
Map<String, Integer> freq2 = new HashMap<>();
for (String w : words) [Link](w, 1, Integer::sum);

// Top-K with min-heap: O(n log K)

int K = 5;
PriorityQueue<[Link]<String,Integer>> pq = new PriorityQueue<>(
[Link]([Link]::getValue)); // min-heap
for ([Link]<String,Integer> e : [Link]()) {
[Link](e);
if ([Link]() > K) [Link](); // evict minimum
}
// pq now contains top-K entries (min at top)

// Stream-based (simpler, O(n log n))

List<String> topK = [Link]().stream()
 .sorted([Link].<String,Integer>comparingByValue().reversed())
.limit(K)
.map([Link]::getKey)
.toList();

💡 Interviewer Tip:
The min-heap approach (O(n log K)) vs sort-all (O(n log n)) difference is meaningful when K=5 and
n=1,000,000: log(5) ≈ 2.3 vs log(1M) ≈ 20 — ~10x fewer comparisons. This is the canonical 'Top-K
Elements' pattern used in search engines, analytics pipelines, and anywhere leaderboard-style ranking
is needed.

Section 3 — Advanced Patterns, Streams & Real-World Scenarios (Q36–

Q50)
These questions separate strong 3-year candidates from everyone else. Be ready for stream internals, memory,
and design scenarios.

How do Java Streams interact with Collections? What is the difference between
Q36
stream() and parallelStream()? [Intermediate] [Intermediate]

Answer:
Collections serve as the source for Streams. Stream operations are lazy — intermediate operations
(filter, map, flatMap, sorted) build a pipeline but don't execute until a terminal operation (collect,
forEach, reduce, count) is invoked.
stream(): sequential, single-threaded processing. Elements processed in encounter order.
parallelStream(): uses [Link]() to process elements in parallel. Can improve
throughput for CPU-bound, stateless operations on large collections. NOT automatically faster —
parallelism has overhead: task splitting, coordination, merge. For small collections or I/O-bound
operations, parallel is often SLOWER.
Stateful operations in parallel streams: sorted(), distinct(), limit() in parallel streams require
coordination and can negate parallelism benefits or produce incorrect results with stateful lambdas.

Code Example:
List<Order> orders = loadOrders(); // millions of orders

// Sequential stream — predictable, ordered

Map<String, Double> avgByRegion = [Link]()
.filter(o -> [Link]() > 100)
.collect([Link](Order::getRegion,
[Link](Order::getAmount)));

// Parallel — beneficial only for CPU-intensive, stateless ops on large data

double total = [Link]()
.mapToDouble(Order::getAmount) // stateless, CPU-bound
.sum(); // parallel reduce

// Anti-pattern: parallel + stateful lambda — data race

List<Order> result = new ArrayList<>();
[Link]().forEach(result::add); // RACE CONDITION!
// Fix: use collect([Link]()) instead
List<Order> safe = [Link]().collect([Link]());
💡 Interviewer Tip:
parallelStream() shares [Link]() (default: cores - 1 threads) with all parallel
streams in the JVM. Blocking I/O in a parallel stream starves all other parallel operations. Rule: parallel
streams for stateless, CPU-bound, large (>10k elements) collections only. Use sequential streams +
CompletableFuture for I/O-bound work.

Q37 What are Collectors? Explain groupingBy, partitioningBy, and joining. [Intermediate]
[Intermediate]

Answer:
[Link] provides static factory methods for common reduction operations used as
terminal operations in [Link]().
groupingBy(classifier): groups stream elements into a Map<K, List<V>> by the classifier function.
Downstream collector (second arg) can change the list to a count, sum, set, etc.
partitioningBy(predicate): special case of groupingBy — returns Map<Boolean, List<T>> (true group
and false group). Exactly two groups.
joining(delimiter, prefix, suffix): concatenates stream elements (CharSequence) with optional
delimiter, prefix, suffix. Efficient — uses StringBuilder internally.
toMap(keyFn, valueFn, mergeFunc): collect into a Map. mergeFunc resolves duplicate keys. Without
mergeFunc, duplicate keys throw IllegalStateException.

Code Example:
List<Employee> emps = loadEmployees();

// groupingBy — Map<String, List<Employee>>

Map<String, List<Employee>> byDept = [Link]()
.collect([Link](Employee::getDept));

// groupingBy + downstream: average salary per department

Map<String, Double> avgSalary = [Link]()
.collect([Link](Employee::getDept,
[Link](Employee::getSalary)));

// groupingBy + count
Map<String, Long> countByDept = [Link]()
.collect([Link](Employee::getDept, [Link]()));

// partitioningBy — two groups

Map<Boolean, List<Employee>> seniorJunior = [Link]()
.collect([Link](e -> [Link]() >= 5));

// joining
String names = [Link]().map(Employee::getName)
.collect([Link](', ', '[', ']')); // [Alice, Bob, Zoe]

// toMap with merge fn (handle duplicate keys)

Map<String, Integer> salaryMap = [Link]()
.collect([Link](Employee::getName, Employee::getSalary,
Integer::max)); // keep higher salary for duplicate names

💡 Interviewer Tip:
groupingBy with a downstream collector is one of the most powerful Stream patterns.
[Link](), summingInt(), averagingDouble(), summarizingInt(), toUnmodifiableList(), toSet()
are all valid downstream collectors. Interviewers often ask: 'How do you group by and count?' —
[Link](fn, [Link]()) is the answer.
 What is the difference between [Link]().forEach() and
Q38
[Link]()? [Intermediate] [Intermediate]

Answer:
Both iterate elements and apply a Consumer — but with important differences.
[Link]() ([Link]()): defined on Iterable since Java 8. Iterates the collection
directly. For List: default implementation uses the iterator internally. CopyOnWriteArrayList overrides it
to iterate a snapshot. No intermediate pipeline.
[Link](): terminal operation on a stream. Can be parallelized (parallelStream().forEach()).
Does NOT guarantee encounter order even for sequential streams (use forEachOrdered() to guarantee
order). Works on any stream source, not just collections.
Mutability during forEach: [Link]() is documented to be undefined behavior if the
collection is structurally modified during iteration. [Link]() may throw
ConcurrentModificationException or behave unexpectedly if the source is modified.

Code Example:
List<String> list = new ArrayList<>([Link]('A','B','C'));

// [Link] — direct iteration, guaranteed order for List

[Link](s -> [Link](s)); // A, B, C (always ordered)

// [Link] — no order guarantee

[Link]().forEach(s -> [Link](s)); // may be A, B, C or other

// forEachOrdered — preserves encounter order even in parallel stream

[Link]().forEachOrdered(s -> [Link](s)); // always A, B, C

// [Link] — operates on snapshot

CopyOnWriteArrayList<String> cow = new CopyOnWriteArrayList<>(list);
[Link](s -> { [Link]('X'); }); // NO ConcurrentModificationException

// [Link] — on the map, not stream

[Link]((k, v) -> process(k, v)); // BiConsumer overload

💡 Interviewer Tip:
forEach() cannot use break or continue — use return to skip (like continue). For break semantics in a
stream, use takeWhile(predicate) (Java 9+) or findFirst(). [Link]() with parallelStream() is
non-deterministic order unless forEachOrdered() is used — a common parallel stream bug.

Q39 What is the Spliterator? Why does it exist? [Advanced] [Advanced]

Answer:
Spliterator (Splittable Iterator) is the mechanism that powers Stream parallel execution. It can split a
data source into two independent halves, each processed by a different thread.
Key methods: tryAdvance(action) — process one element. forEachRemaining(action) — process all
remaining. trySplit() — split into two Spliterators. estimateSize() — estimated remaining elements.
characteristics() — bitmask of properties.
Characteristics: SIZED, ORDERED, SORTED, DISTINCT, IMMUTABLE, CONCURRENT,
NONNULL, SUBSIZED. These help the stream pipeline optimize — e.g., SIZED allows exact parallel
partitioning. SORTED allows merge-sort optimization.
Custom Spliterators: when you wrap a custom data source (e.g., reading a large file in chunks),
implement Spliterator to make it stream-compatible and parallelizable.

Code Example:
 // ArrayList's Spliterator: ORDERED, SIZED, SUBSIZED
Spliterator<String> sp = [Link]();
[Link]([Link]()); // exact size

// trySplit() for parallel processing

Spliterator<String> left = [Link](); // sp retains right half
// left and sp can now be processed in parallel

// Process one at a time

[Link](s -> [Link](s));

// Custom Spliterator example skeleton

class RangeSpliterator implements Spliterator<Integer> {
int start, end;
@Override public boolean tryAdvance(Consumer<? super Integer> action) {
if (start >= end) return false;
[Link](start++); return true;
}
@Override public Spliterator<Integer> trySplit() {
int mid = (start + end) / 2;
if (mid <= start) return null;
RangeSpliterator left = new RangeSpliterator(start, mid);
start = mid; return left;
}
@Override public long estimateSize() { return end - start; }
@Override public int characteristics() { return SIZED|ORDERED|IMMUTABLE; }
}

💡 Interviewer Tip:
Spliterator is the bridge between data sources and the Streams API. [Link](spliterator,
parallel) wraps any Spliterator as a Stream. This is how libraries (like JDBC ResultSet wrappers)
expose custom data sources as Streams. The characteristics flags are critical for stream optimizations
— wrong characteristics cause incorrect or suboptimal pipelines.

What is the difference between [Link]() and [Link]()?

Q40
[Advanced] [Advanced]

Answer:
[Link]() is the convenient public API for collections — calls [Link]() and
passes it to StreamSupport.
[Link](spliterator, parallel) is the low-level factory that all stream creation ultimately
goes through. It's used to create streams from non-collection sources: custom Spliterators, arrays
([Link]), generators ([Link], [Link]), or library-provided data sources.
[Link](arr) uses ArraySpliterator internally. [Link](path) creates a stream from a
BufferedReader's Spliterator. [Link]() creates a stream from regex splitting.
Understanding this matters when wrapping legacy APIs or custom data sources as Streams.

Code Example:
// Collection convenience API → internally calls:
// [Link](spliterator(), false)
Stream<String> s1 = [Link]();

// Direct StreamSupport: wrap custom Spliterator

Spliterator<Integer> sp = new RangeSpliterator(0, 1_000_000);
Stream<Integer> rangeStream = [Link](sp, true); // parallel=true

// Wrap JDBC ResultSet as Stream (common pattern)

Stream<Row> resultStream = [Link](
 [Link](new ResultSetIterator(rs), 0),
false);

// [Link] — uses ArraySpliterator

String[] arr = {'a','b','c'};
Stream<String> arrStream = [Link](arr); // whole array
Stream<String> slice = [Link](arr, 1, 3); // subarray [b,c]

// File lines as stream

try (Stream<String> lines = [Link]([Link]('[Link]'))) {
[Link](l -> [Link]('ERROR')).forEach(log::error);
} // stream closed → reader closed

💡 Interviewer Tip:
[Link]() returns a Stream that wraps the BufferedReader. The stream MUST be closed after use
(try-with-resources) — otherwise the file handle leaks. Any Stream backed by an I/O resource
([Link], [Link], [Link]) requires explicit closing. Collection-backed streams don't need
closing.

What are the memory implications of using Collections in Java? How do you reduce
Q41
memory for large collections? [Advanced] [Advanced]

Answer:
Java collections have significant memory overhead per element due to object headers, references, and
wrapper types for primitives.
ArrayList<Integer>: each Integer is a boxed object (~16 bytes header + 4 bytes value = 20 bytes,
aligned to 16 = 16 bytes on 64-bit with compressed OOPs). Plus 4-8 bytes reference in the array. ~24
bytes per int vs 4 bytes for primitive int[].
HashMap<Integer,Integer>: each entry is a Node object (~32 bytes) + boxed key + boxed value. ~72
bytes per int-int pair vs 8 bytes in a flat int[].
Memory reduction strategies: use int[]/long[] instead of List<Integer> for large primitive collections.
Use Eclipse Collections (primitive maps/lists), Trove, or Koloboke for primitive collections. Use
EnumMap/EnumSet for enum keys. Use compact representations: BitSet for boolean collections.
Stream directly instead of materializing into a list when possible.

Code Example:
// ArrayList<Integer>: ~24 bytes/element (boxing overhead)
List<Integer> boxed = new ArrayList<>(1_000_000); // ~24MB

// int[]: 4 bytes/element — 6x more memory-efficient

int[] primitive = new int[1_000_000]; // ~4MB

// HashMap<Integer,Integer>: ~72+ bytes/pair

// For dense integer ranges: use array as map
int[] sparseMap = new int[MAX_KEY]; // random-access array

// BitSet: 1 bit per boolean instead of 1 byte (boolean[]) or 16 bytes (Boolean)

BitSet flags = new BitSet(1_000_000); // ~125KB for 1M flags
[Link](42); [Link](42); // O(1)

// Stream without materializing (zero collection memory)

OptionalInt max = [Link](1, 1_000_000).filter(n -> n%7==0).max();

// Pre-size collections to avoid excess capacity

ArrayList<String> list = new ArrayList<>(exact_size); // no wasted slots
[Link](); // after loading, trim excess
💡 Interviewer Tip:
The boxing overhead for Integer vs int is a real production concern at scale. A list of 10 million Integers
is ~240MB; an int[] is 40MB. Libraries like Eclipse Collections or Agrona provide primitive int/long
collections that match JVM performance. Profiling with heap dump analysis (VisualVM, JProfiler) is
how you find boxing overhead in production.

What is the best way to copy a collection in Java? Explain shallow vs deep copy.
Q42
[Intermediate] [Intermediate]

Answer:
Shallow copy: new collection with the same element references. Elements themselves are not copied.
Changes to elements in the copy affect the original (if elements are mutable).
Deep copy: new collection with independent copies of all elements. Changes to the copy don't affect
the original.
Shallow copy approaches: new ArrayList<>(original), [Link](original) (Java 10+, unmodifiable),
[Link](new ArrayList<>(original)).
Deep copy: manually copy each element (if it has a copy constructor or clone()). Stream with mapping
to new instances. Serialization round-trip (expensive, avoid in production). Best: design objects as
immutable — then shallow = deep since elements can't change.

Code Example:
// Shallow copy methods
List<String> original = new ArrayList<>([Link]('a','b','c'));
List<String> shallow1 = new ArrayList<>(original); // copy constructor
List<String> shallow2 = [Link](original); // immutable copy
List<String> shallow3 = [Link]().collect([Link]());
List<String> shallow4 = new ArrayList<>([Link](0, [Link]()));

// Shallow copy ISSUE with mutable elements

List<List<Integer>> nested = new ArrayList<>([Link](new
ArrayList<>([Link](1,2,3))));
List<List<Integer>> shallowCopy = new ArrayList<>(nested);
[Link](0).add(99); // modifies BOTH original and copy!

// Deep copy of nested collections

List<List<Integer>> deepCopy = [Link]()
.map(inner -> new ArrayList<>(inner)) // copy each inner list
.collect([Link]());
[Link](0).add(99); // only affects deepCopy

// Deep copy with copy constructor (immutable records: shallow = deep)

record Point(int x, int y) {} // immutable — shallow copy is safe
List<Point> pointsCopy = new ArrayList<>(points); // effectively deep

💡 Interviewer Tip:
Immutable value objects (Java 16 records, immutable classes) eliminate the shallow vs deep copy
distinction entirely — you can freely share references because the objects can't change. This is the
cleanest solution. For mutable objects that need deep copying, a copy constructor pattern (like in
Effective Java) is the recommended approach — avoid [Link]().

Q43 How do you remove duplicates from a List while preserving order? [Basic] [Basic]

Answer:
Several approaches, trading off simplicity, order preservation, and performance:
LinkedHashSet: add all elements — Set rejects duplicates, LinkedHashSet preserves insertion order.
Convert back to list. O(n) time, O(n) space.
[Link](): uses equals()/hashCode() to detect duplicates. Returns elements in encounter
order (insertion order for lists). Clean one-liner.
For sorted lists: adjacent duplicate removal with TreeSet or by scanning and removing adjacent
equals. Avoids extra Set memory.
Frequency counting: when you need to know HOW MANY duplicates, use a LinkedHashMap<T,
Integer> to count while preserving first-occurrence order.

Code Example:
List<String> withDups = new ArrayList<>([Link]('B','A','C','A','B','D'));

// Method 1: LinkedHashSet — preserves insertion order, O(n)

List<String> deduped1 = new ArrayList<>(new LinkedHashSet<>(withDups));
// [B, A, C, D]

// Method 2: [Link]() — cleanest

List<String> deduped2 = [Link]().distinct().toList();
// [B, A, C, D]

// Method 3: TreeSet — sorted order, NOT insertion order

List<String> sorted = new ArrayList<>(new TreeSet<>(withDups));
// [A, B, C, D] — alphabetical, not insertion order

// Method 4: in-place with a Set tracker

Set<String> seen = new HashSet<>();
[Link](s -> ); // removeIf + [Link] returns false for dup
// Modifies original list in-place

// Count occurrences (frequency map, insertion-order-first-occurrence)

Map<String, Long> freq = [Link]()
.collect([Link](s -> s, LinkedHashMap::new,
[Link]()));

💡 Interviewer Tip:
[Link]() internally builds a HashSet to track seen elements — equivalent to the
LinkedHashSet approach. The removeIf + [Link] pattern is elegant in-place deduplication without
creating a new list. Note: removeIf uses the [Link]() mechanism — it's fail-safe against
ConcurrentModificationException.

What is [Link]() vs [Link]() vs

Q44
[Link]()? [Intermediate] [Intermediate]

Answer:
All three produce read-only lists, but with different source handling and immutability guarantees:
[Link](list): returns a view. The underlying list can still be mutated externally,
and changes are visible through the unmodifiable view. Not truly immutable.
[Link](collection): creates a true copy. Changes to the original don't affect the copy. Null
elements not allowed. Implementation is compact and optimized. Returns a new list. Equivalent to new
ArrayList<>(source) but unmodifiable.
[Link](): terminal Stream operation. Creates an unmodifiable list from the
stream. Since Java 10. Equivalent to [Link]([Link]()) then [Link]() but more
efficient (no intermediate list).

Code Example:
 // [Link] — LIVE view
List<String> backing = new ArrayList<>([Link]('a','b'));
List<String> view = [Link](backing);
[Link]('c'); // UnsupportedOperationException
[Link]('c'); // OK — view now shows ['a','b','c']

// [Link] — independent copy

List<String> copy = [Link](backing); // ['a','b','c'] snapshot
[Link]('d'); // copy still shows ['a','b','c']
[Link]([Link](null, 'x')); // NullPointerException!

// [Link] — stream terminal

List<String> result = [Link]()
.filter(s -> [Link]('A'))
.collect([Link]());

// In practice: [Link]() and [Link]() are the idiomatic choices

// For streams: toUnmodifiableList() or .toList() (Java 16+)
List<String> toList = [Link]().filter(...).toList(); // Java 16+,
unmodifiable

💡 Interviewer Tip:
Java 16 added [Link]() — the most concise way to collect to an unmodifiable list. It's a
shorthand for .collect([Link]()). The distinction between unmodifiable (view,
original can change) and immutable (copy, independent) is subtle but important — unmodifiable lists
shared across threads while the original is mutated is a race condition.

How do you implement a multi-map (one key to multiple values) in Java?

Q45
[Intermediate] [Intermediate]

Answer:
Java's standard library has no built-in multi-map, but several idiomatic implementations exist:
Map<K, List<V>>: most common. Use computeIfAbsent for clean insertion. Query returns a List
(ordered, allows duplicates).
Map<K, Set<V>>: when values must be unique per key. computeIfAbsent(key, k -> new
HashSet<>()).add(value).
Map<K, Collection<V>>: abstract type — caller decides List vs Set. Less common.
Guava Multimap: [Link] — API designed for multi-maps.
ArrayListMultimap, HashMultimap, LinkedListMultimap, TreeMultimap. Cleaner API than Map<K,
List<V>>.

Code Example:
// Manual multi-map: Map<K, List<V>>
Map<String, List<String>> multiMap = new HashMap<>();

// Clean insertion with computeIfAbsent

[Link]('fruits', k -> new ArrayList<>()).add('apple');
[Link]('fruits', k -> new ArrayList<>()).add('banana');
[Link]('veggies', k -> new ArrayList<>()).add('carrot');

// Retrieve (returns null if key absent — check!)

List<String> fruits = [Link]('fruits', [Link]());

// Group by = multi-map via Stream

Map<String, List<Employee>> byDept = [Link]()
.collect([Link](Employee::getDept));
 // Guava Multimap (cleaner API)
Multimap<String, String> gMultimap = [Link]();
[Link]('fruits', 'apple');
[Link]('fruits', 'banana');
Collection<String> f = [Link]('fruits'); // ['apple','banana']
[Link]('fruits', 'apple'); // true

💡 Interviewer Tip:
[Link]() is the most common way to build a multi-map in Java — it's effectively Map<K,
List<V>> populated in one stream pass. The key performance note: always use computeIfAbsent() for
multi-map insertion — it avoids the double-lookup of containsKey() + put() and is atomic in
ConcurrentHashMap.

Q46 What is the difference between [Link]()/pop() and [Link]()/poll()? [Basic]

[Basic]

Answer:
Deque (Double-Ended Queue) supports both stack and queue semantics through different method
sets:
Stack semantics (LIFO): push(e) = addFirst(e). pop() = removeFirst(). peek() = peekFirst(). These
mirror [Link] but on ArrayDeque — much faster.
Queue semantics (FIFO): offer(e) = addLast(e). poll() = removeFirst(). peek() = peekFirst(). Same as
Queue interface — Deque implements Queue.
The same ArrayDeque can be used as a stack (push/pop) OR a queue (offer/poll) — just don't mix the
two on the same instance. The names signal intent to readers of your code.

Code Example:
ArrayDeque<String> deque = new ArrayDeque<>();

// As Stack (LIFO) — addFirst / removeFirst

[Link]('A'); // deque: [A]
[Link]('B'); // deque: [B, A]
[Link]('C'); // deque: [C, B, A]
[Link](); // returns 'C' — deque: [B, A]
[Link](); // returns 'B' — no removal

// As Queue (FIFO) — addLast / removeFirst

ArrayDeque<String> queue = new ArrayDeque<>();
[Link]('X'); // deque: [X]
[Link]('Y'); // deque: [X, Y]
[Link]('Z'); // deque: [X, Y, Z]
[Link](); // returns 'X' — deque: [Y, Z]

// Deque-specific: both ends

[Link]('F'); // insert at front
[Link]('L'); // insert at back
[Link](); // view front
[Link](); // view back

💡 Interviewer Tip:
Deque is the workhorse for many algorithm problems: BFS (use as queue), DFS (use as stack), sliding
window maximum (monotonic deque). ArrayDeque outperforms LinkedList for both roles due to array
locality. The palindrome check, browser history simulation, and undo/redo stacks all use Deque
semantics.
 How does [Link]() work and what are alternatives for frequency
Q47
counting? [Basic] [Basic]

Answer:
[Link](collection, element) counts occurrences of an element in a collection using
equals(). It's O(n) — linearly scans the collection.
For counting ONE element, frequency() is fine. For counting ALL elements, use a frequency map:
HashMap<T, Integer> with merge(), or [Link] + counting() in streams.
For very large collections, Apache Commons Collections' Frequency class or Guava's Multiset
(HashMultiset, TreeMultiset) provide more efficient tracking with O(1) count() per element.

Code Example:
List<String> words = [Link]('apple','banana','apple','cherry','banana','apple');

// [Link] — O(n) single element count

int appleCount = [Link](words, 'apple'); // 3

// Frequency map — O(n) all elements

Map<String, Integer> freq = new HashMap<>();
[Link](w -> [Link](w, 1, Integer::sum));
// {apple=3, banana=2, cherry=1}

// Stream groupingBy + counting

Map<String, Long> freq2 = [Link]()
.collect([Link](w -> w, [Link]()));

// Guava HashMultiset — O(1) count()

Multiset<String> ms = [Link](words);
[Link]('apple'); // 3
[Link](); // unique elements: Set<String>

// Most frequent element (single pass + max)

String mostFrequent = [Link]([Link](),
[Link]()).getKey(); // 'apple'

💡 Interviewer Tip:
[Link]() is O(n) per call. If you need to count multiple elements, calling frequency() for
each element is O(n * elements) — quadratic. Always build a frequency map (O(n) total) and query it
instead. Guava Multiset is the cleanest API when frequency operations are first-class concerns.

Q48 What is the best practice for returning an empty collection instead of null? [Basic]
[Basic]

Answer:
Returning null for empty collections is an anti-pattern (Joshua Bloch, Effective Java Item 54). Callers
must null-check before any collection operation — every call site is a potential NullPointerException
bug.
Return empty collections instead: [Link](), [Link](),
[Link]() — singletons, no allocation. [Link](), [Link](), [Link]() — also zero-element
immutable singletons.
For Optional: return Optional<T> for a single value that might be absent, NOT Optional<List<T>> — if
a list can be empty, return an empty list. Optional<List<T>> is an unnecessary double-wrapping.
Performance: [Link]() returns the SAME singleton instance every time — no
allocation. Compare this to returning new ArrayList<>() — always allocates.
Code Example:
// ANTI-PATTERN: returning null
List<Order> getOrders(String userId) {
if (!userExists(userId)) return null; // BAD
}
List<Order> orders = getOrders(id);
[Link](); // NullPointerException if user not found!

// CORRECT: return empty collection

List<Order> getOrders(String userId) {
if (!userExists(userId)) return [Link](); // singleton
return [Link](userId);
}
// Caller never needs to null check
int count = getOrders(id).size(); // always safe

// emptyList is a singleton — no allocation

List<String> e1 = [Link]();
List<String> e2 = [Link]();
[Link](e1 == e2); // true — same instance

// Java 9+: [Link]() for empty is also a singleton

List<String> empty = [Link](); // same cached empty instance

💡 Interviewer Tip:
This is an Effective Java principle that every experienced Java developer is expected to know cold.
'Never return null, always return empty' — this is the answer. The follow-up: 'What about
[Link]() vs new ArrayList<>()?' emptyList() returns a cached singleton, new
ArrayList<>() allocates every time. Use emptyList() for read-only empty returns.

How do you find the intersection, union, and difference of two collections?
Q49
[Intermediate] [Intermediate]

Answer:
Set operations on collections using Java's built-in methods — all O(n) using HashSet semantics:
Intersection (elements in both): retainAll() on a copy. Or stream filter with [Link]().
Union (all elements from both, no duplicates): addAll() to a Set. Or concat two streams into a Set.
Difference (in A but not in B): removeAll() on a copy. Or stream filter with ![Link]().
Critical: always convert the argument of retainAll/removeAll to a HashSet first — these methods call
contains() on the argument. If the argument is a List, each contains() call is O(n), making the whole
operation O(n²).

Code Example:
List<Integer> listA = [Link](1, 2, 3, 4, 5);
List<Integer> listB = [Link](3, 4, 5, 6, 7);
Set<Integer> setB = new HashSet<>(listB); // MUST convert to Set for O(n)

// Intersection (elements in A AND B)

List<Integer> intersection = [Link]()
.filter(setB::contains).toList(); // [3, 4, 5]

// Via retainAll (mutates copy)

Set<Integer> intersectSet = new HashSet<>(listA);
[Link](setB); // {3, 4, 5}

// Union (elements in A OR B, no duplicates)

Set<Integer> union = new HashSet<>(listA);
 [Link](listB); // {1,2,3,4,5,6,7}

// Difference (in A but NOT in B)

List<Integer> diff = [Link]()
.filter(e -> ).toList(); // [1, 2]

// Symmetric difference (in A or B but not both)

Set<Integer> symDiff = new HashSet<>(union);
[Link](intersectSet); // {1, 2, 6, 7}

💡 Interviewer Tip:
The O(n²) trap with retainAll/removeAll is a very common production performance bug.
[Link](otherList) calls [Link]() for each element — O(n) per element, O(n²)
total. Always: Set<T> otherSet = new HashSet<>(otherList); [Link](otherSet); — now O(n)
total.

Design a question: How would you implement a thread-safe, bounded, blocking

Q50
collection with priority ordering? [Advanced] [Advanced]

Answer:
This combines: PriorityQueue (priority ordering), blocking behaviour (put blocks when full, take blocks
when empty), and thread safety. The answer is PriorityBlockingQueue — BUT it is unbounded. For
bounded + priority + blocking, you need a custom implementation.
Standard answer: PriorityBlockingQueue provides thread-safe, priority-ordered, blocking take() — but
is UNBOUNDED (no capacity limit). Use it when you don't need a bound.
Custom bounded priority blocking queue: Use a ReentrantLock + two Conditions (notFull,
notEmpty) + a PriorityQueue internally. Lock protects the PriorityQueue. put() awaits notFull; take()
awaits notEmpty.
Production alternative: bounded PriorityBlockingQueue is not in the JDK — use a wrapper that tracks
size with a Semaphore, or use Disruptor (LMAX) for ultra-low-latency priority processing.

Code Example:
// Standard: PriorityBlockingQueue (unbounded, thread-safe)
PriorityBlockingQueue<Task> pbq = new PriorityBlockingQueue<>(11,
[Link](Task::getPriority));
[Link](task); // always succeeds (unbounded)
Task t = [Link](); // blocks if empty, returns highest priority

// Custom: bounded priority blocking queue

class BoundedPriorityQueue<T> {
private final PriorityQueue<T> pq;
private final ReentrantLock lock = new ReentrantLock();
private final Condition notFull = [Link]();
private final Condition notEmpty = [Link]();
private final int capacity;

BoundedPriorityQueue(int cap, Comparator<T> comp) {

[Link] = cap; [Link] = new PriorityQueue<>(comp);
}
public void put(T e) throws InterruptedException {
[Link](); try {
while ([Link]() == capacity) [Link]();
[Link](e); [Link]();
} finally { [Link](); }
}
public T take() throws InterruptedException {
[Link](); try {
while ([Link]()) [Link]();
 T e = [Link](); [Link](); return e;
} finally { [Link](); }
}
}

💡 Interviewer Tip:
This design question tests Collections + Concurrency together — exactly the kind of synthesis question
asked at senior/FAANG levels. Key points: PriorityBlockingQueue is the standard answer but is
unbounded. The custom implementation uses the ReentrantLock + Condition pattern (which mirrors
[Link]'s implementation). Mentioning ArrayBlockingQueue's source
as reference shows JDK-level knowledge.

Quick-Revision Cheat Sheet

Concept Key Fact / One-liner

ArrayList: O(1) random access, O(n) insert. LinkedList: O(1) head/tail, O(n)
ArrayList vs LinkedList
random access. Use ArrayList for almost everything.

Growth factor 1.5x. Default capacity 10. Pre-size: new ArrayList<>(n) to

ArrayList resize
avoid resizes.

Array of buckets. Hash: h ^ (h>>>16). Index: (n-1) & hash. Java 8:

HashMap internals
chain→tree at bucket size 8 (treeify). Default cap=16, load=0.75.

equals()→ must have same hashCode(). hashCode same → need not be

equals() + hashCode()
equals(). Violate: [Link]() returns null for logically equal keys.

HashSet / LinkedHashSet / HashSet: O(1), no order. LinkedHashSet: O(1), insertion order. TreeSet:
TreeSet O(log n), sorted order. Navigation methods on TreeSet.

HashMap: O(1), unordered, null key ok. TreeMap: O(log n), sorted, no null
HashMap vs TreeMap
key. Use TreeMap for range queries (subMap, headMap, tailMap).

Fail-fast (ArrayList, HashMap): ConcurrentModificationException on

Fail-fast vs fail-safe structural change during iteration. Fail-safe (CopyOnWriteArrayList,
ConcurrentHashMap): no exception, snapshot or weakly-consistent.

Comparable: natural ordering inside class (compareTo). Comparator:

Comparable vs Comparator
external strategy (compare). [Link]() chains fluently.

accessOrder=true + override removeEldestEntry(). get() promotes to tail

LinkedHashMap LRU
(MRU). Head is evicted (LRU) when removeEldestEntry() returns true.

Hashtable: synchronized every method, no null key/value, legacy. HashMap:

HashMap vs Hashtable not synchronized, null key ok, fast. Use ConcurrentHashMap for thread
safety.

Binary min-heap. Poll = O(log n), peek = O(1). Iteration NOT in priority order.
PriorityQueue
Use [Link]() for max-heap.

Faster than Stack and LinkedList for stack/queue roles. No null allowed. Use
ArrayDeque
as stack (push/pop) or queue (offer/poll).
 sort (TimSort, stable), binarySearch (list must be sorted), unmodifiableXxx
Collections utility
(view), synchronizedXxx (full lock), emptyList (singleton).

[Link]: true copy, no null, immutable. unmodifiableList: live view, original can
[Link] vs unmodifiableList
change. [Link](): stream terminal.

Keys are WeakReferences. Entry auto-removed when key GC'd. Use for
WeakHashMap caches tied to object lifecycle. String literals never GC'd — useless as
WeakHashMap keys.

EnumMap: array-indexed by ordinal, O(1) no hashing. EnumSet: bitmask,

EnumMap / EnumSet
bitwise ops. Both faster and compact vs HashMap/HashSet for enum keys.

Uses == and [Link]. For object identity tracking.

IdentityHashMap
Intentionally violates Map contract. Used in serialization cycle detection.

TreeMap methods: lowerKey, floorKey, ceilingKey, higherKey, headMap,

NavigableMap
tailMap, subMap, descendingMap, pollFirstEntry/pollLastEntry.

TimSort: O(n log n) worst, O(n) best (nearly sorted). Stable. Dual-Pivot
[Link]
QuickSort for primitive arrays ([Link] int[]).

synchronizedXxx: full lock. CopyOnWriteArrayList: lock-free reads, O(n)

Thread-safe collection options writes. ConcurrentHashMap: per-bucket. ConcurrentSkipListMap: sorted +
concurrent.

ALWAYS convert argument to HashSet first. retainAll(list) = O(n²).

retainAll/removeAll with Set
retainAll(new HashSet<>(list)) = O(n).

LinkedHashMap(capacity, 0.75f, true) + removeEldestEntry(). Or: HashMap

LRU Cache
+ doubly-linked list (LeetCode 146). Production: Caffeine.

[Link](): O(n) single. [Link](k,1,Integer::sum): O(n) all.

Frequency counting
[Link]+counting(): stream version.

NEVER return null. Return [Link]()/emptySet()/emptyMap()

Empty collection vs null
— singletons, no allocation. Callers never need null checks.

intersection: stream().filter(setB::contains). union: new HashSet<>(a);

Set intersection/union/diff addAll(b). diff: stream().filter(e->). Always pre-convert to
Set.

push/pop: LIFO stack semantics (addFirst/removeFirst). offer/poll: FIFO

Deque push/pop vs offer/poll
queue semantics (addLock/removeFirst). ArrayDeque implements both.

Splittable iterator powering parallel streams. trySplit() divides for parallel.

Spliterator
SIZED, ORDERED, SORTED characteristics drive stream optimizations.

Bounded priority blocking PriorityBlockingQueue: unbounded, thread-safe, blocking take. For bounded:
queue ReentrantLock + Condition + PriorityQueue. Or semaphore-wrapped PBQ.

ArrayList<Integer>: ~24 bytes/int. int[]: 4 bytes/int (6x difference).

Memory: boxing overhead HashMap<Integer,Integer>: ~72 bytes/pair. Use primitive arrays or Eclipse
Collections for scale.

Good luck — you've got this! ☕