Algorithm Interview Questions and Answers: Cross-Concept DSA Problems

Definitions are not enough when an interviewer combines constraints, data structures, complexity and correctness. You must explain how each detail changes your choice. Interview expectations vary by team and role, so the required depth can differ.

What cross-concept algorithm interviews actually test

For every problem, clarify the output and constraints, state a correct baseline, choose and improve an approach, justify correctness, then give time, space and edge cases.

Suppose n <= 100,000, values range from -10^9 to 10^9, and you must return original indices. Quadratic search is too slow, a frequency array is impractical, and sorting values alone loses indices. The same pair-sum pattern anchors DSA Interview Follow-Up Questions: Optimise Brute Force Step by Step, where it develops the baseline-to-hash proof and the constant-extra-space follow-up. DSA Interview Questions by Pattern: Arrays, Trees, Graphs and Complexity compares array, tree and unweighted-BFS baselines. Original-index constraints instead make this pair-sum trace a choice between hashing and sorting; knapsack, weighted-shortest-path and streaming problems then force different paradigms.

A basic round may stop after a dry run; a deeper one may add scale, mutation, duplicates or negative weights. Use: "I choose X because invariant Y holds; the cost is Z; if C changes, I switch to W."

Complexity, sorting and searching answers you can defend

Question: What is the complexity of an outer loop that runs n times and an inner loop whose values are 1, 2, 4, ..., n?

The inner value doubles, so it runs floor(log2 n) + 1 times for positive n. At n = 8, values 1, 2, 4, 8 mean four inner iterations and 8 x 4 = 32 overall. Time is O(n log n). Two sequential O(n) loops instead add to O(n), not O(n^2).

Question: What does stable sorting preserve?

It preserves equal-key records' relative order. Sorting [4A, 2, 4B, 1] stably gives [1, 2, 4A, 4B]. This matters when an earlier order, such as timestamp, must survive a later key sort.

Question: When is binary search valid?

It needs sorted data or a monotonic condition. In [1, 3, 4, 6, 7], probe index 2, value 4. For target 6, discard the left half and find 6 at index 3 in O(log n) time. On [4, 1, 7, 3, 6], a midpoint cannot safely eliminate either half.

Worked pair-sum interview problem: hashing or sorting?

Prompt: For A = [4, 1, 7, 3, 6] and target 10, return any pair of original zero-based indices whose values sum to the target.

Checking every pair is a correct O(n^2)-time, O(1)-space baseline.

For a faster answer, map values to indices. At index 0, 4 needs 6; store 4 -> 0. At index 1, 1 needs 9; store 1 -> 1. At index 2, 7 needs 3; store 7 -> 2. At index 3, 3 needs the stored 7, so return (2, 3). Check the complement before storing the current value to prevent same-index reuse. Expected time and space are O(n).

Sorting also works if indices travel with values: [(1,1), (3,3), (4,0), (6,4), (7,2)]. Two pointers find 3 + 7 or 4 + 6, but sorting costs O(n log n). Correct does not automatically mean best for the contract.

Greedy versus dynamic programming for 0/1 knapsack

Question: With capacity W = 50 and items A = (10,60), B = (20,100) and C = (30,120), can value-per-weight greedy solve 0/1 knapsack?

Ratios are 6, 5 and 4. Greedy takes A+B for weight 10 + 20 = 30 and value 60 + 100 = 160; C cannot fit. B+C instead gives weight 20 + 30 = 50 and value 100 + 120 = 220. The local rule fails.

Let dp[i][w] be the maximum value using the first i items within capacity w. When item i fits, the 0/1 knapsack recurrence is max(dp[i-1][w], value_i + dp[i-1][w-weight_i]). Its two terms exclude or include the item, covering every valid choice.

For capacity columns 0, 10, 20, 30, 40, 50, the rows are:

The method takes O(nW) time and O(W) space after row compression.

Graph algorithm selection and changing constraints

Consider directed edges A->B (4), A->C (1), C->B (2), B->D (1) and C->D (5). Find the shortest path from A to D.

Dijkstra starts at (A=0, B=infinity, C=infinity, D=infinity). Settle A for (0,4,1,infinity). Settle C, updating B to 1 + 2 = 3 and D to 1 + 5 = 6, for (0,3,1,6). Settle B and update D to 3 + 1 = 4. The path is A->C->B->D, weight 1 + 2 + 1 = 4.

All weights are non-negative, so a vertex's distance is final when it leaves the min-heap. Adjacency lists and a binary heap give O((V+E) log V) time and O(V+E) space.

Use BFS for unweighted graphs in O(V+E), Bellman-Ford for possible negative edges in O(VE), and topological relaxation for a DAG in O(V+E), even with negative weights. For reachability alone, use DFS or BFS.

When the data structure changes the algorithm

Question: Find the third-largest value in stream [5, 1, 9, 3, 14, 8] without sorting the whole stream.

Keep a size-3 min-heap. Its logical contents progress {1,5,9}, {3,5,9}, {5,9,14}, then {8,9,14} as 3, 14 and 8 replace the root. Root 8 is third-largest. This takes O(n log k) time and O(k) space, versus O(n log n) sorting.

Clarify duplicates: in [9, 9, 8, 7], third-largest with duplicates is 8, but third-largest distinct is 7. The distinct version also needs a set.

Use a hash table for expected constant-time membership, heap for repeated extrema, balanced tree for ordered updates, and disjoint-set union for connectivity merges. Name the required operation before calling one structure best.

Interview-answer traps and how to repair them

Silent coding hides the baseline, invariant and edge cases. Say: "Brute force checks every pair in O(n^2). Because I need original indices and n can be 100,000, I will scan once with a complement hash table in expected O(n) time and O(n) space. I will define duplicate and same-index behaviour before coding."

Treat service-based and product-based depth differences as possibilities, not hiring rules. Check each employer's current recruitment material.

A seven-day DSA practice plan

Recall five lines: constraints; baseline; data structure or paradigm; correctness invariant; then time, space and edge cases.

• Day 1: complexity and hashing.

• Day 2: sorting and binary search.

• Day 3: stacks, queues, trees and heaps.

• Day 4: graphs.

• Day 5: greedy and DP.

• Day 6: one fundamentals-first mock and one follow-up-heavy mock.

• Day 7: review mistakes and solve a mixed set of cross-concept questions.

If you miss a day, move that block forward instead of doubling the next day. For focused data structures and algorithms, continue with DSA Using Java. For broader multi-language placement coding, use Coding For Placements. You can compare the available paths in Coding & Skill Development Courses.

Cross-concept questions become manageable when you can explain why an approach fits and when it stops fitting. Practise that explanation aloud before you practise typing faster.