Greedy Correctness Proof round·Engineering·Hard·20 min

TCS Prime Software Engineer — Greedy Correctness Proof

Q: What does the TCS Prime greedy and interval coding round actually test?

It tests whether you can do more than write a working greedy solution. You code an interval problem, such as minimum meeting rooms, and a greedy problem, such as the jump game, and then defend why the greedy choice is correct. The panel pushes on the exchange argument for earliest finish time, asks you to dry-run your code on a sample input, and probes when greedy fails and you must switch to dynamic programming. Stating an optimal approach plus its time and space complexity is the bar, not just passing test cases.

Q: How should I structure my answer in this round?

Talk before you type. First state your strategy in one or two sentences, including how you will sort the input and why. Then sketch the interval timeline on the whiteboard so the interviewer can see the overlaps. Write the code, then dry-run it aloud on the sample input. Finish by stating the time and space complexity and naming the dominant operation. When asked why the greedy choice is optimal, give an exchange argument rather than just asserting that it works.

Q: What are the most common mistakes candidates make here?

The biggest mistake is writing correct code but being unable to say why the greedy choice is optimal. Other frequent errors: sorting activities by start time instead of finish time and not noticing, stating a complexity like O of n log n without dry-running to back it up, treating greedy as always correct, and going silent under pressure instead of thinking aloud. Candidates who cannot produce a counter-example for the wrong greedy choice usually lose the round.

Q: How is this AI interviewer different from a real TCS panel?

The behaviour mirrors the real advanced coding panel closely. The AI plays Vikram, a senior engineer, who probes every claim and refuses to accept an answer without a follow-up. The difference is that it never gives mid-interview praise or hints at the outcome, it gives you the full 20 minutes regardless, and it produces a written scorecard afterwards naming the exact step where your reasoning broke. A real panel rarely tells you that.

Q: How is the scoring done in this practice round?

Your transcript and your whiteboard are scored against named dimensions such as greedy correctness justification, interval modelling, complexity honesty, and dry-run discipline. The vision pass checks whether your drawn timeline matches your spoken explanation and whether you annotated the complexity. You are scored on applied reasoning, not on accent or fluency, and multiple valid approaches that are correct score equally.

Q: What should I do in the first two minutes of this round?

Read the interval problem on the canvas card, restate it in your own words to confirm scope, and then state your strategy out loud before writing anything. Pull up the whiteboard and draw a few sample intervals on a timeline. Say how you intend to sort them and why that ordering helps. Do not start coding immediately. The panel differentiates strong candidates in these first two minutes by whether they diagnose the structure before prescribing a solution.

Q: How do I handle being asked to prove the greedy never breaks?

Use an exchange argument. Assume some optimal solution does not make the greedy choice first, then show you can swap the greedy choice in without making the solution worse, which means a solution that does make the greedy choice is at least as good. For interval scheduling, argue that picking the earliest-finishing activity leaves the most room for the rest. Then contrast with a problem like zero-one knapsack where this swap fails, which is why you need a dynamic-programming table there.

Q: What does a strong answer sound like in this round?

A strong candidate says the strategy first: sort by finish time, scan once, keep the last finishing time. They draw the timeline, point at the overlap, and explain that earliest finish leaves maximum room. When pushed they give an exchange argument, then construct the input where sorting by start time fails. They state O of n log n dominated by the sort, dry-run it on the sample, and name a case like coin change with arbitrary denominations where greedy breaks and dynamic programming is required.

Q: Which greedy and interval problems should I revise before this round?

Revise activity selection and why earliest finish time is optimal, merging overlapping intervals after sorting, the minimum number of platforms or meeting rooms using arrival and departure events, the jump game for reachability and minimum jumps, and the gas-station circuit. Also revise one or two problems where greedy fails, such as zero-one knapsack and coin change with arbitrary denominations, so you can articulate the boundary between greedy and dynamic programming.

Q: Is this useful if I am targeting TCS Digital rather than Prime?

Yes. Clearing the Advanced section, which includes Advanced Coding, is required for both TCS Digital and TCS Prime, so the same greedy and interval material applies. The Prime bar is stricter on the correctness justification, so practising at this altitude prepares you well for Digital and gives you headroom. The habit of stating an optimal approach with its complexity and dry-running it helps in any Tier-1 IT-services coding panel.

20 min · 1 credit · scorecard at the end

ZeroPitch Research Desk

Updated 2026-06-11 · 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-11

How to prepare

What this round tests, what strong and weak answers sound like, and the traps to sidestep.

What this round is about

