Top-K, K-th Element and Median Interview Prep Plan

As of 2026-10-19, TrueInterview's bank holds 30 top-K and median coding questions reported at 13 big-tech companies, and 19 of them were reported in phone screens. A heap tags 17 of the 30 and binary search tags 8. Prepare in stages: counting plus a size-k min-heap, then k closest and k-th selection in sorted or two-array inputs, then the running median, then large-log and distributed follow-ups. The heap is the baseline answer; in the reports we cite, the follow-up after it is where candidates were pushed, the median variants need different techniques, and senior candidates should add the scale version as extra preparation.

Disclosure: TrueInterview is an interview-preparation product and publishes this article. Facts about other products come from their public pages on the dates listed under Sources.

Which top-K and median variants do candidates actually report?

Seven titles carry most of the write-up links, and the list is wider than one frequency problem. Top K Frequent Elements and Distributed Mode and Median lead with 8 write-ups each. Behind them come a largest-elements variant, a stream median, a large-log variant, a two-array median and K Closest Points to Origin. Write-up links measure what candidates reported, not how often a company asks.

Read the table as four techniques, not seven problems. The first, third and last rows are one skill: count or compute a ranking value, then keep the best k in a bounded heap. The median rows need two heaps or binary search instead, and the large-log and distributed rows add a memory or machine boundary on top of everything else.

The bank also holds separate entries under the same Top K Frequent Elements title, with their own company lists, so treat the counts above as belonging to one entry. The second column lists write-up companies only, while the example dated reports come from the bank's company filings, which can be wider: Find Median from Data Stream is also filed under Snowflake. The family is also current: 27 of the 30 questions were last reported within the 12 months before 2026-10-19. You are preparing for what candidates are reporting now, not for an old list.

What should the first stage of top-K prep cover?

Hash-map counting plus a min-heap capped at size k, drilled until you can write it without pausing. PracHub's guide puts the point directly: "Interviews are decided by the selection step that follows it". Heap is also the most common tag on phone-screen questions in our bank, at 9 of 19, so this is the code you are most likely to write first.

PracHub's guide recommends the capped min-heap as the default, at O(n log k) time and O(k) extra space beyond the counts, and notes that it still works on a stream. The Python documentation says the smallest element of a min-heap is always at heap[0], which is the element you evict. The same documentation says heapreplace does the pop and push in one step and can suit a fixed-size heap better.

Know the alternatives well enough to dismiss them. A Level Up Coding article describes the brute-force answer as sorting and taking the element at the Kth place, which costs O(N log N) because of the sort. Design Gurus' solution page gives building a max-heap of all unique elements and popping k times as O(n + k log n), and notes that the size-k heap approaches O(n log n) when k is close to n.

Then expect the follow-up. PracHub's guide relays a Google report in which, after a working solution, the interviewer asked whether the time could beat O(n log n) and how to reduce space. Design Gurus' page lists the same follow-up for the problem, asking for faster than O(n log n) on large inputs. Treat that as a single candidate's report plus the problem's own follow-up, not a rule for every interviewer.

Fluency matters as much as the idea. PracHub's guide relays an Amazon report in which the candidate solved a most-frequent-values problem by brute force, was told to rewrite it with a heap, and ran out of time mid-rewrite. PracHub reads that pattern as unfamiliarity at companies that calibrate on LeetCode 347, where the heap is the baseline competent answer.

Our take: the generic advice says to learn three solutions. We would rather you write one solution from memory and speak the other two. Time yourself on the capped heap until the code takes a few minutes, then rehearse a short spoken answer to the beat-O(n log n) follow-up that names bucket sort and quickselect and the condition each needs.

When should you use a heap, bucket sort, quickselect or sorting?

Use the size-k heap by default when k is small or the data streams, bucket sort only when the ranking value is a bounded integer count, quickselect when the data sits in memory and you can state its worst case, and sorting when inputs are moderate. PracHub's guide says the signal is choosing for the constraints and saying why the others fit worse.

