Stage 1 of 3: Everyone downstream
Background. On a referral programme, a user who invites someone is credited with the people their invitation brings in: the user they referred, the users that user referred, and so on down the line. The history of the programme is a list of referrals in the order they happened.
Implement downstream_counts(referrals) in referrals.py.
referralsis a list of(referrer, new_user)pairs of names, in the order the referrals happened, possibly empty.- It returns a new dict with every user named in any pair as a key, on either side. A user's value is the number of users downstream of them: the users they referred, the users those referred, and so on to the end of every line. The user is not counted in their own total, and a user who referred nobody has 0.
The history always follows these rules:
- A pair never names one user twice, and each user is the new user of at most one pair.
- A user named in a pair, on either side, is never the new user of a later pair. So every user has at most one referrer, and a user's own referral comes before the referrals they make.
- Users who were never referred are original members. There may be many, each starting a tree of their own.
Example
downstream_counts([("ana", "ben"), ("ben", "cal"), ("ana", "dee"), ("cal", "eli"), ("fay", "gus")])
# {"ana": 4, "ben": 2, "cal": 1, "dee": 0, "eli": 0, "fay": 1, "gus": 0}
ana referred ben and dee, ben referred cal and cal referred eli, so four users are downstream of ana. fay is a second original member with one user below.
Notes
- Names are non-empty strings, used exactly as given and compared exactly:
"Ann","ann"and"ann "are three users. - At most 1,000 pairs per call, and no line of referrals holds more than 50 users (a line: an original member, a user they referred, a user that user referred, and so on).
- Each call stands alone: nothing carries over from one call to the next.
- On the starter, all 8 tests in
tests/test_part1.pyfail.
Done when Submit goes green.
Constraints
- Python 3.12 standard library only
- Editable:
referrals.py - Read-only: all
tests/test_*.pyfiles - Names are non-empty strings, used exactly as given:
"Ann","ann"and"ann "are three users - At most 1,000 referrals per call, and no line of referrals holds more than 50 users
- Inputs always follow the rules the statement gives
What comes after stage 1
The next stages open once the tests for the one before them pass. Each raises the bar, the way an interviewer does in the room.
- Stage 2: A live leaderboard. Referrals arrive one at a time, tens of thousands of them, and every total and the top three must stay current after each one.
- Stage 3: More than one referrer. A new user can credit more than one referrer, and no one may count the same person twice.
The files you get
- Yours to edit: referrals.py.
- Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.
The round: no AI, an assistant that only answers
Robinhood runs this round without AI. Here the closest format is answer-only: the assistant answers your questions and reviews your code when you ask, the way an interviewer would, and never writes a line of it. The interviewer asks about your decisions as you go, and the report states the format. You can switch to the agent format when you press Begin.
Frequently asked, briefly answered
Is Referral Count free?
It is a Pro problem. Free plan includes one complete problem, plus the first stage of several more, so you can see how a round works before you pay.
Which company asks something like this?
Robinhood. It is modelled on Robinhood's coding round, which runs without AI. Based on candidates' reports of Robinhood interviews. Nyrion wrote this version, so the question you get may differ.
Do I bring my own AI tool?
No. The real round has no AI, so this one opens answer-only: an assistant that answers your questions and can't write code. You can switch to an agent that proposes changes when you press Begin.
What does the interviewer ask?
6 questions along the way about your own code, and one at the end about the whole session. A weak answer gets one follow up. The answers go into the report, which ends with a hire or no hire verdict.
Start the problem
Sign in and the problem opens where you left it. New here? An account takes a minute to create, and the Pro plan starts at the first stage of this problem.
More like it: every practice problem, Robinhood's interviews, the AI coding interview guide.