Topic focus. Two medium-hard problems, one interval-scheduling and one greedy array problem, at the proof-of-correctness altitude where working code alone is not enough.
Conversation dynamic. A senior engineer on the Prime coding panel makes you justify the greedy choice, not just run it, and pushes for a counter-example when you assert optimality.
What gets tested. Whether you can sort the input correctly, give an exchange argument for why earliest finish time wins, dry-run your code, and say when greedy breaks and dynamic programming takes over.
Round format. You think aloud, draw the interval timeline on the whiteboard, write code on the canvas cards, and defend it verbally as the panel probes.

What strong answers look like

Strategy before syntax. You say how you will sort the intervals and why before writing a line, for example sort by finish time and scan once keeping the last finishing time.
Real exchange argument. You argue that if an optimal schedule skips the earliest-finishing activity, you can swap it in and be no worse off, so earliest finish is safe.
Honest complexity. You state O of n log n dominated by the sort, point at the dominant operation, and dry-run it on the sample input rather than asserting the running time.
Knows the boundary. You name a case like zero-one knapsack or coin change with arbitrary denominations where greedy fails and you switch to a dynamic-programming table.

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

Code without a why. Writing a correct greedy and then having nothing when asked why it is optimal. Rehearse the swap argument so the justification is automatic.
Wrong sort key. Sorting activity selection by start time and not noticing. Always ask yourself which key leaves the most room for the rest.
Unbacked complexity. Saying O of n log n with no dry-run to support it. Trace one small input out loud and let the count produce the bound.
Greedy as a hammer. Treating greedy as always correct. Keep one failure case ready so you can mark the line where dynamic programming is required.

Pre-interview checklist (2 minutes before you start)

Recall the interval setup. Have the minimum-rooms model ready: sort arrival and departure events and sweep to count concurrent meetings.
Re-read the swap argument. Be able to state in one breath why picking the earliest finish never hurts the rest of the schedule.
Pull up the jump-game greedy. Recall tracking the farthest reachable index and only jumping when you hit the end of the current range.
Identify one greedy-fails case. Have zero-one knapsack or arbitrary-denomination coin change ready as the dynamic-programming boundary.
Think of a dry-run habit. Plan to trace your code on the given sample before you claim it is correct.

How the AI behaves

Probes every claim. Asks for the underlying argument and the dry-run, not the headline complexity, and never accepts a first answer without a follow-up.
No mid-interview praise. It will not say great answer or validate you; it acknowledges what you said and pushes further.
Interrupts on hand-waving. When you assert optimality without an argument, it stops and asks you to construct the input where the naive choice fails.
Redirects, never teaches. If you freeze, it narrows to one sub-step and asks you to think aloud rather than giving you the algorithm.

Common traps in this type of round

Silent thinking. Going quiet for long stretches; the panel reads silence as not knowing, so narrate your reasoning.
Start-time sort trap. Defaulting to sorting by start time for activity selection and never reconsidering the key.
Asserted optimality. Claiming the greedy is correct with no swap argument and no counter-example for the alternative.
Complexity without trace. Quoting a running time you never validated by dry-running a small input.
Diagram-talk mismatch. Saying one thing about the overlap while the drawn timeline shows another, with no reconciliation.
Greedy everywhere. Failing to name any problem where greedy breaks and dynamic programming is mandatory.

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.

1Minimum Meeting Rooms (Interval Scheduling)
You are given a list of meetings, each with a start time and an end time. Find the minimum number of rooms required so that no two overlapping meetings are assigned to the same room. A meeting that starts exactly when another ends does not overlap with it and may reuse the room. Equivalently, this is the minimum number of railway platforms needed for a set of train arrivals and departures.
Example inputmeetings = [[0, 30], [5, 10], [15, 20]]
Example output2
- 1 <= number of meetings <= 10^5
- 0 <= start < end <= 10^9
- Touching endpoints (one meeting ends exactly when another starts) are not an overlap
- On the whiteboard: draw the meetings on a timeline, then sort the arrival and departure events and sweep them to mark the moment of maximum overlap, that count is your answer.
2Jump Game (Reachability and Minimum Jumps)
You are given an array of non-negative integers where each value is the maximum number of steps you can jump forward from that index. First decide whether you can reach the last index starting from index zero. Then find the minimum number of jumps needed to reach the last index, assuming it is reachable. Be ready to justify why the greedy scan is optimal and how it compares to a dynamic-programming solution.
Example inputarr = [2, 3, 1, 1, 4]
Example outputreachable = true, minimum jumps = 2
- 1 <= array length <= 10^4
- 0 <= arr[i] <= 10^5
- A zero value blocks forward progress unless an earlier index can jump over it
- On the whiteboard: write the array, then under each index annotate the farthest reachable position so far and circle the index where you are forced to spend a jump.

Reference

The full breakdown

How you're scored, the questions candidates ask most, and the research this interview is built on. Skim it — or just start the interview.

Interview framework

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

Greedy Correctness Justification

