Select the Top Unseen Feed Posts

Updated · By

Filter out seen posts with a set lookup as the candidates stream past, and keep the best n of the rest in a bounded heap ordered by score descending, then post id ascending. The tie-break makes the order identical on every refresh. O(c log n) time for c candidates, and O(n) space beyond the seen set.

mediumPattern: HeapsFrom Devana's Meta question set

Problem

A feed refresh produces scored candidate posts for a user. Posts the user has already seen in this session must not appear again, and only the top n are shown.

Write select_feed(candidates, seen, n). candidates is a list of (post_id, score) in no particular order, and seen holds the post ids already shown. Return up to n unseen post ids, highest score first, with ties broken by post id ascending.

def select_feed(candidates: list[tuple[str, float]], seen: set[str], n: int) -> list[str]:

This is one of Devana's own questions, written in the style of Meta's interviews. It is not a question leaked from Meta, and Devana is not affiliated with Meta.

Constraints

  • Seen posts are excluded however high they score.
  • Highest score first; equal scores are ordered by post id ascending.
  • The seen set can be large: test membership, never scan it.
  • Fewer than n unseen candidates returns what there is.
  • Candidates are not sorted, and the code must not assume they are.

Examples

Example 1

Input:  candidates = [("p1", 0.9), ("p2", 0.8), ("p3", 0.7)], seen = {"p1"}, n = 2
Output: ["p2", "p3"]

p1 scores highest but was already seen.

Example 2

Input:  candidates = [("p2", 0.5), ("p1", 0.5)], seen = set(), n = 2
Output: ["p1", "p2"]

Equal scores fall back to post id, so two refreshes of the same candidates show the same order.

Hints

Open one at a time, and try the problem again after each.

Hint 1

Should you filter before or after choosing the top n?

Hint 2

Membership in seen has to be O(1). What does that require of its type?

Hint 3

You want the top n by score descending, then id ascending. Express that as a single sort key.

Hint 4

A heap bounded at n items gives O(c log n) instead of sorting all c candidates.

Approach: from brute force to optimal

Brute force: sort, then filter

Sort every candidate by score and walk down the list, skipping seen ones, until n are collected. Correct, but it sorts everything, and if seen is a list each check is a scan.

Complexity: O(c log c + c × s) with a list for the s seen ids, O(c log c) with a set

Filter with a set, select with a heap

Convert seen to a set if it is not one already. Stream the candidates, skip seen ones, and keep the best n in a heap keyed by (-score, post_id); heapq.nsmallest does exactly that in Python.

Complexity: O(c log n) time, O(n) extra space beyond the seen set

How to say it in the interview

Answer the ordering question before writing code: filter first, because taking the top n and then filtering can leave fewer than n posts even when enough unseen ones exist. Then explain the sort key, especially the tie-break, and why it matters for a feed that refreshes.

Solution

Python

import heapq

def select_feed(candidates, seen, n):
    seen = set(seen)                                    # O(1) membership
    unseen = ((post, score) for post, score in candidates if post not in seen)
    # A heap of n: highest score first, then post id ascending.
    best = heapq.nsmallest(n, unseen, key=lambda c: (-c[1], c[0]))
    return [post for post, _ in best]

JavaScript

// Does a outrank b? Higher score first, then post id ascending.
const outranks = (a, b) => (a[1] !== b[1] ? a[1] > b[1] : a[0] < b[0]);

function selectFeed(candidates, seen, n) {
  if (n <= 0) return [];
  const seenSet = new Set(seen); // O(1) membership
  const heap = []; // the best n so far, the weakest of them on top

  const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };
  const up = (i) => {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!outranks(heap[parent], heap[i])) break;
      swap(parent, i);
      i = parent;
    }
  };
  const down = (i) => {
    for (;;) {
      let weakest = i;
      for (const child of [2 * i + 1, 2 * i + 2]) {
        if (child < heap.length && outranks(heap[weakest], heap[child])) weakest = child;
      }
      if (weakest === i) return;
      swap(weakest, i);
      i = weakest;
    }
  };

  for (const candidate of candidates) {
    if (seenSet.has(candidate[0])) continue;
    if (heap.length < n) {
      heap.push(candidate);
      up(heap.length - 1);
    } else if (outranks(candidate, heap[0])) {
      heap[0] = candidate; // displaces the weakest of the best n
      down(0);
    }
  }
  return heap.sort((a, b) => (outranks(a, b) ? -1 : outranks(b, a) ? 1 : 0)).map(([post]) => post);
}

Both versions are tested against the same cases, including every example on this page.

  • Filtering happens before selection, in the same pass, so seen posts never take a slot.
  • The key (-score, post_id) turns "highest score, then lowest id" into one ascending order, which is what nsmallest wants.
  • The JavaScript heap keeps the weakest of the current best n on top, so a new candidate only has to beat that one.

Follow-up questions

Should you filter before or after selecting the top n? Why?

Before. Taking the top n and then dropping seen posts gives a user who has seen the top 10 an empty feed, even though the 11th to 20th are unseen. Filtering first costs nothing extra in the same pass.

How do you bound the seen set's memory over a long session?

Keep only recent impressions, such as the last few thousand ids or the last day, in a set with a queue for expiry: the same shape as a sliding window. Posts older than that are unlikely to be candidates again.

The user has seen everything. What do you show rather than nothing?

Widen candidate generation to older posts or suggested accounts, or show the best of the seen posts again under a clear "you're all caught up" marker. An empty feed is the worst option.

Why does the tie-break matter?

Without it, equal scores come out in whatever order the heap or the sort left them, which can differ between servers and refreshes, so the feed visibly reshuffles for no reason.

Common mistakes

  • Selecting the top n and then filtering, which returns fewer than n posts even when enough exist.
  • Checking membership in a list.
  • Assuming the candidates arrive sorted by score.
  • No tie-break, so equal scores reorder between refreshes.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Practice this problem out loud

Josh, Devana's AI interviewer, runs this exact problem as a voice mock interview, asks follow-ups like the ones above, and scores you out of 100. The Free plan has 3 interviews a month, no card needed.

Practice this problem in a mock interview