Graphs, DP and Backtracking round·Engineering·Hard·20 min

Tata Consultancy Services Prime Coding Drill — Graphs, DP and Backtracking

20 min · 1 credit · scorecard at the end
Z
ZeroPitch Research Desk
Updated 2026-06-09 · Newly added · be among the first to take it
Field
Engineering
Company
Tata Consultancy Services
Role
Prime Software Engineer
Duration
20 min
Difficulty
Hard
Completions
New
Updated
2026-06-09

What this round is about

This is a simulation of the TCS Prime technical interview — the coding drill that gates the Rs 9-11.5 LPA Prime offer and separates Prime candidates from the Digital band. You will face two hard DSA problems: Number of Islands (graph and grid traversal) and Coin Change (dynamic programming). The AI interviewer plays a senior TCS architect who probes the way real Prime interviewers do: constraint clarification first, then approach justification, then code, then tight Big-O, then one curveball follow-up. The whiteboard is live — use it to sketch the grid, the BFS queue state, and the DP table. The interviewer can see what you draw.

What strong answers look like

A strong candidate starts every problem by asking at least one constraint question (grid size? diagonal adjacency? coin denominations bounded?). They then name the algorithm and justify it over the alternative before writing a single line of code. For graph problems, they trace the BFS or DFS traversal on the example grid, naming what goes into the queue at each step. For DP problems, they derive the recurrence independently — dp[a] = min(dp[a], 1 + dp[a-c]) — by reasoning from the definition of dp[a], not by reciting a memorized formula. They give two complexity answers: one for time, one for space, with the dominant operation identified. When the curveball comes (space optimization, weighted graph, diagonal adjacency), they adapt calmly and reason through the change rather than freezing.

What weak answers look like (and how to avoid them)

The most common rejection pattern is jumping straight into code without asking a single constraint question. The interviewer will interrupt you and it signals poor engineering judgment. The second most common is stating a complexity without justifying it. Greedy for coin change is another trap: if you pick the largest coin each time for coins like 1, 3, 4 with amount 6, you get the wrong answer. Finally, writing BFS or DFS that only starts from one cell and misses disconnected components is a silent bug that kills your output on half the test cases.

Pre-interview checklist (2 minutes before you start)

  • Open the whiteboard panel — you will need it for the grid trace and the DP table.
  • Remind yourself: clarify constraints before coding, always.
  • Know the BFS recurrence: mark cell visited, add unvisited neighbors to queue. Know the DP recurrence: dp[0] = 0, dp[a] = min(1 + dp[a-c]) for each coin c.
  • Have ready: a counterexample where greedy fails for coin change (coins = [1,3,4], amount = 6 — greedy gives 4+1+1=3, optimal is 3+3=2).
  • Know why BFS space can be O(min(rows,cols)) while DFS space can be O(rows*cols).

How the AI behaves

The AI plays Vikram Iyer, a senior TCS architect with 14 years of experience running Prime screening panels. He will interrupt you if you start coding without clarifying constraints. He will ask you to trace through the example input on the whiteboard. He will push back if your complexity analysis is wrong or insufficiently justified. He will give one curveball follow-up per problem. He does not soften corrections and he does not say great job to an average answer. Treat this exactly as you would treat a real Prime technical round.

Common traps in this type of round

Starting to code before clarifying: the interviewer will interrupt you and it is a mark against you. Giving the complexity without the justification: O(rows*cols) is incomplete without explaining why each cell is visited at most once. Missing the outer loop for disconnected components: your BFS starting from row 0 col 0 finds the first island but misses islands in other rows. Using greedy for coin change without testing a counterexample. Freezing on the curveball: the weighted graph follow-up or space-optimization question is not meant to trick you — reason aloud about what changes.

Sample problems you'll face

The 2 problems below are the same ones you'll work through in the live session — no surprises. Read the constraints carefully; the AI persona will refer you to the on-canvas card by problem number.

  1. 1Number of Islands (Graph / Grid Traversal)

    Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically. Solve with BFS or DFS and give the complexity.

    Example inputgrid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]
    Example output2
    • 1 <= rows, cols <= 300
    • Mark visited cells (flip to '0' or use a visited set) to avoid recounting
    • State time O(rows*cols) and the worst-case space for the BFS queue or DFS recursion
    • Be ready to discuss what changes if diagonal adjacency also counts
    • Use the on-canvas card to read the prompt; sketch the grid and the traversal on the whiteboard. The AI sees what you draw.
  2. 2Coin Change — Minimum Coins (Dynamic Programming)

    Given coin denominations and a target amount, return the minimum number of coins needed to make the amount, or -1 if it cannot be formed. Derive the DP recurrence before coding. Be ready to extend to a recursion-with-memo or backtracking explanation if asked.

    Example inputcoins = [1, 2, 5], amount = 11
    Example output3 (5 + 5 + 1)
    • 1 <= coins.length <= 12; amount up to 10^4
    • Define dp[a] = min coins to form amount a; dp[0] = 0; build bottom-up
    • State time O(amount * coins) and space O(amount)
    • Contrast the greedy approach and give a coin set where greedy fails
    • Use the on-canvas card to read the prompt; sketch the DP table on the whiteboard. The AI sees what you draw.

Interview framework

You will be scored on these 5 dimensions. The full rubric with definitions is below.

Constraint Clarification
Did the candidate ask at least one meaningful constraint question before coding each problem?
20%
Algorithm Justification
Did the candidate name the algorithm and justify the choice over the alternative before implementation?
20%
Recurrence And Traversal Derivation
Did the candidate independently derive the DP recurrence or trace the BFS/DFS traversal, rather than reciting from memory?
25%
Complexity Analysis Precision
Did the candidate state correct Big-O for time and space with a clear justification for both problems?
20%
Curveball Adaptability
Did the candidate handle the follow-up extension (space optimization, weighted graph, diagonal adjacency) without freezing?
15%

