Chapter 13 checkpoint

Chapter 13 checkpoint: social graph search

Every question from this chapter’s lessons. Your first answer to each is the one that counts; afterward you can practice again as often as you like. Passing needs 75% right on the first attempt.

0 of 16 answered0 right on the first attempt

Question 1 of 16

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?

Your answer

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

Question 2 of 16

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

Your answer

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

Question 3 of 16

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

Associations are undirected, so one covers a friendshipObjects are users; associations are postsObjects are typed nodes; associations are typed directed edges between objectsAssociations are cached copies of objects

Question 4 of 16

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?

Your answersearches/s

Answers within 5% count.

Question 5 of 16

In an idealized tree where everyone has

b = 100

friends and none are shared, two users are

d = 4

hops apart. Why does searching from both ends reach far fewer people?

The second search reuses the first one’s cacheEach side searches only about half the depth, and reach grows exponentially with depthIt uses edge weights to skip peopleTwo searches run in parallel, so each is twice as fast

Question 6 of 16

In that idealized tree (

b = 100

d = 4

), how many times fewer people does bidirectional search reach than one-sided search?

Your answer×

Answers within 2% count.

Question 7 of 16

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?

Cache the path for next timeSearch from one side onlyLower the hop limitFinish the current level, then pick the meeting point with the smallest total distance

Question 8 of 16

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?

Batch the lookups for friends who live on the same Person ServerSearch more hops at onceGive edges weightsAdd more Person Servers

Question 9 of 16

People are placed with

\text{hash}(\text{user\_id}) \bmod N

. Why are graph traversals slow?

Hashing puts most people on one shardEach person’s friends land on random shards, so every expansion touches many of themHash partitioning disables cachingAdding a shard moves most people

Question 10 of 16

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

At random, to spread load evenlyBy sign-up dateBy the first letter of each nameBy location, because friends tend to live near each other

Question 11 of 16

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

Leader cacheFollower cacheInvalidation and refill messagesConsistent hashing

Question 12 of 16

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

Cross-partition requests do not matter with SSDsIt is not possible, so the cache tier must make remote lookups cheapA good partitioner such as METIS makes them rareGrouping users by region makes them rare

Question 13 of 16

Why does the Adamic/Adar score weight a mutual friend with 20 friends more than one with 2,000?

A friend of few people says more about a shared circle than a friend of thousandsPeople with fewer friends joined more recentlyIt divides by the size of the unionIt does not; popular friends count more

Question 14 of 16

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

Your answer

Answers within 2% count.

Question 15 of 16

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

Your answer

Answers within 2% count.

Question 16 of 16

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

The filter has a false negativeA standard Bloom filter cannot remove entriesThe filter is full and rejects changesThe suggestion list is cached