JAVA + DSA

Placement Interview Master Guide

Core Java Theory & Deep-Dive Q&A + Data Structures & Algorithms
Covering the technical / coding-round style asked across:
Tier-1: Google · Microsoft · Amazon · Meta-style product companies
Tier-2 / Tier-3: IBM · TCS · Infosys · Wipro · Cognizant · Capgemini and similar
service companies

How to use this guide

Each topic has two parts: THEORY NOTES (concept explained clearly, including the 'why', not just the 'what')
and PRACTICE Q&A (the actual questions asked in interviews, phrased the way interviewers phrase them, with
complete answers — including the tricky edge-case / 'gotcha' questions like operator behavior, off-by-one traps,
and 'why does X fail' questions). Work through one topic at a time. For coding-round prep, re-implement every
algorithm mentioned in Part B yourself in Java before your interview — reading answers is necessary but not
sufficient; typing the code out builds the muscle memory interviewers are testing.

Page 1 | Java + DSA Placement Interview Master Guide

 Table of Contents
PART A: CORE JAVA
1. Language Basics, Data Types & Type Conversion
2. Operators — Especially ++ / -- and Precedence Traps
3. Control Flow, Loops & Exception Basics
4. OOP — Encapsulation, Inheritance, Polymorphism, Abstraction
5. Strings, StringBuilder, StringBuffer & the String Pool
6. Exception Handling — Deep Dive
7. Collections Framework
8. Multithreading & Concurrency
9. JVM Architecture, Memory & Garbage Collection
10. Java 8+ Features — Lambdas, Streams, Functional Interfaces, Optional

PART B: DSA
1. Complexity Analysis & Big-O Foundations
2. Arrays & Strings
3. Linked Lists
4. Stacks & Queues
5. Trees — Binary Trees, BSTs, Traversals & Balancing
6. Graphs — Representation, BFS/DFS, Shortest Paths
7. Sorting & Searching Algorithms
8. Recursion & Backtracking
9. Dynamic Programming
10. Greedy Algorithms & Hashing

Page 2 | Java + DSA Placement Interview Master Guide

 PART A: CORE JAVA

1. Language Basics, Data Types & Type Conversion

THEORY NOTES
Java is a statically-typed, compiled-then-interpreted language: source (.java) compiles to bytecode (.class),
which the JVM interprets/JIT-compiles at runtime. This is the first thing interviewers probe: 'compiled or
interpreted?' — correct answer is both.

Primitive types: byte(1B), short(2B), int(4B), long(8B), float(4B), double(8B), char(2B, unsigned, holds Unicode),
boolean(JVM-dependent, conceptually 1 bit). Everything else (String, arrays, custom classes) is a reference
type stored on the heap, with the reference itself living on the stack.

