Chapter 13 checkpoint

Social graph search

Every question from this chapter’s lessons, grouped by the lesson that teaches it. Answer each one right to finish; you can try again whenever you like.

0 of 16 answered right

13.1 Requirements, estimates and the graph model

0 of 4 answered right
Open the lesson
Question 1
The primer’s network has 100 million users with 50 friends each. If each friend id in a user’s friend list takes 8 bytes, how much do all the friend lists take, in GB?

Answers within 5% count, in any unit you choose.

Question 2
With 100 million users who each have 50 friends, how many distinct friendships are there, in billions?

Answers within 2% count, in any unit you choose.

Question 3
In Facebook’s TAO, how do associations differ from objects?

Question 4
The primer assumes 1 billion friend searches a month. Using 400 requests per second ≈ 1 billion a month, how many searches per second is that on average?
searches/s

Answers within 5% count.

13.2 Graph traversal and bidirectional BFS

0 of 4 answered right
Open the lesson
Question 5
In an idealized tree where everyone has b=100b = 100 friends and none are shared, two users are d=4d = 4 hops apart. Why does searching from both ends reach far fewer people?

Question 6
In that idealized tree (b=100b = 100, d=4d = 4), how many times fewer people does bidirectional search reach than one-sided search?
×

Answers within 2% count.

Question 7
A bidirectional search stops as soon as the two frontiers first touch, and sometimes returns a path one hop longer than the shortest. What is the fix?

Question 8
In the primer’s design, each person the search visits costs a Lookup Service call and a fetch from a Person Server. Which optimization from the primer cuts those round trips?

13.3 Graph partitioning and the TAO cache

0 of 4 answered right
Open the lesson
Question 9
People are placed with hash(user_id) mod N\text{hash}(\text{user\_id}) \bmod N. Why are graph traversals slow?

Question 10
How does the primer suggest sharding Person Servers so more friend lookups stay on one server?

Question 11
Match each part of TAO’s caching design to what it does.

Question 12
What does TAO’s paper say about grouping users so that cross-partition requests become rare?

13.4 People you may know: ranking mutual friends

0 of 4 answered right
Open the lesson
Question 13
Why does the Adamic/Adar score weight a mutual friend with 20 friends more than one with 2,000?

Question 14
Ana’s friends are {Bo, Cy, Di, Ed}, and Fay’s are {Di, Ed, Gus}. What is their Jaccard coefficient?

Answers within 2% count.

Question 15
Two people have two mutual friends: one with 10 friends and one with 100. Using base-10 logarithms, what is their Adamic/Adar score?

Answers within 2% count.

Question 16
Dismissed suggestions are kept in a standard Bloom filter. A user undoes a dismissal, but that person stays hidden. Why?