Interview Problem-Solving Patterns

Recognise the shape of a problem, choose a reliable algorithm, and communicate a correct C solution for product-company interviews and online assessments.

Est. 180 min Updated Suggest a fix
Prerequisite: DSA foundations and core structuresC solutionsPlacement practice

Strong interview performance is not about memorising hundreds of answers. It is about identifying what the input and constraints imply, choosing a sound model, and proving your approach works. In Indian campus and lateral placements, product companies commonly combine online assessments with one or more technical rounds; the exact format varies by company and role. Practise under both time pressure and a live discussion, and always follow the instructions of the specific assessment.

A pattern is a useful hypothesis, not a keyword trick. “Contiguous” suggests a window or prefix sums; it does not decide which one until you inspect the condition. State your invariant, test it against an example, and be ready to change course if it does not fit.

Avoid duplication: The dedicated Two Pointers and Sliding Window, Union-Find, Tries, Bit Manipulation, Graph Algorithms, DP Patterns, and Minimum Spanning Trees lessons teach the underlying mechanics. This unit focuses on recognition, trade-offs, interview delivery, and applying patterns together.

Recognise the problem shape

Before naming an algorithm, extract the object, the operation, and the constraint. Ask: Is the answer about a contiguous range or any subset? Is the input sorted? Do updates happen? Is there a graph of dependencies? Does a yes/no feasibility test become easier as the answer changes?

PatternSignal phrases / structureCore ideaTypical timeExtra space
Two pointersSorted array; pair/triplet; palindrome; compare both endsMove one or two indices while preserving an ordering invariant.O(n)O(1)
Sliding windowContiguous subarray/substring; longest/shortest window satisfying a ruleExtend right; move left when the window constraint requires it.O(n)O(1)–O(k)
Fast / slow pointersLinked-list cycle or middle; repeated transitions; cycle detectionAdvance pointers at different speeds; meeting or termination gives structure.O(n)O(1)
Binary search on answerMinimise the maximum / maximise the minimum; feasibility changes monotonicallySearch the answer range and test whether a candidate is feasible.O(n log R)O(1)
Prefix sumsMany range-sum queries; subarray sum; cumulative countsStore cumulative totals so a range is the difference of two prefixes.O(n) build; O(1) queryO(n)
Monotonic stackNext greater/smaller; nearest boundary; histogram; wait until a value is exceededKeep indices in increasing or decreasing value order; resolve them when order breaks.O(n)O(n)
Heap / top-kK largest/smallest; repeatedly get current min/max; streaming rankingKeep a heap of k candidates or a priority queue of pending work.O(n log k)O(k)
IntervalsOverlapping ranges; meeting rooms; merge / schedule intervalsSort by start or end, then merge or greedily choose compatible intervals.O(n log n)O(n) or O(1) extra
BFS / DFS on gridsIslands, regions, shortest unweighted path, flood fill, adjacent cellsTreat each cell as a vertex; mark it visited when adding it to the worklist.O(rows × cols)O(rows × cols)
BacktrackingEnumerate valid arrangements, combinations, paths; constraints prune choicesChoose, explore, undo; prune partial candidates that cannot succeed.O(b^d) worst caseO(d) recursion
DP state designChoices repeat the same subproblems; optimal count/min/max; take or skipDefine a state, recurrence, base case, and evaluation order; memoise or tabulate.O(states × transitions)O(states)
Union-Find (DSU)Dynamic connectivity; components after adding edges; cycle checks in undirected graphsRepresent each component by a parent; find roots and unite distinct roots.O(α(n)) amortised / operationO(n)
Topological sortPrerequisites, dependency ordering, course schedule; directed acyclic graphUse indegrees with Kahn’s queue, or DFS postorder; a cycle prevents a full order.O(V + E)O(V)

Complexities describe common implementations, not guarantees. For example, binary search on answer costs O(n log R) when one feasibility check scans n items over a range of R candidate values.

Ten classic problems, solved in C