Default values matter for interviews: instance/static fields get defaults (0, 0.0, false, null) automatically; local
variables do NOT — the compiler forces you to initialize them before use ('variable might not have been
initialized').

Widening (implicit) conversion goes byte→short→int→long→float→double (char is a side branch that widens to
int). Narrowing conversion is explicit and can lose data or overflow silently — this is a favorite trick-question
area across all companies, from Amazon to TCS.

PRACTICE Q&A — 15 Questions

Q1. Why is Java called both compiled and interpreted?
Source code is compiled to platform-independent bytecode by javac; the JVM then interprets or JIT-compiles
that bytecode into native machine code at runtime. This hybrid model is what gives Java 'write once, run
anywhere'.

Q2. What happens when you print a local variable that was never assigned?
Compile-time error: 'variable X might not have been initialized.' Unlike instance/static fields, local variables get
no default value.

Q3. byte b = 130; — what happens?

Compile-time error. 130 exceeds byte's range (-128 to 127), and since it's a constant expression assigned
directly, the compiler catches it (no explicit cast given).

Q4. byte b = (byte) 130; — what is the result?

-126. 130 in binary overflows the signed 8-bit range; the extra high bits are truncated and the value wraps
around using two's complement.

Q5. Why does 0.1 + 0.2 != 0.3 in Java (or most languages)?
float/double use IEEE-754 binary floating point, which cannot exactly represent decimal fractions like 0.1. The
stored values are approximations, so arithmetic on them yields tiny rounding errors. Use BigDecimal for exact
decimal math.

Q6. What is the size and range of char in Java, and why is it unsigned?
char is 2 bytes (0 to 65535), used to represent a single UTF-16 code unit. It's unsigned because it's meant to
hold a Unicode code point, not a signed number — this differs from C/C++ where char is signed and 1 byte.

Q7. int x = 'A'; is this legal? What is x?

Legal. char widens implicitly to int, so x becomes 65 (the ASCII/Unicode value of 'A').

Page 3 | Java + DSA Placement Interview Master Guide

Q8. char c = 97 + 1; — legal or error?
Legal, c = 'b'. Because 97+1 is a compile-time constant expression that fits in char's range, Java implicitly
narrows it — this special-case rule ('constant expression narrowing') trips up many candidates.

Q9. What's the difference between float f = 1.5; and float f = 1.5f;?
1.5 is a double literal by default, so assigning it to a float without the 'f' suffix (or an explicit cast) is a compile
error — you're narrowing double to float implicitly. 1.5f is a float literal, which compiles fine.

Q10. Is Java pass-by-value or pass-by-reference?

Always pass-by-value. For objects, the value of the reference (i.e., the address) is copied, so you can mutate the
object's internal state through that copy, but reassigning the parameter itself inside the method never affects the
caller's original reference.

Q11. long l = 2147483648; — compiles?

No — 2147483648 exceeds int's max (2147483647) and integer literals are int by default. You need the L suffix:
long l = 2147483648L;

Q12. What is autoboxing/unboxing, and where can it cause a bug?

Autoboxing wraps a primitive into its wrapper (int→Integer); unboxing does the reverse. A classic bug:
comparing two Integer objects with == outside the range -128 to 127 gives false even for equal values, because
Integer caches only that range; use .equals() for value comparison.

Q13. Integer a = 127, b = 127; a == b? Integer a = 200, b = 200; a == b?

First: true — both point to the same cached Integer object (Integer cache covers -128 to 127). Second: false —
200 is outside the cache range so two distinct objects are autoboxed, and == compares references.

Q14. What is the difference between int and Integer?

int is a primitive stored directly with its value; Integer is a reference-type wrapper object stored on the heap that
can be null, used in collections (which require objects), and carries utility methods like [Link]().

Q15. Can a switch statement work on a String? On a long?

Works on String (since Java 7), byte, short, char, int, their wrapper classes, and enums. It does NOT work on
long, float, double, or boolean.

2. Operators — Especially ++ / -- and Precedence Traps

THEORY NOTES
This is the single most 'gotcha-heavy' Java topic in interviews at every company tier, because it tests whether
you actually understand evaluation order rather than pattern-matching code. Master the difference:
pre-increment (++x) increments first, then the (already-incremented) value is used in the expression;
post-increment (x++) uses the current value in the expression first, then increments.

The trap most candidates fall into: assuming x = x++ increments x. It does NOT change x's final value, because
the old value of x is saved before the increment happens, and that saved (unincremented) value is what gets
assigned back.

Short-circuit operators (&&, ||) evaluate the right operand only if necessary; the non-short-circuit versions (&, |)
always evaluate both sides. This matters when the right side has side effects (e.g., a function call, or an
increment).

Operator precedence surprises: bitwise operators have LOWER precedence than relational operators, and the
ternary operator is right-associative. Combined with ++/--, these produce classic 'predict the output' interview

Page 4 | Java + DSA Placement Interview Master Guide

questions.

PRACTICE Q&A — 13 Questions

Q1. int x = 5; int y = x++ + ++x; What are x and y?
x = 7, y = 12. Step by step: x++ yields 5 for the expression, then x becomes 6. ++x then increments x from 6 to 7
and yields 7 for the expression. So y = 5 + 7 = 12, and x ends at 7. (Always trace step by step on paper — this
exact question appears at nearly every company.)

Q2. int x = 5; x = x++; What is x?

5. The value of x (5) is computed and saved for the RHS *before* the increment side-effect is applied; the
increment does happen but is immediately overwritten by the assignment of the saved old value.

Q3. int i = 1; i = i++ + ++i; trace it.

i++ evaluates to 1 (i becomes 2). ++i then increments i from 2 to 3 and evaluates to 3. Sum = 1 + 3 = 4. Final i =
4.

Q4. Why does x = x++ not increment x, but x++; (as a standalone statement) does?
In x = x++, the assignment overwrites x with the saved pre-increment value, masking the increment. As a
standalone statement x++;, there's no assignment competing with it, so the incremented value simply becomes
x's new value with nothing overwriting it.

Q5. What's the output of: int a=10; [Link](a++ + ++a);

22. a++ yields 10 for the expression, then a becomes 11. ++a then increments a from 11 to 12 and yields 12 for
the expression. Sum = 10 + 12 = 22. (Trace on paper every time; off-by-one errors here are extremely common
even for experienced developers.)

Q6. Difference between & and && in a condition like (a != null & [Link]())?
& always evaluates both operands, so if a is null this throws NullPointerException. && short-circuits — if a != null
is false, isValid() is never called, avoiding the NPE. Always prefer && / || in guard conditions.

Q7. What does (5 & 3) == 1 evaluate as, given == binds tighter than &?
This is false-if-misjudged: relational (==) has HIGHER precedence than bitwise (&) in Java, so this parses as 5 &
(3==1) → 5 & false, which is a compile error (can't mix int and boolean with &). You must write (5 & 3) == 1
explicitly with parentheses.

Q8. What is the result of 5 % -3 and -5 % 3 in Java?

5 % -3 = 2; -5 % 3 = -2. Java's % (remainder) operator takes the sign of the dividend (left operand), unlike
Python's modulo which takes the sign of the divisor.

Q9. Is the ternary operator ?: left- or right-associative? Give an example that matters.
Right-associative. a ? b : c ? d : e parses as a ? b : (c ? d : e), which matters when chaining nested ternaries — a
common source of subtle bugs in condensed one-liners.

Q10. What's the difference between >> and >>> in Java?

>> is the signed (arithmetic) right shift — it fills vacated bits with the sign bit, preserving the sign of negative
numbers. >>> is the unsigned (logical) right shift — it always fills with 0, so shifting a negative number with >>>
produces a large positive number.

Q11. int x = 1; boolean result = (x == 1) | (++x == 3); What is x after this?

x = 2. Because | is NOT short-circuit, both sides are evaluated: x==1 is true, but ++x still executes, incrementing
x to 2 (and 2==3 is false), giving result = true. Contrast with || which would skip the right side entirely, leaving x =
1.

Q12. What does the instanceof operator do, and can it be used with null?

Page 5 | Java + DSA Placement Interview Master Guide

 It checks whether an object reference is an instance of a given type at runtime, returning a boolean. obj
instanceof SomeClass on a null reference always returns false (never throws), which is a useful safety property.

Q13. Compound assignment: byte b = 10; b += 5; — does this compile, and why does byte b = b + 5;
not?
b += 5; compiles because compound assignment operators implicitly cast the result back to the target type. byte
b = b + 5; does NOT compile because b+5 promotes to int, and assigning an int to byte needs an explicit cast —
this asymmetry is a classic interview question.

3. Control Flow, Loops & Exception Basics

THEORY NOTES
Java offers if/else, switch (statement and, since Java 14, switch expressions), for, enhanced-for, while,
do-while. Labeled break/continue let you control nested loops — rare in production code but a favorite
whiteboard question.

try-with-resources (Java 7+) auto-closes any resource implementing AutoCloseable, replacing verbose finally
blocks and guaranteeing close() runs even on an exception — a frequently asked 'why is this better' question.

finally always runs except for [Link]() or JVM crash — even if try or catch has a return statement. If finally
itself has a return, it silently overrides any return/exception from try/catch, which is considered a code smell.

PRACTICE Q&A — 10 Questions

Q1. Difference between break and continue inside a loop?
break exits the loop entirely; continue skips the rest of the current iteration and jumps to the next one
(re-evaluating the loop condition).

Q2. What does a labeled break do? Give a use case.

It lets you break out of an outer loop from inside a nested loop, e.g. outer: for(...){ for(...){ if(cond) break outer; } }.
Useful for exiting a nested search as soon as a match is found.

Q3. If both try and finally have return statements, which one wins?
The return in finally wins — it silently discards whatever try or catch was about to return (or even an exception
being propagated), which is why returning from finally is considered bad practice.

Q4. Does finally run if the try block has a return statement?
Yes. finally always executes before the method actually returns, unless the JVM exits ([Link]()) or crashes.

Q5. What is try-with-resources and what interface must a resource implement?

A try(...) syntax that auto-closes resources implementing AutoCloseable (or Closeable) when the block exits,
whether normally or via exception — eliminating manual close() calls in finally and avoiding resource leaks.

Q6. Checked vs unchecked exceptions — give one example of each and explain the compiler
difference.
Checked (e.g., IOException) extends Exception but not RuntimeException, and the compiler forces you to either
catch it or declare it with throws. Unchecked (e.g., NullPointerException, ArithmeticException) extends
RuntimeException and the compiler doesn't enforce handling.

Q7. Can you catch multiple exception types in one catch block?
Yes, using the pipe syntax: catch (IOException | SQLException e) { ... }. The exceptions in that list must not be
related by subclassing (no catching a parent and child together).

Page 6 | Java + DSA Placement Interview Master Guide

Q8. What is the difference between throw and throws?
throw is used inside a method body to actually raise an exception instance (throw new
IllegalArgumentException(...)). throws is used in a method signature to declare that the method might propagate
a checked exception to its caller.

Q9. What happens if you don't catch a checked exception and don't declare throws?
Compile-time error: 'unreported exception must be caught or declared to be thrown.'

Q10. Difference between Error and Exception in Java's Throwable hierarchy?

Both extend Throwable. Error represents serious JVM-level problems (OutOfMemoryError, StackOverflowError)
that applications generally shouldn't try to catch/recover from. Exception represents conditions an application
can reasonably handle.

4. OOP — Encapsulation, Inheritance, Polymorphism, Abstraction

THEORY NOTES
These four pillars are asked in nearly identical form at every company, but the follow-ups distinguish tiers: tier-1
companies (Google, Amazon, Microsoft) push into 'why' and edge cases (constructor chaining, diamond
problem, method hiding vs overriding); tier-2/3 (TCS, Infosys, Wipro, IBM) often stop at definitions plus one
code example, so know both a crisp definition AND a working code snippet for each.

Overloading = same method name, different parameter list, resolved at COMPILE time (static/early binding).
Overriding = subclass redefines a superclass method with the identical signature, resolved at RUNTIME based
on the actual object type (dynamic/late binding) — this is the mechanism behind polymorphism.

Java doesn't support multiple inheritance of classes (to avoid the diamond problem) but does support it through
interfaces, since Java 8 interfaces can have default methods — if two interfaces provide conflicting default
methods, the implementing class MUST override the method to resolve the ambiguity, or it's a compile error.

PRACTICE Q&A — 13 Questions

Q1. Define encapsulation with a code-level explanation.
Bundling data (fields) and the methods that operate on it into a single unit (a class), while restricting direct
external access to the internal state — typically via private fields with public getter/setter methods. It protects
invariants and hides implementation details.

Q2. Method overloading vs overriding — list at least 3 differences.

Overloading: same name/different params, same class or subclass, resolved at compile time, return type can
differ freely. Overriding: same name/same params/same return type (or covariant), only in a subclass, resolved
at runtime via the actual object type, access modifier can't be more restrictive than the parent's.

Q3. Can you overload a method by changing only the return type?
No. Return type alone is not part of the method signature for overload resolution — you'll get a compile error
'method already defined' if only the return type differs.

Q4. Can a static method be overridden?

No — static methods are resolved at compile time based on the reference type (method hiding, not overriding). If
a subclass defines a static method with the same signature, it 'hides' the parent's version rather than overriding
it; calling it via a parent-typed reference invokes the parent's version.

Q5. What is the diamond problem, and how does Java avoid/handle it?

Page 7 | Java + DSA Placement Interview Master Guide

 When a class could inherit conflicting implementations of the same method from two parents (as with multiple
class inheritance in C++). Java avoids it for classes by disallowing multiple class inheritance. For interfaces with
default methods, if two interfaces supply the same default method, the implementing class is FORCED to
override it explicitly, resolving the ambiguity at compile time.

Q6. What is the order of constructor calls in a class hierarchy when you instantiate a subclass?
The superclass constructor always runs first (implicitly via super() if not written explicitly), then the subclass
constructor body — this happens all the way up the hierarchy to Object, then unwinds back down.

Q7. Can a constructor be private? What's the use case?

Yes — used in Singleton pattern (prevents external instantiation) and in classes exposing only static factory
methods, forcing all object creation through a controlled path.

Q8. What is the difference between abstraction and encapsulation?

Abstraction hides implementation COMPLEXITY, focusing on what an object does (via abstract
classes/interfaces) rather than how. Encapsulation hides internal STATE/data, controlling access to it.
Abstraction is about design/interface; encapsulation is about data protection.

Q9. Abstract class vs interface — when would you choose one over the other (post Java 8)?
Abstract class: can hold state (instance fields), constructors, and a mix of implemented/abstract methods — use
it when subclasses share common state/behavior ('is-a' with shared implementation). Interface: purely a contract
of capability (can now include default/static methods but no instance state) — use it for unrelated classes to
share a capability ('can-do'), and because a class can implement multiple interfaces but extend only one class.

Q10. What is polymorphism, and what are its two forms in Java?
The ability of an object to take many forms. Compile-time (static) polymorphism = method overloading, resolved
by the compiler. Runtime (dynamic) polymorphism = method overriding, resolved by the JVM at runtime using
the actual object's type (virtual method dispatch).

Q11. If a subclass object is referenced by a superclass variable, and both define a field with the same
name, which field is accessed?
Field access is resolved at compile time based on the REFERENCE type, not the object's runtime type (fields
are not polymorphic like methods) — so the superclass's field is accessed. This differs from method calls, which
use the runtime type.

Q12. Can you call an overridden method from a constructor? Why is this dangerous?
Yes, syntactically, but it's dangerous: if the subclass overrides that method and relies on fields initialized in the
subclass constructor, the overridden version runs BEFORE those subclass fields are initialized (since superclass
constructor runs first), leading to subtle bugs (e.g., NPEs on fields that look 'always initialized').

Q13. What is the 'super' keyword used for? Give three uses.
(1) super() calls the immediate superclass's constructor, must be the first statement if used explicitly. (2)
[Link]() explicitly invokes the superclass's version of an overridden method. (3) [Link] accesses a
superclass field that's shadowed by a subclass field of the same name.

5. Strings, StringBuilder, StringBuffer & the String Pool

THEORY NOTES
Strings in Java are IMMUTABLE — every 'modification' method (concat, substring, replace, toUpperCase, etc.)
returns a NEW String object; the original is untouched. This single fact drives a huge fraction of String interview
questions.

Page 8 | Java + DSA Placement Interview Master Guide

The String Constant Pool (part of the heap since Java 7) caches string literals for reuse: String a = "hi"; String b
= "hi"; makes a and b point to the SAME pooled object. String c = new String("hi") forces a new object
OUTSIDE the pool, even though its content is identical — this is the classic == vs .equals() trap.

StringBuilder is mutable and NOT thread-safe (fast, use in single-threaded code, e.g. loops building large
strings). StringBuffer is mutable and thread-safe (methods are synchronized, slightly slower). Both avoid the
overhead of creating a new String object on every append, unlike naive String concatenation in a loop.

PRACTICE Q&A — 10 Questions

Q1. Why is String immutable in Java? Give at least two real reasons, not just 'security'.
(1) Security/reliability: Strings are used for class names, file paths, network connections, DB URLs — if mutable,
a String passed to one method could be changed by another, unpredictably. (2) String pool safety: pooling only
works safely if strings can't change after being shared. (3) Thread safety: immutable objects are inherently
thread-safe with no synchronization needed. (4) Hashcode caching: String's hashCode is computed once and
cached, which is only valid if the content can never change — this makes Strings efficient as HashMap keys.

Q2. String a = "test"; String b = "test"; a == b?

true — both literals are interned in the string pool, so a and b reference the identical object.

Q3. String a = new String("test"); String b = "test"; a == b?

false — new String(...) explicitly creates a new object on the heap outside the pool, even though [Link](b) is
true (same content).

Q4. How do you force a and b above to be ==?

Call [Link]() — String a = new String("test").intern(); this returns the pooled reference for that content, so a == b
becomes true.

Q5. String s = "a" + "b"; — is this pooled, and why does it matter that both are literals?
Yes. The compiler performs constant folding on literal concatenation at COMPILE time, producing "ab" as a
single pooled literal — equivalent to writing "ab" directly. This differs from concatenating with a variable (String s
= a + "b";), which happens at RUNTIME via StringBuilder internally and does NOT get pooled.

Q6. Why is doing String result = ""; for(...) { result += item; } bad in a loop with many iterations?
Each += creates a brand-new String object (since String is immutable) and copies the old content plus the new
piece — for N iterations this is roughly O(N^2) total character copying. Use [Link]() inside the
loop instead, which mutates an internal char array in amortized O(1) per append.

Q7. StringBuilder vs StringBuffer — the one-line answer interviewers want.

Same API, but StringBuffer's methods are synchronized (thread-safe, slower); StringBuilder's are not (faster, use
when no multi-threaded access to the same instance).

Q8. How does [Link]() differ from ==, precisely?

== compares reference identity (do both variables point to the same object in memory). .equals() (overridden in
String) compares the actual character sequence content, regardless of whether they're the same object.

Q9. Is String thread-safe? Why?

Yes, inherently, because it's immutable — there is no mutable state that multiple threads could race on, so no
synchronization is ever needed for a String's safety.

Q10. What does [Link]() do internally?

It looks up the string pool for a String with the same content; if found, returns that pooled reference; if not found,
adds this string's content to the pool and returns that reference. Effectively lets you manually deduplicate
identical String content.

Page 9 | Java + DSA Placement Interview Master Guide

6. Exception Handling — Deep Dive
THEORY NOTES
Beyond basics (Section 3), interviewers dig into custom exceptions, exception chaining, and performance
implications — this is where tier-1 companies differentiate strong candidates.

A common design question: 'when would you create a custom exception?' — when you need to convey
domain-specific failure information (e.g., InsufficientFundsException) that generic exceptions can't express, or
to let calling code catch/handle your specific failure type distinctly from unrelated errors.

PRACTICE Q&A — 7 Questions

Q1. How do you create a custom checked exception?
class InsufficientFundsException extends Exception { public InsufficientFundsException(String msg) {
super(msg); } } — extending Exception (not RuntimeException) makes it checked, forcing callers to handle or
declare it.

Q2. What is exception chaining and why use it?

Wrapping a lower-level exception inside a higher-level one via the cause constructor (throw new
ServiceException("failed", originalException);) so the original stack trace/root cause is preserved for debugging,
even while exposing a more meaningful exception type to callers.

Q3. What's wrong with catch (Exception e) {} (empty catch block)?

It silently swallows ALL exceptions, including ones you didn't anticipate (like NullPointerException from a bug),
making failures invisible and debugging extremely hard. At minimum, log the exception; better, catch specific
exception types you actually expect.

Q4. Difference between throw new RuntimeException(e) and just rethrowing e?

throw new RuntimeException(e) wraps the checked exception e as the 'cause' inside an unchecked exception,
letting you propagate it without declaring throws — but it changes the exception type seen by callers. Rethrowing
the original preserves its exact type and message but requires the checked-exception contract to be honored up
the call stack.

Q5. Can a finally block suppress an exception thrown from try? How?
Yes, if finally itself throws an exception (or has a return), it replaces/suppresses whatever exception was
propagating from try/catch — the original exception is lost unless explicitly captured, which is one reason to
avoid throwing or returning from finally.

Q6. What is a try-with-resources 'suppressed exception'?

If both the try block and the automatic close() of a resource throw exceptions, the exception from try is the one
propagated, and the close() exception is attached to it as a 'suppressed' exception (retrievable via
getSuppressed()), rather than being lost.

Q7. Is it good practice to catch Throwable? Why or why not?

Generally no — Throwable includes Error (like OutOfMemoryError, StackOverflowError), which typically
indicates unrecoverable JVM-level problems that an application shouldn't try to handle or continue past.

7. Collections Framework
THEORY NOTES

Page 10 | Java + DSA Placement Interview Master Guide

The Collections Framework is asked constantly because it combines OOP theory (interfaces), data structures
(DSA), and practical coding — expect both conceptual questions ('when would you use X over Y') and
implementation questions ('how does HashMap actually work internally').

Core interface hierarchy: Collection → List (ordered, duplicates allowed: ArrayList, LinkedList, Vector), Set (no
duplicates: HashSet, LinkedHashSet, TreeSet), Queue/Deque (PriorityQueue, ArrayDeque). Map is separate
(not a Collection): HashMap, LinkedHashMap, TreeMap, Hashtable.

HashMap internals (very frequently asked at Amazon/Google/Microsoft level): backed by an array of 'buckets';
each key's hashCode() is used to compute a bucket index; collisions within a bucket are handled via a linked list
(converted to a red-black tree if a bucket gets 8+ entries, since Java 8, for O(log n) worst case instead of O(n)).
Default capacity 16, load factor 0.75, resizes (doubles) when size exceeds capacity*loadFactor.

PRACTICE Q&A — 13 Questions

Q1. ArrayList vs LinkedList — access and insertion complexity?
ArrayList: O(1) random access (backed by array), O(n) insertion/deletion in the middle (needs shifting),
amortized O(1) append at end. LinkedList: O(n) random access (must traverse), O(1) insertion/deletion once you
have a reference to the node, but finding that node is still O(n).

Q2. When would you actually choose LinkedList over ArrayList in practice?
Rarely in modern Java — ArrayDeque usually beats LinkedList for queue/stack use cases due to better cache
locality. LinkedList is justified when you frequently insert/delete at both ends or in the middle AND you already
hold iterator references to the insertion point, avoiding traversal cost.

Q3. How does HashMap handle collisions, and what changed in Java 8?
Before Java 8: colliding entries in the same bucket formed a singly linked list, so worst-case lookup was O(n) if
all keys collided. Since Java 8: if a bucket's list grows to 8+ entries (and the table is large enough), it's converted
into a red-black tree, making worst-case lookup O(log n).

Q4. What is the load factor in HashMap, and why 0.75?

The threshold (capacity * loadFactor) at which the map resizes (doubles capacity) to keep lookups fast. 0.75 is a
time-space tradeoff: lower wastes more memory but reduces collisions; the default balances reasonable memory
use with low collision probability per Java's benchmarking.

Q5. Why must a class override both equals() and hashCode() together for correct HashMap/HashSet
behavior?
HashMap uses hashCode() to locate the bucket, then equals() to find the exact matching key within that bucket
(handling collisions). If you override equals() but not hashCode(), two 'equal' objects can produce different hash
codes and land in different buckets — the map won't recognize them as duplicates, breaking the
equals/hashCode contract.

Q6. What is the equals/hashCode contract, precisely?

(1) If two objects are equal per equals(), they MUST have the same hashCode(). (2) The reverse is not required
— unequal objects CAN share a hash code (a collision), just not the other way around. (3) hashCode() must be
consistent — calling it multiple times on the same unmodified object must return the same value.

Q7. HashMap vs Hashtable vs ConcurrentHashMap — thread safety differences?

HashMap: not thread-safe, allows one null key and multiple null values. Hashtable: thread-safe via full method
synchronization (legacy, coarse-grained, slow under contention), disallows null keys/values.
ConcurrentHashMap: thread-safe using fine-grained locking/CAS on segments/buckets (much better concurrent
throughput than Hashtable), also disallows null keys/values.

Page 11 | Java + DSA Placement Interview Master Guide

Q8. HashSet vs TreeSet vs LinkedHashSet — what does each guarantee?
HashSet: no ordering guarantee, O(1) average add/contains, backed by a HashMap internally. LinkedHashSet:
maintains insertion order, backed by a linked hash map, slightly more overhead than HashSet. TreeSet:
maintains sorted order (natural or via Comparator), backed by a red-black tree, O(log n) operations.

Q9. What's the difference between Comparable and Comparator?

Comparable is implemented BY the class itself to define its single 'natural ordering' (compareTo method).
Comparator is a SEPARATE class/lambda that defines an ordering externally, letting you sort the same objects
in multiple different ways without modifying the class.

Q10. Can you modify a List while iterating over it with a for-each loop? What happens?
No — this throws ConcurrentModificationException, because the enhanced for-loop uses an Iterator internally,
and structurally modifying the list (add/remove) outside the iterator's own remove() method invalidates it via a
'fail-fast' modCount check. Use [Link](), or a ListIterator, or collect items to remove separately.

Q11. What is the difference between fail-fast and fail-safe iterators? Give an example of each.
Fail-fast iterators (ArrayList, HashMap's default) detect concurrent structural modification and throw
ConcurrentModificationException immediately. Fail-safe iterators (CopyOnWriteArrayList, ConcurrentHashMap)
operate on a snapshot or tolerate concurrent changes without throwing, though they may not reflect the very
latest modifications during iteration.

Q12. PriorityQueue — what ordering does it use by default, and how do you customize it?
By default, min-heap ordering based on natural ordering (Comparable) — the smallest element is always at the
head. Pass a custom Comparator to the constructor to get max-heap behavior or any other ordering.

Q13. How would you make an ArrayList thread-safe?

Options: [Link](new ArrayList<>()) (wraps with synchronized methods, must manually
synchronize during iteration), or use CopyOnWriteArrayList for read-heavy/write-rare scenarios (copies the
entire array on every write, so reads never block).

8. Multithreading & Concurrency

THEORY NOTES
Multithreading questions escalate sharply by company tier: TCS/Wipro/Infosys typically ask 'what is a thread,
how do you create one, what is synchronized'; Google/Amazon/Microsoft push into deadlocks, the executor
framework, volatile vs synchronized, and the Java Memory Model.

A Thread can be created by extending Thread (overriding run()) or implementing Runnable (passed to a
Thread) — implementing Runnable is generally preferred since Java doesn't support multiple inheritance, so it
leaves your class free to extend something else, and it better separates 'the task' from 'the thread executing it'.

synchronized provides both mutual exclusion (only one thread in the critical section at a time) AND a memory
visibility guarantee (changes made inside a synchronized block by one thread become visible to other threads
that later synchronize on the same lock). volatile provides ONLY the visibility guarantee, not atomicity/mutual
exclusion — this distinction is a very common trick question.

PRACTICE Q&A — 11 Questions

Q1. Two ways to create a thread in Java — which is preferred and why?
Extend Thread and override run(), or implement Runnable and pass an instance to new Thread(runnable).
Implementing Runnable is preferred because Java only allows single class inheritance — extending Thread uses

Page 12 | Java + DSA Placement Interview Master Guide

 up your one inheritance slot — and Runnable cleanly separates 'what to run' from 'the mechanism that runs it',
making it reusable with ExecutorService too.

Q2. What happens if you call run() directly instead of start()?

run() just executes as a normal synchronous method call on the current thread — no new thread is created.
start() is what actually creates a new OS-level thread and then invokes run() on it asynchronously.

Q3. What does synchronized guarantee, precisely — two things, not one.
(1) Mutual exclusion: only one thread can hold the lock on a given object/class at a time, so only one thread
executes the synchronized block/method concurrently. (2) Visibility: it establishes a happens-before relationship,
so writes made by a thread before releasing the lock are guaranteed visible to the next thread that acquires the
same lock.

Q4. volatile vs synchronized — what's the key difference?

volatile guarantees visibility only (reads always see the latest write from any thread) but provides NO
atomicity/mutual exclusion — compound operations like count++ on a volatile variable are still NOT thread-safe
because increment is read-modify-write (three separate steps). synchronized guarantees both visibility and
atomicity for the guarded block.

Q5. Is count++ on a volatile int thread-safe? Why not?

No. count++ is really three operations: read count, add 1, write count back. Even with volatile ensuring each
individual read/write is visible, two threads can both read the same old value before either writes back, causing a
lost update — you need synchronized, AtomicInteger, or a lock for true atomicity.

Q6. What is a deadlock? Give the four necessary conditions.

A state where two or more threads are each waiting forever for a resource held by another, so none can
proceed. Four Coffman conditions: (1) mutual exclusion, (2) hold and wait, (3) no preemption, (4) circular wait.
Breaking any one prevents deadlock — commonly done by always acquiring multiple locks in a fixed, consistent
global order.

Q7. What is the difference between wait() and sleep()?

wait() (defined on Object) releases the held monitor lock and pauses the thread until notified (notify()/notifyAll())
— must be called from within a synchronized block. sleep() (static on Thread) pauses the thread for a fixed
duration WITHOUT releasing any locks it holds, and doesn't require synchronization.

Q8. What is the Executor framework, and why is it preferred over manually creating Thread objects?
A higher-level abstraction (ExecutorService, thread pools via [Link]() etc.) that
manages a reusable pool of worker threads, queues submitted tasks, and separates task submission from
thread lifecycle management — avoiding the overhead/unpredictability of creating a new OS thread per task.

Q9. What is a race condition? Give a minimal example.

A bug where the program's outcome depends on the unpredictable timing/interleaving of multiple threads
accessing shared mutable state. Classic example: two threads both executing balance += amount; on a shared
unsynchronized variable can lose one of the updates if their read-modify-write steps interleave.

Q10. What is the difference between Runnable and Callable?

Runnable's run() method returns void and cannot throw checked exceptions. Callable<V>'s call() method returns
a value of type V and CAN throw checked exceptions — used with [Link]() when you need a
result back (via Future<V>) or need to propagate exceptions from the task.

Q11. What does ThreadLocal do, and when would you use it?
Gives each thread its own independent copy of a variable, isolated from other threads (no sharing, no
synchronization needed). Common use: per-thread state like a database connection, a SimpleDateFormat
instance (not thread-safe by itself), or a per-request user context in a web server handling concurrent requests.

Page 13 | Java + DSA Placement Interview Master Guide

9. JVM Architecture, Memory & Garbage Collection
THEORY NOTES
JVM memory areas: Heap (objects, shared across threads, further divided into Young Generation [Eden + 2
Survivor spaces] and Old/Tenured Generation), Stack (one per thread; stores local variables, method call
frames, references), Method Area/Metaspace (class metadata, static fields, since Java 8 replacing PermGen),
PC Register, Native Method Stack.

Garbage Collection reclaims heap memory occupied by objects with no reachable references. Java uses a
generational hypothesis: most objects die young, so GC focuses effort on the (small, fast-to-scan) Young
Generation via frequent 'Minor GC', promoting long-surviving objects to Old Gen, which is collected less often
via slower 'Major/Full GC'.

StackOverflowError happens when the call stack exceeds its size limit — classically from unbounded/infinite
recursion (missing or wrong base case). OutOfMemoryError happens when the heap can't allocate more
memory and the GC can't free enough — from memory leaks (unintentionally retained references) or genuinely
needing more heap than allocated.

PRACTICE Q&A — 9 Questions

Q1. What are the main memory areas of the JVM?
Heap (shared, holds all objects), Stack (per-thread, holds local variables and call frames), Method
Area/Metaspace (class-level metadata, static variables), PC Register (per-thread, tracks current instruction),
Native Method Stack (for native/JNI calls).

Q2. Why is the stack divided per-thread but the heap shared?
Each thread executes its own sequence of method calls, so it needs its own independent call frames/local
variables (stack) to avoid interference. Objects on the heap, however, can be shared and passed between
threads, so a single shared heap allows that sharing — this is also exactly why heap access needs
synchronization but stack-local variables generally don't.

Q3. What causes a StackOverflowError? Give a concrete example.

Exceeding the JVM's stack size limit, almost always from deep or infinite recursion without a proper base case,
e.g., a recursive factorial(n) that calls factorial(n) instead of factorial(n-1).

Q4. What causes an OutOfMemoryError, and name two common real-world causes.
The heap is exhausted and GC cannot reclaim enough space. Common causes: (1) memory leaks — objects
unintentionally kept reachable (e.g., growing static collections that are never cleared, unclosed resources,
listener registrations never removed), (2) genuinely processing data larger than the configured heap allows.

Q5. Explain the generational garbage collection hypothesis.

Empirically, most objects become garbage very shortly after creation ('most objects die young'), while a small
fraction survive long-term. GC exploits this by focusing frequent, cheap collections on a small 'Young
Generation' (where most garbage is found fast), and only occasionally running expensive full collections on the
'Old Generation' where long-lived objects accumulate.

Q6. What is the difference between Minor GC and Major/Full GC?

Minor GC cleans only the Young Generation, is fast and frequent, and promotes surviving objects to Old Gen
after they survive enough collection cycles. Major/Full GC cleans the Old Generation (and typically the whole
heap), is much slower and less frequent, and can cause noticeable application pause times ('stop-the-world').

Page 14 | Java + DSA Placement Interview Master Guide

Q7. When is an object eligible for garbage collection?
When it becomes unreachable — no live thread can access it through any chain of references from GC roots
(active thread stacks, static fields, JNI references, etc.). Simply setting a reference to null is one common way to
make an object unreachable, but it's the reachability, not the null assignment itself, that matters.

Q8. Can you force garbage collection in Java?

You can call [Link]() as a hint/suggestion, but the JVM is free to ignore it entirely — there is no guaranteed
way to force GC to run immediately. Relying on it in production logic is considered bad practice.

Q9. What is Metaspace, and how does it differ from the old PermGen?
Metaspace (Java 8+) stores class metadata (like PermGen did), but unlike PermGen, it's allocated from native
(off-heap) memory and grows dynamically by default rather than having a small fixed size — this largely
eliminated the once-common 'PermGen space' OutOfMemoryError from too many loaded classes.

10. Java 8+ Features — Lambdas, Streams, Functional Interfaces,

Optional
THEORY NOTES
A functional interface has exactly ONE abstract method (SAM — Single Abstract Method), which is what makes
it eligible to be implemented with a lambda expression. Common built-in ones: Runnable, Callable, Comparator,
and [Link]'s Function<T,R>, Predicate<T>, Supplier<T>, Consumer<T>.

Streams provide a declarative, pipeline style for processing collections: a source, zero or more intermediate
operations (map, filter, sorted — these are LAZY, they don't execute until a terminal operation is invoked), and
exactly one terminal operation (collect, forEach, reduce, count) which triggers actual execution.

Optional<T> is a container object that may or may not hold a non-null value, designed to make the possibility of
'no value' explicit in a method's return type, reducing accidental NullPointerExceptions and forcing callers to
consciously handle the empty case.

PRACTICE Q&A — 9 Questions

Q1. What makes an interface a 'functional interface'?
It declares exactly one abstract method (default and static methods don't count toward this limit). The
@FunctionalInterface annotation is optional but recommended — it makes the compiler enforce the
single-abstract-method rule and documents intent.

Q2. Write a lambda that implements Comparator<Integer> for descending order.

Comparator<Integer> cmp = (a, b) -> b - a; (or more safely for large values, avoiding overflow: (a, b) ->
[Link](b, a);)

Q3. Are Stream intermediate operations like map() and filter() lazy or eager? Why does it matter?
Lazy — they just build up a pipeline description and don't process any elements until a terminal operation (like
collect() or forEach()) is called. This matters because it allows short-circuiting (e.g., findFirst() can stop early
without processing the whole source) and avoids unnecessary intermediate collection allocation.

Q4. Can a stream be reused/traversed twice?

No — once a terminal operation has been invoked on a stream, that stream is considered 'consumed' and calling
another operation on it throws IllegalStateException ('stream has already been operated upon or closed'). You
must create a fresh stream from the source to process it again.

Page 15 | Java + DSA Placement Interview Master Guide

Q5. What is the difference between map() and flatMap()?
map() transforms each element into exactly one new element (one-to-one), producing a Stream<Stream<X>> if
the mapper itself returns a stream. flatMap() transforms each element into a stream of elements and then
FLATTENS all those streams into a single stream (one-to-many, then merged) — used e.g. to turn a
List<List<Integer>> into a flat Stream<Integer>.

Q6. What is [Link]() vs [Link]() — and why does the difference matter for
performance?
orElse(defaultValue) always evaluates/constructs the default value argument eagerly, even if the Optional has a
value present and it will be discarded. orElseGet(supplier) only invokes the supplier lazily if the Optional is
actually empty — preferred when constructing the default is expensive (e.g., a DB call), since orElse would
waste that work unconditionally.

Q7. Why shouldn't you call [Link]() without checking isPresent() first?
If the Optional is empty, get() throws NoSuchElementException — calling it blindly reintroduces exactly the kind
of unchecked failure Optional was designed to prevent. Prefer orElse/orElseGet/orElseThrow/ifPresent/map
instead of a raw isPresent()+get() pattern.

Q8. What does [Link]() do? Give a quick example.

Groups stream elements by a classifier function into a Map<K, List<T>> (or a custom downstream collector).
Example: [Link]().collect([Link](Employee::getDepartment)) groups employees into
a map keyed by department.

Q9. What's the difference between Predicate, Function, Supplier, and Consumer?
Predicate<T>: takes T, returns boolean (a test/condition). Function<T,R>: takes T, returns R (a transformation).
Supplier<T>: takes nothing, returns T (a factory/source). Consumer<T>: takes T, returns void (performs a
side-effecting action).

Page 16 | Java + DSA Placement Interview Master Guide

 PART B: DSA

1. Complexity Analysis & Big-O Foundations

THEORY NOTES
Big-O describes the WORST-CASE upper bound on how an algorithm's running time or space grows as input
size n grows, ignoring constant factors and lower-order terms — this is the language every DSA interview is
conducted in, so being fluent (not just able to recite definitions) is essential.

Common complexity classes from best to worst: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n)
linearithmic, O(n^2) quadratic, O(2^n) exponential, O(n!) factorial. Know at least one canonical algorithm
example for each.

Amortized analysis matters for structures like ArrayList/dynamic arrays: a single append is occasionally O(n)
(when resizing), but AVERAGED over a sequence of n appends, each is O(1) amortized — interviewers ask
this specifically to check you understand the difference between worst-case-per-operation and amortized cost.

PRACTICE Q&A — 8 Questions

Q1. What does 'worst case O(n^2)' actually mean, precisely?
It means the running time is bounded above by c*n^2 for some constant c, for all sufficiently large n, in the input
scenario that is hardest for the algorithm. It's an upper bound on growth rate, not an exact formula or a statement
about typical/average performance.

Q2. Give one canonical algorithm for each: O(log n), O(n log n), O(n^2), O(2^n).
O(log n): binary search. O(n log n): merge sort / heap sort / efficient comparison-based sorting in general.
O(n^2): bubble sort / naive nested-loop pair checking. O(2^n): naive recursive Fibonacci without memoization, or
generating all subsets of a set.

Q3. Why is [Link]() considered O(1) amortized, even though resizing is O(n)?
Resizing (doubling capacity) happens rarely — roughly every time the array fills up — and each resize costs
O(n) to copy elements, but you 'pay' for that cost gradually across all the O(1) appends that happened since the
last resize. Summed over n appends, the total work is O(n), so the AVERAGE cost per append is O(1), even
though occasional individual appends are more expensive.

Q4. What's the difference between time complexity and space complexity?
Time complexity measures how the number of operations (roughly, running time) grows with input size. Space
complexity measures how much extra memory the algorithm uses (beyond the input itself) as input size grows —
including auxiliary data structures and recursion call-stack depth.

Q5. Is O(n) always faster than O(n^2) in practice?

Not necessarily for small n — an O(n^2) algorithm with tiny constant factors can outperform an O(n) algorithm
with large constants/overhead for small inputs. Big-O describes asymptotic (large-n) growth trends, not a
guarantee at every specific input size — this is exactly why algorithms like insertion sort (O(n^2)) are still used
for small arrays or as a fallback in hybrid sorts like Timsort.

Q6. What is the time complexity of recursive Fibonacci without memoization, and why?
O(2^n) — each call to fib(n) spawns two more calls (fib(n-1) and fib(n-2)), creating a binary recursion tree of
roughly 2^n nodes, with massive redundant recomputation of the same subproblems.

Q7. How does memoization change recursive Fibonacci's complexity, and why?

Page 17 | Java + DSA Placement Interview Master Guide

 Down to O(n) time (with O(n) extra space for the memo table/array). Each subproblem fib(k) for k from 0 to n is
computed exactly once and cached; subsequent calls with the same k are O(1) lookups instead of re-branching.

Q8. What is the space complexity of an algorithm that uses O(n) recursion depth but no other data
structures?
O(n) — even without any explicit arrays/maps, each recursive call adds a frame to the call stack, and with depth
n, that's O(n) stack space, which counts toward space complexity.

2. Arrays & Strings

THEORY NOTES
Arrays: fixed-size, contiguous memory, O(1) random access by index (this is why it beats linked lists for
lookups), O(n) insertion/deletion in the middle since elements must shift. Two-pointer and sliding-window
techniques are the two most-tested patterns on arrays/strings across every company.

Strings in most languages (Java included) are effectively char arrays under the hood for algorithmic purposes
even though the Java String object itself is immutable — most string algorithm questions (reverse, palindrome
check, anagram check, substring search) reduce to array/two-pointer techniques.

Know these patterns cold: two-pointer (opposite ends closing in, e.g., reverse array, two-sum on sorted array,
container-with-most-water), sliding window (variable or fixed size, e.g., longest substring without repeating
characters, max sum subarray of size k), and prefix sums (precompute cumulative sums for O(1) range-sum
queries).

PRACTICE Q&A — 11 Questions

Q1. How do you reverse an array in-place? Complexity?
Two pointers, one at start (i=0) one at end (j=n-1); swap arr[i] and arr[j], then move i++ and j-- until i >= j. Time
O(n), Space O(1) — classic two-pointer pattern.

Q2. How do you check if a string is a palindrome, and what's the complexity?
Two pointers from both ends moving inward, comparing characters at each step; mismatch means not a
palindrome. O(n) time, O(1) extra space (ignoring the string itself).

Q3. How do you detect if two strings are anagrams of each other?
Either (a) sort both strings and compare (O(n log n)), or (b) count character frequencies using a fixed-size array
(26 for lowercase English) or a HashMap, then compare counts — O(n) time, O(1) space for a bounded
alphabet, O(k) for a HashMap of distinct chars.

Q4. What is the sliding window technique, and when do you use it?
A technique for problems involving a contiguous subarray/substring, where you maintain a 'window' (defined by
two pointers) that expands and contracts based on a condition, avoiding recomputation from scratch for every
possible window — turning an O(n^2) or O(n^3) brute force into O(n). Used for problems like 'longest substring
without repeating characters', 'maximum sum subarray of size k', 'smallest subarray with sum >= target'.

Q5. How would you find the maximum sum subarray of size k in an array of size n?
Sliding window: compute the sum of the first k elements, then slide the window one step at a time by subtracting
the element leaving the window and adding the element entering it, tracking the max sum seen. O(n) time
instead of the brute force O(n*k).

Q6. What is Kadane's Algorithm, and what problem does it solve?

Page 18 | Java + DSA Placement Interview Master Guide

 It finds the maximum sum of any contiguous subarray in O(n) time, O(1) space. At each index, maintain
currentMax = max(arr[i], currentMax + arr[i]) — either extend the previous subarray or start fresh at the current
element — and track the overall max across all indices.

Q7. How do you find the first non-repeating character in a string?

Count frequency of each character in one pass (HashMap or fixed array), then in a second pass over the string
in original order, return the first character whose count is 1. O(n) time, O(k) space for k distinct characters.

Q8. How do you rotate an array by k positions in-place, in O(n) time and O(1) space?
Reverse the whole array, then reverse the first k elements, then reverse the remaining n-k elements (for a right
rotation) — three reversals achieve the rotation without extra space, each reversal being O(n), total still O(n).

Q9. What is a prefix sum array, and what problem class does it solve efficiently?
An array where prefix[i] = sum of all elements from index 0 to i-1 of the original array. It lets you answer any 'sum
of range [l, r]' query in O(1) time (prefix[r+1] - prefix[l]) after an O(n) one-time preprocessing step, instead of O(n)
per query with a naive approach — ideal when you have many range-sum queries on a static array.

Q10. How would you find all pairs in an array that sum to a target value?
With a sorted array: two pointers from both ends, moving inward based on whether the current sum is too high or
too low — O(n log n) for the sort plus O(n) scan. Without sorting: a HashSet, iterating once and for each element
checking if (target - element) has already been seen — O(n) time, O(n) space.

Q11. Given a string, how do you find the longest substring without repeating characters?
Sliding window with a HashMap/HashSet tracking characters currently in the window; expand the right pointer,
and whenever a repeated character is found, move the left pointer forward past its previous occurrence. O(n)
time, O(min(n, alphabet size)) space.

3. Linked Lists
THEORY NOTES
A singly linked list node holds data plus a reference to the next node; traversal is O(n) but insertion/deletion at a
known position is O(1) once you have the node reference (no shifting like arrays). Doubly linked lists add a
'prev' reference, enabling O(1) backward traversal and easier deletion.

Fast/slow pointer (Floyd's Tortoise and Hare) is THE canonical linked-list technique: move one pointer one step
and another two steps at a time — used for cycle detection, finding the middle node, and finding the start of a
cycle.

Reversing a linked list (iteratively, in O(1) space) is one of the single most commonly asked coding questions
across literally every company tier from TCS to Google, precisely because it tests pointer manipulation
fundamentals cleanly.

PRACTICE Q&A — 9 Questions

Q1. How do you reverse a singly linked list iteratively? Give the core logic.
Maintain three pointers: prev (starts null), curr (starts at head), next (temp). Loop while curr != null: save next =
[Link], reverse the link [Link] = prev, then advance prev = curr and curr = next. At the end, prev is the new
head. O(n) time, O(1) space.

Q2. How do you reverse a linked list recursively?

Recurse to the end of the list first; on the way back up, set each node's [Link] = node and [Link] = null,
then return the new head (the original tail). O(n) time, but O(n) space due to the recursion call stack — this space

Page 19 | Java + DSA Placement Interview Master Guide

 difference vs the iterative approach is a common interview follow-up.

Q3. How do you detect a cycle in a linked list without extra space?
Floyd's cycle detection (tortoise and hare): a slow pointer moves 1 step, a fast pointer moves 2 steps; if there's a
cycle, they will eventually meet inside it; if fast reaches null, there's no cycle. O(n) time, O(1) space.

Q4. Once a cycle is detected with Floyd's algorithm, how do you find where the cycle STARTS?
After slow and fast meet inside the cycle, reset one pointer to the head and keep the other at the meeting point;
move both one step at a time — they will meet exactly at the cycle's starting node. This works due to the
mathematical relationship between the distances traveled before and after the first meeting.

Q5. How do you find the middle node of a linked list in one pass?
Slow/fast pointers: slow moves 1 step, fast moves 2 steps; when fast reaches the end (or null), slow is at the
middle. O(n) time, O(1) space, single pass.

Q6. How do you merge two sorted linked lists into one sorted list?
Use a dummy head node and a tail pointer; repeatedly compare the current nodes of both lists, attach the
smaller one to tail, and advance that list's pointer; after one list is exhausted, attach the remainder of the other
list directly. O(n+m) time, O(1) extra space (just rewiring pointers).

Q7. How do you detect if two linked lists intersect, and find the intersection node, in O(n+m) time and
O(1) space?
Compute lengths of both lists (or use a two-pointer trick): advance the longer list's pointer by the length
difference first, then move both pointers together one step at a time — they will meet at the intersection node
(compared by reference, not value), or both reach null if there's no intersection.

Q8. How do you remove the Nth node from the end of a linked list in one pass?
Two pointers, both starting at a dummy head: advance the 'fast' pointer n steps ahead first, then move both
pointers together until fast reaches the last node; at that point, 'slow' is right before the node to remove, so
[Link] = [Link] removes it. O(n) time, one pass, O(1) space.

Q9. Singly vs doubly linked list — what's the tradeoff?

Doubly linked lists allow O(1) backward traversal and simpler O(1) deletion (no need to track the previous node
separately), at the cost of extra memory per node (the prev pointer) and slightly more pointer updates on
insert/delete.

4. Stacks & Queues

THEORY NOTES
Stack: LIFO (last-in-first-out) — push/pop/peek all O(1). Classic uses: expression evaluation/parsing (balanced
parentheses, postfix/infix conversion), undo functionality, DFS (implicit via recursion call stack, or explicit stack
for iterative DFS), backtracking.

Queue: FIFO (first-in-first-out) — enqueue/dequeue O(1) with a proper implementation (like a circular buffer or
linked list; a naive array-based queue that shifts elements on dequeue is O(n), a common beginner mistake).
Classic uses: BFS, task scheduling, buffering.

Monotonic stack (elements kept in increasing or decreasing order as you push/pop) is a very high-value pattern
for 'next greater element', 'largest rectangle in histogram', and stock-span type problems — worth memorizing
the template.

PRACTICE Q&A — 7 Questions

Page 20 | Java + DSA Placement Interview Master Guide

Q1. How do you check if a string of parentheses/brackets is balanced?
Push opening brackets onto a stack; on a closing bracket, check if the stack's top is the matching opener — if
yes pop it, if no (or stack is empty) it's unbalanced. At the end, the string is balanced only if the stack is empty.
O(n) time, O(n) space.

Q2. How do you implement a queue using two stacks?

Use an 'inStack' for enqueue (always push there) and an 'outStack' for dequeue: when dequeuing, if outStack is
empty, pop everything from inStack and push it onto outStack (this reverses the order to FIFO), then pop from
outStack. Each element moves between stacks at most once, giving amortized O(1) per operation.

Q3. What is a monotonic stack, and what problem does it solve efficiently?
A stack maintained so its elements are always in strictly increasing or decreasing order; when a new element
would violate that order, you pop elements off before pushing. It efficiently solves 'next greater/smaller element'
type problems in O(n) total (each element is pushed and popped at most once), versus O(n^2) brute force with
nested loops.

Q4. How do you find the 'next greater element' for every element in an array?
Iterate right to left (or left to right with a different technique) maintaining a monotonic decreasing stack of
candidate values; for each new element, pop all stack elements smaller than it (they've found their next greater
element = current element), then push the current element. O(n) time overall despite the nested-looking loop,
since each element is pushed/popped once.

Q5. Why is a naive array-based queue (shifting elements on dequeue) inefficient, and what's the fix?
Removing from the front and shifting every remaining element left is O(n) per dequeue. Fixes: a circular buffer
(track head/tail indices, wrap around with modulo, no shifting), or a linked-list-based queue (O(1) removal from
the front by just updating the head pointer).

Q6. How would you implement a stack that also supports getMin() in O(1) time?
Maintain a second 'min stack' alongside the main stack: whenever you push a value <= the current min stack's
top (or the min stack is empty), also push it onto the min stack; when you pop from the main stack, if the popped
value equals the min stack's top, pop the min stack too. getMin() just peeks the min stack. O(1) for push, pop,
and getMin, O(n) extra space worst case.

Q7. What is the difference between a Deque and a regular Queue?

A Deque (double-ended queue) supports insertion and removal from BOTH ends in O(1), so it can function as a
stack, a queue, or both simultaneously. A regular Queue only supports insertion at the rear and removal from the
front (strict FIFO).

5. Trees — Binary Trees, BSTs, Traversals & Balancing

THEORY NOTES
Binary tree: each node has at most two children. Traversal orders: Inorder (left, root, right — gives SORTED
order for a BST, extremely important fact), Preorder (root, left, right — used to serialize/recreate tree structure),
Postorder (left, right, root — used when children must be processed before the parent, e.g., deleting a tree,
evaluating expression trees), Level-order (BFS, using a queue).

BST (Binary Search Tree) property: for every node, all values in the left subtree are smaller, all values in the
right subtree are larger. This gives O(log n) average search/insert/delete for a BALANCED BST, but degrades
to O(n) for a skewed/unbalanced one (e.g., inserting sorted data into a naive BST produces a linked-list-like
structure) — this exact degradation scenario is a very common follow-up question.

Page 21 | Java + DSA Placement Interview Master Guide

Self-balancing trees (AVL, Red-Black) automatically maintain O(log n) height via rotations after insert/delete,
guaranteeing O(log n) worst-case operations — Java's TreeMap/TreeSet use red-black trees internally, and
HashMap's Java-8+ bucket-to-tree conversion also uses red-black trees.

PRACTICE Q&A — 11 Questions

Q1. What are the four standard tree traversal orders, and give one practical use case for each.
Inorder (L, Root, R): yields sorted order for a BST — use to retrieve elements in sorted sequence. Preorder
(Root, L, R): use to create a copy/serialize a tree's structure (root info comes before children, useful for
reconstruction). Postorder (L, R, Root): use when children must be fully processed before the parent, e.g., safely
deleting a tree bottom-up, or evaluating an expression tree. Level-order (BFS via queue): use for level-by-level
processing, e.g., finding tree width, or shortest path in an unweighted tree-like structure.

Q2. Why does an inorder traversal of a BST always produce sorted output?
By the BST property, at every node, everything in the left subtree is smaller and everything in the right subtree is
larger than the node itself. Inorder visits left-subtree-entirely, then the node, then right-subtree-entirely —
recursively this guarantees strictly increasing order across the whole traversal.

Q3. How do you check whether a binary tree is a valid BST?

You CANNOT just check each node against its immediate children — you must check against a valid (min, max)
RANGE inherited from ancestors, recursively narrowing the allowed range as you go left (upper bound becomes
the parent's value) or right (lower bound becomes the parent's value). A common wrong answer just compares
[Link] < [Link] < [Link], which misses violations from grandparents.

Q4. What is the time complexity of search/insert/delete in a BST, best case vs worst case?
Best/average case (balanced tree): O(log n), because each comparison eliminates roughly half the remaining
nodes. Worst case (degenerate/skewed tree, e.g. built by inserting already-sorted data): O(n), because the tree
degrades into essentially a linked list.

Q5. Why does inserting sorted data into a plain BST produce a bad (O(n) operations) tree?
Each new value is either always greater or always smaller than everything already inserted, so each insertion
just extends a single chain to one side (all right children, or all left children) instead of branching — producing a
tree of height n with no left/right balance, i.e., effectively a linked list.

Q6. How does an AVL tree keep operations at O(log n) worst case?
It maintains a 'balance factor' (height difference between left and right subtrees) of at most 1 for every node; after
any insert/delete, it performs rotations (single or double, i.e., left/right/left-right/right-left) to restore this balance,
which bounds the tree's height to O(log n) at all times.

Q7. What is the height/depth of a balanced binary tree with n nodes, in terms of n?
O(log n) — specifically roughly log2(n) for a fully balanced tree, since each level can hold up to double the nodes
of the previous level.

Q8. How do you find the Lowest Common Ancestor (LCA) of two nodes in a BST?
Start at the root; if both target values are less than the current node, go left; if both are greater, go right; the first
node where the values 'split' (one is <= current, other is >= current, or one equals current) is the LCA. O(h) time
where h is tree height, O(1) space (iterative).

Q9. How do you find the LCA in a general binary tree (not necessarily a BST)?
Recursively search both subtrees for the two target nodes; if a node itself is one of the targets, return it up; if both
left and right recursive calls return non-null (meaning one target was found on each side), the current node is the
LCA; otherwise propagate up whichever side found something. O(n) time, O(h) space for recursion.

Q10. What's the difference between a complete binary tree and a full (proper) binary tree?

Page 22 | Java + DSA Placement Interview Master Guide

 A complete binary tree has all levels fully filled except possibly the last, which is filled left to right. A full (proper)
binary tree is one where every node has either 0 or exactly 2 children (never exactly 1). These are independent
properties — a tree can be one, both, or neither.

Q11. Why do Java's TreeMap/TreeSet use red-black trees rather than plain BSTs?
A plain BST offers no balance guarantee and can degrade to O(n) operations on adversarial or sorted input.
Red-black trees self-balance via rotations and color-based rules, guaranteeing O(log n) worst-case for
search/insert/delete, which is essential for a general-purpose library data structure that must perform predictably
regardless of insertion order.

6. Graphs — Representation, BFS/DFS, Shortest Paths

THEORY NOTES
Graph representations: Adjacency Matrix (2D array, O(1) edge lookup, O(V^2) space — good for dense graphs)
vs Adjacency List (array/map of lists, O(V+E) space — good for sparse graphs, which is most real-world
graphs, hence the far more common choice in interviews).

BFS (queue-based, explores level by level) finds the SHORTEST PATH in an UNWEIGHTED graph, O(V+E)
time. DFS (stack-based or recursive, explores as deep as possible before backtracking) is used for cycle
detection, topological sort, connected components, and path existence — also O(V+E) time.

Dijkstra's algorithm finds shortest paths from a source in a weighted graph with NON-NEGATIVE edge weights,
O((V+E) log V) with a min-heap/priority queue. For graphs with negative weights, Bellman-Ford is needed
instead (O(V*E), also detects negative-weight cycles).

PRACTICE Q&A — 10 Questions

Q1. Adjacency list vs adjacency matrix — when would you choose each?
Adjacency matrix: O(1) edge-existence lookup, O(V^2) space regardless of edge count — good for dense
graphs or when frequent edge-existence queries matter. Adjacency list: O(V+E) space (much better for sparse
graphs, which is the vast majority of real-world graphs), but O(degree) to check if a specific edge exists —
generally the default choice unless you specifically need fast edge lookups on a dense graph.

Q2. Why does BFS (not DFS) find the shortest path in an unweighted graph?
BFS explores the graph in increasing distance 'layers' from the source — it fully explores all nodes at distance 1,
then all at distance 2, and so on — so the first time it reaches a target node is guaranteed to be via the shortest
(fewest-edges) path. DFS explores as deep as possible along one path first and offers no such distance-ordering
guarantee.

Q3. How do you detect a cycle in an undirected graph?

DFS while tracking the parent of the current node; if you visit a neighbor that's already visited AND it's not the
immediate parent, there's a cycle. (Alternatively: Union-Find — if two nodes of an edge are already in the same
set before union, adding that edge creates a cycle.)

Q4. How do you detect a cycle in a directed graph?

DFS while tracking nodes in the current recursion path (a 'visiting' set, distinct from a permanently 'visited' set); if
you encounter a node that's still in the current recursion path, there's a cycle. (Parent-checking, as used for
undirected graphs, does NOT work for directed graphs.)

Q5. What is topological sort, and what precondition must a graph satisfy for it to exist?

Page 23 | Java + DSA Placement Interview Master Guide

 An ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, u comes
before v in the ordering. It only exists if the graph has no cycles (hence 'acyclic' is required) — used for
scheduling tasks with dependencies, e.g., course prerequisites, build systems.

Q6. Name two algorithms for topological sort and briefly describe one.
Kahn's algorithm (BFS-based: repeatedly remove nodes with in-degree 0, decrementing the in-degree of their
neighbors) and DFS-based (do a DFS, and prepend each node to the result once ALL its descendants have
been fully explored — i.e., use the reverse of the DFS postorder finishing times).