What we evaluate

Your final scorecard breaks down across these dimensions. The full rubric and tier criteria are revealed inside the interview itself.

  • Constraint Clarification Discipline20%
  • Algorithm Approach Verbalization20%
  • Recurrence and Traversal Derivation25%
  • Complexity Analysis Precision20%
  • Curveball Adaptability10%
  • Implementation Correctness5%

Common questions

What DSA topics does the TCS Prime technical interview cover in 2026?
The TCS Prime technical interview in 2026 focuses on hard DSA — specifically graph traversal (BFS, DFS, Number of Islands, Course Schedule), dynamic programming (Coin Change, LCS, House Robber, Unique Paths), and backtracking (N-Queens, subsets, permutations). Only the top 1-2 percent of NQT performers receive a Prime interview call.
What is the difference between TCS Prime and TCS Digital for India freshers?
TCS Prime offers Rs 9 LPA for UG and Rs 11.5 LPA for PG freshers, compared to Rs 7-7.9 LPA for Digital. The Prime bar requires solving all three NQT advanced coding problems including hard DSA on graphs and DP. The Prime technical interview is significantly harder and includes complexity analysis and approach-defense follow-ups.
How do I solve Number of Islands in a TCS Prime interview?
Start by clarifying whether adjacency is 4-directional or 8-directional and the grid size. Use BFS with a queue or DFS with recursion, marking visited cells by flipping them to zero or using a visited set. The outer loop over all cells handles disconnected components. Time complexity is O(rows*cols); BFS queue space is O(min(rows,cols)) and DFS recursion stack is O(rows*cols) worst case.
How do I derive the Coin Change recurrence for a TCS interview?
Define dp[a] as the minimum number of coins needed to form amount a. Base case: dp[0] = 0. For each amount a from 1 to target, iterate over all coins c: if a minus c is reachable, dp[a] = min(dp[a], 1 + dp[a-c]). This gives O(amount*coins) time and O(amount) space. Greedy fails for non-canonical coin sets — test with coins [1,3,4] and amount 6.
What is the TCS NQT Prime package for 2026?
The TCS NQT Prime package for 2026 is Rs 9 LPA for UG candidates (B.Tech, B.E.) and Rs 11.5 LPA for PG candidates (M.Tech, MCA). Only the top 1-2 percent of NQT test-takers qualify for the Prime interview, roughly 1,000-2,000 candidates from 50,000-80,000 applicants per cycle.
Why does greedy fail for the Coin Change problem?
Greedy picks the largest coin that fits at each step. For canonical coin sets like [1,5,10,25] this works, but for coins like [1,3,4] with amount 6, greedy picks 4+1+1 = 3 coins while the optimal is 3+3 = 2 coins. Dynamic programming considers all sub-problems and finds the globally optimal solution.
How many coding problems are in the TCS Prime technical interview?
Candidates typically face 1-2 hard DSA coding problems in the TCS Prime technical interview, plus questions on OOP, DBMS, and their final year project. The technical round lasts 45-60 minutes. For each coding problem, the interviewer expects constraint clarification, algorithm justification, recurrence derivation or traversal trace, clean implementation, tight Big-O, and one curveball follow-up.
What is the pass rate for TCS Prime in the NQT campus drive?
The TCS Prime selection rate is approximately 1-2 percent of NQT test-takers, with roughly 1,000-2,000 Prime offers extended per hiring cycle out of 50,000-80,000 candidates who take the NQT. The Prime bar requires solving all three advanced NQT coding problems and passing a hard technical interview with a senior TCS engineer.
What follow-up questions does a TCS Prime interviewer ask after coding?
Standard TCS Prime follow-ups include: what is the time and space complexity and why; can you reduce the space complexity (for DP problems); what changes if the graph is weighted or directed (for graph problems); what changes if diagonal adjacency counts (for grid problems); and why does greedy fail for this coin set. These follow-ups are the main differentiator between a Prime and a Digital candidate.
How should I prepare for TCS Prime coding interviews in India?
Focus on LeetCode Medium-Hard problems in three categories: graph traversal (Number of Islands, Course Schedule, Topological Sort), dynamic programming (Coin Change, LCS, House Robber, Unique Paths), and backtracking (N-Queens, subsets, permutations). For each problem, practice the clarify-approach-derive-code-complexity-defend sequence. Use TakeUforward, GeeksforGeeks, and PrepInsta for TCS-specific preparation materials.
What is the difference between BFS and DFS for graph interview questions in TCS?
BFS uses a queue and processes nodes level by level, giving O(min(rows,cols)) queue space for grid problems. DFS uses a recursion stack which can be O(rows*cols) deep for large grids and carries a stack overflow risk. BFS finds shortest paths in unweighted graphs; DFS is simpler to code for flood-fill and cycle detection. TCS Prime interviewers expect you to justify your choice between them.
Can I use memoization instead of bottom-up DP in a TCS Prime interview?
Yes — top-down memoization and bottom-up tabulation are both acceptable. Memoization makes the subproblem structure more visible and is often easier to derive first. Bottom-up is typically more space-efficient and avoids recursion overhead. TCS Prime interviewers want to see that you can derive the recurrence either way; if you use memoization, be ready to convert to bottom-up if asked about space optimization.

Sources this interview is built on

Real candidate-report URLs (Glassdoor / AmbitionBox / PrepInsta / GeeksforGeeks / Medium) reviewed when authoring the questions, persona, and rubric. Verify the realism yourself.