Each example names the invariant and includes a small dry-run. Snippets use C99 features where noted (variable-length arrays in the stack, heap, grid, and DP examples). In production or a platform with fixed limits, validate sizes and adapt storage to its constraints.

1. Two Sum in a Sorted Array — two pointers

Problem: Given a sorted array and a target, return the indices of two values whose sum equals the target. Assume one answer exists.

Pattern / invariant: If the sum is too small, only moving the left pointer can increase it; if too large, move the right pointer. The sorted order lets us discard a whole set of pairs at each step.

C
int twoSumSorted(const int a[], int n, int target, int *leftOut, int *rightOut) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        long long sum = (long long)a[left] + a[right];
        if (sum == target) {
            *leftOut = left;
            *rightOut = right;
            return 1;
        }
        if (sum < target) left++;
        else right--;
    }
    return 0;
}

Dry run: a = [1, 2, 4, 6, 10], target = 8. Start (1, 10) = 11, so move right; (1, 6) = 7, so move left; (2, 6) = 8. Return indices 1 and 3.

Complexity: O(n) time, O(1) extra space.

2. Longest Substring Without Repeating Characters — sliding window

Problem: Find the length of the longest substring with no repeated byte characters.

Pattern / invariant: Maintain a valid window [left, right]. When a character repeats inside it, jump left past that character’s previous position. This is the variable-window technique taught in the dedicated Two Pointers and Sliding Window lesson, now used as a pattern-recognition example.

C
int longestUniqueSubstring(const char *s) {
    int lastSeen[256];
    for (int i = 0; i < 256; i++) lastSeen[i] = -1;
    int left = 0;
    int best = 0;
    for (int right = 0; s[right] != '\0'; right++) {
        unsigned char ch = (unsigned char)s[right];
        if (lastSeen[ch] >= left) left = lastSeen[ch] + 1;
        lastSeen[ch] = right;
        int length = right - left + 1;
        if (length > best) best = length;
    }
    return best;
}

Dry run: s = "pwwkew". At the second w (index 2), move left from 0 to 2. The window then grows to "wke" at indices 2–4 (length 3); the final w cannot extend it past the prior w. Answer: 3.

Complexity: O(n) time, O(1) space for a fixed 256-character table.

3. Find the Middle of a Linked List — fast / slow pointers

Problem: Return the middle node. For an even-length list, return the second of the two middle nodes.

Pattern / invariant: Move slow by one link and fast by two. When fast reaches the end, slow has travelled half as far. No length count or second pass is needed.

C
struct Node {
    int value;
    struct Node *next;
};

