HackWithInfy — Complete Preparation Hub 2026

Official Paper

HackWithInfy 2026 Exam

All 4 official questions from the 2026 HackWithInfy sample paper. Full Java solutions included.

Easy 2026 Food Stamps — Maximum Taste Points

▼

Problem Statement: You have N food types and a meal budget of M meals. Buying food type i for the t-th time gives taste points = v[i] − d[i] × (t−1). You want to maximize the total taste points using at most M meals. You can buy the same food multiple times, but each repeat reduces its value by d[i].

Constraints: 1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁶, 1 ≤ v[i] ≤ 10⁹, 0 ≤ d[i] ≤ 10⁶

Key Insight: This is a greedy problem. At each step, always buy the food that gives the most taste points right now. A Max-Heap (PriorityQueue) lets you always fetch the current best option in O(log N). After picking food i, its next-purchase value = current − d[i], so push this new value back into the heap. Stop early if the top value ≤ 0.

Build-Up: Sub-Problems to Solve First

Step 1

Max Heap Basics

Given an array, repeatedly extract the maximum element k times. → Understand PriorityQueue with custom comparator: new PriorityQueue<>((a,b) -> b-a)

Step 2

Greedy Pick with Replacement

Each pick changes the item's value. After picking item i, reduce v[i] by some delta. → Re-insert the modified item back into the heap.

Step 3

Early Termination

If the heap's top value ≤ 0, further picks only decrease total. → Break early to save time when all remaining options give ≤ 0 taste.

Java — Food Stamps

import java.util.*;

public class FoodStamps {
    // n = number of food types, m = total meal budget
    // v[i] = initial taste of food i, d[i] = decrease per repeat buy
    public static long maxTastePoints(int n, long m, long[] v, long[] d) {

        // Max-Heap stores [currentValue, decrement] sorted by currentValue desc
        PriorityQueue<long[]> heap = new PriorityQueue<>(
            (a, b) -> Long.compare(b[0], a[0])
        );

        // Only add food types with positive initial value
        for (int i = 0; i < n; i++) {
            if (v[i] > 0) heap.offer(new long[]{v[i], d[i]});
        }

        long total = 0;
        for (long meal = 0; meal < m; meal++) {
            if (heap.isEmpty()) break;
            long[] top = heap.poll();
            long curr = top[0], dec = top[1];

            if (curr <= 0) break;     // No more positive taste options

            total += curr;            // Buy this food
            long next = curr - dec;   // Next purchase gives less taste
            if (next > 0) heap.offer(new long[]{next, dec});
        }
        return total;
    }

    public static void main(String[] args) {
        // Test Case: n=3, m=5, v=[5,7,9], d=[2,4,6] → Expected: 27
        System.out.println(maxTastePoints(3, 5,
            new long[]{5,7,9}, new long[]{2,4,6}));
        // Trace: Pick 9→sum=9, Pick 7→16, Pick 5→21, Pick 3→24, Pick 3→27 ✓
    }
}

Step 1 — Initialize Heap: Insert all (v[i], d[i]) pairs into a max-heap keyed by v[i]. Skip foods with v[i] ≤ 0.
Step 2 — Greedy Loop: For each of the M meals, poll the heap top (highest current taste). If top ≤ 0, stop — no benefit in buying more.
Step 3 — Re-insert: After picking food i, its next value = curr - dec. If next > 0, push it back. Otherwise discard it.
Step 4 — Accumulate: Add the picked value to total. Return total after all M picks.

TimeO(M log N)

SpaceO(N)

Medium 2026 MSS with Swaps — Max Subarray Sum After K Swaps

▼

Problem Statement: Given array A of length n (≤ 500) and k swaps, perform at most k swaps between any two elements in the array to maximize the Maximum Subarray Sum (MSS). Note: a "double-swap" (swap and swap back) counts as 2 swaps but nets 0 change — so only useful swaps matter. If k is odd, you can always make 1 net useful swap.

Constraints: 1 ≤ n ≤ 500, 0 ≤ k ≤ 10⁹, |A[i]| ≤ 10⁴

Key Insight: With k ≥ 1 swaps, for any chosen subarray [l..r], we can swap the worst elements inside with the best elements outside. Strategy: Try all O(n²) subarrays. For each subarray, sort the negatives inside and positives outside, then simulate swapping the most negative inside with the most positive outside (up to k swaps). Track the maximum achievable sum.

Step 1

Kadane's Algorithm (k=0 case)

Find MSS with no swaps. O(n) DP. cur = max(0, cur + a[i]); ans = max(ans, cur). This handles the base case perfectly.

Step 2

All Subarrays Brute Force

Enumerate all O(n²) subarrays [l..r]. For each, compute the sum. Used as a building block for k > 0.

Step 3

Optimal Swap Simulation

For subarray [l..r], negatives inside can be swapped with positives outside. Sort both lists and greedily match smallest negative with largest positive outside.

Java — MSS with Swaps

import java.util.*;

public class MSSWithSwaps {

    // Kadane's — used when k=0
    static int kadane(int[] a) {
        int best = 0, cur = 0;
        for (int x : a) { cur = Math.max(0, cur + x); best = Math.max(best, cur); }
        return best;
    }

    public static int solve(int n, int k, int[] a) {
        if (k == 0) return kadane(a);

        int ans = 0;

        // Try every subarray [l..r]
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {

                // Collect negatives inside subarray (sorted ascending)
                List<Integer> inside = new ArrayList<>();
                int subSum = 0;
                for (int i = l; i <= r; i++) {
                    subSum += a[i];
                    if (a[i] < 0) inside.add(a[i]);
                }
                Collections.sort(inside); // Worst negatives first

                // Collect positives outside subarray (sorted descending)
                List<Integer> outside = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    if (i < l || i > r) if (a[i] > 0) outside.add(a[i]);
                }
                outside.sort(Collections.reverseOrder()); // Best positives first

                // Greedily swap: worst inside negative with best outside positive
                int swapped = 0, simSum = subSum;
                for (int s = 0; s < Math.min((long)k, Math.min(inside.size(), outside.size())); s++) {
                    int gain = outside.get(s) - inside.get(s);
                    if (gain <= 0) break; // No benefit
                    simSum += gain;
                }
                ans = Math.max(ans, simSum);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        // k=1, a=[-1, 2, -3, 4, -5] → swap -5 into subarray [2..4], pick [4,2,-1] etc
        System.out.println(solve(5, 1, new int[]{-1,2,-3,4,-5}));
    }
}

Step 1: If k=0, just return Kadane's result.
Step 2: For each O(n²) subarray, compute its sum and find negatives inside + positives outside.
Step 3: Sort negatives ascending (worst first), sort outside positives descending (best first).
Step 4: Greedily swap the worst inside negative with the best outside positive, up to k swaps. Stop if gain ≤ 0.
Step 5: Return the maximum sum seen across all subarrays.

TimeO(n³ log n)

SpaceO(n)

NoteWorks for n ≤ 500

Hard 2026 Lock & Parity — Minimum Even-Cost Pair

▼

Problem Statement: You are given N locks, each with a cost c[i] and a parity type p[i] (0=even, 1=odd). To open a pair of locks (i, j), the cost is c[i] + c[j]. The combined cost must be even (i.e., both locks must have the same parity type: both even OR both odd cost). Find the minimum total cost to open any valid pair. If no valid pair exists, return -1.

Constraints: 2 ≤ N ≤ 10⁵, 1 ≤ c[i] ≤ 10⁹

Key Insight: Cost c[i] + c[j] is even if and only if c[i] and c[j] have the same parity (both even or both odd). So: separate all even-cost locks and odd-cost locks. For each group, find the two minimum-cost elements. Answer is min of (best pair from even group, best pair from odd group).

Step 1

Parity Check

Sum of two numbers is even iff both are even or both are odd. (a+b) % 2 == 0 iff a%2 == b%2. This is the core condition.

Step 2

Partition and Find 2-Minimum

Partition array into two groups. Find the two smallest elements in each group. This is O(n) — no sorting needed, just track min1 and min2.

Step 3

Answer Aggregation

For even group: ans = even_min1 + even_min2. For odd group: ans = odd_min1 + odd_min2. Final answer = min of both. If a group has fewer than 2 elements, skip it.

Java — Lock & Parity

import java.util.*;

public class LockAndParity {

    public static long minEvenPair(int n, long[] c) {

        // Separate into even-cost and odd-cost groups
        List<Long> evens = new ArrayList<>();
        List<Long> odds  = new ArrayList<>();

        for (long cost : c) {
            if (cost % 2 == 0) evens.add(cost);
            else             odds.add(cost);
        }

        long ans = Long.MAX_VALUE;

        // Find 2 minimums from each group → O(n) no sort needed
        for (List<Long> group : Arrays.asList(evens, odds)) {
            if (group.size() < 2) continue;
            long m1 = Long.MAX_VALUE, m2 = Long.MAX_VALUE;
            for (long x : group) {
                if (x <= m1) { m2 = m1; m1 = x; }
                else if (x < m2) { m2 = x; }
            }
            ans = Math.min(ans, m1 + m2);
        }

        return (ans == Long.MAX_VALUE) ? -1 : ans;
    }

    public static void main(String[] args) {
        // Locks: c=[3,6,4,9,2], expected: min even pair = 2+4=6 OR min odd pair = 3+9=12 → ans=6
        System.out.println(minEvenPair(5, new long[]{3,6,4,9,2}));
    }
}