The verdicts are short. The heap wins the phone screen because it handles every input shape in the table. Bucket sort wins only on frequencies: PracHub's guide notes it reaches O(n) only because a frequency is an integer between 1 and n, so it stops applying once the ranking value is a distance or a score. Design Gurus' page adds that bucket sort may use more memory and have larger constants than its linear bound suggests. Sorting is the honest baseline, and Wikipedia's selection-algorithm article notes its appeal when the runtime library ships an optimized sort but no selection routine. The same article says that for inputs of moderate size, sorting can beat non-random selection because of smaller constant factors.

Quickselect deserves the most care, because it is where confident candidates overclaim. Wikipedia's quickselect article says it is usually implemented in place and partially sorts the data, and that it recurses into only the side of the partition holding the target. The same article says consistently bad pivots make it quadratic, for example first-element pivots on sorted data, and that a random pivot is the easiest fix, with almost certain linear time. PracHub's guide is blunt about the consequence: "if you propose it, name the worst case and the random-pivot mitigation unprompted, or the follow-up will do it for you." Give quickselect when asked for average linear time, never as a guarantee.

How should you prepare median questions differently from top-K?

Give medians their own sessions, because the data structure changes. A running median needs two balanced heaps, and the median of two sorted arrays needs binary search, not a heap. Find Median from Data Stream alone is filed under 6 companies in the bank, including Snowflake, Meta and Snapchat, so it is worth a full session before your first phone screen.

Wikipedia's selection-algorithm article treats the minimum, median and maximum as special cases of selection, but a stream breaks the top-K approach because the midpoint moves with every insert. The Python documentation describes the fix: "a max-heap for values at or below the midpoint and a min-heap for values above the midpoint." The same documentation says that with equal-sized heaps the median is the average of the two tops, and otherwise it is the top of the larger heap.

Test the even case on purpose. Wikipedia notes that an even count gives two possible medians, depending on rounding, so confirm with the interviewer whether they want the average or one of the middle values. In Python, heapq is a min-heap, and the documentation lists heapify_max as added in version 3.14. On an older interpreter, store negated values in the lower heap and say so before you write it.

Our take: write the invariant before the code: every value in the lower heap is at most every value in the upper heap, and their sizes differ by at most one. A common bug is a rebalance that runs before the new value has gone to the correct heap. If you can state the invariant and test an even-length input, the rest is bookkeeping.

Why is binary search the second technique in this family?

Because a real share of the family has sorted inputs, where a heap is the slow answer. Binary search ties hashing on phone-screen questions, at 6 of 19 each, which makes it the second technique to prepare after the heap. On already-sorted inputs, a heap answer is slower than a binary search, so a heap-only plan leaves the two-sorted-array variants uncovered.

Three titles anchor this stage. Median of Two Sorted Arrays is filed under 3 companies in the bank. K-th Smallest Element in Two Sorted Arrays was reported in an Amazon phone screen in 2026-08, and K Smallest Squared Values in a Sorted Array in an Uber phone screen in 2026-09. Both two-array problems reward the same idea: binary search on how many elements to take from each array, so that the left parts together hold the right count and every left value is at most every right value.

Going by its title, K Smallest Squared Values in a Sorted Array is a sorted-input selection problem where negative values can square larger than positive ones. A two-pointer sweep from both ends, or a binary search for the smallest absolute value followed by an outward merge, avoids sorting again. Practise saying why the input order lets you skip the heap.

Our take: do not spend all your top-K time on heaps. For the two-array median, search over the shorter array, define the partition boundaries with sentinels for empty sides, and test an empty array and arrays of very different lengths. Those three cases expose most off-by-one errors.

Which trade-offs and mistakes should you state before the interviewer asks?

State four things up front: whether bucket sort applies to your ranking value, quickselect's worst case, how ties break, and the output contract. PracHub's guide says tie-breaking rules test whether you can build a comparator, and that they show up as warm-ups at Bytedance and Squarepoint. Each takes one sentence to say and costs a follow-up if you skip it.

