Overlapping Topics — In-Depth Notes &
Q&A
Companion to the Master Prep Notebook — Phase 2: DSA, Algorithms,
Discrete Mathematics
This covers the remaining topics from the Overlap Map ("Study Once, Use Three Times") that weren't yet
built in full depth: DSA fundamentals (Arrays/Strings/HashMap), Algorithms (complexity, greedy, DP,
graphs), and Discrete Mathematics. Already covered in Phase 1: OOP, DBMS+SQL, Operating Systems,
Computer Networks — see that document for those. Aptitude/Reasoning and HR/Communication are skill-
practice topics rather than notes-and-theory topics, so they're handled as question banks/frameworks in
Phase 1 rather than repeated here.
Sources & Confidence: 🟢 Core CS fundamentals (complexity analysis, standard algorithms, discrete math theorems) are stable,
well-established content cross-checked against GeeksforGeeks and standard curricula. 🟡 Interview question framing is
synthesized from common patterns across 2024–2026 candidate reports.
Part 1 — DSA Fundamentals (Arrays, Strings, HashMap)
Why this subject matters
● EY: Round 1 coding questions are consistently reported as array/hashing-level (easy-medium) — this
is the exact tier covered here.
● Cognizant: Automata Fix (debugging) and the CodePro track both draw heavily on
array/string/hashmap manipulation.
● GATE: Programming & Data Structures is tested in C but the underlying concepts (array traversal,
string processing, hashing behavior) are language-independent and worth an estimated 10–12
marks.
Complete topic checklist
☐ Array traversal & in-place modification
☐ Two pointers
☐ Sliding window (fixed & variable size)
☐ Prefix sum
☐ Kadane's algorithm (max subarray)
☐ String manipulation (reverse, palindrome check, anagram check)
☐ HashMap for frequency counting
☐ HashMap for O(1) lookup (two-sum pattern)
☐ Sorting-based techniques
☐ Binary search on sorted arrays
☐ In-place array rotation
In-depth notes — high-yield patterns
1. Two Pointers
Definition: Use two indices moving toward each other (or in the same direction at different speeds) to avoid
a nested loop, cutting an O(n²) brute force to O(n).
Recognition: Sorted array + "find a pair/triplet that sums to X", or "reverse in place", or "remove duplicates
in place" — these are two-pointer signals.
Example — Two Sum on a sorted array: Start i=0 at the left, j=n-1 at the right. If arr[i]+arr[j] == target, found.
If sum < target, move i right (need a bigger sum). If sum > target, move j left.
int i=0, j=[Link]-1;
while (i < j) {
int sum = arr[i] + arr[j];
if (sum == target) return new int[]{i, j};
else if (sum < target) i++;
else j--;
}
Common mistake ⚠️: Using two pointers on an unsorted array without sorting first (breaks correctness), or
forgetting the array must be sorted for this specific pattern — for unsorted "two sum", use a HashMap
instead (see below).
2. Sliding Window
Definition: Maintain a "window" (subarray/substring) between two pointers, expanding the right edge and
contracting the left edge based on a condition, so each element is visited a bounded number of times —
turning an O(n²) brute force into O(n).
Recognition: "Longest/shortest substring/subarray with condition X", "maximum sum of a subarray of size k"
— these phrases signal sliding window.
Example — longest substring without repeating characters: Expand right, adding characters to a HashSet; if
a duplicate is found, shrink from the left until the duplicate is removed; track max window size seen.
Set<Character> seen = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < [Link](); right++) {
while ([Link]([Link](right))) {
[Link]([Link](left));
left++;
}
[Link]([Link](right));
maxLen = [Link](maxLen, right - left + 1);
}
Common mistake ⚠️: Recomputing the window sum/state from scratch every time instead of incrementally
updating it — this silently reintroduces O(n²) behavior.
3. HashMap patterns
Pattern A — Frequency counting: Count occurrences of each element/character in one pass, then use those
counts (e.g., anagram check, first non-repeating character, majority element).
Pattern B — O(1) lookup (Two Sum, unsorted): For each element, check if (target - element) already exists
in the map before inserting the current element — single pass, O(n) time, O(n) space.
Map<Integer,Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < [Link]; i++) {
int need = target - arr[i];
if ([Link](need)) return new int[]{[Link](need), i};
[Link](arr[i], i);
}
Interview angle: Always state the trade-off out loud: HashMap trades O(n) extra space for O(1) average
lookup, turning an O(n²) brute force into O(n) time — interviewers want to hear you name this trade-off
explicitly, not just produce working code.
GATE angle: GATE tests hashing conceptually — collision resolution (chaining vs open addressing), load
factor, and average-case vs worst-case complexity (O(1) average, O(n) worst case) rather than
implementation.
4. Kadane's Algorithm (Maximum Subarray Sum)
Definition: At each index, decide whether to extend the previous subarray or start a new one from the
current element — track the running sum and the maximum seen so far.
int maxSoFar = arr[0], currMax = arr[0];
for (int i = 1; i < [Link]; i++) {
currMax = [Link](arr[i], currMax + arr[i]);
maxSoFar = [Link](maxSoFar, currMax);
}
Common trap ⚠️: Forgetting that if all elements are negative, the answer is the single largest (least negative)
element, not 0 — don't initialize maxSoFar to 0.
Interview questions — leveled
Level 1 — Basic Q: How would you check if a string is a palindrome?
Ideal answer: Use two pointers from both ends moving inward, comparing characters; return false on the
first mismatch, true if the pointers cross.
Why asked: Fundamental string-manipulation fluency check.
Follow-up: "Can you do it without extra space?" (Two-pointer approach already uses O(1) extra space.)
Common wrong answer: Reversing the string and comparing — works, but uses O(n) extra space and is less
efficient than the two-pointer approach.
Level 2 — Intermediate Q: Given an array, find two numbers that add up to a target. What's your approach
and complexity?
Ideal answer: Use a HashMap: for each element, check if (target - element) has already been seen; if yes,
return the pair; otherwise store the current element and continue. O(n) time, O(n) space — better than the
O(n²) brute-force nested loop.
Why asked: One of the most universally asked coding questions across EY, Cognizant, and general fresher
interviews.
Follow-up: "What if the array is sorted — can you do better on space?" (Yes — two pointers, O(1) extra
space.)
Common wrong answer: Nested loop (O(n²)) without mentioning the HashMap optimization when explicitly
asked for an efficient approach.
Level 3 — Tricky Q: Your sliding window solution passes on the sample input but times out on large input
— what's the likely bug?
Ideal answer: Most likely the window's internal state (sum, character counts, etc.) is being recomputed from
scratch on every expansion instead of updated incrementally — turning what should be O(n) into O(n²) or
worse. Check that the left-pointer contraction loop and any sum/count updates are O(1) amortized per step.
Why asked: Tests whether the candidate actually understands why sliding window is efficient, not just that
they memorized the pattern.
Follow-up: "How would you prove your window pointer never moves backward, so the algorithm is truly
O(n)?"
Common wrong answer: Blaming it on "the input is too large for Java" without inspecting the actual time
complexity of the implementation.
Sources & Confidence: 🟢 Patterns and complexity analysis are standard DSA fundamentals, cross-checked against GeeksforGeeks
and InterviewBit. 🟡 Question framing reflects common fresher-interview phrasing across 2024–2026 candidate reports.
Part 2 — Algorithms (Complexity, Greedy, DP, Graphs)
Why this subject matters
● EY/Cognizant: Complexity analysis ("what's the time complexity of your solution?") is asked after
almost every coding question, regardless of company.
● GATE: Algorithms is historically the single highest-weighted GATE CS section (estimated 12–16
marks) — recurrences, graph algorithms, and DP are core, recurring numerical-question territory.
Complete topic checklist
☐ Asymptotic notation (Big-O, Big-Ω, Big-Θ)
☐ Recurrence relations & Master theorem
☐ Sorting algorithms & complexity
☐ Searching (linear, binary)
☐ Hashing (collision resolution)
☐ Greedy algorithms
☐ Divide and conquer
☐ Dynamic programming (memoization vs tabulation)
☐ Graph representations (adjacency list/matrix)
☐ Graph traversal (BFS, DFS)
☐ Minimum Spanning Tree (Kruskal's, Prim's)
☐ Shortest path (Dijkstra's, Bellman-Ford, Floyd-Warshall)
☐ Topological sort
In-depth notes — high-yield concepts
1. Complexity analysis
Notation Meaning Use
Big-O (O) Upper bound — worst case "Algorithm never does worse than this"
Big-Omega (Ω) Lower bound — best case "Algorithm never does better than this"
Big-Theta (Θ) Tight bound — both "Algorithm's growth rate exactly matches this"
Common mistake ⚠️: Using "O(n)" to describe average-case behavior when the worst case is actually higher
(e.g., calling HashMap lookup "O(1)" without the caveat that it's O(1) average, O(n) worst case under heavy
collisions).
GATE angle: GATE frequently gives a recurrence relation (e.g., T(n) = 2T(n/2) + n) and asks you to solve it via
the Master theorem or recursion tree — practice both methods, since Master theorem doesn't apply to every
recurrence form.
2. Master Theorem — quick reference
For T(n) = aT(n/b) + f(n), compare f(n) to n^(log_b a):
Case Condition Result
Case 1 f(n) = O(n^(log_b a - ε)) T(n) = Θ(n^log_b a)
Case 2 f(n) = Θ(n^log_b a) T(n) = Θ(n^log_b a · log n)
Case 3 f(n) = Ω(n^(log_b a + ε)), regularity holds T(n) = Θ(f(n))
Example: Merge sort: T(n) = 2T(n/2) + n. Here a=2, b=2, so n^(log_b a) = n^1 = n. f(n) = n matches Case 2
exactly, so T(n) = Θ(n log n).
3. Greedy vs Dynamic Programming
Aspect Greedy Dynamic Programming
Choice Makes the locally optimal choice and never Explores overlapping subproblems, often
revisits it revisiting/reusing prior results
Correctness needs Greedy-choice property + optimal substructure Optimal substructure + overlapping
subproblems
Speed Usually faster (single pass) Slower — needs a table/memo
Example Activity selection, Huffman coding, Dijkstra's 0/1 Knapsack, Longest Common Subsequence,
(non-negative weights) Fibonacci with memoization
Interview angle: The classic trap is applying greedy where DP is required — e.g., 0/1 Knapsack cannot be
solved greedily (fractional Knapsack can). Be ready to explain *why* greedy fails for 0/1 Knapsack: a locally
optimal item choice can block a better combination later, since items can't be split.
Explain like an interviewer expects: Dynamic Programming
10-sec: DP solves a problem by breaking it into overlapping subproblems and storing their results to avoid
recomputation.
30-sec: Dynamic programming applies when a problem has optimal substructure — the optimal solution can
be built from optimal solutions to subproblems — and overlapping subproblems, meaning the same
subproblem recurs multiple times. We store each subproblem's result (memoization, top-down, or
tabulation, bottom-up) so we compute it once instead of exponentially many times.
1-min: DP is really about avoiding redundant work in problems that have optimal substructure and
overlapping subproblems. Take Fibonacci: naive recursion recomputes fib(n-2) many times across different
branches — that's the overlap. With memoization we cache each fib(k) the first time we compute it, turning
exponential time into linear. Tabulation does the same thing bottom-up, filling a table iteratively from the
base case, which also avoids recursion-stack overhead. The general recipe is: define the state, write the
recurrence relating a state to smaller states, decide the iteration order, and use memoization or tabulation to
store results. I'd apply this to problems like Knapsack, LCS, or edit distance by identifying what the 'state'
represents — e.g., 'best value achievable with the first i items and capacity w' for Knapsack.
4. Graph algorithms — when to use which
Problem Algorithm Complexity Note
Shortest path, non- Dijkstra's O((V+E) log V) with a Greedy; fails with negative
negative weights min-heap edges
Shortest path, negative Bellman-Ford O(V·E) Also detects negative-weight
weights allowed cycles
All-pairs shortest path Floyd-Warshall O(V³) DP-based; simple to
implement
Problem Algorithm Complexity Note
Minimum Spanning Kruskal's (edge-based, needs O(E log E) / O(E log V) Both greedy; choose based
Tree Union-Find) or Prim's (vertex- on graph density
based, needs a heap)
Dependency ordering Topological sort O(V+E) Requires no cycles —
(DAG only) undefined on a cyclic graph
Common trap ⚠️: Using Dijkstra's on a graph with negative edge weights — it will silently produce a wrong
(too-optimistic) answer instead of erroring, because its greedy assumption breaks.
Interview questions — leveled
Level 1 — Basic Q: What is the time complexity of binary search, and why?
Ideal answer: O(log n) — each comparison eliminates half the remaining search space, so the number of
steps to reduce n elements to 1 is log₂(n).
Why asked: Baseline complexity-analysis fluency.
Follow-up: "What's the precondition for binary search to work?" (The array must be sorted.)
Common wrong answer: Saying O(n) — confusing it with linear search.
Level 2 — Intermediate Q: Why can't Dijkstra's algorithm handle negative edge weights?
Ideal answer: Dijkstra's greedily finalizes a vertex's shortest distance once it's popped from the priority
queue, assuming no future path could ever improve on it. Negative edges break that assumption — a longer-
looking path could later become shorter via a negative edge, but the algorithm has already "locked in" the
wrong answer for a finalized vertex.
Why asked: Tests whether the greedy-choice property is actually understood, not just the algorithm's steps
memorized.
Follow-up: "What would you use instead?" (Bellman-Ford, which relaxes all edges V-1 times and can also
detect negative cycles.)
Common wrong answer: "It just doesn't support negative numbers" without explaining the underlying
greedy-correctness reason.
Level 3 — Tricky Q: Given a recurrence T(n) = T(n/2) + T(n/2) + O(1), is this the same growth rate as merge
sort's T(n) = 2T(n/2) + n?
Ideal answer: No. T(n) = 2T(n/2) + O(1) has f(n) = O(1), which is polynomially smaller than n^(log_2 2) = n —
this is Master theorem Case 1, giving T(n) = Θ(n). Merge sort's f(n) = n matches n^1 exactly — Case 2, giving
Θ(n log n). Same branching structure, different combine-step cost, different final complexity.
Why asked: Tests precise application of the Master theorem rather than pattern-matching "looks like merge
sort so it must be n log n."
Follow-up: "What real algorithm has this T(n) = 2T(n/2) + O(1) recurrence?" (e.g., a balanced binary tree
traversal that does O(1) work per node.)
Common wrong answer: Assuming any "2T(n/2) + something" recurrence is automatically O(n log n) without
checking the combine-step cost.
Sources & Confidence: 🟢 Algorithm complexity and behavior are standard, well-established CS content, cross-checked against
GeeksforGeeks and CLRS-level fundamentals — stable and safe to treat as high confidence for both interviews and GATE.
Part 3 — Discrete Mathematics
Why this subject matters
● EY/Cognizant: Rarely asked directly, but logical reasoning and puzzle-style aptitude questions draw
on the same thinking (propositional logic, counting, graph basics).
● GATE: Part of the fixed 13-mark Engineering Mathematics allocation — graph theory, combinatorics,
and propositional logic are consistently among the more "reliable scoring" areas in GATE, since the
question patterns repeat more predictably than in some CS-core sections.
Complete topic checklist
☐ Propositional & first-order logic
☐ Sets, relations, functions
☐ Partial orders & lattices
☐ Monoids, groups
☐ Graph theory: connectivity, matching, colouring
☐ Combinatorics: counting, permutations & combinations
☐ Recurrence relations
☐ Generating functions
In-depth notes — high-yield concepts
1. Propositional logic — key equivalences
Law Equivalence
De Morgan's ¬(P ∧ Q) ≡ ¬P ∨ ¬Q ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Implication P → Q ≡ ¬P ∨ Q
Contrapositive P → Q ≡ ¬Q → ¬P
Biconditional P ↔ Q ≡ (P → Q) ∧ (Q → P)
Common trap ⚠️: Confusing the converse (Q → P) and contrapositive (¬Q → ¬P) of P → Q — only the
contrapositive is logically equivalent to the original; the converse is not.
2. Relations — properties
Property Definition
Reflexive ∀a, (a,a) ∈ R
Symmetric (a,b) ∈ R ⟹ (b,a) ∈ R
Antisymmetric (a,b) ∈ R and (b,a) ∈ R ⟹ a = b
Transitive (a,b) ∈ R and (b,c) ∈ R ⟹ (a,c) ∈ R
Equivalence relation Reflexive + Symmetric + Transitive → partitions the set into equivalence classes
Interview/GATE angle: GATE loves giving a relation as a set of pairs and asking which properties it satisfies —
the fastest method is to check reflexivity first (quick to rule in/out), then scan pairs for symmetric/transitive
violations by counter-example rather than proving properties abstractly.
3. Graph theory — GATE-favorite results
Handshaking lemma: Sum of all vertex degrees = 2 × number of edges. Consequence: the number of odd-
degree vertices in any graph is always even.
Trees: A tree with n vertices has exactly n−1 edges and is connected with no cycles. Any two of {connected,
acyclic, n−1 edges} imply the third.
Bipartite graphs: A graph is bipartite if and only if it contains no odd-length cycle.
Common GATE trap ⚠️: Assuming a graph with n−1 edges must be a tree — this is only true if the graph is
also known to be connected; otherwise it could be a disconnected forest plus one extra cycle, which still has
n−1 edges but isn't a tree.
4. Combinatorics — counting principles
Concept Formula Use case
Permutation P(n,r) = n! / (n−r)! Arrangements where order matters
Combination C(n,r) = n! / (r!(n−r)!) Selections where order doesn't matter
Pigeonhole principle n items into m boxes, n>m ⟹ some Proving existence, not construction
box has ≥2 items
Inclusion-Exclusion |A∪B| = |A|+|B|−|A∩B| Counting unions of overlapping sets
Common mistake ⚠️: Using permutation formula when the problem actually asks for combinations (or vice
versa) — always ask "does order matter here?" before picking the formula.
Interview / GATE-style questions — leveled
Level 1 — Basic Q: Is the relation "≤" on the set of integers reflexive, symmetric, antisymmetric, and/or
transitive?
Ideal answer: Reflexive (a≤a always true), not symmetric (a≤b doesn't imply b≤a unless equal),
antisymmetric (a≤b and b≤a implies a=b), and transitive (a≤b and b≤c implies a≤c). So it's a partial order, not
an equivalence relation.
Why asked: Standard relation-properties fluency check, very common as a GATE-style MCQ.
Follow-up: "What relation on integers would be an equivalence relation instead?" (e.g., "congruent mod n".)
Common wrong answer: Calling ≤ symmetric because it "looks like" an ordering relation — a common
confusion.
Level 2 — Intermediate Q: A graph has 6 vertices, all of degree 3. How many edges does it have?
Ideal answer: By the handshaking lemma, sum of degrees = 2×edges. Sum of degrees = 6×3 = 18, so edges =
18/2 = 9.
Why asked: Tests direct application of the handshaking lemma — a very common GATE numerical pattern.
Follow-up: "Could such a graph actually exist (is it realizable)?" (Yes — e.g., the complement of a perfect
matching on K6, or other 3-regular graphs on 6 vertices exist.)
Common wrong answer: Forgetting to divide by 2, giving 18 as the edge count instead of 9.
Level 3 — Tricky Q: If a graph has n−1 edges, is it necessarily a tree?
Ideal answer: Not necessarily. n−1 edges plus connectedness together guarantee a tree, but n−1 edges alone
doesn't guarantee connectedness — you could have a disconnected graph where one component has a cycle
(using up an "extra" edge) while another component is smaller, still totaling n−1 edges overall without being
a tree.
Why asked: A classic GATE trap question that tests whether "tree = connected + acyclic + n−1 edges" is
understood as needing exactly two of the three conditions to conclude the third, not just the edge count
alone.
Follow-up: "What's the minimum additional condition needed to guarantee it's a tree?" (Either
connectedness or acyclicity, given n−1 edges.)
Common wrong answer: Answering "yes" outright — the single most common wrong answer to this exact
GATE-style question.
Sources & Confidence: 🟢 Discrete mathematics content (logic laws, relation properties, graph theorems, counting formulas) is
standard, stable theory cross-checked against GeeksforGeeks and the official GATE CS 2027 Engineering Mathematics syllabus
(unchanged from 2026).