Step 1 — Partition: Split all costs into two lists: even-cost and odd-cost locks.
Step 2 — Two-Min Scan: For each group, find the two smallest values in a single O(n) pass using two variables (m1, m2).
Step 3 — Compare: Candidate answer from even group = m1_even + m2_even. Candidate from odd group = m1_odd + m2_odd.
Step 4 — Return: Answer = min of both candidates. If a group has < 2 elements, it can't form a valid pair.

TimeO(N)

SpaceO(N)

OptimizedO(1) space possible

Complex 2026 Layer-Split Path — DFS with Non-Decreasing Layer Constraint

▼

Problem Statement: Given a tree of N nodes, each node has a "layer" value L[i]. Find the path from root to any leaf such that: (1) Layer values are non-decreasing along the path, (2) The cost of the path is minimized. Cost of a path = sum of (y−x)² for each edge (x,y) where x is parent. Return the minimum cost path with the constraint.

Constraints: 1 ≤ N ≤ 10⁵, layers are integers, tree is rooted at node 1.

Key Insight: DFS from root. Maintain current path cost and current maximum layer seen. At each node, only recurse into children where child_layer ≥ current_max_layer (non-decreasing). Accumulate (child_layer − parent_layer)² as edge cost. Track minimum cost path that reaches a leaf.

Step 1

DFS Tree Traversal

Basic DFS from root with a visited array. Identify when a node is a leaf (no unvisited children).

Step 2

Path with Constraint

DFS with a running maximum. At each step, only go deeper if next value ≥ current max. Classic "non-decreasing path" pattern.

Step 3

Edge Cost Accumulation

Cost = sum of (y−x)² per edge. Track cumulative cost as you recurse. At leaf nodes, update global minimum.

Java — Layer-Split Path

import java.util.*;

public class LayerSplitPath {
    static List<Integer>[] tree;
    static int[] layer;
    static long minCost = Long.MAX_VALUE;

    public static void dfs(int node, int parent, int maxLayer, long cost) {
        boolean isLeaf = true;

        for (int child : tree[node]) {
            if (child == parent) continue;
            isLeaf = false;

            // Non-decreasing layer constraint
            if (layer[child] >= maxLayer) {
                long edgeCost = (long)(layer[child] - layer[node]) * (layer[child] - layer[node]);
                dfs(child, node, layer[child], cost + edgeCost);
            }
        }

        if (isLeaf) {
            minCost = Math.min(minCost, cost);
        }
    }

    public static long solve(int n, int[] L, int[][] edges) {
        tree = new List[n + 1];
        layer = L;
        for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
        for (int[] e : edges) { tree[e[0]].add(e[1]); tree[e[1]].add(e[0]); }
        minCost = Long.MAX_VALUE;
        dfs(1, -1, layer[1], 0);
        return minCost;
    }

    public static void main(String[] args) {
        // Tree: 1-2, 1-3, 2-4. Layers: [0,2,1,3]. Edges: [[1,2],[1,3],[2,4]]
        // Valid paths: 1→2→4 (layers 0,2,3 non-dec, cost=(2-0)²+(3-2)²=4+1=5)
        // Path 1→3 blocked: layer[3]=1 < layer[1]=0... but 1>0 so it's valid actually
        System.out.println(solve(4, new int[]{0,2,1,3},
            new int[][]{{1,2},{1,3},{2,4}}));
    }
}

Step 1: Build adjacency list. Perform DFS from root (node 1).
Step 2: At each node, try all children. Only proceed to child if layer[child] ≥ current max layer seen.
Step 3: Add edge cost (y−x)² when traversing edge from parent layer x to child layer y.
Step 4: At leaf nodes, update global minimum cost. Return minCost after DFS completes.

TimeO(N)

SpaceO(N)

All Years

Previous Year Questions

All official questions from the 2024 and 2025 HackWithInfy sample papers with full Java solutions.

2025 Questions (10)

2024 Questions (3)

Easy 2025 Array Type Queries — Simulation with Prefix Count

▼

Problem: Given an array of N elements, answer Q queries. Each query is of type: "Count elements in range [l, r] that satisfy some condition (e.g., are even, or divisible by k)." Use prefix sum arrays to answer each query in O(1).

Key Insight: Precompute prefix count arrays — one for each query type. prefix[i] = number of qualifying elements in A[0..i-1]. Query [l,r] = prefix[r+1] - prefix[l].

Java — Array Type Queries

public class ArrayTypeQueries {
    public static int[] solve(int[] a, int[][] queries) {
        int n = a.length;
        // prefix[i] = count of even numbers in a[0..i-1]
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++)
            prefix[i+1] = prefix[i] + (a[i] % 2 == 0 ? 1 : 0);

        int[] ans = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int l = queries[q][0], r = queries[q][1];
            ans[q] = prefix[r+1] - prefix[l]; // Count evens in [l,r]
        }
        return ans;
    }
}

BuildO(N)

QueryO(1)

SpaceO(N)

Easy 2025 Good Subarray — Sliding Window with Frequency Map

▼

Problem: A subarray is "good" if all elements in it appear at most k times. Find the number of good subarrays, or find the longest good subarray. Use a sliding window that maintains element frequencies.

Key Insight: Two-pointer / sliding window. Expand right pointer. If any element's count exceeds k, shrink from the left until the window is valid again. Count valid windows.

Java — Good Subarray

import java.util.*;
public class GoodSubarray {
    public static long countGoodSubarrays(int[] a, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        long count = 0;
        int left = 0;
        for (int right = 0; right < a.length; right++) {
            freq.merge(a[right], 1, Integer::sum);
            // Shrink window if element appears more than k times
            while (freq.get(a[right]) > k) {
                freq.merge(a[left], -1, Integer::sum);
                if (freq.get(a[left]) == 0) freq.remove(a[left]);
                left++;
            }
            count += right - left + 1; // All subarrays ending at 'right'
        }
        return count;
    }
}

TimeO(N)

SpaceO(N)

Easy 2025 Oil Tank — Circular Array Prefix Sum

▼

Problem: N gas stations arranged in a circle. Station i has gas[i] litres and costs cost[i] to travel to the next. Find the starting station from which you can complete the full circle. Return -1 if impossible. Classic "Gas Station" problem.

Key Insight: If total gas ≥ total cost, a solution always exists. Start from station 0. Track running "tank". If tank goes negative at station i, reset tank=0 and try starting from i+1. The last chosen start is the answer.

Java — Oil Tank (Gas Station)

public class OilTank {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) { start = i + 1; tank = 0; }
        }
        return totalGas >= totalCost ? start : -1;
    }
}

TimeO(N)

SpaceO(1)

Easy 2025 Reduce Soldiers — BFS Level Processing with HashMap

▼

Problem: An army starts with N soldiers. At each step, soldiers are split: soldiers divisible by 2 go into one group, odd soldiers into another. Process continues until 1 soldier remains. Find number of steps (BFS levels) and total soldiers processed. Similar to "Power of Two" countdown with BFS simulation.

Key Insight: BFS on soldier counts. At each level, split: even count → count/2 (processed immediately), odd count → left in queue. Use a HashMap to avoid re-processing duplicate counts. Total steps = max BFS depth.

Java — Reduce Soldiers

import java.util.*;
public class ReduceSoldiers {
    public static int stepsToOne(int n) {
        // BFS: how many steps to reduce n to 1
        // Each step: n → n/2 if even, n → (n-1)/2 if odd (count the odd one)
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(n); visited.add(n);
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int curr = queue.poll();
                if (curr == 1) return steps;
                // Next states depend on parity
                int[] nexts = (curr % 2 == 0)
                    ? new int[]{curr/2}
                    : new int[]{(curr-1)/2, (curr+1)/2};
                for (int nx : nexts)
                    if (nx >= 1 && visited.add(nx)) queue.offer(nx);
            }
            steps++;
        }
        return steps;
    }
}

TimeO(log N)

SpaceO(log N)

Easy 2025 Invasion Grid — Multi-Source BFS on Matrix

▼

Problem: Given an N×M grid with multiple invasion sources (marked as 'I'). Each turn, invasion spreads to all adjacent cells (up/down/left/right). Find the minimum number of turns for invasion to reach all cells, or find cells that are never reached due to walls ('#').

Key Insight: Multi-Source BFS. Initialize BFS queue with ALL source cells simultaneously. BFS naturally gives minimum distance from the nearest source for every cell. Time = max distance in BFS.

Java — Invasion Grid (Multi-Source BFS)

import java.util.*;
public class InvasionGrid {
    static int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};

    public static int[][] minInvasionTime(char[][] grid) {
        int R = grid.length, C = grid[0].length;
        int[][] dist = new int[R][C];
        for (int[] row : dist) Arrays.fill(row, -1);

        Queue<int[]> q = new LinkedList<>();
        // Add ALL invasion sources to BFS queue at time 0
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (grid[i][j] == 'I') { dist[i][j] = 0; q.offer(new int[]{i, j}); }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : DIRS) {
                int nr = cur[0]+d[0], nc = cur[1]+d[1];
                if (nr>=0 && nr<R && nc>=0 && nc<C && grid[nr][nc]!='#' && dist[nr][nc]==-1) {
                    dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return dist; // dist[i][j] = min turns for invasion to reach (i,j)
    }
}

TimeO(N×M)

SpaceO(N×M)

