Friend Recommender

Friend Recommender

You've joined the growth-engineering team that owns friendrec, the service behind a social app's "People you may know" panel. It stores the friendship graph and suggests friends of friends. Support has a bug report, and three feature tickets are queued behind it.

Codebase

How your code is run

The grader calls run(operations) from friendrec/app.py and compares the list of results with the expected one: one result per operation, in order. Errors are strings starting with error:, never exceptions. User ids are non-empty strings. Wherever this brief says "ascending" for ids, it means plain string comparison, so "u10" comes before "u2".

A suggestion for user U is someone who is a friend of at least one of U's friends. Errors for recommend, in this order: error: unknown user 'x', error: invalid k (k must be an integer of at least 1), error: unknown strategy 'x'. Strategy "id" lists suggestions in ascending id order. A wrong number of arguments gives error: bad arguments for 'name', an unknown name error: unknown operation 'name', and anything that is not a non-empty list starting with a string error: malformed operation.

Worked example:

[["add_user", "ann"], ["add_user", "bob"], ["add_user", "cat"], ["add_user", "dan"],
 ["befriend", "ann", "bob"], ["befriend", "bob", "cat"], ["befriend", "bob", "dan"],
 ["recommend", "ann", 5]]

returns "ok" eight times and then ["cat", "dan"].

Part 1 — Wrong and stale suggestions

Goal: Suggestions must be correct and always up to date.

Support reports: "the panel suggests people I'm already friends with, and sometimes myself", and "I added a friend, but my friends' panels didn't show them until much later".

Rules

1. A suggestion is never the user themselves and never someone who is already their friend.
2. After befriend or unfriend, every later recommend reflects the new graph. That includes users other than the two involved.
3. Everything else keeps working as described above.

Example: with friendships ann-bob, ann-cat, bob-cat and cat-dan, ["recommend", "ann", 5] is ["dan"].

Part 2 — Rank by mutual friends

Goal: Offer a smarter ordering through the existing strategy argument.

Rules

1. A new strategy "mutual" orders suggestions by number of mutual friends (friends the user and the suggestion share), highest first. Equal counts are ordered by ascending id. The default strategy "id" is unchanged.
2. New operation ["explain", id, candidate] returns {"mutual": n, "via": [ids]}, where via is the ascending list of the shared friends, if candidate would be suggested to id, and null otherwise (the candidate is the user, a friend, or shares no friend). Errors: error: unknown user 'x' (first argument checked first).
3. Unknown strategies still give error: unknown strategy 'x'.

Example: ann is friends with bob, cat and dan. eve is friends with all three, fay and ivy with bob and cat, gus with dan. ["recommend", "ann", 10, "mutual"] is ["eve", "fay", "ivy", "gus"] (counts 3, 2, 2, 1), while "id" gives ["eve", "fay", "gus", "ivy"]. ["explain", "ann", "eve"] is {"mutual": 3, "via": ["bob", "cat", "dan"]}.

Part 3 — Blocks and privacy

Goal: Let users block each other and control how they appear in suggestions.

The flags are in PRIVACY_FLAGS and both default to true: discoverable and friends_visible.

Rules

1. block also removes any friendship between the two users. unblock does not restore it.
2. While either user has blocked the other, befriend fails with error: blocked (after the unknown-user and self checks, before already friends), and each is hidden from the other: never suggested, and explain returns null for the pair.
3. A user with discoverable set to false is never suggested to anyone and explain returns null for them as a candidate. Their own suggestions still work.
4. A user with friends_visible set to false is not used as a connection: they are not counted as a mutual friend for anyone, do not appear in via, and do not by themselves make someone a suggestion. Their own suggestions still work, and friends and mutuals ignore this flag.
5. With no blocks and both flags true, behaviour is exactly that of Parts 1 and 2. Changes to blocks and flags must show up in later recommend results.

Example: with friendships ann-bob, bob-cat and bob-dan, after ["block", "ann", "cat"], ["recommend", "ann", 5] and ["recommend", "cat", 5] both return ["dan"].

Part 4 — Network-wide top pairs (FR-310)

Goal: Growth wants a report of the strongest introductions across the whole network. It must work on networks of thousands of users.

["top_pairs", k] returns up to k entries {"a": id, "b": id, "mutual": n} where a < b as strings, ordered by mutual descending, then a, then b ascending. Error: error: invalid k (same rule as recommend); a wrong number of arguments is error: bad arguments for 'top_pairs'.

Rules

1. A pair is listed only if the two users are not friends, neither has blocked the other, both are discoverable, and they have at least one mutual friend.
2. mutual counts mutual friends the same way as explain: friends with friends_visible set to false are not counted.
3. The result must agree with recommend and explain, and with every change made through earlier operations.
4. The tests include networks of up to 8000 users; comparing every pair of users will time out.

Example: with friendships ann-bob, ann-cat, ann-dan, bob-eve, cat-eve and dan-eve, ["top_pairs", 2] is [{"a": "ann", "b": "eve", "mutual": 3}, {"a": "bob", "b": "cat", "mutual": 2}].

Notes

• graph.py, demo.py, cache.py and app.py are known-good, apart from what the parts ask you to extend. Bugs are in the logic reachable from recommend.
• You may use the AI assistant freely. Later parts must not break earlier ones; the visible tests are a starting point, not the full suite.
• Completing Parts 1 to 3 is a strong result; Part 4 is a stretch.