struct Node *middleNode(struct Node *head) {
    struct Node *slow = head;
    struct Node *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Dry run: 1 → 2 → 3 → 4 → 5: after two iterations, slow is at 3 and fast is at 5; the loop ends, so return 3. With 1 → 2 → 3 → 4, slow finishes at 3, the second middle.

Complexity: O(n) time, O(1) extra space.

4. Minimum Eating Speed — binary search on answer

Problem: Given positive pile sizes and h hours, find the smallest integer speed k that can finish all piles in h hours. One pile is worked on per hour.

Pattern / invariant: Feasibility is monotonic: if speed k works, any larger speed also works. Binary-search the answer, not an array index. Search from 1 to the largest pile.

C
int feasible(const int piles[], int n, int h, int speed) {
    long long hours = 0;
    for (int i = 0; i < n; i++) {
        hours += ((long long)piles[i] + speed - 1) / speed;
        if (hours > h) return 0;
    }
    return 1;
}

int minEatingSpeed(const int piles[], int n, int h) {
    int low = 1;
    int high = piles[0];
    for (int i = 1; i < n; i++)
        if (piles[i] > high) high = piles[i];
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (feasible(piles, n, h, mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

Dry run: piles = [3, 6, 7, 11], h = 8. At speed 3, required hours = 1 + 2 + 3 + 4 = 10 (too slow). At speed 4, hours = 1 + 2 + 2 + 3 = 8 (feasible). Binary search continues left to prove 4 is the minimum.

Complexity: O(n log M) time, O(1) extra space; M is the largest pile.

5. Range Sum Query — prefix sums

Problem: Preprocess an integer array so any inclusive range [left, right] can be summed quickly.

Pattern / invariant: prefix[i] stores the sum of the first i values. The requested range is prefix[right + 1] − prefix[left]. Define the prefix convention clearly to avoid off-by-one errors.

C
void buildPrefix(const int a[], int n, long long prefix[]) {
    prefix[0] = 0;
    for (int i = 0; i < n; i++)
        prefix[i + 1] = prefix[i] + a[i];
}

long long rangeSum(const long long prefix[], int left, int right) {
    return prefix[right + 1] - prefix[left];
}

Dry run: a = [2, -1, 3, 5] gives prefix = [0, 2, 1, 4, 9]. Sum indices 1 through 3 = prefix[4] − prefix[1] = 9 − 2 = 7.

Complexity: O(n) preprocessing, O(1) per query, O(n) extra space.

6. Next Greater Element — monotonic stack

Problem: For each array position, find the first value to its right that is strictly greater; use -1 if none exists.

Pattern / invariant: Keep indices whose next greater value is not known in a decreasing-value stack. A new larger value resolves every smaller value at the top. Each index is pushed and popped once.

C
void nextGreater(const int a[], int n, int answer[]) {
    int stack[n];
    int top = -1;
    for (int i = 0; i < n; i++) answer[i] = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && a[i] > a[stack[top]])
            answer[stack[top--]] = a[i];
        stack[++top] = i;
    }
}

Dry run: a = [2, 1, 2, 4, 3]. The 2 at index 0 is resolved by 4; 1 at index 1 is resolved by the 2 at index 2; that 2 is resolved by 4. The 4 and final 3 remain unresolved. Answer: [4, 2, 4, -1, -1].

Complexity: O(n) time, O(n) extra space.

7. Kth Largest Element — min-heap of size k

Problem: Return the kth largest value without sorting the entire input. Assume 1 <= k <= n.

Pattern / invariant: Keep only the k largest values seen so far in a min-heap. Its root is the smallest of those k values, and therefore the kth largest overall. Heap helpers are shown explicitly for a zero-based array.

C
void swapInt(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

void siftDown(int heap[], int size, int i) {
    while (2 * i + 1 < size) {
        int child = 2 * i + 1;
        if (child + 1 < size && heap[child + 1] < heap[child]) child++;
        if (heap[i] <= heap[child]) break;
        swapInt(&heap[i], &heap[child]);
        i = child;
    }
}

int kthLargest(const int a[], int n, int k) {
    int heap[k];
    int size = 0;
    for (int i = 0; i < n; i++) {
        if (size < k) {
            int j = size++;
            heap[j] = a[i];
            while (j > 0 && heap[(j - 1) / 2] > heap[j]) {
                swapInt(&heap[j], &heap[(j - 1) / 2]);
                j = (j - 1) / 2;
            }
        } else if (a[i] > heap[0]) {
            heap[0] = a[i];
            siftDown(heap, size, 0);
        }
    }
    return heap[0];
}

Dry run: [3, 2, 1, 5, 6, 4], k = 2. The heap retains the two largest seen: after 3 and 2 it is {2,3}; 1 is ignored; 5 replaces 2; 6 replaces 3; 4 is ignored. The min-heap root is 5, the second largest.

Complexity: O(n log k) time, O(k) extra space.

8. Number of Islands — BFS on a grid

Problem: Count groups of adjacent land cells represented by 1, connected horizontally or vertically. Each island is counted once.

Pattern / invariant: A grid is an implicit graph. Start BFS at each unvisited land cell and mark cells when enqueued, so no cell enters the queue twice. Diagonal neighbors are not connected in this definition.

C
int countIslands(int rows, int cols, char grid[rows][cols]) {
    int queue[rows * cols];
    int directions[5] = {-1, 0, 1, 0, -1};
    int islands = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != '1') continue;
            islands++;
            int head = 0, tail = 0;
            queue[tail++] = r * cols + c;
            grid[r][c] = '0';
            while (head < tail) {
                int cell = queue[head++];
                int row = cell / cols, col = cell % cols;
                for (int d = 0; d < 4; d++) {
                    int nr = row + directions[d];
                    int nc = col + directions[d + 1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                        grid[nr][nc] = '0';
                        queue[tail++] = nr * cols + nc;
                    }
                }
            }
        }
    }
    return islands;
}

