Story to Share

Medium, in its own words, is "a place where everyone has a story to share and the best ones are delivered right to you." You might recall that CS50’s own blog lives at medium.com/@cs50.

So how does Medium know whether someone’s read a post already? Read a tale of code, dinner, and a favour with unexpected consequences to find out. The post’s a bit long, but odds are you’ll find it sufficient to read these sections, merely skimming or skipping the rest:

Answer the below in story.txt.

Questions

  1. (2 points.) Why doesn’t Medium just use an array to store, for each user, the unique identifiers of the posts that a user has already read?

  2. (2 points.) Why doesn’t Medium just use a linked list to store, for each user, the unique identifiers of the posts that a user has already read?

  3. (2 points.) Why doesn’t Medium just use a trie to store, for each user, the unique identifiers of the posts that a user has already read, effectively treating the identifiers like words in a dictionary?

  4. (4 points.) Why does Medium sometimes think a user has read some post, even though the user has not?

Debrief

  1. Which resources, if any, did you find helpful in answering this problem’s questions?

  2. About how long did you spend on this problem’s questions?