Quick Overview

This question evaluates a developer's ability to design in-memory data structures that support constant-time vote updates, score aggregation, and recent flip-event tracking while handling vote-change semantics.

Track article votes and last three flips

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem Design an in-memory data structure for voting on articles. Users can vote on an article with either: - **Thumbs up** - **Thumbs down** - **No vote** (user clears their vote) A **flip** is when a user changes their vote from up→down or down→up (clearing a vote is *not* a flip). ## Operations Implement the following operations efficiently: 1) `vote(user_id, article_id, new_vote)` - `new_vote` is one of `{UP, DOWN, NONE}`. - Updates the user’s vote for that article. 2) `getScore(article_id)` - Returns `(up_count - down_count)` for the article. 3) `getLast3Flips(article_id)` - Returns the **last 3 flip events** for the article in chronological order (oldest→newest). - Each flip event should include at least `{user_id, from_vote, to_vote, timestamp_or_sequence}`. ## Complexity requirements - `vote`: O(1) - `getScore`: O(1) - `getLast3Flips`: O(1) ## Notes - Multiple users can vote on the same article. - A user can vote multiple times; only changes may affect counts and flips. - Assume the system runs in a single process (no persistence required).

Quick Answer: This question evaluates a developer's ability to design in-memory data structures that support constant-time vote updates, score aggregation, and recent flip-event tracking while handling vote-change semantics.

You are given a list of operations for an in-memory article voting system. Each user can have at most one current vote on an article: "UP", "DOWN", or "NONE". The score of an article is: up_count - down_count A flip happens only when a user changes directly from "UP" to "DOWN" or from "DOWN" to "UP". Changing to or from "NONE" is not a flip. Process all operations in order and return the results of the query operations. For deterministic output, every flip event must receive a 1-based global sequence number in the order flips occur across the entire input. Rules: - Voting the same value again does nothing. - If an article has fewer than 3 flips, return all of them. - getLast3Flips(article_id) must return events in chronological order (oldest to newest). - Each flip event should be returned as [user_id, from_vote, to_vote, sequence].

Constraints

  • 0 <= len(operations) <= 2 * 10^5
  • Each operation is either ["vote", user_id, article_id, new_vote], ["getScore", article_id], or ["getLast3Flips", article_id]
  • user_id and article_id are non-empty strings, and new_vote is one of {"UP", "DOWN", "NONE"}
  • Your approach should run in O(1) average time per operation

Examples

Input: [['vote', 'u1', 'a1', 'UP'], ['vote', 'u2', 'a1', 'DOWN'], ['getScore', 'a1'], ['vote', 'u1', 'a1', 'DOWN'], ['getLast3Flips', 'a1'], ['vote', 'u2', 'a1', 'UP'], ['vote', 'u3', 'a1', 'UP'], ['vote', 'u3', 'a1', 'DOWN'], ['getScore', 'a1'], ['getLast3Flips', 'a1']]

Expected Output: [0, [['u1', 'UP', 'DOWN', 1]], -1, [['u1', 'UP', 'DOWN', 1], ['u2', 'DOWN', 'UP', 2], ['u3', 'UP', 'DOWN', 3]]]

Explanation: The first score is 0 because one user voted UP and one voted DOWN. Then three flips happen globally on the same article with sequence numbers 1, 2, and 3. The final score is -1.

Input: [['vote', 'u1', 'a2', 'DOWN'], ['getScore', 'a2'], ['getLast3Flips', 'a2'], ['vote', 'u1', 'a2', 'NONE'], ['getScore', 'a2'], ['vote', 'u1', 'a2', 'DOWN'], ['vote', 'u1', 'a2', 'UP'], ['getLast3Flips', 'a2']]

Expected Output: [-1, [], 0, [['u1', 'DOWN', 'UP', 1]]]

Explanation: Changing from DOWN to NONE is not a flip. After voting DOWN again and then UP, there is exactly one flip event.

Hints

  1. Map votes to numbers: UP = +1, DOWN = -1, NONE = 0. Then a vote update changes the score by value(new_vote) - value(old_vote).
  2. Store the current vote for each (user_id, article_id) pair, and keep a fixed-size queue/deque of at most 3 flip events per article.

Loading coding console...