Dry run: For grid rows 110 / 010 / 001, start at the top-left land and visit its two connected neighbors: island 1. The bottom-right land is disconnected: island 2. The function returns 2 and marks visited land as water.

Complexity: O(rows × cols) time and queue space in the worst case; the input grid is modified.

9. Coin Change — one-dimensional dynamic programming

Problem: Given coin denominations and an amount, return the fewest coins needed to make that amount, or -1 if it cannot be made. Coins may be reused.

Pattern / invariant: State: dp[value] is the minimum number of coins for that value. Transition from each coin c: dp[value] = min(dp[value], dp[value − c] + 1). The smaller value is already solved.

C
int minCoins(const int coins[], int count, int amount) {
    int dp[amount + 1];
    int unreachable = amount + 1;
    for (int value = 0; value <= amount; value++) dp[value] = unreachable;
    dp[0] = 0;
    for (int value = 1; value <= amount; value++) {
        for (int i = 0; i < count; i++) {
            int coin = coins[i];
            if (coin <= value && dp[value - coin] != unreachable &&
                dp[value - coin] + 1 < dp[value])
                dp[value] = dp[value - coin] + 1;
        }
    }
    return dp[amount] == unreachable ? -1 : dp[amount];
}

Dry run: coins = [1, 3, 4], amount = 6. dp[0] = 0; dp[3] = 1 (3); dp[4] = 1 (4); dp[6] becomes dp[3] + 1 = 2 (3 + 3), better than 4 + 1 + 1. Answer: 2.

Complexity: O(amount × number of denominations) time, O(amount) extra space.

10. Course Schedule — topological sort with Kahn’s algorithm

Problem: Given prerequisite pairs [course, prerequisite], decide whether all courses can be completed. This example supports at most MAX_COURSES courses.

Pattern / invariant: Build directed edges prerequisite → course. Repeatedly remove nodes with indegree zero. If all nodes are removed, the graph is acyclic; otherwise a cycle blocks progress. This matrix version keeps the example self-contained.

C
#define MAX_COURSES 100

int canFinish(int n, const int prerequisites[][2], int edgeCount) {
    int graph[MAX_COURSES][MAX_COURSES] = {{0}};
    int indegree[MAX_COURSES] = {0};
    int queue[MAX_COURSES];
    for (int i = 0; i < edgeCount; i++) {
        int course = prerequisites[i][0];
        int prerequisite = prerequisites[i][1];
        if (!graph[prerequisite][course]) {
            graph[prerequisite][course] = 1;
            indegree[course]++;
        }
    }
    int head = 0, tail = 0, completed = 0;
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) queue[tail++] = i;
    while (head < tail) {
        int current = queue[head++];
        completed++;
        for (int next = 0; next < n; next++) {
            if (graph[current][next] && --indegree[next] == 0)
                queue[tail++] = next;
        }
    }
    return completed == n;
}

Dry run: Prerequisites [1,0], [2,1], [3,2] give edges 0→1→2→3. Initially only 0 has indegree zero; removing each course unlocks the next, so all four complete. Adding [0,3] creates a cycle: the queue stalls before all nodes are removed.

Complexity: O(V² + E) time and O(V²) space for this adjacency-matrix teaching version. An adjacency list improves this to O(V + E).

The interview communication framework

