Q5 - The Story Tray (Designing Ephemeral Stories)
We believe a variation of this interview question has recently been asked by Meta to software engineering candidates. Stories are the classic ephemeral feature: a post that vanishes a day after you share it. Designing the little service behind it, posting, listing what is still live, and tracking who has seen each one, is a clean low-level-design question, and the real test is answering "what is still active?" without rescanning everything each time.
Scenario: You are designing the component behind Stories: short posts that automatically expire a fixed number of time units (the ttl) after they are posted. You build a class supporting these operations, where author, viewer, and storyId are integer ids and time / now are integer timestamps:
post(author, storyId, time)posts a story attime; it expires attime + ttl.view(viewer, storyId, time)records thatvieweropened the story attime.activeStories(author, now)returns the author's still-active (unexpired) stories, oldest-first.viewerCount(storyId)returns how many distinct viewers a story has.- (Part 2)
viewers(storyId)returns those distinct viewers, most-recent-first.
Part 1. Implement post, view, activeStories, and viewerCount. You may assume a user's stories are posted in non-decreasing time order, and now passed to activeStories only moves forward (the clock never runs backward).
⏱️ On pacing a multi-part question. Interviewers usually do not reveal Part 2 until you have finished Part 1, and you often will not even know more parts are coming. So get Part 1 correct and clean without burning the whole slot on it, and keep some time in reserve for whatever comes next.
Example 1 (Part 1: posting, expiry, viewers)
ttl = 24
post(1, 101, 0) user 1 posts story 101 at time 0 (expires at 24)
post(1, 102, 10) story 102 at time 10 (expires at 34)
view(7, 101, 2), view(8, 101, 5) two viewers open story 101
view(7, 101, 8) viewer 7 opens it again (kept as their latest view)
activeStories(1, 20) -> [101, 102] both still live at time 20
activeStories(1, 30) -> [102] story 101 expired at 24, so it drops off
viewerCount(101) -> 2 distinct viewers are 7 and 8
💡 The one idea that makes it fast. The only interesting query is activeStories. The lazy answer rescans all of a user's stories and keeps the unexpired ones, which is O(their whole history) every call. But a user posts over time, so their stories sit in posting order, oldest first, which means the expired ones are always a contiguous block at the very front. So you never scan the middle: you just drop expired stories off the front until the front is still alive. Each story is removed once, so listing active stories is amortized O(1).
Part 1: Model the State, Then Expire From the Front
Getting this clean is three small steps: pick the state, do the easy writes, then the one clever read.
Step 1: Choose the state
Two stores do the whole job. One maps each story to its post time and who has viewed it. The other holds, per author, that author's story ids in posting order, so we can expire from the front later.
after post(1,101,0), post(1,102,10), view(7,101,2):
stories = {
101: { postTime: 0, viewedAt: {7: 2} }, # viewedAt maps a viewer -> their latest view time
102: { postTime: 10, viewedAt: {} },
}
byAuthor = { 1: [101, 102] } # user 1's stories, oldest (front) first
Step 2: The writes (post, view) and the count
post drops the story into both stores. view records the viewer's latest view time (storing it in a map keyed by viewer means a repeat view just overwrites the old time, so a viewer is never double-counted). viewerCount is then just the size of that map. Each is O(1).
view(8, 101, 5) -> viewedAt of 101 becomes {7: 2, 8: 5}
view(7, 101, 8) -> viewer 7 already there, so just update: {7: 8, 8: 5}
viewerCount(101) = size of viewedAt = 2 (a repeat view does not add a new viewer)
Step 3: Active stories, by evicting the expired front
byAuthor[author] is a queue of story ids in posting order, so it is sorted by post time. To list what is active at now, pop story ids off the front while the front story is expired (postTime + ttl <= now); the moment the front is still alive, everything behind it is too, so stop and return the rest. Because now only moves forward, a popped story is gone for good, so each is removed at most once.
activeStories(1, now) with ttl = 24 and queue = [101(exp 24), 102(exp 34), 103(exp 50)]
now = 30: front 101 expires at 24 <= 30 -> pop it
front 102 expires at 34 > 30 -> still alive, stop
return [102, 103]
The method is just that front-eviction loop: drop expired stories off the front while the front one is still expired, then return the rest.
def active_stories(self, author, now):
queue = self.by_author.get(author, deque())
while queue and self.stories[queue[0]]["post_time"] + self.ttl <= now: # expired -> drop from front
queue.popleft()
return list(queue)
Watch the tray evolve as stories are posted and now marches forward. Expired stories drop off the front, the still-active ones remain, and each activeStories call returns just the live ones:
# post/view/viewer_count: O(1) | active_stories: amortized O(1)
from collections import deque
class Stories:
def __init__(self, ttl):
self.ttl = ttl
self.stories = {} # story_id -> {"post_time", "viewed_at": {viewer: time}}
self.by_author = {} # author -> deque of story_ids, oldest at the front
def post(self, author, story_id, time):
self.stories[story_id] = {"post_time": time, "viewed_at": {}}
self.by_author.setdefault(author, deque()).append(story_id)
def view(self, viewer, story_id, time):
if story_id in self.stories:
self.stories[story_id]["viewed_at"][viewer] = time # keep only the latest view time
def active_stories(self, author, now):
queue = self.by_author.get(author, deque())
while queue and self.stories[queue[0]]["post_time"] + self.ttl <= now: # expired -> drop from front
queue.popleft()
return list(queue)
def viewer_count(self, story_id):
return len(self.stories[story_id]["viewed_at"]) if story_id in self.stories else 0
Part 2: "Seen By," Newest Viewer First
The interviewer adds the feature the author actually looks at: the "Seen by" list. Return a story's distinct viewers ordered by most-recent view first, breaking ties by viewer id.
Example 2 (Part 2: the viewer list)
using story 101 from Example 1, whose views were: 7 @2, 8 @5, 7 @8 (again)
viewers(101) -> [7, 8]
You already have exactly what you need. Part 1 stored viewedAt as a map from each viewer to their latest view time, so a repeat view moved that viewer's time forward instead of adding a duplicate. So the "Seen by" list is just those viewers sorted by their stored time, descending (ties broken by id). No extra bookkeeping, the dedup happened for free when you recorded the views.
viewedAt of story 101 = {7: 8, 8: 5} (7's latest view was at time 8)
sort viewers by (view time desc, id asc):
7 -> viewed at 8 (newest)
8 -> viewed at 5
viewers(101) = [7, 8]
Step through the list as the views land. A new viewer slots in by recency, and viewer 7's second view just lifts them back to the top, never a duplicate:
# add to the Stories class
def viewers(self, story_id):
if story_id not in self.stories:
return []
viewed_at = self.stories[story_id]["viewed_at"]
return sorted(viewed_at, key=lambda viewer: (-viewed_at[viewer], viewer)) # newest first, tie by id
The Full Solution
Here is the whole Stories class in one piece, all five operations together.
from collections import deque
class Stories:
def __init__(self, ttl):
self.ttl = ttl
self.stories = {} # story_id -> {"post_time", "viewed_at": {viewer: time}}
self.by_author = {} # author -> deque of story_ids, oldest at the front
def post(self, author, story_id, time): # O(1)
self.stories[story_id] = {"post_time": time, "viewed_at": {}}
self.by_author.setdefault(author, deque()).append(story_id)
def view(self, viewer, story_id, time): # O(1)
if story_id in self.stories:
self.stories[story_id]["viewed_at"][viewer] = time # keep only the latest view time
def active_stories(self, author, now): # amortized O(1)
queue = self.by_author.get(author, deque())
while queue and self.stories[queue[0]]["post_time"] + self.ttl <= now: # expired -> drop from front
queue.popleft()
return list(queue)
def viewer_count(self, story_id): # O(1)
return len(self.stories[story_id]["viewed_at"]) if story_id in self.stories else 0
def viewers(self, story_id): # O(k log k) for k viewers
if story_id not in self.stories:
return []
viewed_at = self.stories[story_id]["viewed_at"]
return sorted(viewed_at, key=lambda viewer: (-viewed_at[viewer], viewer)) # newest first, tie by id
Complexity Analysis
post,view,viewerCount:O(1)each, one or two hash-map operations.activeStories(author, now): amortizedO(1). A single call can pop several expired stories, but every story is pushed once and popped at most once over the whole run, so a stream ofnposts costsO(n)of eviction total. That is the whole point of expiring from the front instead of rescanning the author's history on every call.viewers(storyId):O(k log k)for a story withkdistinct viewers, the cost of sorting them by recency.- Space:
O(active stories + total viewers). The per-author queues stay bounded to live stories. The view data lives with each story (a real system archives or purges it on a background job once the story has long expired, keeping the hot path, the active tray, small and fast).
Final Notes
🕒 We believe the "Stories" problem, and TTL-plus-tracking design questions like it, have appeared frequently in recent interviews for software engineers at Meta. It is not about a clever algorithm; it is about picking state that makes every operation fall out cleanly. The one insight that carries it: because posts arrive in time order, expired stories are always a prefix, so you evict from the front instead of scanning.
- Model the state first, out loud. "A map from story to its data, plus a per-author queue in posting order" is the whole design, and naming it before you code is most of what the interviewer is grading in an LLD round.
- Expire from the front, not by scanning. Posts arrive in time order, so a user's expired stories are always the oldest ones at the front of the queue. Popping them off is amortized
O(1); rescanning the whole history each call is the trap. - Let the data structure do the dedup. Storing views as a map from viewer to their latest time means a repeat view overwrites instead of duplicating, so
viewerCountand the recency-orderedviewerslist both come for free. Choosing a map over a list here is the small decision that makes Part 2 trivial. - Name the assumptions. Monotonic time is what makes front-eviction correct; if
nowcould jump backward you would binary-search the queue instead of permanently popping. Say that assumption out loud, because it is doing real work: drop it and the cheap front-pop is suddenly wrong.