Medium 2025 Expert Number — Greedy MEX on Sorted Groups

▼

Problem: Given an array, at each step remove the Minimum Excludant (MEX) — the smallest non-negative integer NOT in the array. Do this until the array is empty. Count how many times each integer is removed, and find the total operations.

Key Insight: Sort the array. Group equal elements. The MEX at each step is the smallest missing number. Greedily simulate: maintain a pointer for the current MEX. Count consecutive missing values.

Java — Expert Number (MEX)

import java.util.*;
public class ExpertNumber {
    public static int mexOperations(int[] a) {
        Arrays.sort(a);
        int ops = 0, mex = 0;
        int i = 0;

        while (i < a.length) {
            if (a[i] == mex) {
                // Found an element equal to current MEX — remove it
                i++;
                mex++;
                ops++;
            } else if (a[i] < mex) {
                i++; // Already less than MEX, skip
            } else {
                // a[i] > mex: gap exists, MEX isn't present, wrap around
                mex = 0;
                ops++; // This pass ends with MEX=0 removal (empty round)
            }
        }
        return ops;
    }
}

TimeO(N log N)

SpaceO(1)

Medium 2025 Graph Beauty — BFS on Weighted Graph with State Tracking

▼

Problem: Given an undirected graph where edges have "beauty" values, find the path from source to destination that maximizes the minimum edge beauty (or minimizes the maximum). Classic "bottleneck path" problem.

Key Insight: Binary search on the answer (minimum beauty threshold). For a given threshold T, check if a path exists from source to destination using only edges with beauty ≥ T (BFS/DFS check). Binary search on T to find the maximum feasible threshold.

Java — Graph Beauty (Binary Search + BFS)

import java.util.*;
public class GraphBeauty {
    static List<int[]>[] graph; // [neighbor, beauty]
    static int n;

    static boolean canReach(int src, int dst, int minBeauty) {
        boolean[] visited = new boolean[n+1];
        Queue<Integer> q = new LinkedList<>();
        q.offer(src); visited[src] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == dst) return true;
            for (int[] e : graph[cur])
                if (!visited[e[0]] && e[1] >= minBeauty) {
                    visited[e[0]] = true; q.offer(e[0]);
                }
        }
        return false;
    }

    public static int maxBottleneck(int src, int dst, int[] beautyVals) {
        Arrays.sort(beautyVals);
        int lo = 0, hi = beautyVals.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (canReach(src, dst, beautyVals[mid])) { ans = beautyVals[mid]; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }
}

TimeO((V+E) log E)

SpaceO(V+E)

Medium 2025 Circular Chairs — Circular BFS with Modular Indexing

▼

Problem: N chairs arranged in a circle. Some chairs have people. At each second, people move: each person sitting on an empty chair can move to an adjacent chair. Find after T seconds, how many people are in each chair, or which chairs are occupied. Classic circular BFS/simulation.

Key Insight: Model as BFS where sources are all initially occupied chairs. BFS level = time. Use modular arithmetic for circular movement: next = (i+1)%N, prev = (i-1+N)%N. Multi-source BFS gives min time for each chair.

Java — Circular Chairs

import java.util.*;
public class CircularChairs {
    public static int[] minTimeToReach(int n, boolean[] occupied) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++)
            if (occupied[i]) { dist[i] = 0; q.offer(i); }

        while (!q.isEmpty()) {
            int cur = q.poll();
            int[] nexts = {(cur+1)%n, (cur-1+n)%n};
            for (int nx : nexts)
                if (dist[nx] == Integer.MAX_VALUE) {
                    dist[nx] = dist[cur] + 1;
                    q.offer(nx);
                }
        }
        return dist; // dist[i] = min steps for any person to reach chair i
    }
}

TimeO(N)

SpaceO(N)

Medium 2025 XOR Partition — Prefix XOR with HashMap

▼

Problem: Given an array, partition it into the minimum number of subarrays where each subarray's XOR equals a target value T. Return the minimum number of partitions, or -1 if impossible.

Key Insight: Compute prefix XOR. A partition ends at index r if prefixXOR[r] = (number_of_partitions × T). Greedily: when prefix XOR matches the target multiple, finalize a partition. This gives O(n) greedy solution.

Java — XOR Partition

public class XORPartition {
    public static int minPartitions(int[] a, int target) {
        int xorSoFar = 0, parts = 0;
        int runTarget = target;

        for (int x : a) {
            xorSoFar ^= x;
            if (xorSoFar == runTarget) {
                // End of a valid partition
                parts++;
                xorSoFar = 0; // Reset for next segment
            }
        }
        // Valid if all elements are covered (xorSoFar == 0 at end)
        return (xorSoFar == 0) ? parts : -1;
    }
    // Note: Also check if total XOR == target → if yes, partition into single subarray
}

TimeO(N)

SpaceO(1)

Hard 2025 Min-K Longest Path — Binary Search on Answer + DP

▼

Problem: Given a DAG (Directed Acyclic Graph) with weighted edges, find the longest path that uses at most K edges with weight ≥ some threshold T. Binary search on T; for each T, run DP to find longest path using only edges with weight ≥ T.

Key Insight: Binary search on T (the minimum edge weight). For each T, do topological DP: dp[node] = longest path ending at node using only edges with weight ≥ T. Binary search halves the search space. Total: O(n² log n).

Java — Min-K Longest Path

import java.util.*;
public class MinKLongestPath {
    static int n;
    static int[][] adjMatrix; // adjMatrix[u][v] = weight, -1 if no edge

    static int longestPathWithThreshold(int T) {
        int[] dp = new int[n];
        int ans = 0;
        // Process nodes in topological order (assumed 0..n-1)
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (adjMatrix[u][v] >= T) {
                    dp[v] = Math.max(dp[v], dp[u] + 1);
                    ans = Math.max(ans, dp[v]);
                }
            }
        }
        return ans;
    }

    public static int solve(int k, int[] weights) {
        int[] sorted = weights.clone(); Arrays.sort(sorted);
        int lo = 0, hi = sorted.length - 1, ans = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (longestPathWithThreshold(sorted[mid]) >= k) {
                ans = sorted[mid]; lo = mid + 1;
            } else hi = mid - 1;
        }
        return ans;
    }
}

TimeO(n² log n)

SpaceO(n)

Easy 2024 Array AP Queries — Reverse Processing with Difference Array

▼

Problem: Given an array and Q queries, each query adds an Arithmetic Progression to a subrange [l, r]: add values a, a+d, a+2d, ... to positions l through r. Answer all queries, then print the final array. Use a difference array technique extended for APs.

Key Insight: Standard difference array handles range-add of a constant. For AP, use a second-order difference array: D1[l]+=a, D1[r+1]-=(a+len*d), D2[l]+=d, D2[r+1]-=d. Apply two prefix sum passes to reconstruct the array.

Java — Array AP Queries

public class ArrayAPQueries {
    public static long[] solve(int n, int[][] queries) {
        long[] D1 = new long[n + 2];
        long[] D2 = new long[n + 2];

        for (int[] q : queries) {
            int l = q[0], r = q[1];
            long a = q[2], d = q[3]; // AP: a, a+d, a+2d, ...
            int len = r - l + 1;
            D1[l] += a;     D1[r+1] -= (a + (long)len * d);
            D2[l] += d;     D2[r+1] -= d;
        }

        // Reconstruct: two prefix sum passes
        long[] res = new long[n];
        long val = 0, inc = 0;
        for (int i = 0; i < n; i++) {
            inc += D2[i];
            val += D1[i] + inc;
            res[i] = val;
        }
        return res;
    }
}

BuildO(Q)

ReconstructO(N)

SpaceO(N)

Medium 2024 3D XYZ DP — Three-Dimensional State Dynamic Programming

▼

Problem: Given a 3D grid of size N×N×N, you start at (0,0,0) and want to reach (N-1, N-1, N-1). You can only move in +x, +y, +z directions. Each cell has a value. Find the path with maximum sum. Classic 3D grid DP.

Key Insight: dp[x][y][z] = max path sum to reach (x,y,z). Transition: dp[x][y][z] = grid[x][y][z] + max(dp[x-1][y][z], dp[x][y-1][z], dp[x][y][z-1]). Fill in order of increasing x, y, z.

Java — 3D XYZ DP

public class ThreeDXYZDP {
    public static long maxPathSum(int n, int[][][] grid) {
        long[][][] dp = new long[n][n][n];

        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                for (int z = 0; z < n; z++) {
                    long best = Long.MIN_VALUE;
                    if (x==0 && y==0 && z==0) { dp[0][0][0] = grid[0][0][0]; continue; }
                    if (x > 0) best = Math.max(best, dp[x-1][y][z]);
                    if (y > 0) best = Math.max(best, dp[x][y-1][z]);
                    if (z > 0) best = Math.max(best, dp[x][y][z-1]);
                    dp[x][y][z] = best + grid[x][y][z];
                }
            }
        }
        return dp[n-1][n-1][n-1];
    }
}

TimeO(N³)

SpaceO(N³)

Hard 2024 Tree Beautiful Set — DFS with Subtree Count DP

▼

Problem: Given a tree of N nodes, a "beautiful set" is a subset of nodes such that for any two nodes u, v in the set, the path between them passes through at least one other node in the set. Find the maximum size beautiful set.