Whether you prove the greedy choice with a swap or exchange argument and a counter-example, not just assert that the code works.

28%

Interval Modelling

How cleanly you turn meetings into sorted events and count concurrent overlaps instead of comparing every pair.

20%

Greedy Versus Dp Boundary

Whether you can name where the locally best choice fails and switch to a dynamic-programming table with a reason.

18%

Complexity Honesty

Whether you state the running time, name the dominant step, and back it with a dry-run rather than reciting a bound.

16%

Dry-run Discipline

Whether you trace your logic on a concrete sample input out loud before claiming it is correct.

10%

Reasoning Out Loud

Whether you keep narrating your thinking under pressure instead of going silent while you work.

What we evaluate

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

Common questions

What does the TCS Prime greedy and interval coding round actually test?

It tests whether you can do more than write a working greedy solution. You code an interval problem, such as minimum meeting rooms, and a greedy problem, such as the jump game, and then defend why the greedy choice is correct. The panel pushes on the exchange argument for earliest finish time, asks you to dry-run your code on a sample input, and probes when greedy fails and you must switch to dynamic programming. Stating an optimal approach plus its time and space complexity is the bar, not just passing test cases.

How should I structure my answer in this round?

Talk before you type. First state your strategy in one or two sentences, including how you will sort the input and why. Then sketch the interval timeline on the whiteboard so the interviewer can see the overlaps. Write the code, then dry-run it aloud on the sample input. Finish by stating the time and space complexity and naming the dominant operation. When asked why the greedy choice is optimal, give an exchange argument rather than just asserting that it works.

What are the most common mistakes candidates make here?

The biggest mistake is writing correct code but being unable to say why the greedy choice is optimal. Other frequent errors: sorting activities by start time instead of finish time and not noticing, stating a complexity like O of n log n without dry-running to back it up, treating greedy as always correct, and going silent under pressure instead of thinking aloud. Candidates who cannot produce a counter-example for the wrong greedy choice usually lose the round.

How is this AI interviewer different from a real TCS panel?

The behaviour mirrors the real advanced coding panel closely. The AI plays Vikram, a senior engineer, who probes every claim and refuses to accept an answer without a follow-up. The difference is that it never gives mid-interview praise or hints at the outcome, it gives you the full 20 minutes regardless, and it produces a written scorecard afterwards naming the exact step where your reasoning broke. A real panel rarely tells you that.

How is the scoring done in this practice round?

Your transcript and your whiteboard are scored against named dimensions such as greedy correctness justification, interval modelling, complexity honesty, and dry-run discipline. The vision pass checks whether your drawn timeline matches your spoken explanation and whether you annotated the complexity. You are scored on applied reasoning, not on accent or fluency, and multiple valid approaches that are correct score equally.

What should I do in the first two minutes of this round?

Read the interval problem on the canvas card, restate it in your own words to confirm scope, and then state your strategy out loud before writing anything. Pull up the whiteboard and draw a few sample intervals on a timeline. Say how you intend to sort them and why that ordering helps. Do not start coding immediately. The panel differentiates strong candidates in these first two minutes by whether they diagnose the structure before prescribing a solution.

How do I handle being asked to prove the greedy never breaks?

Use an exchange argument. Assume some optimal solution does not make the greedy choice first, then show you can swap the greedy choice in without making the solution worse, which means a solution that does make the greedy choice is at least as good. For interval scheduling, argue that picking the earliest-finishing activity leaves the most room for the rest. Then contrast with a problem like zero-one knapsack where this swap fails, which is why you need a dynamic-programming table there.

What does a strong answer sound like in this round?

A strong candidate says the strategy first: sort by finish time, scan once, keep the last finishing time. They draw the timeline, point at the overlap, and explain that earliest finish leaves maximum room. When pushed they give an exchange argument, then construct the input where sorting by start time fails. They state O of n log n dominated by the sort, dry-run it on the sample, and name a case like coin change with arbitrary denominations where greedy breaks and dynamic programming is required.

Which greedy and interval problems should I revise before this round?

Revise activity selection and why earliest finish time is optimal, merging overlapping intervals after sorting, the minimum number of platforms or meeting rooms using arrival and departure events, the jump game for reachability and minimum jumps, and the gas-station circuit. Also revise one or two problems where greedy fails, such as zero-one knapsack and coin change with arbitrary denominations, so you can articulate the boundary between greedy and dynamic programming.

Is this useful if I am targeting TCS Digital rather than Prime?

Yes. Clearing the Advanced section, which includes Advanced Coding, is required for both TCS Digital and TCS Prime, so the same greedy and interval material applies. The Prime bar is stricter on the correctness justification, so practising at this altitude prepares you well for Digital and gives you headroom. The habit of stating an optimal approach with its complexity and dry-running it helps in any Tier-1 IT-services coding panel.

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.