Top-K Heap Under a Clock round·Engineering·Hard·20 min

TCS Digital Engineer Interview — Top-K Heap Under a Clock

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: Digital Software Engineer Trainee
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 heap and priority-queue problems on the canvas: the kth largest element of an unsorted array, then the running median of a stream of numbers.
Conversation dynamic. The interviewer asks for your first idea, lets you propose sorting everything, then pushes on whether the whole array needs sorting to nudge you toward a heap of size k.
What gets tested. Whether you state time and space complexity before coding, justify a min-heap over a max-heap, and reach for two heaps when you hear the word stream.
Round format. A twenty-minute spoken drill with a shared whiteboard where you draw the heap as a tree and trace a small example.

What strong answers look like

Brute force first, with a number. You open with sort descending and index to k, then say that costs order n log n, before writing anything.
Pattern recognition. You hear kth largest and reach for a heap of size k at order n log k without being dragged there.
Choice justified. You say a min-heap keeps the kth largest at the root so you can evict the smallest of your current k cheaply.
Trace on the board. You draw the heap as a tree and dry-run five or six numbers, catching your own off-by-one.

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

Code before approach. Writing the loop before saying the plan or the complexity; say the approach and the cost out loud first.
Heap named, not defended. Saying use a heap but not why a heap beats a sort; tie the choice to evicting the smallest cheaply.
Sort the whole thing. Sorting the full array when only the k largest are needed; ask whether you need everything sorted.
Silence under pushback. Going quiet when challenged; keep thinking out loud so the interviewer can follow.

Pre-interview checklist (2 minutes before you start)

Recall the size-k trick. Push each element into a min-heap and pop when it grows past k, leaving the kth largest at the root.
Have the two-heap median ready. A max-heap for the smaller half, a min-heap for the larger half, kept balanced.
Pull up the whiteboard. Be ready to draw the heap as a tree, not just talk about it.
Identify your baseline. Decide the brute-force sort cost for kth largest so you can state it immediately.
Think of quickselect. Have the average linear time partition argument ready for the follow-up.

How the AI behaves

Probes every answer. Asks for the complexity and the reason behind the data structure, not just the headline idea.
No mid-interview praise. Will not say great answer; it acknowledges the specific point you made and pushes further.
Interrupts on code-first. Pushes you back to the approach and the complexity if you start writing the loop too early.
Escalates when you are clear. Brings up quickselect and the streaming median once you are reasoning out loud.

Common traps in this type of round

Complexity stated wrong. Calling the heap-of-size-k solution order n log n instead of order n log k.
Wrong heap polarity. Using a max-heap of size k for the k largest and making eviction of the smallest expensive.
No invariant. Describing two heaps for the median without saying the sizes differ by at most one.
Skipping the dry run. Declaring the code correct without tracing it on a small example.
Quickselect worst case ignored. Claiming quickselect is always linear without noting the order n squared worst case unless the pivot is randomised.
Stream cue missed. Re-sorting the whole history on every new number instead of maintaining the two heaps.

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.

1Kth Largest Element in an Array
You are given a large unsorted array of integers nums and an integer k. Return the kth largest element in the array. Note that it is the kth largest in sorted order, not the kth distinct element. Start by stating your brute-force approach and its complexity, then optimise. Do we need the whole array sorted just to know the kth largest?
Example inputnums = [3, 2, 1, 5, 6, 4], k = 2
Example output5
- 1 <= k <= length of nums <= 1,000,000
- Array values can repeat; the kth largest counts duplicates by position, not by distinct value
- State time and space complexity for every approach before coding
- On the whiteboard: draw the min-heap of size k as a tree, label the root, and trace one push and pop as a bigger element arrives
2Find Median From a Data Stream
Numbers arrive one at a time as a stream. After each new number, return the median of all numbers seen so far. The median is the middle value if the count is odd, or the average of the two middle values if the count is even. Keep the median cheap to read on every arrival without re-sorting the whole history.
Example inputaddNum(1), addNum(2) -> median 1.5, then addNum(3) -> median 2
Example output1.5, then 2
- Up to 1,000,000 numbers may stream in, so re-sorting on every arrival is too slow
- Insertion should be order log n and reading the median should be order one
- State the balancing invariant out loud before coding
- On the whiteboard: draw the max-heap for the smaller half and the min-heap for the larger half side by side, label both roots, and show which root gives the median

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.

Brute-force To Optimal Path

Whether you start from a sort-everything baseline, price it, then move yourself to the heap solution rather than waiting to be dragged there.

20%

Complexity Reasoning

How accurately you state time and space costs, like order n log k for the heap of size k, and update them as the approach changes.

20%

Data-structure Justification

Whether you defend min-heap over max-heap by tying it to evicting the smallest cheaply, not just naming the structure.

20%

Whiteboard Trace Fidelity

Whether your drawn heap tree and your spoken walkthrough agree when you push and pop a sample element.

15%

Streaming Pattern Recognition