Ties are a Python trap as well as a spec question. PracHub's guide notes that (freq, value) tuples work for integers but throw for values with no ordering, and suggests pushing (freq, i, value) with a counter index. The Python documentation says heap elements can be tuples so that a priority sits alongside the record, which is the mechanism behind both the tie-break and the counter.

The output contract is the other silent failure. Wikipedia's selection-algorithm article notes that some versions return the k values in sorted order and others in arbitrary order, and that definitions differ in how ranks are numbered. Ask which one you are solving before you code. For edge cases, Design Gurus' page suggests testing k equal to the number of unique elements and an array where every element is identical.

Our take: check the heap direction before anything else. For the k largest values you keep a min-heap and evict the smallest; for the k closest points you keep a max-heap on distance and evict the farthest. Say the direction and the reason out loud, and the interviewer stops worrying about the rest.

What changes at senior and staff level?

The heap is still expected, but it is no longer the whole test. Senior-or-above candidates link these questions 28 times, against 21 for junior-or-below, by the levels candidates reported on their write-ups. Distributed Mode and Median stands out: all 8 of its write-up links come from senior-or-above candidates, all at Anthropic. Because that signal rests on one question, treat the scale version as likely extra preparation, not a proven deciding factor.

The topic split shows where the senior weight sits. Heap links are even at 15 senior-or-above against 16 junior-or-below, while sorting runs 11 to 2 and hashing 14 to 9. Top K Largest Elements leans junior, with 2 senior-or-above links against 4, and Top K Frequent Elements splits evenly at 4 and 4. Find Median In Large Array was reported in an Airbnb phone screen in 2026-08, and it is filed under 3 companies in the bank.

We do not know what Distributed Mode and Median, Top-K Frequent in Large Logs or Find Median In Large Array require beyond their titles. Going by the titles, practise the case where data is split across parts or too large to hold at once. Mode combines cleanly: per-part counts add up by value, then a size-k heap runs over the merged counts. Median does not: per-part medians do not give the global median, so you need per-part counts below a candidate value and a binary search over the value range, or sorted runs merged in order. The Python documentation describes heapq.merge as merging sorted inputs such as timestamped entries from several log files, which is one building block for the merge route.

Our take: at senior level, the decisions an interviewer is likely to push on are general engineering ones. What is the memory bound per part, and what crosses the network: raw values, counts or summaries? Is an exact answer required, or would an approximate count be acceptable for a top-K over logs? State the single-machine heap answer first, then show how it changes when the data no longer fits.

Down-leveling note (our view): in this family, the scale follow-up is the part most likely to show senior scope, since the senior-only links above sit on the distributed title. A senior candidate who stops at the heap answer shows less of that scope than one who explains how partial results combine.

Which companies should change your prep weighting?

The core stage is the same everywhere, because heap leads the tags at every company with enough questions to compare. Google and Amazon file 9 top-K and median questions each, Uber 8, ByteDance and Meta 7 each, and Anthropic 2. Use the second technique on each row to choose one extra block for your target.

These per-company counts are small, so treat them as a weighting hint rather than a forecast. Google and Uber are where binary search shows up most, so add the sorted-input stage early if either is your target. Amazon's profile leans on heap and hashing, so spend its extra time on counting fluency.

Take a senior engineer with a Google phone screen. The first session is Top K Frequent Elements with a capped heap, ending with a spoken answer to the beat-O(n log n) follow-up. The second is Find Median from Data Stream with two heaps and an even-length test. The third is Median of Two Sorted Arrays by binary search. The fourth is Top-K Frequent in Large Logs, reading the title as counting in parts and merging, with the single-machine answer stated first.

How we counted

Counts come from TrueInterview's question bank as of 2026-10-19 and cover the questions filed as top-K and median coding problems. These are candidate-reported questions reconstructed for practice, not any company's official question list. A question can be filed under several companies and reported in several rounds, so tallies overlap. Write-up links count candidate reports, split by the level each candidate gave, and entries that share a title are counted separately.

FAQ

How do I solve Top K Frequent Elements faster than O(n log n)?