Q7. Why doesn't Dijkstra's algorithm work correctly with negative edge weights?
Dijkstra greedily finalizes a node's shortest distance as soon as it's popped from the priority queue, assuming no
future path could possibly improve on it — but a negative edge encountered later could still reduce the distance
to an already-finalized node, violating that greedy assumption and producing an incorrect result.

Q8. What algorithm handles negative edge weights, and what extra capability does it provide over
Dijkstra?
Bellman-Ford, O(V*E) time. It correctly computes shortest paths with negative edges (but not negative cycles
reachable from the source), and additionally can DETECT negative-weight cycles (if you can still relax an edge
after V-1 iterations, a negative cycle exists) — something Dijkstra cannot do at all.

Q9. How would you find the number of connected components in an undirected graph?
Run BFS or DFS from any unvisited node, marking all nodes reachable from it as visited (that's one component);
repeat from the next unvisited node; count how many times you start a fresh traversal. O(V+E) time overall.

Q10. What's the difference between a graph and a tree?

A tree is a special case of a graph: connected, acyclic, and has exactly V-1 edges for V vertices, with exactly one
path between any two nodes. A general graph can have cycles, can be disconnected, and can have multiple
paths between two nodes (or none).

7. Sorting & Searching Algorithms

THEORY NOTES
Comparison-based sorting has a proven lower bound of O(n log n) — this is why merge sort/heap sort/quicksort
(average case) can't be beaten asymptotically by any comparison-based algorithm; only non-comparison sorts
(counting sort, radix sort, bucket sort) can go below that, by exploiting known structure/range in the data instead
of pairwise comparisons.

Quicksort: average O(n log n), worst-case O(n^2) (when the pivot is consistently the smallest/largest element,
e.g., already-sorted input with a naive first-element pivot) — this is exactly why production implementations use
randomized or median-of-three pivot selection to make worst-case behavior astronomically unlikely.

Merge sort: guaranteed O(n log n) in ALL cases (no bad-input worst case like quicksort), but requires O(n) extra
space for merging, whereas quicksort is in-place (O(log n) space for recursion only) — this space/guarantee
tradeoff is a frequently asked comparison question.

PRACTICE Q&A — 9 Questions

Q1. Why is comparison-based sorting bounded below by O(n log n)?
With n elements there are n! possible orderings; a comparison-based algorithm must, in the worst case,
distinguish between all n! possibilities, and since each comparison gives at most 1 bit of information, you need at
least log2(n!) comparisons, which by Stirling's approximation is Θ(n log n).

Page 24 | Java + DSA Placement Interview Master Guide

Q2. Quicksort vs Merge sort — compare time complexity, space, and stability.
Quicksort: average O(n log n), worst O(n^2) (rare with good pivot choice), in-place (O(log n) space for recursion),
NOT stable by default. Merge sort: guaranteed O(n log n) always, needs O(n) extra space for merging, IS stable
(equal elements keep their relative order) — this stability makes merge sort preferable when sorting objects by
one key while needing to preserve original order among ties.

Q3. What causes quicksort's worst-case O(n^2), and how do real implementations avoid it?
Consistently picking a 'bad' pivot (the smallest or largest remaining element every time), which happens with a
naive first-element pivot on already-sorted or reverse-sorted input, causing highly unbalanced partitions (one
side has n-1 elements) at every level, giving O(n^2) instead of the balanced O(n log n). Fix: randomized pivot
selection or median-of-three, making the worst case extremely unlikely in practice.

Q4. How does binary search work, and what precondition does it require?
Repeatedly compare the target to the middle element of the current search range; if equal, found; if target is
smaller, recurse/iterate on the left half; if larger, the right half — halving the search space each step. Requires
the array to be SORTED beforehand; O(log n) time, O(1) space iteratively (O(log n) space if implemented
recursively, due to call stack).

Q5. What's a common off-by-one bug in binary search, and how do you avoid it?
Computing mid = (low + high) / 2 can integer-overflow for very large low+high in languages with fixed-size ints
(less of an issue in Java's int range for typical interview-sized inputs, but still good practice); safer: mid = low +
(high - low) / 2. Another common bug: using high = mid instead of high = mid - 1 (or low = mid instead of low =
mid + 1) can cause infinite loops — always verify the loop invariant shrinks the range on every iteration.

Q6. How would you find the first and last occurrence of a target value in a sorted array with duplicates,
in O(log n)?
Two separate binary searches: one biased to keep searching LEFT even after finding a match (to find the first
occurrence), one biased to keep searching RIGHT after finding a match (to find the last occurrence). Both are
still O(log n), so O(log n) total, much better than an O(n) linear scan.

Q7. What is counting sort, and when is it useful?

A non-comparison sort that counts occurrences of each distinct value (assuming values fall in a known,
reasonably small range), then reconstructs the sorted output from those counts. O(n + k) time where k is the
range of input values — much faster than O(n log n) when k is small relative to n, but wasteful/impractical when k
is very large (e.g., sorting arbitrary large doubles).

Q8. What is the difference between a stable and an unstable sort, and why would it matter in a real
scenario?
A stable sort preserves the relative order of elements that compare as equal; an unstable sort makes no such
guarantee. It matters e.g. when sorting a list of orders first by customer name and then (stably) by order date —
a stable sort on date preserves the prior name-based grouping/order for orders with the same date, while an
unstable sort could scramble it.

Q9. Explain how you'd search in a rotated sorted array in O(log n).
Modified binary search: at each step, determine which half (left of mid, or right of mid) is properly sorted by
comparing arr[low] and arr[mid]; then check if the target lies within that sorted half's range — if yes,
recurse/iterate into that half, otherwise recurse into the other half. Still O(log n) since you always eliminate half
the search space each step.

8. Recursion & Backtracking

THEORY NOTES

Page 25 | Java + DSA Placement Interview Master Guide

Every recursive function needs a base case (stopping condition) and a recursive case that makes measurable
progress toward the base case — missing either causes infinite recursion and a StackOverflowError, tying back
directly to the JVM memory section.

Backtracking = recursion + explicit undo: try a choice, recurse deeper, and if that path fails (or you've explored it
fully), UNDO the choice ('backtrack') and try the next option. It's the standard technique for generating all
subsets/permutations/combinations, and for constraint-satisfaction problems (N-Queens, Sudoku solver, word
search in a grid).

The backtracking template: define the choices available at each step, recurse into each choice, and explicitly
revert any shared state (like removing the last-added element from a running path, or un-marking a visited cell)
before trying the next choice — forgetting the 'undo' step is the single most common bug.

PRACTICE Q&A — 8 Questions

Q1. What are the two essential components of any correct recursive function?
A base case (a condition that stops the recursion and returns directly without further recursive calls) and a
recursive case that calls itself with a strictly 'smaller'/simpler input, making guaranteed progress toward the base
case.

Q2. What happens if a recursive function has no base case, or the base case is unreachable?
Infinite recursion — each call adds a new frame to the call stack, and since it never stops, the stack eventually
exceeds its size limit, throwing a StackOverflowError.

Q3. How would you generate all subsets of a set using backtracking?
At each element, recursively branch into two choices: include it in the current subset, or don't; when you've made
a decision for every element, add the current subset to the results. This explores 2^n leaf outcomes for n
elements, O(2^n) time, matching the number of possible subsets.

Q4. How would you generate all permutations of an array using backtracking?
Maintain a 'used' marker per element (or swap-based approach); at each recursive step, try placing each
not-yet-used element next in the current permutation, recurse, then UNDO (mark it unused again / swap back)
before trying the next candidate. O(n!) time, matching the number of permutations.

Q5. What is the key difference between backtracking and plain brute-force recursion?
Backtracking actively PRUNES: as soon as a partial solution is known to violate a constraint, it abandons that
branch immediately rather than continuing to build it out fully — this can dramatically reduce the actual explored
search space below the theoretical worst case, even though the worst-case complexity bound is often the same.

Q6. Explain the classic N-Queens backtracking approach at a high level.

Place queens row by row; for each row, try placing a queen in each column, checking if it conflicts with any
previously placed queen (same column, or same diagonal); if no conflict, recurse to the next row; if a full valid
placement across all rows is reached, record the solution; if a row has no valid column, backtrack to the previous
row and try its next option.

Q7. Why is memoization (top-down DP) essentially 'recursion + a cache'?

Plain recursion may recompute the exact same subproblem many times (like naive Fibonacci). Memoization
stores each subproblem's result the first time it's computed (usually in a HashMap or array keyed by the
subproblem's parameters), and any subsequent identical call just returns the cached result instead of
recomputing — turning exponential-time recursion into polynomial time for problems with overlapping
subproblems.

Page 26 | Java + DSA Placement Interview Master Guide

Q8. What is the time complexity of the naive recursive approach to computing all combinations of k
elements out of n?
O(C(n,k) * k) roughly — you generate C(n,k) combinations, each taking O(k) to build/copy — the backtracking
approach prunes branches early (once you can't possibly reach k elements with remaining choices) rather than
blindly generating all 2^n subsets and filtering by size.

9. Dynamic Programming
THEORY NOTES
DP applies when a problem has (1) OVERLAPPING SUBPROBLEMS (the same smaller subproblem is solved
repeatedly in a naive recursive approach) and (2) OPTIMAL SUBSTRUCTURE (the optimal solution to the full
problem can be built from optimal solutions to its subproblems). Recognizing these two properties — usually by
first writing the naive recursive solution and noticing repeated calls — is the actual interview skill being tested,
more than memorizing specific problems.

Two implementation styles: top-down (memoization — write the natural recursion, add a cache) and bottom-up
(tabulation — build up a table iteratively from the smallest subproblems to the full problem, usually avoiding
recursion/call-stack overhead entirely). Both achieve the same time complexity; tabulation is often preferred in
practice for avoiding stack depth issues and sometimes allows further space optimization (e.g., only keeping
the last 1-2 rows of a 2D table).

Classic DP problem families worth having memorized end-to-end: 0/1 Knapsack, Longest Common
Subsequence, Longest Increasing Subsequence, Coin Change (min coins / number of ways), Edit Distance,
and House Robber-style 'take or skip adjacent' problems.

PRACTICE Q&A — 9 Questions

Q1. What two properties must a problem have for Dynamic Programming to apply?
Overlapping subproblems (a naive recursive solution solves identical smaller subproblems repeatedly) and
optimal substructure (the globally optimal solution can be constructed from optimal solutions of its subproblems).
If either is missing — e.g., no overlap — plain recursion or divide-and-conquer is more appropriate than DP.

Q2. What's the difference between top-down (memoization) and bottom-up (tabulation) DP?
Top-down: write the natural recursive solution, then add a cache (array/map) to store and reuse results of
subproblems already solved — closely mirrors the recursive structure, computes only subproblems actually
needed. Bottom-up: build an iterative table starting from the smallest base-case subproblems, progressively
combining them up to the final answer — usually avoids recursion/stack overhead, and computes all
subproblems in the table's range whether needed or not.

Q3. How would you solve 0/1 Knapsack with DP? State the recurrence and complexity.
dp[i][w] = max value using the first i items with capacity w. Recurrence: dp[i][w] = dp[i-1][w] (skip item i) if item i's
weight > w, else max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) (best of skip vs take). O(n*W) time and space,
where n is item count and W is capacity; space can be reduced to O(W) using a 1D rolling array.

Q4. How would you find the Longest Common Subsequence (LCS) of two strings with DP?
dp[i][j] = length of LCS of the first i characters of string A and first j characters of string B. If A[i-1] == B[j-1], dp[i][j]
= dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). O(n*m) time and space for strings of length n and m.

Q5. How would you compute the minimum number of coins to make a target amount (Coin Change)?
dp[amount] = minimum coins to make that amount. Base case dp[0] = 0. For each amount from 1 upward,
dp[amount] = min over all coin denominations c <= amount of (dp[amount - c] + 1), if reachable; otherwise

Page 27 | Java + DSA Placement Interview Master Guide

 infinity/unreachable. O(amount * number of coin types) time.

Q6. What is the House Robber problem, and what is its DP recurrence?
Given houses in a row with values, find the max sum you can rob without robbing two ADJACENT houses. dp[i]
= max(dp[i-1] (skip house i), dp[i-2] + value[i] (rob house i, must skip i-1)). O(n) time, and space can be reduced
to O(1) since you only ever need the last two dp values.

Q7. What is the recurrence for Longest Increasing Subsequence (LIS), and its time complexity in the
basic DP formulation?
dp[i] = length of the LIS ending exactly at index i = 1 + max(dp[j]) over all j < i where arr[j] < arr[i] (or just 1 if no
such j exists). O(n^2) time in this basic form (can be optimized to O(n log n) using binary search with a
patience-sorting-style approach, a common 'can you do better' follow-up).

Q8. Why can House Robber's DP be optimized from O(n) space to O(1) space, but LCS generally cannot
go below O(n) or O(min(n,m)) easily?
House Robber's recurrence for dp[i] only ever depends on the two immediately preceding values (dp[i-1],
dp[i-2]), so you only need to keep those two rolling variables. LCS's dp[i][j] depends on an entire previous ROW
(dp[i-1][*]) to compute the current row, so you need at least one full row's worth of space (O(min(n,m)) with a
rolling-row optimization), not just a couple of scalars.

