# ☕ The Nobel Prize of Computing

### 2020's Turing Award (often referred to as the Nobel Prize of Computing) has been awarded! Also, what happens when your website gets 50 million hits over a period of 5 days?

Hey Guys,

Interviewing.io is a *fantastic* resource I wanted to share with you all.

You can **book realistic mock interviews with senior FAANG engineers** who will give you **detailed and actionable feedback** on exactly what you need to work on.

Mastering algorithms on LeetCode and system design on SystemsExpert is great, but they don’t prepare you for the pressure and stress that comes from an actual interview setting.

The best part?

**You don’t pay anything until you’re hired.**

Check them out here.

*Special thanks to Interviewing.io for sponsoring Quastor Daily. I’m a user of the service!*

# Tech Snippets

**Alfred Vaino Aho and Jeffrey David Ullman are recipients of the 2020 Turing Award**The Turing Award (named after Alan Turing) is recognized as the highest distinction in computer science (the “Nobel Prize of Computing”)

This year’s recipients are being recognized for their highly influential work on compilers and algorithm design/analysis techniques.

Aho and Ullman are the authors (along with Ravi Sethi) of the amazing “Dragon Book” on Compilers

The Turing Award carries a $1 million dollar prize, so a pretty good payday!

This was an awesome read on what it was like to build and operate a website that goes viral (50 million views in a 5 day period).

istheshipstillstuck.com displays a simple Yes/No message on the status of the Ever Given, a container ship that got stuck in the Suez Canal and blocked billions of dollars worth of goods for six days.

Tom Neil, creator of the site, built it with NextJS (a framework built on top of React) and used Vercel for hosting. With this combo, Neil didn’t have to worry about scaling the site at any point. Even with millions of hits, the page continued to load in less than half a second.

Neil also used Simple Analytics in order to track page views and traffic source. They don’t use cookies so you don’t have to display cookie consent banners.

Neil then goes into how he tried to monetize his website…. with NFTs of course!

Obviously, he ends the saga by rick-rolling his users.

**Substack raises $65 million dollars at a valuation of $650 million dollars**Substack is an online platform that provides publishing, payment, analytics and design infrastructure for subscription newsletters.

The company’s goal is to build more “single person media companies”, where a single person can use Substack’s infrastructure to build their own publishing business and distribute content to their audience.

Andreessen Horowitz was originally planning to do the deal at a valuation of $325 million, but Marc Andreessen got word that Quastor Daily is using Substack and immediately upped his valuation.

This would be Substack’s Series B round, so a valuation of $650 million for a Series B is pretty enormous.

# Interview Question

Design an algorithm to figure out if someone has won a game of tic-tac-toe.

*We’ll send a detailed solution tomorrow, so make sure you move our emails to primary, so you don’t miss them!*

**Gmail users**—move us to your primary inbox

**On your phone?**Hit the 3 dots at the top right corner, click "Move to" then "Primary"**On desktop?**Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

**Apple mail users**—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

# Previous Solution

**As a refresher, here’s the last question**

Write a function to randomly generate a set of *m* integers from an array of size *n*.

Each element must have an equal probability of being chosen.

**Solution**

The key to solving questions of this type is a technique called Reservoir Sampling.

Reservoir Sampling is a family of algorithms for choosing a simple random sample of *k* items from a population of unknown size *n* **in a single pass over the items**.

Here’s a *fantastic *video on Reservoir Sampling. I’d highly recommend you watch it if you’re unfamiliar with the concept.

So, the video is for picking 1 item from *n* items where *n* is unknown (and you want each of the *n* items to have an equally likely probability of being picked).

For our problem, we want to pick *m* items out of *n*.

We can do this by selecting the first *m* items and placing them in our sample.

Then, for the *m+1*th* *item, we will randomly select it with a probability of (m/m+1).

If the *m+1*th item is selected, then we will randomly select one of our m items (each has a (1/m) probability of being selected) to be replaced by the *m+1*th item.

For the *m+2*th item, that will have a probability of (m/m+2) of being selected, and if selected will randomly replace one of the items in our current sample (chosen with probability 1/m).

For the *m+i*th item, that will have a probability of (m/m+i) of being selected.

And so on until we reach the *n*th integer.

At the end, we’ll have *m* integers out of the *n* possible choices where each integer had an equally likely chance of being selected.

**Want more practice with real FAANG software engineers?**

Check out Interviewing.io!

You don’t have to pay anything until you get that job at FAANG!

## Create your profile

## Only paid subscribers can comment on this post

Log in## Check your email

For your security, we need to re-authenticate you.

Click the link we sent to , or click here to log in.