Whether the word stream makes you reach for two heaps and state the at-most-one balancing invariant.

15%

Edge-case Awareness

Whether you catch inputs that break your code, like k larger than the array, duplicates, or an empty stream.

10%

What we evaluate

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

Brute-Force To Heap Optimisation Path20%
Time And Space Complexity Accuracy20%
Min Versus Max Heap Justification18%
Whiteboard Trace Alignment15%
Streaming Two-Heap Invariant15%
Edge-Case And Correctness Discipline12%

Common questions

What does the TCS Digital heaps and priority-queue round actually test?

It tests whether you can move from a brute-force idea to an optimal one under time pressure, not whether you have memorised heap code. The interviewer gives you a top-k problem, finding the kth largest element, and expects you to first propose sorting the whole array, state that it is order n log n, then improve it to a min-heap of size k at order n log k. A second problem, the running median of a stream, checks if you reach for two heaps. Throughout, you must state time and space complexity and justify the data structure you pick over a plain sort.

How should I structure my answer when the interviewer gives me the problem?

Say the brute-force approach first and name its complexity out loud before you write anything. For kth largest, that is sort descending and index to k, which is order n log n. Then ask yourself whether you need the whole array sorted, which opens the door to a heap of size k. State the new time and space complexity, draw the heap as a tree on the whiteboard, and dry-run it on five or six numbers. Finishing with a correctness trace on a small example is what separates a strong answer from a memorised one.

What are the most common mistakes candidates make in this round?

The biggest one is jumping straight to writing code without stating the approach or the complexity, which leaves the interviewer unable to follow your reasoning. The second is naming a heap but being unable to say why a heap beats a full sort here. The third is defaulting to sorting the entire array when only the k largest are needed and never noticing the waste. Candidates also freeze when pushed back on, instead of thinking out loud, and they skip dry-running their own code, so off-by-one errors go uncaught.

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

It behaves like a Digital-tier tech lead, not a friendly panel. It probes every answer at least once, it never offers mid-interview praise, and it interrupts the moment you write code before stating an approach. It adapts: if you reason out loud and name complexities, it escalates to harder follow-ups like quickselect and the streaming median. If you struggle, it simplifies the question once and gives you a fair second chance, but it never hands you the answer. Unlike a human panel, it produces a transcript-backed scorecard afterwards.

How is scoring done in this practice round?

Your transcript is scored against dimensions that mirror what a Digital interviewer grades: whether you recognised the top-k cue and reached for a heap, whether your stated time and space complexity were correct, whether you justified min-heap versus max-heap, whether your whiteboard trace matched your verbal walkthrough, and whether you dry-ran your code. Each dimension has observable signals, so two reviewers would land within a few points. The report names the exact moment a complexity claim or a data-structure choice did not hold up.

What should I do in the first two minutes before I start?

Recall the heap-size-k trick for top-k: push every element into a min-heap and pop the smallest whenever the heap grows past k, leaving the kth largest at the root. Have the two-heap median pattern ready, a max-heap for the smaller half and a min-heap for the larger half. Pull up the two problem cards on your canvas and open the whiteboard so you can draw the heap as a tree. Re-read the kth largest prompt and decide your brute-force baseline before the interviewer finishes talking.

How do I justify choosing a min-heap over a max-heap for the kth largest?

To keep the k largest elements you need to discard the smallest of your current k cheaply whenever a bigger element arrives. A min-heap puts the smallest of the k at the root, so popping it is order log k and the kth largest ends up at the root once all elements are processed. A max-heap of size k would put the largest at the root, which makes evicting the smallest expensive, so it does not fit the keep-the-k-largest goal. Saying this tradeoff out loud is exactly what the interviewer is listening for.

When does quickselect beat a heap for the kth largest element?

Quickselect, the partition-based selection algorithm, runs in average linear time when the entire array is available in memory at once, because it only recurses into the side of the pivot that contains the kth position. A heap of size k is order n log k and shines when data arrives as a stream or k is small relative to n. So if all the data is in memory and k is large, quickselect is usually faster on average, with the caveat that its worst case is order n squared unless you randomise the pivot. Naming that worst case earns extra credit.

What is the balancing invariant for the two-heap running median?

You hold a max-heap for the smaller half of the numbers seen so far and a min-heap for the larger half. The invariant is that the two heaps differ in size by at most one, and every element in the max-heap is less than or equal to every element in the min-heap. After each insert you rebalance by moving a root across if one side grows too large. The median is then the larger root if one heap has an extra element, or the average of the two roots if the heaps are equal in size. Insertion is order log n and reading the median is order one.

What does a strong answer sound like in this round?

A strong candidate says the brute-force baseline and its complexity in the first sentence, then asks whether the whole array needs sorting, then names a heap of size k and states order n log k and order k space without prompting. They draw the heap as a tree, trace one small example, and justify min-heap over max-heap in terms of evicting the smallest. When pushed, they bring up quickselect and its average linear time, and on the stream problem they state the two-heap balancing invariant. They think out loud the entire time.

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.