Q9. How would you compute Edit Distance (minimum operations to convert string A to string B)?
dp[i][j] = edit distance between first i chars of A and first j chars of B. If A[i-1]==B[j-1], dp[i][j] = dp[i-1][j-1] (no
operation needed); otherwise dp[i][j] = 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)). O(n*m)
time and space.

10. Greedy Algorithms & Hashing

THEORY NOTES
A greedy algorithm makes the locally optimal choice at each step, hoping (and in provably-correct cases,
guaranteeing) that this leads to a globally optimal solution — it works only when the problem has the 'greedy
choice property' (a locally optimal choice never needs to be revisited/undone later). Interviewers often ask you
to justify WHY greedy works for a specific problem, or to find a counterexample where a naive greedy approach
fails.

Classic correct-greedy problems: Activity Selection (sort by finish time, pick the earliest-finishing compatible
activity each time), Fractional Knapsack (sort by value/weight ratio), Huffman Coding, Dijkstra's shortest path
(greedy + priority queue). Classic problems where naive greedy FAILS: 0/1 Knapsack (greedy by value/weight
ratio does not guarantee optimal — needs DP instead), which is a favorite 'why doesn't greedy work here' trap
question.

Hashing underlies HashMap/HashSet and is separately tested as a standalone technique: using a hash
set/map to achieve O(1) average lookups turns many O(n^2) brute-force pair/subarray problems into O(n) —
e.g., Two Sum, detecting duplicates, subarray sum equals K.

