Exercise: Friends of Friends

A small social app needs a "people you may know" box and a "how many steps apart?" line that stay fast in a town of 90,000 people: turn the app's list of friendships into something quick to search, write both features, and let the tests check them, the big town included.

Journeyman · Data Structures · Updated

By

Here's the ticket from the social app's product lead:

Our app is growing past its first town. Two features are next on the list.

  1. People you may know. On your home screen, show the friends of your friends who aren't your friends yet, each once, A to Z.
  2. How far apart are we? On anyone's profile, show the fewest friendships between you and them: "1 step" for a friend, "2 steps" for a friend of a friend, and so on, or nothing when no chain of friends joins you.

The app stores each friendship as a pair, the moment someone taps Add friend. Both features have to stay quick as we grow: the test town has 90,000 people, and "how far apart?" must answer from one corner of it to the other in under 2 seconds.

The chapter's eight people (Ava, Ben, Cara, Dev, Eli, Fay, Gus and Hana) are the app's first users, and the demo uses them.

Before you start

You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.

Get the exercise code

Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-friends-of-friends, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

git clone https://github.com/ask-codey/exercise-ds-friends-of-friends.git

Git makes a folder, exercise-ds-friends-of-friends, with the exercise code inside.

The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:

  • your code: one file with three functions to finish (the repository's README.md names the file for each language);
  • the tests that check your functions. You don't need to change them;
  • a demo program that tries your functions on the eight-person network.

In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.

What to do

Every function is already there, with its parameters, and returns an empty network, an empty list or 0 for now. The comment above each one says what it should return, with examples. Here is the third one in Python, as the starter has it (the other languages say the same in their own syntax):

def steps_between(network, start, end):
    """
    The fewest friendships between start and end: 1 for friends, 2 for a
    friend of a friend, and so on. A person is 0 steps from themselves.
    Return -1 when no chain of friendships joins them, or when either
    person isn't in the network.

    In the sample network (the demo's):
    steps_between(network, "Ava", "Fay") -> 4
    steps_between(network, "Ava", "Ava") -> 0
    steps_between(network, "Ava", "Hana") -> -1
    """
    return 0
  1. Turn the pairs into something quick to search. Finish buildNetwork (build_network in Python, BuildNetwork in C#). It gets the friendships as pairs, such as Ava and Ben, and returns a dictionary from each person to the list of their friends.
  2. People you may know. Finish suggestFriends: everyone exactly two steps away from a person, the friends of their friends who aren't the person and aren't already their friends, each listed once, in A to Z order.
  3. How far apart? Finish stepsBetween: the fewest friendships between two people, 0 from a person to themselves, and -1 when nothing joins them.

Check your work

Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).

Language Run the tests Run the demo
C# dotnet test dotnet run --project FriendsOfFriends
Java ./mvnw test (.\mvnw test in PowerShell) java src/main/java/Demo.java
Python python -m pytest python demo.py
JavaScript npm test node demo.js
TypeScript npm test node demo.ts

At first all 10 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: Dev may know Ava (through Ben and Cara) and Fay (through Eli), listed once each, A to Z.

The last test is the town of 90,000 people, a 300 by 300 grid of friendships, and it has to finish in under 2 seconds. If it runs for a long time, stop it with Ctrl+C: it's telling you to change your approach, not that your answer is wrong.

<details> <summary>Stuck?</summary>

  • Write every friendship twice, once in each person's list, as the code in Who Knows Whom? When Anything Can Connect: Graphs does. The dictionary of lists is an adjacency list.
  • Friends of friends are two loops: for each friend, go through their friends. Skip the person, their own friends, and anyone already in your answer. Then sort.
  • "How far apart?" is breadth-first search, from How Many Steps Apart? Breadth-First Search. A queue holds who to explore next, and a dictionary holds how many steps away each person was found, which also makes it the visited set. When you take the person you're looking for out of the queue, you have the answer. In Python, the queue is deque from collections; in Java, ArrayDeque; in JavaScript and TypeScript, an array with a head index.
  • If the line of 2,000 people stops with a stack overflow or a recursion error, your search goes deep with recursion: switch to the queue.
  • If the town of 90,000 is slow, check two things: are you trying every route, and is your "already seen" a list? Reading a list from the top for each person makes the search O(V²). Use a set or a dictionary.

</details>

When you're done

Every test is green, and the demo prints the same six lines in every language:

Network: 8 people
Ava's friends: Ben, Cara
People Ava may know: Dev
People Dev may know: Ava, Fay
Steps from Ava to Fay: 4
Steps from Ava to Hana: -1

Now think about a real app with 1,000,000 people and about 200 friends each. Roughly how many names does suggestFriends look at for one person? Why does that make "people you may know" one of the more expensive features a social app has?

<details> <summary>Why Should I Choose This?</summary>

Open this once your tests are green. The town is 90,000 people and 179,400 friendships, and the question is corner to corner, 598 steps.

  • The pairs as they are: every "who are this person's friends?" reads all 179,400 pairs. A search asks that once for each of the 90,000 people: about 16 billion pair reads.
  • Every route, keep the shortest: a 300 by 300 grid has more shortest routes from corner to corner than there are atoms in the Earth. It never finishes.
  • Rounds with a list for "already seen": correct, but checking a list reads it from the top. With 90,000 people that took more than 4 minutes in Python (we stopped it there) and 68 seconds in C#.
  • A dictionary of friend lists and breadth-first search: each person joins the queue once and each friendship is looked at from both ends, O(V + E). It took under a fifth of a second in Python, and about a twentieth in C#.
  • What it gives up: breadth-first search counts friendships, not how close they are. For "the fastest drive", where every road takes a different time, the next chapter needs something more.

</details>

Where else does this shape show up?

You've built "things that can connect to anything, searched round by round". Before you open the answers, think of three other places, in apps or in daily life, where a question is really "how few hops from here to there?" or "who can I reach from here?"

<details> <summary>Some answers</summary>

  • A subway app counting the fewest transfers between two stations: stations are vertices, lines between them are edges.
  • A game moving a character to the door in the fewest squares, around the walls.
  • LinkedIn's "2nd" and "3rd" badges, which are the steps between you and a stranger.
  • A web crawler following links from page to page, never visiting a page twice.
  • A spreadsheet finding every cell that depends, directly or not, on the one you changed.

</details>

Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

  1. On GitHub, click +, then New repository. Name it (for example exercise-ds-friends-of-friends), choose Public, and click Create repository. Leave out the README: your folder already has one.

  2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

    git remote set-url origin https://github.com/your-name/exercise-ds-friends-of-friends.git
    git add .
    git commit -m "My solution"
    git push -u origin main
    
  3. Paste your repo's address, such as https://github.com/your-name/exercise-ds-friends-of-friends, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

So what

You've turned raw data into a graph and answered two real product questions with it, fast enough for a whole town. The next chapter gives the edges weights, for a GPS, and direction, for a course catalog.

Key terms

Related