Key Insight: A beautiful set = a connected subtree. The maximum beautiful set is the maximum connected induced subgraph. Use tree DP: dp[node] = max beautiful set size in the subtree rooted at node. Merge children greedily.

Java — Tree Beautiful Set

import java.util.*;
public class TreeBeautifulSet {
    static List<Integer>[] tree;
    static int[] val;  // node values
    static int ans = 0;

    static int dfs(int node, int par) {
        int maxFromChild = 0;
        for (int child : tree[node]) {
            if (child == par) continue;
            int childBest = dfs(child, node);
            // Update answer: path through this node using best two child subtrees
            ans = Math.max(ans, maxFromChild + childBest + 1);
            maxFromChild = Math.max(maxFromChild, childBest);
        }
        ans = Math.max(ans, maxFromChild + 1);
        return maxFromChild + 1; // Best chain including this node
    }

    public static int solve(int n, int[][] edges) {
        tree = new List[n + 1];
        for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
        for (int[] e : edges) { tree[e[0]].add(e[1]); tree[e[1]].add(e[0]); }
        ans = 1;
        dfs(1, -1);
        return ans;
    }
}

TimeO(N)

SpaceO(N)

Practice Test

Mock Exam — Test Yourself

3 fresh questions in authentic HackWithInfy style. Set a 3-hour timer. Try each before expanding the solution.

Exam Simulation Rules: Easy = max 30 min → Medium = max 60 min → Hard = max 90 min. No copy-paste. Write all code by hand. Read the problem twice before coding. Always check edge cases: empty input, single element, all-negative arrays, INT_MAX overflow.

Easy Mock Staircase Steps — Count Ways to Climb (Fibonacci DP)

▼

Problem: You are at the bottom of a staircase with N steps. You can climb 1 or 2 steps at a time. Count the total number of distinct ways to reach the top. For large N (up to 10⁶), answer modulo 10⁹+7.

Sample: N=4 → Ways: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2) = 5 ways.
Constraints: 1 ≤ N ≤ 10⁶

Think First: Notice ways(N) = ways(N-1) + ways(N-2) — it's Fibonacci! Base: ways(1)=1, ways(2)=2.

Java — Staircase Steps

public class StaircaseSteps {
    static final int MOD = 1_000_000_007;

    public static long countWays(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        // Space-optimized: only need last two values
        long prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            long curr = (prev1 + prev2) % MOD;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println(countWays(4));  // 5
        System.out.println(countWays(10)); // 89
        System.out.println(countWays(1000000)); // Very large, mod applied
    }
}

Recurrence: ways(n) = ways(n-1) + ways(n-2) — either last step was 1 or 2.
Space Optimization: Only store last 2 values instead of full dp array → O(1) space.
Modulo: Apply modulo at each step to prevent integer overflow.

TimeO(N)

SpaceO(1)

Medium Mock Minimum Platforms — Interval Scheduling with Sorting

▼

Problem: You are given arrival times and departure times of N trains at a railway station. Find the minimum number of platforms required so that no train waits. Each platform can hold one train at a time.

Sample: arrivals=[900,940,950,1100,1500,1800], departures=[910,1200,1120,1130,1900,2000] → Answer: 3
Constraints: 1 ≤ N ≤ 10⁶, times in HHMM format.

Think First: Sort arrival and departure separately. Two-pointer sweep: when next arrival comes before earliest departure, need a new platform. Classic interval scheduling.

Java — Minimum Platforms

import java.util.*;
public class MinimumPlatforms {
    public static int findPlatforms(int[] arr, int[] dep) {
        Arrays.sort(arr);
        Arrays.sort(dep);

        int platforms = 1, maxPlatforms = 1;
        int i = 1, j = 0;  // i = arrival pointer, j = departure pointer

        while (i < arr.length && j < dep.length) {
            if (arr[i] <= dep[j]) {
                // A train arrives before earliest departure — need new platform
                platforms++;
                i++;
            } else {
                // A train departs before next arrival — platform freed
                platforms--;
                j++;
            }
            maxPlatforms = Math.max(maxPlatforms, platforms);
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arr = {900,940,950,1100,1500,1800};
        int[] dep = {910,1200,1120,1130,1900,2000};
        System.out.println(findPlatforms(arr, dep)); // 3
    }
}

Step 1: Sort both arrival and departure arrays independently.
Step 2: Use two pointers i (arrivals), j (departures). Start with 1 platform.
Step 3: If arr[i] ≤ dep[j]: new train arrives before earliest leaves → need +1 platform. Else: dep[j] < arr[i] → train leaves, free platform.
Step 4: Track max platforms seen. This is the answer.

TimeO(N log N)

SpaceO(1)

Hard Mock Word Ladder — BFS on Word Graph (Shortest Transformation Sequence)

▼

Problem: Given beginWord, endWord, and a wordList, find the length of the shortest transformation sequence from beginWord to endWord such that: (1) Each step, change exactly one character, (2) Every intermediate word must be in wordList. Return 0 if no such sequence exists.

Sample: begin="hit", end="cog", list=["hot","dot","dog","lot","log","cog"] → Answer: 5 (hit→hot→dot→dog→cog)
Constraints: 1 ≤ wordLen ≤ 10, 1 ≤ wordList.size ≤ 5000

Think First: Model as a graph: nodes = words, edges = words differing by 1 char. BFS gives shortest path. Optimization: instead of comparing all word pairs, try all 26 letter substitutions at each position.

Java — Word Ladder (BFS)

import java.util.*;
public class WordLadder {
    public static int ladderLength(String begin, String end, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(end)) return 0;

        Queue<String> q = new LinkedList<>();
        q.offer(begin);
        int steps = 1;

        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                String curr = q.poll();
                char[] chars = curr.toCharArray();

                for (int i = 0; i < chars.length; i++) {
                    char orig = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        chars[i] = c;
                        String next = new String(chars);
                        if (next.equals(end)) return steps + 1;
                        if (wordSet.remove(next)) q.offer(next);
                    }
                    chars[i] = orig; // Restore
                }
            }
            steps++;
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(ladderLength("hit", "cog",
            Arrays.asList("hot","dot","dog","lot","log","cog"))); // 5
    }
}

Step 1: Put wordList into a HashSet for O(1) lookup and removal.
Step 2: BFS from beginWord. At each level (step), try changing each character position to 'a'-'z'.
Step 3: If the new word is in the set, add it to queue. Remove from set to avoid revisiting.
Step 4: If new word == endWord, return current step count + 1. If queue empties, return 0.
Key Trick: Remove from set instead of using visited[] — faster and cleaner.

TimeO(N × L × 26)

SpaceO(N × L)

N=words, L=word length

Core Concepts

DSA Guide — 14 Essential Topics

Every topic has a concept explanation, a representative problem, and a complete Java solution. Study these in roadmap order.

Quick Complexity Reference:

Algorithm	Time	Space	Use Case
Binary Search	O(log N)	O(1)	Sorted array queries
BFS/DFS	O(V+E)	O(V)	Graph traversal
Dijkstra	O((V+E) log V)	O(V)	Shortest path weighted
Merge Sort	O(N log N)	O(N)	Stable sort, inversions
Kadane's	O(N)	O(1)	Max subarray sum
Sliding Window	O(N)	O(1)-O(N)	Contiguous subarrays
Heap (PQ)	O(N log N)	O(N)	K-th smallest/largest
Union-Find	O(N α(N))	O(N)	Connected components
Segment Tree	O(N) build, O(log N) query	O(N)	Range queries
Trie	O(L) per op	O(N×L)	String prefix search
LCS/LIS	O(N²) or O(N log N)	O(N)	Sequence DP
Tree DP	O(N)	O(N)	Tree path problems

1. Prefix Sum & Difference Array

▼

Concept

Prefix Sum: pre[i] = A[0] + A[1] + ... + A[i]. Range sum query [l,r] = pre[r] - pre[l-1] in O(1).
Difference Array: D[i] = A[i] - A[i-1]. Range update [l,r] by +k → D[l]+=k, D[r+1]-=k. Reconstruct with prefix sum. Turns O(n) per update into O(1) per update, O(n) final reconstruction.

Representative Problem: Given array A and Q range-add queries, find the final array.

Java — Difference Array Range Update

public class DiffArray {
    public static int[] rangeUpdates(int n, int[][] updates) {
        int[] diff = new int[n + 1];
        for (int[] u : updates) { // [l, r, val]
            diff[u[0]] += u[2];
            if (u[1] + 1 <= n) diff[u[1] + 1] -= u[2];
        }
        // Prefix sum to reconstruct final array
        for (int i = 1; i < n; i++) diff[i] += diff[i-1];
        return diff;
    }
}

UpdateO(1)

BuildO(N+Q)

🪟

2. Sliding Window — Two Pointers

▼

Concept

Maintain a window [left, right]. Expand right to include elements. Shrink from left when a constraint is violated. The window always represents a valid state. Used for: longest subarray with sum ≤ K, max length with at most K distinct characters, minimum window substring.

Problem: Longest subarray with sum ≤ K.

Java — Sliding Window Max Length

