title: Algorithm design for instagram giveaway
body: <p><strong>I saw this question online and was wondering how to design an efficient ADT and data structure for a raffle like problem.</strong></p>
  <p>Sashu is an Instagram influencer for Nike and is doing a giveaway of the new Air Jordans! She posted on Instagram revealing this and asking everyone to comment on the post in order to enter the raffle! Instagram has limited the number of times each individual can comment on a post to 50 as each comment represents a single entry for a giveaway. At the end of one week, Sashu announces that she will randomly select 10 individuals to win the giveaway and the shoes!</p>
  <p>You are tasked with designing a system (a digital bowl) from which Sashu can draw the names, specifically implementing the following methods:</p>
  <p><strong>addEntry(String username)</strong>: insert a new entry with the given username into the digital bowl (people can comment multiple times, duplicates will be allowed)</p>
  <p><strong>withdrawUser(String username)</strong>: withdraw every entry with the given username from the digital bowl (if a winner is already selected, they must not be chosen again)</p>
  <p><strong>drawWinner()</strong>: randomly select a winner from the digital bowl for the giveaway and withdraw all entries with the same name from the bowl. The probability of a specific name being selected must remain proportional to the number of entries from the same username in the digital bowl.</p>
  <p><strong>My solution:</strong></p>
  <p>Because I want this design to run in O(n), I was thinking of creating a hashmap so that every key represents the username and the count represents the value. To maintain the probability of a specific name being selected to remain proportional to the number of entries from the same username, I will be using another data structure, an arraylist to store the usernames and add it to the end of the list each time with duplicates. Since I need to withdrawn an entry after selecting a winner, I will need to search the username in the list. However, the worst case might take O(n) if the username is at the end of the list. How might I prevent the worst case and let the runtime be constant and not linear? Thank you</p>