Stage 1 of 3: Follows and checkpoints
Background. A social app keeps a follow graph: one user follows another, and the follow goes one way. The app also numbers moments worth keeping, checkpoints, and later asks how the graph stood at one of them.
Implement FollowGraph(), follow(user, target), unfollow(user, target), checkpoint() and was_following(user, target, checkpoint) in follow_graph.py.
follow(user, target): from now onuserfollowstarget.targetfollowsuseronly afterfollow(target, user). Following someone already followed changes nothing.unfollow(user, target): from now onuserdoes not followtarget. Unfollowing someone not followed changes nothing. Both calls returnNone.checkpoint()records the follows as they stand when it is called and returns its id:0for the graph's first checkpoint, then1,2and so on, a new id on every call even when nothing changed since the last one.was_following(user, target, checkpoint)returnsTruewhenuserfollowedtargetat the moment that checkpoint was recorded, andFalseotherwise, users the graph has never seen included. Follows and unfollows made after a checkpoint never change what it answers.
Example
g = FollowGraph()
g.follow(4, 9)
g.follow(4, 15)
first = g.checkpoint() # 0
g.unfollow(4, 9)
g.follow(15, 4)
second = g.checkpoint() # 1
g.was_following(4, 9, first) # True
g.was_following(4, 9, second) # False
g.was_following(15, 4, first) # False: 15 followed 4 only after the first checkpoint
g.was_following(9, 4, first) # False: 4 followed 9, not the other way round
Notes
- Users are integers from 0 to 10^12.
followandunfolloware never called withuser == target, and every checkpoint id passed towas_followingis one this graph'scheckpoint()returned. - Several graphs can be alive at once; each holds only its own follows and checkpoints.
- On the starter, all 9 tests in
tests/test_part1.pyfail.
Done when Submit goes green.
Constraints
- Python 3.12 standard library only
- Editable:
follow_graph.py - Read-only: all
tests/test_*.pyfiles - Users are integers from 0 to 10^12;
followandunfolloware never called withuser == target, and every checkpoint id passed to a read is one the graph returned
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: Both lists, kept cheaply. Whom anyone followed, and who followed them, at any of tens of thousands of kept moments, in little time and memory.
- Stage 3: Suggestions and changes. Whom to suggest as the graph stood at a kept moment, and what changed between two of them.
The files you get
- Yours to edit: follow_graph.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
OpenAI 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 Friend Circle Snapshots 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?
OpenAI. It is modelled on OpenAI's coding round, which runs without AI. Based on candidates' reports of OpenAI 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, OpenAI's interviews, the AI coding interview guide.