Count with a hash map first. Then either place each value in a bucket indexed by its count and read the buckets from the highest count down, or run quickselect over the unique values with a random pivot. The bucket version is linear in the worst case because counts are bounded; quickselect is linear on average only. In the interview, write the capped heap first, then offer one of these as the follow-up answer and say which condition it depends on, using the decision table above.

Can I use heapq.nlargest in an interview?

Use it after you have shown what it does, not as your opener. PracHub's guide says reasonable interviewers allow it once you have shown you know what it does internally, and calls leading with it a gamble. The Python documentation says nlargest and nsmallest perform best for smaller n and that sorted() is more efficient for larger values. The same documentation suggests turning the iterable into an actual heap if you call these functions repeatedly, and heapify does that in place in linear time.

Is Top K Frequent Elements asked at Meta?

The Meta evidence comes from bank filings rather than linked write-ups. One Top K Frequent Elements entry is filed under Meta among six companies, and Top K Largest Elements is filed under Meta as well. Another entry, Top K Frequent Elements in Integer Array Efficiently, is filed under five companies including Meta but has no linked write-ups. Our suggestion: prepare the core frequency and largest-elements problems fluently for Meta, and treat anything beyond that as general preparation rather than a Meta signal.

How is Top K Frequent Words different?

Treat it as the tie-break version of the same problem. The counting pass and the capped heap are unchanged, but equal counts must be ordered by the word, which means the heap's comparison has to flip the word order relative to the count order when you evict. Write the comparator as a tuple and test two words with the same count before anything else. If the interviewer asks for the result in sorted order, sort the k survivors at the end rather than relying on heap order.

Do I need median of medians for interviews?

Know what it guarantees and why you would not code it. Wikipedia's quickselect article says the median of medians pivot guarantees linear time in the worst case, but computing the pivot is costly enough that it is generally not used in practice. In an interview, the random-pivot answer plus a correct statement of the worst case is what gets credit. Mention median of medians only if the interviewer asks for a guaranteed bound.

Your practice plan

A three-week plan for someone working full time, at about an hour a day:

1. First week, counting and the capped heap. Solve Top K Frequent Elements and Top K Largest Elements from memory with a size-k min-heap, timed, then say your beat-O(n log n) answer aloud.
2. First week, a distance value. Solve K Closest Points to Origin with a max-heap on distance, explain why buckets no longer apply, and write the tie-break into the heap tuple.
3. Second week, the stream median. Build Find Median from Data Stream with two heaps, write the invariant first, and test an even-length input.
4. Second week, sorted inputs. Solve Median of Two Sorted Arrays and K-th Smallest Element in Two Sorted Arrays by binary search; for an Uber target, add K Smallest Squared Values in a Sorted Array.
5. Third week, quickselect out loud. Re-solve Top K Frequent Elements with quickselect and a random pivot, then name the input that makes a first-element pivot quadratic.
6. Third week, the scale version. Work Top-K Frequent in Large Logs and Find Median In Large Array, stating the single-machine answer first; if you are senior or above, or interviewing at Anthropic, add Distributed Mode and Median.
7. Throughout, check against the tests. TrueInterview says every question has a reference solution and that coding answers are judged on hidden tests that show the case you failed; re-run any problem where a hidden test caught a tie or an empty input.

Sources

• TrueInterview question bank — top-K and median at big-tech companies — counted 2026-10-19
• Top K Frequent Elements: Heap vs Quickselect vs Bucket Sort | PracHub Knowledge Hub — checked 2026-10-19
• heapq — Heap queue algorithm — Python 3.15.0 documentation — checked 2026-10-19
• Medium — checked 2026-10-19
• 347. Top K Frequent Elements - Detailed Explanation — checked 2026-10-19
• Selection algorithm - Wikipedia — checked 2026-10-19
• Quickselect - Wikipedia — checked 2026-10-19
• Interview prep compared: your application, end to end · TrueInterview — checked 2026-10-19

Last reviewed: 2026-10-19.