Java Runtime
- JVM architecture
- ClassLoader
- JIT compiler
- Heap and GC
- Java Memory Model
Loading...
Loading...
A structured prep page for Java internals, collections, concurrency, and DSA coding rounds. Study the concept, revise the pattern, then solve the matching interview problem.
40+
Interview Q&A
8
Core Tracks
18
DSA Patterns
2026-27
Target
Study Flow
Follow this order when you want interview readiness instead of random topic hopping.
Week 1
OOP, String pool, exception handling, generics, streams, and collection basics.
Week 2
JVM memory, GC, HashMap, ConcurrentHashMap, PriorityQueue, and Java 21 updates.
Week 3
Two sum, Kadane, sliding window, cycle detection, LRU cache, and dry runs.
Week 4
Traversal, LCA, diameter, topological sort, union-find, knapsack, and LCS.
DSA becomes easier when every problem is mapped to a pattern first. Use this as a quick revision board before solving.
| Area | Pattern | Examples |
|---|---|---|
| Arrays and Strings | Two pointers, sliding window, prefix sum | Two Sum, Three Sum, Longest Substring |
| Linked List | Slow-fast pointer, reversal, dummy node | Cycle detection, merge, palindrome list |
| Trees | DFS, BFS, recursion return values | Traversal, LCA, diameter, serialize tree |
| Graphs | BFS, DFS, indegree, DSU | Topological sort, components, Kruskal pattern |
| Dynamic Programming | State, transition, base case | Coin Change, LCS, 0/1 Knapsack |
First revise the concept, then write the Java implementation, then explain time and space complexity aloud.
2 Java internals questions, 2 DSA problems, 1 dry run, and 1 mock explanation per day.
Move from arrays and strings to linked lists, trees, graphs, and then dynamic programming.
Original Content
Neeche original article ka full content hai. Design sirf navigation aur revision ko better banata hai; content remove nahi kiya gaya.
Q.1
Explain JVM Architecture in depth - ClassLoader, Runtime Data Areas, Execution Engine.FAANG
**JVM (Java Virtual Machine)**has 3 main subsystems:
1. ClassLoader Subsystem:
2. Runtime Data Areas (Memory):
3. Execution Engine:
Metaspace
Q.2
What is the Parent Delegation Model in ClassLoading? Why is it important?HARD
When a ClassLoader is asked to load a class, itdelegates the request to its parent first, and only loads the class itself if the parent cannot find it.
**Order:**App ClassLoader → Extension ClassLoader → Bootstrap ClassLoader → (loads or delegates back down)
Why important?
// Custom ClassLoader breaking delegation (for plugins/hot-reload):
public class
extends
public
throws
if
"com.myapp"
return
// skip parent delegation
return super
// use parent for rest
Q.3
Explain JIT compilation - C1 vs C2, Tiered Compilation, Deoptimization.FAANG
JIT (Just-In-Time) compiler converts bytecode into native machine code at runtime forhot methods(frequently executed code).
**C1 Compiler (Client):**Fast compilation with basic optimizations. Used for startup speed. Generates code quickly with limited optimization.
**C2 Compiler (Server):**Aggressive optimizations - inlining, loop unrolling, escape analysis, dead code elimination. Takes longer to compile but generates highly optimized native code.
**Tiered Compilation (Java 7+):**Uses both C1 and C2. Starts with interpreted mode → C1 → C2 as method heats up. Best of both worlds.
Key optimizations by JIT:
**Deoptimization:**If JIT made an assumption (e.g., a method is always called with int) and that assumption is violated, JVMdeoptimizesback to interpreter. This is why polymorphism can slow code - it prevents certain inlining.
-XX:+PrintCompilation
Q.4
What is String Pool? Where does it live in Java 8+? Explain intern().MEDIUM
TheString Pool(also called String Constant Pool) is a special storage area that holds unique String literals to avoid creating duplicate String objects.
**In Java 7 and before:**String Pool was in PermGen (fixed-size, could cause OutOfMemoryError).
In Java 8+:String Pool moved toHeap memory(can grow, eligible for GC).
"hello"
// goes to String Pool
"hello"
// reuses same pool object
new
"hello"
// creates NEW object in Heap
// true (same pool reference)
// false (s3 is separate heap object)
// true (same content)
// returns the pool reference for "hello"
// true
intern()- Adds the string to the pool if not present, and returns the pool reference. Useful for memory optimization when handling many duplicate strings.
Q.5
What is Escape Analysis? How does it affect object allocation?HARD
Escape Analysisis a JIT optimization where the JVM analyzes whether an object "escapes" the scope of the method that created it.
If an object does NOT escape:
public
new
3
4
// p doesn't escape → stack allocated
return
public
new
3
4
// p escapes → heap allocated
return
-XX:+DoEscapeAnalysis
-XX:+PrintEscapeAnalysis
Q.6
Explain Java Memory Model (JMM) - visibility, happens-before, volatile.FAANG
The**Java Memory Model (JMM)**defines how threads interact through memory - specifically, when writes by one thread become visible to another.
**Problem without JMM guarantees:**Each CPU has its own cache. A write by Thread-1 may stay in CPU-1's cache and Thread-2 (on CPU-2) reads stale data.
**Happens-Before Relationship:**If action Ahappens-beforeaction B, then A's results are visible to B. Key rules:
volatile keyword:
private volatile boolean
true
// Thread 1:
false
// visible to Thread 2 immediately
// Thread 2:
while
// sees updated value
Q.7
Explain HashMap internal working - hashing, collision, treeification in Java 8+.FAANG
HashMapis backed by an array ofNode<K,V>[](called buckets). Default initial capacity = 16, load factor = 0.75.
How put(key, value) works:
hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)- this is thespread/perturbationstep to reduce collisions.index = hash & (capacity - 1)**Rehashing:**When size > capacity × loadFactor (default: 16 × 0.75 = 12), the array is resized to 2× and all entries are re-hashed.
// Key internal constants:
static final int
1
4
// 16
static final float
0.75f
static final int
8
// list → tree
static final int
6
// tree → list
static final int
64
Q.8
How does ConcurrentHashMap achieve thread-safety without locking the whole map?FAANG
Java 7 ConcurrentHashMap:UsedSegment-level locking(16 segments by default). Each segment was a ReentrantLock-guarded mini-HashMap. Max 16 concurrent writes.
**Java 8 ConcurrentHashMap:**Completely redesigned. No segments. Uses:
This allows truly concurrent reads and concurrent writes to different buckets simultaneously.
// Java 8 putVal simplified logic:
if
// CAS - no lock
else
synchronized
// lock only this bucket
// insert into chain or tree
Q.9
Compare HashMap vs LinkedHashMap vs TreeMap vs WeakHashMap.MEDIUM
| Feature | HashMap | LinkedHashMap | TreeMap | WeakHashMap | | --- | --- | --- | --- | --- | | Order | No order | Insertion order | Sorted (natural/comparator) | No order | | Null keys | 1 null allowed | 1 null allowed | NOT allowed | 1 null allowed | | get/put | O(1) avg | O(1) avg | O(log n) | O(1) avg | | Backed by | Array + LL/Tree | HashMap + DoublyLL | Red-Black Tree | WeakReference array | | Special use | General use | LRU Cache | Range queries | Caches (GC collectable) | | Thread-safe | No | No | No | No |
**WeakHashMap:**Keys are held with WeakReferences. When a key has no strong references elsewhere, it becomes eligible for GC and the entry is automatically removed. Used for memory-sensitive caches.
LinkedHashMap for LRU Cache:
new
0.75f
true
// true = access-order
protected boolean
return
Q.10
What is fail-fast vs fail-safe iteration? Explain with examples.MEDIUM
**Fail-Fast:**ThrowsConcurrentModificationExceptionimmediately if the collection is modified during iteration (other than through the iterator itself). Uses amodCountfield - checked on every next() call.
Examples: ArrayList, HashMap, HashSet iterators.
**Fail-Safe:**Works on acopyof the collection (snapshot). No ConcurrentModificationException. Changes during iteration are not reflected.
Examples: CopyOnWriteArrayList, ConcurrentHashMap iterators.
// Fail-Fast - THROWS ConcurrentModificationException:
new
"a"
"b"
"c"
for
if
"b"
// modifies during iteration
// Safe way - use iterator.remove():
while
if
"b"
// OK
// Fail-Safe - no exception:
new
for
"new"
// no exception, iterates original copy
Q.11
ArrayList vs LinkedList - when to use which? Internal structure?EASY
| Operation | ArrayList | LinkedList | | --- | --- | --- | | get(index) | O(1) - random access | O(n) - traversal needed | | add(end) | O(1) amortized | O(1) | | add(middle) | O(n) - shift elements | O(n) - traversal, then O(1) insert | | remove(middle) | O(n) - shift elements | O(n) - traversal, then O(1) remove | | Memory | Less (contiguous array) | More (each node has 2 pointers) | | Cache performance | Better (spatial locality) | Worse (scattered memory) |
Use ArrayListfor random access, frequent reads, and when size is roughly known.
Use LinkedListfor frequent insertions/deletions at head/tail (as Deque). In practice, ArrayList is almost always faster due to CPU cache effects.
Q.12
Explain PriorityQueue and its internal structure. How is it used in Dijkstra's algorithm?HARD
PriorityQueueis backed by aMin-Heap(binary heap stored in array). The element with the smallest natural order (or comparator order) is always at the head.
**Operations:**offer/add O(log n), poll O(log n), peek O(1).
// Min-heap (default): smallest element at top
new
// Max-heap: largest element at top
new
// Dijkstra's shortest path skeleton:
int
new
1
1
// [node, dist]
new int
0
int
new int
0
while
int
int
0
1
if
continue
// stale entry
for
int
int
1
if
0
0
new int
0
Time
O((V + E) log V)
Space
O(V + E)
Q.13
What is Type Erasure? Why does Java use it? What are its limitations?HARD
Type Erasureis the process by which the Java compiler removes all generic type information at compile time and replaces type parameters with their bounds (or Object).
**Why?**Java generics were added in Java 5 for backward compatibility. The JVM does not know about generics at runtime - only the compiler does.
// At compile time:
new
"hello"
0
// After type erasure (what JVM sees):
new
// raw type
"hello"
0
// compiler inserts cast
Limitations due to type erasure:
new T()- type not known at runtime.instanceof List<String>- always useinstanceof List.new T[10]- illegal.void m(List<String>)andvoid m(List<Integer>)are same after erasure.List<String>.classdoesn't exist - onlyList.class.Q.14
Explain PECS principle - Producer Extends, Consumer Super.HARD
**PECS (Producer Extends, Consumer Super)**is a guideline for using wildcards in Generics correctly.
**? extends T (Upper Bounded - Producer):**Use when you only READ from the collection. The collection produces elements of type T or subtype.
**? super T (Lower Bounded - Consumer):**Use when you only WRITE to the collection. The collection consumes elements of type T or supertype.
// Producer: reading from source (extends)
public
static
void
extends
super
for
// reading from src (producer)
// writing to dst (consumer)
// Use extends when reading:
extends
// can hold List<Integer>, List<Double>
0
// OK - reading
42
// ERROR - cannot add (type unknown)
// Use super when writing:
super
// can hold List<Integer>, List<Number>, List<Object>
42
// OK - writing Integer
0
// ERROR - returns Object, not Integer
copy(List<? super T> dest, List<? extends T> src)
Q.15
Explain Stream pipeline - intermediate vs terminal operations. Is a Stream lazy?MEDIUM
AStream pipelinehas three parts: Source → Intermediate Operations → Terminal Operation.
Intermediate operationsarelazy- they don't execute until a terminal operation is called. They return a new Stream. Examples: filter, map, flatMap, distinct, sorted, peek, limit, skip.
Terminal operationstrigger the pipeline execution. Examples: collect, forEach, count, reduce, findFirst, anyMatch, toArray.
"Alice"
"Bob"
"Charlie"
"Anna"
"A"
// intermediate (lazy)
// intermediate (lazy)
// intermediate (lazy)
// terminal - triggers execution
// Short-circuit: stops early when condition met
"A"
// stops at "Alice"
**Laziness benefit:**filter(predicate).findFirst() won't process all elements - stops at first match.
Q.16
Explain flatMap() vs map(). Explain reduce() with examples.MEDIUM
map()- 1-to-1 transformation. Each element maps to exactly one result.
flatMap()- 1-to-many transformation. Each element maps to a Stream, then all streams are flattened into one.
// map: List of lists stays nested
1
2
3
4
// [[1,2],[3,4]]
// flatMap: flattens the nested structure
// [1, 2, 3, 4]
// reduce: fold elements into single result
int
1
10
0
// 55
Q.17
When should you use parallel streams? What are the pitfalls?HARD
Parallel streamsuse ForkJoinPool.commonPool() (threads = CPU cores - 1) to split work across threads.
When to use:
Pitfalls:
// WRONG - race condition:
new
// not thread-safe
// data corruption
// RIGHT - thread-safe collector:
0
// thread-safe
Q.18
synchronized vs ReentrantLock - when to use which?HARD
| Feature | synchronized | ReentrantLock | | --- | --- | --- | | Acquisition | Implicit (block/method) | Explicit: lock()/unlock() | | Fairness | No guarantee | Can be fair: new ReentrantLock(true) | | Interruptible | No | lockInterruptibly() - yes | | Try lock | No | tryLock() - yes | | Multiple conditions | One wait/notify set | Multiple Condition objects | | Scope | Block/method only | Can span across methods | | Performance | Good (JVM optimized) | Slightly more overhead |
// ReentrantLock example:
new
try
// critical section
finally
// ALWAYS in finally!
// tryLock to avoid deadlock:
if
5
try
/* do work */
finally
else
// couldn't get lock - handle gracefully
Q.19
What are Virtual Threads (Project Loom, Java 21)? How do they differ from platform threads?FAANG
Virtual Threads(introduced as preview in Java 19, stable in Java 21) are lightweight threads managed by the JVM, not the OS.
Platform threads= OS threads. Creating 10,000 platform threads is expensive (each ~1MB stack, OS context switching). A JVM typically runs up to a few thousand.
Virtual threadsare mounted oncarrier threads(platform threads in ForkJoinPool). When a virtual thread blocks on I/O, it isunmountedfrom the carrier thread (which can pick up another virtual thread). No OS thread is wasted waiting.
You can createmillionsof virtual threads.
// Creating virtual threads (Java 21):
"Running in virtual thread"
// Virtual thread per task executor:
try
for
int
0
1_000_000
// 1M concurrent tasks!
**Key point:**Virtual threads excel for I/O-bound tasks (HTTP, DB calls). For CPU-bound work, they offer no advantage - parallel streams with platform threads are better.
Q.20
Explain CompletableFuture - thenApply vs thenCompose vs thenCombine. Exception handling.HARD
CompletableFutureis Java 8's async programming API that allows chaining of async tasks without blocking threads.
// thenApply: transform result (like map)
// User → String
// thenCompose: chain futures (like flatMap - avoids nesting)
// returns CF, not nested CF<CF>
// thenCombine: combine two independent futures
" is "
// Exception handling:
"default value"
// recover
// or handle both
if
null
return
"error"
return
Q.21
What is a deadlock? How to detect and prevent it?MEDIUM
Adeadlockoccurs when two or more threads wait for each other to release locks they hold, forming a cycle - all threads are stuck forever.
**Four conditions (Coffman's):**Mutual Exclusion + Hold and Wait + No Preemption + Circular Wait. All four must hold for deadlock.
// Classic deadlock:
// Thread-1: lock A → wait for B
// Thread-2: lock B → wait for A
synchronized
100
synchronized
// Thread-1 waits here for lockB
// Thread-2 does same but lockB first, then lockA
Prevention strategies:
**Detection:**Usejstack <pid>orjconsoleto detect deadlocks. ThreadMXBean.findDeadlockedThreads() in code.
Q.22
Explain Java Heap structure and Generational GC. How does Minor GC vs Major GC work?HARD
Heap structure:
**Minor GC (Young GC):**Collects only Young Gen. Fast (usually < 100ms). Objects surviving GC are copied to a Survivor space. After N cycles (default: 15), object promoted to Old Gen.
**Major/Full GC:**Collects Old Gen (and usually Young Gen). Slow - can cause Stop-The-World (STW) pauses of seconds. Application threads paused during STW.
**Object lifecycle:**Eden → (Minor GC) → S0/S1 → (age++) → Old Gen → (Major GC)
-Xms
-Xmx
-Xmn
-XX:MaxTenuringThreshold
Q.23
Compare G1 GC vs ZGC vs Shenandoah. Which should you use when?FAANG
| GC | STW Pause | Throughput | Best For | Available Since | | --- | --- | --- | --- | --- | | G1 GC | ~10-200ms | High | Default for most apps, balanced | Java 9 (default) | | ZGC | <1ms (sub-ms) | Medium | Low-latency, large heaps (TB+) | Java 15 (stable) | | Shenandoah | <10ms | Medium | Low-latency, moderate heaps | Java 15 (stable) | | Serial GC | High | Low | Single-core, very small heaps | Java 1.0 | | Parallel GC | Medium | Highest | Batch processing, max throughput | Java 1.4 |
**G1 GC:**Divides heap into equal-size regions (~2048 regions). Prioritizes collecting "garbage first" - regions with most garbage collected first. Predictable pause times.
**ZGC (Java 21 enhanced):**Concurrent - most work done while app threads run. Pause times independent of heap size. Uses colored pointers and load barriers. Now also generational in Java 21 for better throughput.
// Switch GC from command line:
// G1 (default Java 9+)
// ZGC - low latency
// Shenandoah
// Parallel - max throughput
Q.24
Longest Substring Without Repeating Characters - explain Sliding Window approach.MEDIUM
**Problem:**Given a string, find the length of the longest substring without repeating characters.
**Approach:**Sliding Window with HashMap. Maintain a window [left, right]. Expand right, if character repeated, shrink left past the last occurrence.
public int
new
int
0
0
for
int
0
char
if
1
// skip past duplicate
1
return
// "abcabcbb" → 3 ("abc")
Time
O(n)
Space
O(min(m,n))
Q.25
Two Sum, Three Sum, Two Sum II - explain all variants with optimal solutions.EASY-MEDIUM
**Two Sum (unsorted):**HashMap approach - store complement.
public int
int
int
new
for
int
0
int
if
return new int
return new int
1
1
// O(n) time, O(n) space
// Three Sum: Sort + Two Pointers
public
int
new
for
int
0
2
if
0
1
continue
// skip dup
int
1
1
while
int
if
0
while
1
while
1
else if
0
else
return
// O(n²) time, O(1) extra space
Q.26
Maximum Subarray (Kadane's Algorithm). Explain and code it.EASY
Find the contiguous subarray with the largest sum.
**Kadane's Algorithm:**At each position, decide - should I extend the current subarray, or start fresh? Take whichever is larger.
public int
int
int
0
0
for
int
1
// extend or restart
return
// [-2,1,-3,4,-1,2,1,-5,4] → 6 ([4,-1,2,1])
Time
O(n)
Space
O(1)
Q.27
Trapping Rain Water - explain the approach.HARD
Water trapped at index i = min(maxLeft[i], maxRight[i]) - height[i].
Optimal: Two Pointer approach - O(1) space.
public int
int
int
0
1
int
0
0
0
while
if
if
else
else
if
else
return
Time
O(n)
Space
O(1)
Q.28
Detect cycle in a linked list (Floyd's Algorithm). Find the start of the cycle.MEDIUM
**Floyd's Tortoise and Hare:**slow moves 1 step, fast moves 2 steps. If there's a cycle, they will meet inside the cycle.
// Detect cycle:
public boolean
while
null
null
if
return true
return false
// Find cycle START:
// After meeting: reset one pointer to head.
// Move both 1 step. They meet at cycle start.
public
while
null
null
if
// reset to head
while
return
// cycle start node
return null
Time
O(n)
Space
O(1)
Q.29
Design LRU Cache with O(1) get and O(1) put.HARD
UseHashMap + Doubly Linked List. HashMap gives O(1) access. DLL maintains order (most recent at head, LRU at tail).
class
private
new
private
// dummy nodes
private int
class
int
int
int
public
int
this
new
0
0
new
0
0
public int
int
if
return
1
// mark as recently used
return
public void
int
int
if
new
if
// evict LRU
private void
private void
Q.30
All tree traversals - recursive and iterative. Level order traversal using queue.EASY
// Inorder: Left → Root → Right (BST gives sorted output)
void
if
null
return
// Iterative Inorder:
public
new
new
while
null
while
null
return
// Level Order (BFS):
public
new
if
null
return
new
while
int
new
for
int
0
if
null
if
null
return
Q.31
Lowest Common Ancestor (LCA) of a Binary Tree. Explain with code.MEDIUM
LCA of two nodes p and q is the deepest node that is an ancestor of both.
public
if
null
return
// If both sides return non-null, root is LCA
if
null
null
return
// Otherwise one side has both nodes
return
null
// O(n) time - visits every node once in worst case
Time
O(n)
Space
O(h) - recursion stack
Q.32
Diameter of a Binary Tree. Serialize and Deserialize a Binary Tree.HARD
Diameter= longest path between any two nodes (may not pass through root).
int
0
public int
return
private int
if
null
return
0
int
// path through this node
return
1
// height of this node
// Serialize/Deserialize (preorder + null markers):
public
if
null
return
"#"
return
","
","
private int
0
public
","
return
private
if
"#"
return null
new
return
Q.33
Topological Sort - Kahn's Algorithm (BFS) vs DFS approach.MEDIUM
Topological sort orders nodes of a DAG (Directed Acyclic Graph) such that for every edge u→v, u comes before v.
// Kahn's Algorithm (BFS - in-degree based):
public int
int
int
int
new int
new
for
int
0
new
for
int
0
1
1
new
for
int
0
if
0
int
new int
int
0
while
int
for
int
if
0
return
new int
0
// empty = cycle exists
Time
O(V + E)
Space
O(V + E)
Q.34
Union-Find (Disjoint Set Union) - path compression + union by rank. Applications.HARD
DSU maintains a collection of disjoint sets, supporting union and find operations in nearly O(1) (amortized O(α(n)) where α is inverse Ackermann).
class
int
int
new int
new int
for
int
0
int
int
if
// path compression
return
boolean
int
int
int
if
return false
// already connected
if
int
// union by rank
if
return true
**Applications:**Number of connected components, Detect cycle in undirected graph, Kruskal's MST, Number of Islands variation, Accounts Merge.
Q.35
Coin Change problem - bottom-up DP. Explain the recurrence.MEDIUM
Find the minimum number of coins to make amount. Coins can be reused (unbounded).
**Recurrence:**dp[i] = min(dp[i - coin] + 1) for each coin ≤ i.
public int
int
int
int
new int
1
1
// infinity
0
0
for
int
1
for
int
if
1
return
1
// coins=[1,5,11], amount=15 → 3 (5+5+5)
Time
O(amount × coins)
Space
O(amount)
Q.36
Longest Common Subsequence (LCS) - 2D DP table. Space optimization.MEDIUM
// 2D DP:
public int
int
int
new int
1
1
for
int
1
for
int
1
if
1
1
1
1
1
else
1
1
return
// Space optimized O(n) - use 1D array:
public int
int
new int
1
for
char
int
0
for
int
1
int
1
1
1
return
Time
O(m × n)
Space
O(n) optimized
Q.37
0/1 Knapsack problem - explain the DP approach.MEDIUM
Given weights and values of n items, and capacity W. Maximize value without exceeding capacity. Each item used at most once.
public int
int
int
int
int
int
new int
1
1
for
int
1
for
int
0
1
// don't take item i
if
1
// take item i (if fits)
1
1
1
return
// Space optimize: traverse w from W to wt[i] (right to left)
Time
O(n × W)
Space
O(n × W) or O(W)
Q.38
Compare all sorting algorithms. When does QuickSort fail?MEDIUM
| Algorithm | Best | Average | Worst | Space | Stable | | --- | --- | --- | --- | --- | --- | | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | | Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ |
**QuickSort fails (O(n²)) when:**Pivot is always min/max (already sorted array + first/last pivot). Fixed by random pivot or median-of-three pivot.
Java's Arrays.sort():UsesDual-Pivot QuickSortfor primitives (faster in practice), andTimSort(merge sort + insertion sort hybrid) for Objects (stable sort).
Q.39
Binary Search and all its variants - find first/last occurrence, search rotated sorted array.MEDIUM
// Standard binary search:
int
int
int
int
0
1
while
int
2
// avoid integer overflow
if
return
else if
1
else
1
return
1
// First occurrence:
int
int
int
int
0
1
1
while
int
2
if
1
// go left
else if
1
else
1
return
// Search in Rotated Sorted Array:
int
int
int
int
0
1
while
int
2
if
return
if
// left half sorted
if
1
else
1
else
// right half sorted
if
1
else
1
return
1
Q.40
Dutch National Flag algorithm - sort 0s, 1s, 2s in one pass.MEDIUM
Three-pointer approach by Dijkstra: low, mid, high. All 0s go before low, all 2s after high, 1s between low and high.
public void
int
int
0
0
1
while
if
0
// 0: move to front
else if
1
// 1: in place
else
// 2: move to back
// [2,0,2,1,1,0] → [0,0,1,1,2,2]
Time
O(n)
Space
O(1)
Passes
Single pass