PRACTICE Q&A — 8 Questions

Q1. What is the 'greedy choice property', and why does it justify a greedy algorithm's correctness?
A property where making the locally optimal choice at the current step never prevents you from reaching a
globally optimal solution — i.e., you never need to reconsider or undo an earlier greedy choice. When a problem
provably has this property (usually shown via an exchange argument), a greedy algorithm is guaranteed correct,
not just a heuristic.

Page 28 | Java + DSA Placement Interview Master Guide

Q2. Why does greedy work for Activity Selection (interval scheduling to maximize count of
non-overlapping activities)?
Sorting by EARLIEST FINISH TIME and always picking the next compatible activity is provably optimal:
choosing the activity that finishes earliest always leaves the maximum possible remaining time for future
activities, so it can never be worse than any other valid first choice (standard exchange-argument proof).

Q3. Why does a naive greedy-by-value/weight-ratio approach FAIL for 0/1 Knapsack, when it works for
Fractional Knapsack?
In Fractional Knapsack, you can take a PARTIAL item, so always grabbing the best ratio first and filling
remaining capacity fractionally is optimal. In 0/1 Knapsack, items are all-or-nothing — greedily taking the
best-ratio item first can lock in a choice that leaves awkward leftover capacity that can't be used efficiently,
missing a better combination that a full DP search over all inclusion/exclusion choices would find. This is exactly
why 0/1 Knapsack requires DP, not greedy.

