Katkat
Back

Design a voting counter for restaurants

ZiprecruiterSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to manage real-time updates to counters using hash maps and to implement a deterministic sorting logic for ranking items with tie-breaking rules.

Problem Statement

You are building a backend service for a restaurant rating platform. Users cast votes for restaurants, and the system needs to maintain the current ranking. Implement a class VotingSystem with the following methods:

  1. vote(restaurant_name: str): Records a vote for the given restaurant. If the restaurant does not exist, initialize its count to 1.
  2. get_top_restaurant() -> str: Returns the name of the restaurant with the highest number of votes. If there is a tie, return the restaurant name that is alphabetically smaller (lexicographically first).

Constraints

  • restaurant_name consists of lowercase English letters.
  • The number of calls to vote can reach 1,000,000.
  • The number of unique restaurants is at most 10,000.

Examples

# Example 1
vs = VotingSystem()
vs.vote("pizza_hut")
vs.vote("burger_king")
vs.vote("pizza_hut")
vs.get_top_restaurant() # Returns "pizza_hut" (2 votes vs 1)

# Example 2
vs = VotingSystem()
vs.vote("b")
vs.vote("a")
vs.get_top_restaurant() # Returns "a" (Tie: both 1 vote, "a" < "b")

Edge Cases

  • What should get_top_restaurant() return if no votes have been cast yet? (Return None or an empty string).
  • Consider the performance of get_top_restaurant() when called repeatedly after every vote.

Hints

Hint 1

Use a hash map to keep track of the vote count for each restaurant name.

Hint 2

To handle tie-breaking efficiently, maintain the current winner as state variables (winner_name, max_votes) and update them during each vote call.

Hint 3

Consider the trade-off between updating the winner on every vote versus calculating the top restaurant only when requested.

Follow-up questions

  • How would you modify your design if you also needed to implement a `get_top_k_restaurants(k)` method?
  • If this system were distributed across multiple servers, how would you ensure data consistency for the global vote count?
  • What data structure would you use if the number of unique restaurants was extremely large and you needed to support frequent range queries?