Katkat
Back

Design a Raffle Drum That Draws Duplicate Tickets Fairly in O(1)

LinkedInSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Design a drum that holds raffle ticket codes, where the same code can be dropped in more than once, and supports adding a ticket, pulling a specific ticket out, and drawing one at random so every physical ticket in the drum is equally likely to come out — all in average O(1) time. Tests combining an array with a hash index so removal and random draw both stay constant time even with string keys and duplicates.

You're building the backing structure for a raffle drum. People drop in ticket codes (short strings), and the same code can be dropped in multiple times — each drop is a separate physical ticket sitting in the drum. Implement:

class RaffleDrum:
    def insert(self, code: str) -> bool: ...
    def remove(self, code: str) -> bool: ...
    def draw(self) -> str: ...
  • insert(code) always drops one more physical ticket into the drum. Whether that ticket's code is brand new to the drum or a repeat is reflected in the return value: brand new yields True, a repeat yields False.
  • remove(code) tries to pull exactly one ticket bearing that code out of the drum. When the drum is holding none, there's nothing to pull and the call reports False; otherwise one physical ticket disappears and the call reports True.
  • draw() returns the code of one uniformly random ticket currently sitting in the drum — every physical ticket has the same chance of being drawn, so a code dropped in 3 times out of 10 total tickets in the drum should come up with probability 3/10, not 1/4.

All three operations must run in average O(1) time.

Example

d = RaffleDrum()
d.insert("GOLD-7")     # True  (first GOLD-7 ticket)
d.insert("GOLD-7")     # False (a GOLD-7 ticket already existed)
d.insert("SILVER-2")   # True
d.remove("GOLD-7")     # True  -> one GOLD-7 ticket pulled, one remains
d.remove("BRONZE-9")   # False -> none in the drum
d.draw()                # "GOLD-7" or "SILVER-2", with probability 1/2 each

Constraints

  • Up to 10^5 total insert/remove/draw calls.
  • Codes are short, printable strings; the same code may appear many times at once.
  • draw() is only called when the drum is non-empty.
  • Treat hashing and comparing a code as O(1) for complexity purposes, independent of its length.

What a strong design addresses

  • A layout where draw() can land on a uniformly random physical ticket in one step, regardless of how duplicates are distributed.
  • Removing one ticket without shifting the rest of the drum's contents, including when the removed ticket happens to be the most recently added one, or the one being moved to fill its spot shares the same code.
  • The exact probability argument for why draw() is fair across physical tickets, not just across distinct codes.

Hints

Hint 1

A dense array you can index into directly makes a uniformly random draw a single random-index lookup; think about what structure lets removal also stay O(1) from that same array.

Hint 2

To delete a specific ticket from the middle of an array in O(1), swap it with the last element and pop — but that only works if you can find *an* index holding the target code immediately.

Hint 3

Keep, per distinct code, the set of positions in the array currently holding that code; removal picks any one of those positions, not a specific one.

Hint 4

When you swap an element into a new position, something else in your bookkeeping now points to the wrong place — figure out exactly what has to update.

Follow-up questions

  • How would you support `draw_and_remove()` — drawing a ticket and removing that exact physical instance in one O(1) call — and does your current design already make that easy?
  • If codes could be very long (say, full serialized receipts), how would that change your complexity analysis, and would you change the design at all?
  • How would you adapt this to a weighted draw, where each distinct code has an explicit weight independent of how many physical tickets it has?
  • Would this structure stay correct if `insert` and `remove` were called concurrently from multiple threads without any locking? What's the smallest change that would make it safe?