Q4. How does hashing turn the 'Two Sum' problem from O(n^2) to O(n)?
Brute force checks every pair (O(n^2)). With a HashMap, iterate once, and for each element check whether
(target - element) has already been seen and stored in the map; if yes, you found the pair; if no, add the current
element to the map and continue. Single pass, O(n) time, O(n) space.

Q5. How would you find if an array contains any duplicate elements efficiently?
Iterate once, inserting each element into a HashSet; if an insertion attempt finds the element already present
(add() returns false, or contains() check first), a duplicate exists. O(n) time, O(n) space — versus O(n log n) via
sorting first, or O(n^2) via brute-force nested comparison.

Q6. How would you find the count of subarrays whose sum equals a target K, in O(n)?
Use a prefix sum running total plus a HashMap that tracks how many times each prefix-sum VALUE has
occurred so far. At each index, check if (currentPrefixSum - K) exists in the map — its count tells you how many
subarrays ending here sum to K — then increment the map's count for currentPrefixSum. O(n) time, O(n) space.

Q7. What is a hash collision, and name two common resolution strategies.
When two different keys map to the same hash bucket/index. Two strategies: (1) Chaining — each bucket holds
a list (or tree, as in Java 8+ HashMap) of all entries that hash there. (2) Open addressing — on collision, probe
for the next available slot using a defined sequence (linear probing, quadratic probing, or double hashing).

Q8. Give an example of a problem where greedy gives a WRONG answer and explain why, to show you
understand greedy's limitations.
Coin Change (minimum coins) with an arbitrary coin system, e.g. coins = {1, 3, 4}, target = 6: greedy (always
take the largest coin <= remaining) picks 4, then 1, then 1 → 3 coins (4+1+1), but the optimal answer is 3+3 → 2
coins. Greedy fails here because taking the largest coin first isn't always part of the truly optimal combination —
this specific coin system lacks the greedy-choice property, which is exactly why general Coin Change is solved
with DP, not greedy.

Page 29 | Java + DSA Placement Interview Master Guide