Track a User's Top Trending Viewed Pin Within a Sliding Time Window

On a visual discovery platform, every Pin has a **trending score**. Build a per-user feature that keeps track of the Pins a user has viewed within a recent time window and, at any moment, reports the highest-scoring Pin among them. For example: of all the Pins this user viewed in the last 24 hours, which one is the most trending now? The interviewer described the window as the last week, and noted that once views carry a timestamp the same question could use the last 5 minutes, 5 hours or 5 days instead. Treat the window length as a parameter. Sample data, as (Pin ID, trending score) pairs in the order the user viewed them: ```python pin_scores = [ {"981292206280418755": 50}, {"981292206280418756": 35}, {"981292206280418757": 91}, {"981292206280418758": 92}, {"981292206280418759": 3}, {"981292206280418760": 88}, {"981292206280418761": 34}, {"981292206280418762": 9}, {"981292206280418763": 77}, {"981292206280418764": 55}, ] ``` The sample has no timestamps. For simplicity, treat it as the 10 most recent Pins viewed, all inside the window. A possible interface (adjust it as you clarify): ```python class PinScoreTracker: def __init__(self, window_seconds: int): ... def add_new_pin(self, pin_id: str, score: int, viewed_at: int) -> None: ... def remove_expired_pin(self, now: int) -> None: ... def get_top_scoring_pin(self, now: int) -> str | None: ... ``` ### Constraints and Clarifications - Pin IDs are long digit strings; treat them as opaque strings, not numbers. - Assume views are recorded in the order they happen, so `viewed_at` never decreases from one call to the next. - One tracker serves one user; every user has their own. ### Clarifying Questions - Can the user view the same Pin more than once? If so, does a repeat view refresh the Pin's place in the window, and should it count once or twice? - Is a Pin's trending score fixed when it is viewed, or can it change while the Pin is still in the window? - How should two Pins with the same score be ordered? - What should `get_top_scoring_pin` return when no viewed Pin is inside the window? - Is the window defined by time (the last week) or by count (the 10 most recent views), and is a view exactly one window length old still inside it? ### Part 1 — Add a viewed Pin Implement `add_new_pin`, which adds each newly viewed Pin to the running set of Pins the tracker considers. ```hint Keep the maximum within reach Choose a structure in which the highest score can be found without scanning every viewed Pin, and decide what each stored record must carry so that its age can be checked later. ``` #### What This Part Should Cover - The data structure chosen and the fields stored per record (ID, score, view time) - How repeat views of the same Pin are handled - The cost of one insertion ### Part 2 — Remove expired Pins Implement `remove_expired_pin`, which ensures the top-scoring Pin the tracker returns is not outside the time range. The sample has no timestamps, but you can check the top Pin's view time against the current time and remove it if it is too old. ```hint Expire only what matters An old Pin buried below a higher-scoring live Pin cannot change the answer yet. Ask when an expired record actually has to leave the structure. ``` #### What This Part Should Cover - Removing expired records at the top until the top is live, not just one - The exact boundary condition of the window - Why expired records that are not at the top can stay for now, and what that costs in memory ### Part 3 — Return the top-scoring Pin Implement `get_top_scoring_pin`, which returns the ID of the highest-scoring Pin in the current window. With the sample data treated as the 10 most recent Pins, it returns `"981292206280418758"`. ```hint Clean before you read Decide what must be true about the record at the top before you return it. ``` #### What This Part Should Cover - Combining the expiry check with the read so that a stale result is never returned - Tie handling and the empty case - The correct result on the sample data ### Part 4 — Runtime complexity Discuss the runtime complexity of each operation above for your structure, and its memory use. ```hint Count work across calls One call may remove many records. Count how many times each record can be inserted and removed over a whole sequence of calls. ``` #### What This Part Should Cover - Worst-case and amortized time per operation - Memory, including records that have expired but not yet been removed - A comparison with at least one alternative structure ### What a Strong Answer Covers - Clarifies repeat views, changing scores, ties and the window definition before coding - A structure that keeps the maximum cheaply available and supports expiry by view time - Correct, runnable code for all three methods, checked against the sample data - Accurate amortized complexity and an honest account of memory growth - Awareness of when a different structure fits better: scores that change, top K instead of top 1, a count-based window ### Follow-up Questions - Trending scores are recomputed every few minutes while Pins stay in the window. How does your structure keep the answer correct? - The product now wants the top 5 trending Pins instead of the top 1. What changes? - Switch to a count-based window: the 10 most recent views. What do you store instead of a timestamp, and does the expiry logic change? - The feature must serve millions of users. How much memory does each tracker use, and how would you bound it?