In a live round, the interviewer is evaluating how you reason as well as whether the final code passes. Keep the discussion structured and collaborative.

1. ClarifyRestate the goal. Ask about input sizes, sortedness, duplicates, negative values, mutation, and what to return when no answer exists. Confirm examples and constraints before coding.
2. Brute forceGive a correct simple approach first. State its time and space costs. This proves you understand the requirement and gives a baseline to improve.
3. OptimiseUse constraints and signals to select a data structure or pattern. Explain the invariant and why it improves complexity; state trade-offs and edge cases.
4. CodeName variables for their roles, use small helpers when helpful, and narrate the invariant rather than reading each line. Keep the implementation aligned with the discussed algorithm.
5. TestDry-run the sample, then test boundaries: empty/singleton input, duplicates, all-equal values, no solution, and minimum/maximum constraints. Recheck complexity.

A practical 4-week placement plan

Aim for consistent, deliberate practice rather than a large problem count. A realistic session is 60–90 minutes: attempt independently, review one solution only after making progress, then re-solve from a blank editor.

Week 1 · Arrays and strings

Focus: Two pointers, sliding windows, prefix sums, hash-based lookup.

Five focused sessions: learn/review one pattern, solve two easy and three medium problems, then explain one solution aloud. Revisit the Two Pointers and Sliding Window lesson for the underlying mechanics.

Week 2 · Search and ordering

Focus: Binary search on answer, intervals, monotonic stacks, heaps / top-k.

Practise boundary-safe binary search and heap invariants. Complete at least one timed 45-minute set and review every incorrect assumption.

Week 3 · Graphs and choices

Focus: Grid BFS/DFS, union-find, topological sort, backtracking, DP state design.

Draw states and transitions before coding. Solve one graph and one DP problem on most days; explain why the algorithm is complete.

Week 4 · Placement simulation

Focus: Mixed pattern selection, online assessments, communication, revision.

Take three timed mock assessments; practise writing compilable C under the platform constraints; maintain an error log and redo missed problems without hints.

For Indian placement schedules, adapt the final week to the company’s announced format: timed OA, coding interview, or both. Practise in the required language and editor, read negative-marking and submission rules carefully, and do not assume one company’s pattern applies to another.

Common mistakes to avoid

  • Pattern-matching by one keyword: verify all constraints and prove the invariant; “subarray” alone does not guarantee a sliding window (negative values can break common shrink rules).
  • Skipping clarification: assumptions about duplicates, indexing, empty inputs, and output format can invalidate an otherwise good algorithm.
  • Coding before estimating complexity: compare the expected input size with your time and memory costs before committing.
  • Off-by-one binary search: write down the search invariant and use overflow-safe midpoint calculation.
  • Marking graph nodes too late: mark when enqueuing, not when dequeuing, to avoid duplicate work or queue overflow.
  • Vague DP definitions: define exactly what a state means, then derive transitions and base cases from that meaning.
  • Ignoring C details: consider integer overflow, array bounds, null pointers, string signedness, allocation limits, and platform C standard.
  • Treating an OA like a live interview: online assessments may reward exact input/output handling and fast edge-case coverage; live interviews additionally require clear collaboration. Practise both.
  • Memorising without retrieval practice: after reviewing an explanation, close it and reconstruct the algorithm, code, tests, and complexity yourself.

🎯 Key Takeaways

  • ✓Translate the prompt into an input model, constraints, and output before selecting a pattern.
  • ✓Use signal phrases to generate candidate patterns, then verify the invariant with examples and edge cases.
  • ✓Two pointers and sliding window have dedicated lessons; this unit connects those techniques to interview recognition and other core patterns.
  • ✓Use the clarify → brute force → optimise → code → test framework to make reasoning visible.
  • ✓For product-company placements and online assessments, practise the actual language, editor, timing, and rules announced for that process.
  • ✓Review mistakes deliberately and solve again without hints; durable pattern recognition beats answer memorisation.

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...