public class SlidingWindow {
    public static int longestSubarrayWithSumK(int[] a, int k) {
        int left = 0, sum = 0, maxLen = 0;
        for (int right = 0; right < a.length; right++) {
            sum += a[right];
            while (sum > k && left <= right) sum -= a[left++];
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

TimeO(N)

SpaceO(1)

⟺

3. Binary Search — On Answer

▼

Concept

"Binary Search on Answer" pattern: when the answer lies in a monotonic range and you can check feasibility in O(f(n)), binary search the answer. Common problems: "minimize maximum", "maximize minimum", "find smallest K such that condition holds".

Problem: Split N books of chapters into K groups. Minimize the maximum sum in any group (Painter's Partition).

Java — Binary Search on Answer (Painter's Partition)

public class PaintersPartition {
    static boolean feasible(int[] books, int k, long maxWork) {
        int painters = 1; long curr = 0;
        for (int b : books) {
            if (curr + b > maxWork) { painters++; curr = b; }
            else curr += b;
        }
        return painters <= k;
    }

    public static long minTime(int[] books, int k) {
        long lo = 0, hi = 0;
        for (int b : books) { lo = Math.max(lo, b); hi += b; }
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            if (feasible(books, k, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

TimeO(N log(sum))

SpaceO(1)

🕸

4. BFS & DFS — Graph Traversal Patterns

▼

Concept

BFS (Queue): Explores level by level. Gives shortest path in unweighted graphs. Use when: minimum steps, nearest cell, flood fill.
DFS (Stack/Recursion): Goes deep before backtracking. Use when: cycle detection, connected components, topological sort, tree paths.
Multi-source BFS: Add all sources to queue at time=0. Automatically gives min distance from ANY source.

Problem: 0/1 Matrix — find distance of each cell from nearest 0.

Java — 01 Matrix Multi-Source BFS

import java.util.*;
public class ZeroOneMatrix {
    public static int[][] updateMatrix(int[][] mat) {
        int R = mat.length, C = mat[0].length;
        int[][] dist = new int[R][C];
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (mat[i][j] == 0) q.offer(new int[]{i,j});
                else dist[i][j] = Integer.MAX_VALUE;
        int[][] d = {{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] dir : d) {
                int r=cur[0]+dir[0], c=cur[1]+dir[1];
                if (r>=0&&r<R&&c>=0&&c<C && dist[r][c]>dist[cur[0]][cur[1]]+1) {
                    dist[r][c] = dist[cur[0]][cur[1]] + 1;
                    q.offer(new int[]{r,c});
                }
            }
        }
        return dist;
    }
}

TimeO(R×C)

SpaceO(R×C)

△

5. Heap / Priority Queue — Top K & Greedy

▼

Concept

A heap is a complete binary tree. Min-Heap: parent ≤ children (Java PriorityQueue default). Max-Heap: parent ≥ children (use reverse comparator). Insert/Delete: O(log N). Peek (min/max): O(1). Key patterns: K largest elements (use min-heap of size K), K smallest (max-heap), merge K sorted lists, median of stream.

Problem: Find median from a data stream.

Java — Median Finder (Two Heaps)

import java.util.*;
public class MedianFinder {
    PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder()); // max-heap (lower half)
    PriorityQueue<Integer> large = new PriorityQueue<>(); // min-heap (upper half)

    public void addNum(int num) {
        small.offer(num);
        large.offer(small.poll()); // Balance: max of small goes to large
        if (small.size() < large.size())
            small.offer(large.poll()); // Keep small size >= large size
    }

    public double findMedian() {
        if (small.size() > large.size()) return small.peek();
        return (small.peek() + large.peek()) / 2.0;
    }
}

AddO(log N)

MedianO(1)

⬛

6. Dynamic Programming — Tabulation & Memoization

▼

Concept

DP solves problems with overlapping subproblems and optimal substructure. Two approaches:
Top-down (Memoization): Recursion + cache results. Easier to write.
Bottom-up (Tabulation): Fill a table iteratively. Better for space optimization.
Classic problems: 0/1 Knapsack, LCS, LIS, Coin Change, Edit Distance, Partition DP.

Problem: Longest Increasing Subsequence (LIS) in O(N log N).

Java — LIS in O(N log N) with Patience Sorting

import java.util.*;
public class LIS {
    public static int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int num : nums) {
            // Binary search: find first tail >= num
            int lo = 0, hi = tails.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails.get(mid) < num) lo = mid + 1;
                else hi = mid;
            }
            if (lo == tails.size()) tails.add(num);
            else tails.set(lo, num); // Replace to keep tails as small as possible
        }
        return tails.size();
    }
}

TimeO(N log N)

SpaceO(N)

∪

7. Union-Find (DSU) — Disjoint Set Union

▼

Concept

DSU tracks which elements belong to the same set. Two operations: find(x) = root of x's set, union(x,y) = merge x and y's sets. Optimizations: Path Compression (flatten tree in find), Union by Rank (attach smaller tree under larger). With both: nearly O(1) per operation.

Problem: Number of connected components in an undirected graph.

Java — DSU with Path Compression + Union by Rank

public class DSU {
    int[] parent, rank;

    DSU(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // Path compression
        return parent[x];
    }

    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false; // Already same set
        if (rank[rx] < rank[ry]) { int t=rx; rx=ry; ry=t; }
        parent[ry] = rx; // Union by rank
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }

    public static int countComponents(int n, int[][] edges) {
        DSU dsu = new DSU(n);
        int components = n;
        for (int[] e : edges)
            if (dsu.union(e[0], e[1])) components--;
        return components;
    }
}

TimeO(α(N)) per op

SpaceO(N)

🌲

8. Segment Tree — Range Queries with Point Updates

▼

Concept

Segment tree divides an array into segments. Each node stores aggregate (sum/min/max) of a range. Build: O(N). Query range [l,r]: O(log N). Update a point: O(log N). The tree is stored as an array: node i → children 2i and 2i+1. Leaf nodes are individual elements.

Problem: Range sum queries with point updates.

Java — Segment Tree (Sum)

public class SegTree {
    int[] tree;
    int n;

    SegTree(int[] arr) {
        n = arr.length; tree = new int[4*n];
        build(arr, 1, 0, n-1);
    }

    void build(int[] arr, int node, int s, int e) {
        if (s == e) { tree[node] = arr[s]; return; }
        int m = (s+e)/2;
        build(arr, 2*node, s, m);
        build(arr, 2*node+1, m+1, e);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    void update(int node, int s, int e, int idx, int val) {
        if (s == e) { tree[node] = val; return; }
        int m = (s+e)/2;
        if (idx <= m) update(2*node, s, m, idx, val);
        else update(2*node+1, m+1, e, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    int query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return 0; // Out of range
        if (l <= s && e <= r) return tree[node]; // Fully covered
        int m = (s+e)/2;
        return query(2*node, s, m, l, r) + query(2*node+1, m+1, e, l, r);
    }
}

BuildO(N)

QueryO(log N)

UpdateO(log N)

🌿

9. Tree DP — Rerooting & Subtree Aggregation

▼

Concept

Tree DP computes values bottom-up (leaves → root). Each node's answer depends on its children's computed values. Key patterns: maximum path sum in tree (diameter), max independent set on tree, counting paths with property. "Rerooting" technique: first DFS downward, then DFS upward to aggregate from parent's direction too.

Problem: Diameter of a tree (longest path between any two nodes).

Java — Tree Diameter (DFS DP)

import java.util.*;
public class TreeDiameter {
    static List<Integer>[] adj;
    static int diameter = 0;

    static int dfs(int u, int par) {
        int maxDepth = 0, secondMax = 0;
        for (int v : adj[u]) {
            if (v == par) continue;
            int depth = dfs(v, u) + 1;
            if (depth >= maxDepth) { secondMax = maxDepth; maxDepth = depth; }
            else if (depth > secondMax) secondMax = depth;
        }
        // Path through node u: maxDepth + secondMax (or just maxDepth if leaf)
        diameter = Math.max(diameter, maxDepth + secondMax);
        return maxDepth;
    }
}

TimeO(N)

SpaceO(N)

10. Trie — Prefix Tree for String Problems

▼

Concept

Trie is a tree where each path from root to a node represents a string prefix. Each node has up to 26 children (for lowercase letters). Insert a word: O(L). Search a prefix: O(L). Used for: autocomplete, longest common prefix, word search, XOR maximization (binary trie).

Java — Trie Implementation

public class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd;

    public void insert(String word) {
        Trie cur = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) cur.children[idx] = new Trie();
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }

    public boolean startsWith(String prefix) {
        Trie cur = this;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) return false;
            cur = cur.children[idx];
        }
        return true;
    }
}

InsertO(L)

SearchO(L)

SpaceO(N×L)

11. Kadane's Algorithm — Maximum Subarray Variants

▼

Concept

Kadane's finds maximum subarray sum in O(N). Key recurrence: cur = max(cur + a[i], a[i]). If cur goes negative, start fresh. Variants: maximum subarray product (track both max and min — negatives matter), maximum sum circular subarray (total sum − minimum subarray sum), max subarray with at most K elements.

Java — Kadane's + Circular Variant

public class Kadane {
    public static int maxSubarraySum(int[] a) {
        int maxSoFar = a[0], cur = a[0];
        for (int i = 1; i < a.length; i++) {
            cur = Math.max(a[i], cur + a[i]);
            maxSoFar = Math.max(maxSoFar, cur);
        }
        return maxSoFar;
    }

