Bloomberg Coding Interview: Office Lottery Entry Book

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Bloomberg. We'll work through one coding problem together, and I'd like you to think out loud as you code. If you need to step out or take a break, you can pause any time with the Pause button at the top right.

The problem is about an office lottery that draws winners by seat number, and it's up in the Problem tab now. Read it through, take your time, and ask me any questions before you start.

The problem

Build the entry book for an office lottery that draws winners by seat number.

• ops: a list of operations, each {kind, name, r}; kind is "add" (uses name) or "pick" (uses r, a non-negative integer). Unused fields are "" or 0.

Process the operations in order and return one string per operation. Entrants sit in seats 0..n-1 in the order they joined. add seats name in the next free seat and returns "true", or returns "false" (changing nothing) if that person is already entered. pick returns the entrant in seat r mod n, or "" if nobody is entered.

Example: add ann, add bob, add ann, pick r=3, pick r=0 → ["true","true","false","bob","ann"]

Up to 2·10^5 operations; each must run in O(1) average time.