Article Voting / Top-K

Design an in-memory article voting tracker. Support article creation, user upvotes/downvotes, each user's most recent three opinion flips, and global top-K by score. Requirements Implement an in-memory ArticleVotingSystem: class ArticleVotingSystem: def add_article(self, article_name: str) -> int: ... # Creates an article and returns a unique article_id. def up_vote_article(self, article_id: int, user_id: int) -> None: ... # First upvote adds +1. Repeating an upvote is a no-op. # A previous downvote changes to upvote and counts as a flip. def down_vote_article(self, article_id: int, user_id: int) -> None: ... # First downvote adds -1. Repeating a downvote is a no-op. # A previous upvote changes to downvote and counts as a flip. def get_most_recent_k_flips(self, user_id: int, k: int) -> list[int]: ... # Returns newest-first article ids where the user changed vote direction. # Must run in O(k), not O(total_flips). def get_top_k(self, k: int) -> list[int]: ... # Returns article ids with highest current score. A flip is exactly UP -> DOWN or DOWN -> UP; UP -> UP, DOWN -> DOWN, and a first vote are not flips. Flip history is append-only for a user; if the same article is flipped multiple times, it can appear multiple times in the returned history. The older onsite variant asks for get_most_recent_3_flip_article(user_id) (also seen as print_last_three_flips(user_id)) and may require O(1); the generalized canonical version is get_most_recent_k_flips(user_id, k) with O(k) slicing. Implement get_top_k(k) returning top articles by current score, highest score first. Discuss read-heavy versus write-heavy trade-offs. Examples system = ArticleVotingSystem() a1 = system.add_article("Article 1") a2 = system.add_article("Article 2") system.up_vote_article(a1, 100) system.down_vote_article(a1, 100) # flip: a1 system.up_vote_article(a2, 100) system.down_vote_article(a2, 100) # flip: a2 system.up_vote_article(a2, 100) # flip: a2 again assert system.get_most_recent_k_flips(100, 3) == [a2, a2, a1] # Scores now: a1 = -1, a2 = +1; get_top_k(2) -> [a2, ...] tie-broken deterministically. Notes Store (user_id, article_id) -> vote so idempotent repeat votes do not create fake flips. Keep score_by_article updated during each vote-state transition: first upvote +1, first downvote -1, down-to-up +2, up-to-down -2, repeat vote 0. For recent flips, append the article id only when the previous vote exists and differs from the new vote. Returning flips[-1:-k-1:-1] satisfies the O(k) requirement for the generalized API; a deque(maxlen=3) satisfies the fixed-size O(1) onsite variant. The three common O(n) traps to avoid: reversing the whole list, copying the whole list, or scanning from the start. For top-K, the standard skeleton is a min-heap of size K (O(N log K) one-shot) for read-on-demand, and bucket-sort over frequency buckets (O(N)) when scores are small integers. If top-K is queried frequently after each vote, use a sorted set / balanced tree keyed by (score, article_id) so updates are O(log N) and reads are O(k). A lazy heap is a practical streaming compromise: push updated (score, article_id) on every vote without removing stale entries; when popping, re-check current score against score_by_article and skip stale tuples. This keeps writes O(log N) at the cost of a heap that may grow beyond K until lazy compaction. Define tie-breaking before coding. A common deterministic order is higher score first, then smaller article_id (e.g. sort on (score, -article_id)). LC 692 (Top K Frequent Words) and LC 347 (Top K Frequent Elements) are the algorithmic anchors for the top-K follow-up; LC 895 (Maximum Frequency Stack) is the closest match for the recency-aware variant some onsite versions ask about. Read-heavy top-K — ordered structure If get_top_k is called far more often than votes arrive, keep an always-sorted structure keyed on (-score, article_id) and update it on each vote (discard old key, insert new key, O(log N) per vote), making the query itself O(k). A sortedcontainers.SortedList shows the idea; in an interview, state you would back it with a balanced BST. Trade-off: Method Vote Top-K read Best for Heap O(1) O(N log k) Rare top-K checks Ordered (BST / SortedList) O(log N) O(k) Frequent top-K checks Follow-ups interviewers add Remove a vote (remove_vote(article_id, user_id)): subtract the current vote from the score and drop the (user, article) entry. Removing a vote is normally NOT counted as a flip. Concurrency (many simultaneous voters): guard per-article score mutation with a lock, or lean on the database's consistency guarantees in a real deployment. Preparation Code the vote-state transition table before writing handlers: no-op repeat, up-to-down flip, down-to-up flip, and first vote. Add tests for repeat upvote, upvote to downvote, downvote to upvote, more than K flips (the oldest must drop), and the same article flipped twice (it appears twice in history). Drill the lazy-heap top-K template once on LC 347, then again with score updates so the staleness check feels automatic. Prepare a read-heavy vs write-heavy top-K trade-off: heap / bucket sort for periodic recomputation, lazy heap for streaming, sorted set / skip list / BST for ordered O(k) queries.