    // Circular variant: max of (normal Kadane) vs (total − minSubarray)
    public static int maxCircularSubarray(int[] a) {
        int total = 0, maxSum = a[0], minSum = a[0], curMax = 0, curMin = 0;
        for (int x : a) {
            curMax = Math.max(curMax + x, x); maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + x, x); minSum = Math.min(minSum, curMin);
            total += x;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

TimeO(N)

SpaceO(1)

📚

12. Monotonic Stack — Next Greater / Smaller Element

▼

Concept

Monotonic Stack maintains elements in increasing or decreasing order. When you push a new element, pop all elements it "dominates". Next Greater Element: maintain decreasing stack. Next Smaller: increasing stack. Applications: histogram max rectangle, daily temperatures, stock span, trapping rain water.

Java — Largest Rectangle in Histogram

import java.util.*;
public class LargestRectangle {
    public static int largestArea(int[] h) {
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        for (int i = 0; i <= h.length; i++) {
            int currH = (i == h.length) ? 0 : h[i];
            while (!stack.isEmpty() && h[stack.peek()] > currH) {
                int height = h[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

TimeO(N)

SpaceO(N)

⇒

13. Dijkstra's Algorithm — Shortest Path in Weighted Graph

▼

Concept

Dijkstra finds shortest path from source to all nodes in a non-negative weighted graph. Uses a min-heap to always process the node with smallest known distance. dist[u] = min weight from source to u. Relaxation: if dist[u] + w(u,v) < dist[v], update dist[v].

Java — Dijkstra's Algorithm

import java.util.*;
public class Dijkstra {
    public static long[] shortestPath(int n, List<int[]>[] graph, int src) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a,b) -> Long.compare(a[0],b[0]));
        pq.offer(new long[]{0, src});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0]; int u = (int)cur[1];
            if (d > dist[u]) continue; // Outdated entry
            for (int[] edge : graph[u]) {
                int v = edge[0]; long w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

TimeO((V+E) log V)

SpaceO(V+E)

↩

14. Backtracking — Permutations, Combinations, N-Queens

▼

Concept

Backtracking builds a solution incrementally. At each step, try all valid options. If stuck, undo the last choice (backtrack) and try another. Key template: choose → explore → unchoose. Pruning (early termination) makes it efficient. Common use: all subsets, permutations, N-Queens, Sudoku solver, word search in grid.

Problem: Generate all subsets (power set) of an array.

Java — All Subsets (Backtracking)

import java.util.*;
public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    static void backtrack(int[] nums, int start,
            List<Integer> curr, List<List<Integer>> result) {
        result.add(new ArrayList<>(curr)); // Record current state
        for (int i = start; i < nums.length; i++) {
            curr.add(nums[i]);                      // Choose
            backtrack(nums, i + 1, curr, result); // Explore
            curr.remove(curr.size() - 1);          // Unchoose (backtrack)
        }
    }
}

TimeO(2ᴺ × N)

SpaceO(N)

Interview Prep

Theoretical Questions & Answers

50+ commonly asked theoretical questions in technical rounds. Know these concepts cold.

DSA Concepts

Java & OOPs

System Design

Databases

OS & Networks

What is the difference between Array and ArrayList in Java?

▼

Answer:

Array: Fixed size, homogeneous elements, can store primitives and objects, faster access O(1), memory efficient
ArrayList: Dynamic size (grows automatically), only objects (autoboxing for primitives), slower due to resizing overhead, provides built-in methods
Array uses [] syntax; ArrayList is part of Collections framework with methods like add(), remove(), get()

Explain Time Complexity and Space Complexity with examples.

▼

Answer:
Time Complexity: Measures how runtime grows with input size n.
- O(1): Constant time (array access)
- O(log n): Logarithmic (binary search)
- O(n): Linear (single loop)
- O(n log n): Linearithmic (merge sort)
- O(n²): Quadratic (nested loops)

Space Complexity: Measures extra memory used.
- O(1): In-place algorithms
- O(n): Requires auxiliary array
- O(log n): Recursion stack depth

What is the difference between Stack and Queue?

▼

Answer:
Stack: LIFO (Last In First Out). Operations: push(), pop(), peek(). Used for: function calls, expression evaluation, undo operations, DFS.

Queue: FIFO (First In First Out). Operations: enqueue(), dequeue(), front(). Used for: BFS, task scheduling, print spooling, caching.

Variants: Priority Queue (ordered by priority), Deque (double-ended queue for both ends).

Explain Binary Search and when to use it.

▼

Answer:
Binary Search finds an element in a sorted array by repeatedly dividing the search interval in half.

Algorithm:
1. Compare target with middle element
2. If equal, return index
3. If target < middle, search left half
4. If target > middle, search right half
5. Repeat until found or interval is empty

Time: O(log n) | Space: O(1) iterative, O(log n) recursive

Use when: Array is sorted, need O(log n) lookup, doing "binary search on answer" problems.

What is the difference between BFS and DFS?

▼

Answer:
BFS (Breadth First Search):
- Uses Queue, explores level by level
- Finds shortest path in unweighted graphs
- More memory (stores all nodes at current level)
- Use for: shortest path, connected components, level-order traversal

DFS (Depth First Search):
- Uses Stack (or recursion), explores depth first
- Less memory (only stores path to current node)
- May not find shortest path
- Use for: cycle detection, topological sort, maze solving, tree traversals

Explain Dynamic Programming (DP) with an example.

▼

Answer:
DP solves problems with overlapping subproblems and optimal substructure by storing solutions to subproblems to avoid recomputation.

Two approaches:
1. Top-down (Memoization): Recursion + cache. Easier to implement.
2. Bottom-up (Tabulation): Iterative table filling. Better space optimization.

Example — Fibonacci:
- Naive: O(2ⁿ) time
- DP: O(n) time, O(1) space with space optimization

Common DP patterns: 0/1 Knapsack, Unbounded Knapsack, LCS, LIS, Matrix Chain, Edit Distance

What is a HashMap and how does it work internally?

▼

Answer:
HashMap stores key-value pairs using a hash table data structure.

Internal Working:
1. Hashing: key.hashCode() determines bucket index (index = hash & (n-1))
2. Collision Handling: Separate chaining (linked list at each bucket)
3. Java 8+: Linked list converts to Red-Black Tree when size > 8 for O(log n) lookup
4. Load Factor: Default 0.75 — triggers rehashing when exceeded
5. Rehashing: Doubles capacity and redistributes entries

Time: O(1) average for get/put, O(n) worst case (all collisions)
Space: O(n) where n = number of entries

What is the difference between Tree and Graph?

▼

Answer:
Tree:
- Hierarchical structure with one root
- No cycles, exactly n-1 edges for n nodes
- Connected and acyclic
- One unique path between any two nodes

Graph:
- Network structure, can have multiple components
- Can have cycles
- May or may not be connected
- Multiple paths possible between nodes

Types: Directed/Undirected, Weighted/Unweighted, Cyclic/Acyclic, Connected/Disconnected

Explain Quick Sort and Merge Sort. Compare them.

▼

Answer:
Quick Sort:
- Divide and conquer with pivot element
- Partition array around pivot
- Recursively sort subarrays
- Time: O(n log n) avg, O(n²) worst
- Space: O(log n) stack
- In-place: Yes, Stable: No

Merge Sort:
- Divide array into halves recursively
- Merge sorted halves
- Time: O(n log n) always
- Space: O(n) auxiliary
- In-place: No, Stable: Yes

When to use: Quick Sort for arrays (cache friendly), Merge Sort for linked lists and external sorting.

Q10

What is a Trie and what are its applications?

▼

Answer:
Trie (Prefix Tree) is a tree-based data structure for efficient storage and retrieval of strings.

Structure:
- Each node represents a character
- Path from root to node forms a prefix
- End of word marked with flag

Operations:
- Insert: O(L) where L = word length
- Search: O(L)
- Prefix search: O(L)

Applications:
- Autocomplete/suggestions
- Spell checking
- IP routing (longest prefix match)
- Word games (Boggle solver)
- XOR maximization problems (binary trie)

Q11

Explain the four pillars of OOPs.

▼

Answer:
1. Encapsulation: Bundling data and methods together, hiding internal details using private access modifiers. Provides data security.

2. Inheritance: Child class inherits properties and methods from parent class. Promotes code reusability (extends keyword).

3. Polymorphism: Same method behaves differently based on object. Types: Compile-time (method overloading), Runtime (method overriding).

4. Abstraction: Hiding implementation details, showing only essential features. Achieved via abstract classes and interfaces.

Q12

What is the difference between Abstract Class and Interface?

▼

Answer:
Abstract Class:
- Can have both abstract and concrete methods
- Can have instance variables
- Single inheritance (extends one class)
- Can have constructors
- Use when classes share common code

Interface:
- All methods abstract (Java 8+: default/static methods allowed)
- Only constants (public static final)
- Multiple inheritance (implements multiple interfaces)
- No constructors
- Use for defining contracts/capabilities

Java 8+: Interfaces can have default and static methods with implementations.

Q13

Explain Method Overloading vs Method Overriding.

▼

Answer:
Method Overloading (Compile-time polymorphism):
- Same method name, different parameters (type/number/order)
- Within same class
- Return type can differ
- Example: add(int, int), add(double, double), add(int, int, int)

Method Overriding (Runtime polymorphism):
- Same method signature in parent and child
- Child provides specific implementation
- Requires inheritance (@Override annotation)
- Cannot reduce visibility (public → private not allowed)
- Example: toString(), equals() overridden in custom classes

Q14

What is the difference between == and equals() in Java?

▼

Answer:
== operator:
- For primitives: compares values
- For objects: compares memory addresses (reference equality)
- "hello" == "hello" → true (string pool)
- new String("hello") == "hello" → false

equals() method:
- Compares content/value equality
- Default implementation in Object class uses ==
- Should be overridden for meaningful comparison
- String class overrides to compare character by character

Best Practice: Always override equals() and hashCode() together for custom classes.

Q15

Explain the Java Collections Framework hierarchy.

▼

Answer:
Core Interfaces:
- Collection: Root interface (List, Set, Queue)
- List: Ordered, allows duplicates (ArrayList, LinkedList, Vector)
- Set: No duplicates (HashSet, LinkedHashSet, TreeSet)
- Queue: FIFO (PriorityQueue, LinkedList)
- Map: Key-value pairs (HashMap, TreeMap, LinkedHashMap)

Key Implementations:
- ArrayList: Dynamic array, O(1) get, O(n) insert/delete middle
- LinkedList: Doubly linked list, O(1) insert/delete, O(n) get
- HashMap: Hash table, O(1) avg operations
- TreeMap: Red-Black tree, O(log n) operations, sorted

Q16

What is the difference between String, StringBuilder, and StringBuffer?

▼

Answer:
String:
- Immutable (cannot be modified after creation)
- Stored in String Pool for memory efficiency
- Thread-safe by default
- Use for constant strings

StringBuilder:
- Mutable, not synchronized
- Faster than StringBuffer
- Use in single-threaded environments

StringBuffer:
- Mutable, synchronized (thread-safe)
- Slower due to synchronization overhead
- Use in multi-threaded environments

Rule: Use String for constants, StringBuilder for modifications, StringBuffer for thread-safe modifications.

Q17

Explain Exception Handling in Java.

▼

Answer:
Exception Hierarchy:
- Throwable → Error (unchecked) / Exception
- Exception → RuntimeException (unchecked) / Other Exceptions (checked)

Checked Exceptions: Must handle or declare (IOException, SQLException)
Unchecked Exceptions: Runtime exceptions (NullPointerException, ArrayIndexOutOfBounds)

Keywords:
- try: Block to monitor for exceptions
- catch: Handle specific exception types
- finally: Always executes (cleanup code)
- throw: Explicitly throw an exception
- throws: Declare exceptions method might throw

Q18

What is the difference between final, finally, and finalize?

▼

Answer:
final (keyword):
- Variable: Cannot be reassigned (constant)
- Method: Cannot be overridden
- Class: Cannot be inherited

finally (block):
- Executes after try-catch regardless of exception
- Used for cleanup (closing resources)
- Executes even if return statement in try

finalize() (method):
- Called by Garbage Collector before object destruction
- Used for cleanup before object is garbage collected
- Deprecated since Java 9, use try-with-resources instead

Q19

Explain Multithreading in Java.

▼

Answer:
Multithreading allows concurrent execution of multiple threads for better CPU utilization.

Ways to create threads:
1. Extend Thread class
2. Implement Runnable interface (preferred — allows multiple inheritance)
3. Implement Callable (returns result, can throw exceptions)

Thread States: NEW → RUNNABLE → RUNNING → BLOCKED/WAITING/TIMED_WAITING → TERMINATED

Synchronization:
- synchronized keyword (method/block level)
- Locks (ReentrantLock) for more control
- Atomic classes (AtomicInteger) for lock-free operations

Thread Pool: ExecutorService manages pool of worker threads efficiently.

Q20

What is Garbage Collection in Java?

▼

Answer:
Garbage Collection (GC) automatically reclaims memory occupied by objects that are no longer reachable/used.

How it works:
1. Mark: Identify unreachable objects
2. Sweep: Reclaim memory from unreachable objects
3. Compact: Defragment memory (optional)

Generational GC:
- Young Generation: New objects, frequent minor GC
- Old Generation: Long-lived objects, major GC
- Permanent/MetaSpace: Class metadata

GC Algorithms: Serial, Parallel, CMS, G1 (default in Java 9+), ZGC

Trigger GC: System.gc() (suggestion, not guarantee)

Q21

What is Load Balancing and why is it needed?

▼

Answer:
Load Balancing distributes incoming network traffic across multiple servers to ensure no single server bears too much load.

Benefits:
- High availability and reliability
- Better resource utilization
- Scalability (horizontal scaling)
- Fault tolerance (if one server fails, others handle traffic)

Algorithms:
- Round Robin
- Least Connections
- IP Hash
- Weighted Round Robin

Types: Layer 4 (transport level), Layer 7 (application level)

Q22

Explain Caching and its types.

▼

Answer:
Caching stores frequently accessed data in fast, temporary storage to reduce latency and database load.

Cache Levels:
- L1/L2/L3 Cache: CPU caches (hardware)
- Application Cache: In-memory (Redis, Memcached)
- CDN Cache: Static content near users
- Browser Cache: Client-side storage

Cache Policies:
- LRU: Least Recently Used
- LFU: Least Frequently Used
- FIFO: First In First Out

Challenges: Cache invalidation, cache penetration, cache avalanche, consistency

Q23

What is the difference between Monolithic and Microservices architecture?

▼

Answer:
Monolithic:
- Single unified codebase
- All components tightly coupled
- Easier to develop and test initially
- Harder to scale individual components
- Single deployment unit

Microservices:
- Application divided into small, independent services
- Each service has its own database and logic
- Services communicate via APIs (REST/gRPC)
- Independent deployment and scaling
- Better fault isolation

Trade-offs: Microservices add complexity (distributed systems challenges) but offer better scalability and maintainability.

Q24

Explain CAP Theorem.

▼

Answer:
CAP Theorem states that a distributed system can only guarantee two out of three properties:

C — Consistency: All nodes see the same data at the same time
A — Availability: Every request receives a response (success or failure)
P — Partition Tolerance: System continues to operate despite network partitions

Combinations:
- CP: Consistency + Partition Tolerance (sacrifice availability) — e.g., MongoDB, HBase
- AP: Availability + Partition Tolerance (sacrifice consistency) — e.g., Cassandra, DynamoDB
- CA: Consistency + Availability (no partition tolerance) — single node systems

In practice: Network partitions are inevitable, so systems choose between CP or AP.

Q25

What are RESTful APIs and their principles?

▼

Answer:
REST (Representational State Transfer) is an architectural style for designing networked applications.

Principles:
1. Stateless: Each request contains all information needed; server doesn't store client state
2. Client-Server: Separation of concerns
3. Cacheable: Responses can be cached
4. Uniform Interface: Standard HTTP methods (GET, POST, PUT, DELETE)
5. Layered System: Client cannot tell if connected directly to end server

HTTP Methods:
- GET: Read
- POST: Create
- PUT: Update (full)
- PATCH: Update (partial)
- DELETE: Remove

Q26

What is the difference between SQL and NoSQL databases?

▼

Answer:
SQL (Relational):
- Structured schema with tables, rows, columns
- ACID transactions
- Vertical scaling
- Examples: MySQL, PostgreSQL, Oracle
- Best for: Complex queries, structured data, transactions

NoSQL (Non-relational):
- Flexible schema (schema-less)
- BASE properties (Basically Available, Soft state, Eventually consistent)
- Horizontal scaling
- Types: Document (MongoDB), Key-Value (Redis), Column (Cassandra), Graph (Neo4j)
- Best for: Big data, real-time, unstructured data

Q27

Explain ACID properties in databases.

▼

Answer:
ACID ensures reliable processing of database transactions.

A — Atomicity: All operations in a transaction complete successfully or none do. "All or nothing."

C — Consistency: Database remains in a valid state before and after transaction. All constraints satisfied.

I — Isolation: Concurrent transactions don't interfere with each other. Results as if transactions executed sequentially.

D — Durability: Once committed, changes persist even in case of system failure (power loss, crash).

Isolation Levels: Read Uncommitted, Read Committed, Repeatable Read, Serializable

Q28

What are Indexes and why are they important?

▼

Answer:
Indexes are data structures that speed up data retrieval operations on database tables.

How they work:
- Similar to book index — allows direct lookup instead of full scan
- B-Tree is most common index structure
- Stores sorted key values with pointers to actual data

Types:
- Primary Index: On primary key, unique
- Secondary Index: On non-key columns
- Composite Index: On multiple columns
- Unique Index: Ensures uniqueness

Trade-offs:
- Speeds up SELECT, but slows down INSERT/UPDATE/DELETE
- Requires additional storage space

Q29

Explain Normalization and its forms.

▼

Answer:
Normalization organizes data to reduce redundancy and improve integrity.

1NF (First Normal Form):
- Atomic values (no repeating groups)
- Each cell contains single value

2NF (Second Normal Form):
- Must be in 1NF
- No partial dependency (non-key attributes depend on entire primary key)

3NF (Third Normal Form):
- Must be in 2NF
- No transitive dependency (non-key attributes depend only on primary key)

BCNF (Boyce-Codd Normal Form):
- Stricter version of 3NF
- Every determinant must be a candidate key

Q30

What is the difference between JOIN types in SQL?

▼

Answer:
INNER JOIN: Returns only matching rows from both tables.

LEFT JOIN: Returns all rows from left table, matching rows from right (NULL if no match).

RIGHT JOIN: Returns all rows from right table, matching rows from left (NULL if no match).

FULL OUTER JOIN: Returns all rows from both tables (NULL where no match).

CROSS JOIN: Cartesian product — every row from first table with every row from second.

SELF JOIN: Join a table with itself (useful for hierarchical data).

Q31

Explain Process vs Thread.

▼

Answer:
Process:
- Independent program in execution
- Has own memory space (code, data, heap, stack)
- Heavyweight — context switching is expensive
- Inter-process communication (IPC) needed for communication
- One process crash doesn't affect others

Thread:
- Lightweight unit of execution within a process
- Shares memory space with other threads in same process
- Lightweight — fast context switching
- Direct communication via shared memory
- One thread crash can kill entire process

Q32

What is Deadlock and how to prevent it?

▼

Answer:
Deadlock occurs when processes are blocked waiting for resources held by each other, creating a circular wait.

Four Conditions (all must hold):
1. Mutual Exclusion: Resources cannot be shared
2. Hold and Wait: Process holds resources while waiting for more
3. No Preemption: Resources cannot be forcibly taken
4. Circular Wait: Circular chain of processes waiting

Prevention Strategies:
- Prevention: Break one of the four conditions
- Avoidance: Banker's algorithm (safe state checking)
- Detection & Recovery: Detect cycles, kill processes or preempt resources

Q33

Explain the OSI Model layers.

▼

Answer:
OSI (Open Systems Interconnection) model has 7 layers:

7. Application: HTTP, FTP, SMTP — user interface
6. Presentation: Data translation, encryption, compression
5. Session: Session management, authentication
4. Transport: TCP, UDP — end-to-end communication, reliability
3. Network: IP, routing — logical addressing, packet forwarding
2. Data Link: MAC addressing, framing, error detection (Ethernet)
1. Physical: Cables, signals, bits on wire

Mnemonic: "Please Do Not Throw Sausage Pizza Away"

Q34

What is the difference between TCP and UDP?

▼

Answer:
TCP (Transmission Control Protocol):
- Connection-oriented (3-way handshake)
- Reliable — guarantees delivery, ordering, no duplicates
- Error checking and retransmission
- Flow control and congestion control
- Slower, more overhead
- Use: HTTP, FTP, Email

UDP (User Datagram Protocol):
- Connectionless (no handshake)
- Unreliable — no guarantee of delivery
- No error recovery
- Faster, less overhead
- Use: DNS, Video streaming, Gaming, VoIP

Q35

Explain Virtual Memory.

▼

Answer:
Virtual Memory allows a computer to use more memory than physically available by using disk space as an extension of RAM.

How it works:
- Each process has its own virtual address space
- Memory Management Unit (MMU) translates virtual to physical addresses
- Pages (fixed-size blocks) are swapped between RAM and disk

Page Fault: When accessed page is not in RAM, OS fetches it from disk.

Benefits:
- Larger address space than physical memory
- Memory isolation between processes
- Efficient memory sharing (shared libraries)

Thrashing: Excessive page swapping degrading performance.

Building Blocks

Sub-Problems Bank

Master these smaller patterns first. Every HackWithInfy question is a combination of 2–3 of these building blocks.

Easy Patterns

Medium Patterns

Hard Patterns

Pattern E1

Two-Sum with HashMap

Store each element in a map. For each element x, check if (target − x) exists. O(N) time. Foundation for 3-sum, 4-sum, pair-with-given-sum problems.

map.containsKey(target - a[i])

Pattern E2

Frequency Count

Count occurrences using HashMap or int[]. Used in: anagram check, majority element, first non-repeating character, character frequency in strings.

freq.merge(key, 1, Integer::sum)

Pattern E3

Stack-Based Parsing

Use stack for balanced parentheses, expression evaluation, undo operations. Push on open, pop on close. Valid brackets check is a 5-line solution.

stack.push('('); stack.pop() == '('

Pattern E4

Prefix Sum Query

Precompute prefix sums. Answer range sum in O(1). Essential for all range query problems. pre[r+1] - pre[l] = sum of A[l..r].

sum[l..r] = pre[r+1] - pre[l]

Pattern E5

Cyclic Rotation

Rotate array by k positions: reverse whole → reverse first k → reverse remaining. O(N) time, O(1) space. Cleaner than shift-and-copy.

reverse(0,n-1); reverse(0,k-1); reverse(k,n-1)

Pattern E6

Fast Power (Binary Exponentiation)

Compute a^n mod p in O(log N). Essential for modular arithmetic. Uses the identity: a^n = (a^(n/2))² if n even, a × a^(n-1) if n odd.

pow(a,n,p) = pow(a,n/2,p)² % p

Pattern M1

Merge Intervals

Sort intervals by start time. Merge overlapping ones: if cur.start ≤ prev.end, merge by extending end. O(N log N). Used in calendar, task scheduling, meeting rooms problems.

if(cur[0] <= prev[1]) prev[1] = max(prev[1], cur[1])

Pattern M2

Top-K with Heap

Find K largest: use min-heap of size K. For K smallest: use max-heap of size K. Each insertion: if heap size > K, remove worst. O(N log K).

if(heap.size()>K) heap.poll()

Pattern M3

BFS on Implicit Graph

When states form a graph not explicitly given. Model states as nodes, transitions as edges. BFS gives min steps. Used in: word ladder, sliding puzzle, knight on chessboard.

BFS on (state) → generate next valid states

Pattern M4

2D DP (Grid Paths)

dp[i][j] = answer for cell (i,j). Fill row by row. Transition from top and left. Used in: unique paths, minimum path sum, dungeon game, edit distance table.

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Pattern M5

Topological Sort (BFS/Kahn's)

Process nodes in dependency order. Compute in-degrees. Add 0-in-degree nodes to queue. Process and reduce neighbors' in-degrees. Used in: task order, course schedule, build systems.

queue ← {nodes with indegree 0}; reduce indegree of neighbors

Pattern M6

String Hashing (Rolling Hash)

Compute polynomial hash of string. Rolling hash allows O(1) substring hash computation after O(N) build. Used in: Rabin-Karp string matching, finding duplicate substrings.

hash = Σ a[i] × BASE^i mod MOD

Pattern H1

Sparse Table (Range Minimum Query)

Precompute answers for ranges of power-of-2 lengths. Build: O(N log N). Query: O(1). Used for LCA in trees and static RMQ problems where no updates occur.

sparse[i][j] = min(sparse[i][j-1], sparse[i+2^(j-1)][j-1])

Pattern H2

Bitmasking DP

When state space is small (≤ 20 elements), represent subsets as bitmasks. dp[mask] = best answer using the subset represented by mask. Used in: TSP, minimum XOR, shortest superstring.

dp[mask|(1<

Pattern H3

Matrix Exponentiation

Express a linear recurrence as matrix multiplication. Compute A^n in O(k³ log n) where k = state size. Used in: Fibonacci in O(log N), linear recurrences with large n (up to 10¹⁸).

F(n) = [[1,1],[1,0]]^n × [1,0]

Pattern H4

XOR Basis (Linear Algebra on GF2)

Gaussian elimination over GF(2). Maintain a basis of XOR-independent vectors. Find max XOR of any subset. Used in: maximum XOR subarray, XOR basis queries.

insert(x): for each basis[bit], if x>>bit&1: x^=basis[bit]

Pattern H5

LCA with Binary Lifting

Precompute ancestors at power-of-2 distances. LCA query: lift both nodes to same depth, then binary lift together. Build: O(N log N). Query: O(log N). Essential for tree path problems.

up[v][j] = up[up[v][j-1]][j-1]

Pattern H6

Mo's Algorithm (Offline Range Queries)

Process range queries offline sorted by block. Maintain a window, extending/shrinking by 1. Total operations: O((N+Q)√N). Best for static arrays with complex aggregates where sliding window is O(1).

Sort queries by (l/√N, r); process in order

CrackHackWithInfy

How to Use This Website

Read the Roadmap First

Study DSA Topics in Order

Solve Sub-Problems First

Try Questions Yourself First

Take the Mock Exam

Use the Complexity Table

HackWithInfy 2026 Exam

Build-Up: Sub-Problems to Solve First

Max Heap Basics

Greedy Pick with Replacement

Early Termination

Kadane's Algorithm (k=0 case)

All Subarrays Brute Force

Optimal Swap Simulation

Parity Check

Partition and Find 2-Minimum

Answer Aggregation

DFS Tree Traversal

Path with Constraint

Edge Cost Accumulation

Previous Year Questions

Mock Exam — Test Yourself

DSA Guide — 14 Essential Topics

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Concept

Theoretical Questions & Answers

Sub-Problems Bank

Two-Sum with HashMap

Frequency Count

Stack-Based Parsing

Prefix Sum Query

Cyclic Rotation

Fast Power (Binary Exponentiation)

Merge Intervals

Top-K with Heap

BFS on Implicit Graph

2D DP (Grid Paths)

Topological Sort (BFS/Kahn's)

String Hashing (Rolling Hash)

Sparse Table (Range Minimum Query)

Bitmasking DP

Matrix Exponentiation

XOR Basis (Linear Algebra on GF2)

LCA with Binary Lifting

Mo's Algorithm (Offline Range Queries)

6-Week Preparation Roadmap

Week 1 — Foundations

Week 2 — Searching & Greedy

Week 3 — Graph Algorithms

Week 4 — Dynamic Programming

Week 5 — Tree Algorithms

Week 6 — Advanced Data Structures + Mock Exams

Exam Day Strategy

Crack
HackWithInfy