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!

• Inside a Viral Website

  • 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+1th item, we will randomly select it with a probability of (m/m+1).

If the m+1th 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+1th item.

For the m+2th 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+ith item, that will have a probability of (m/m+i) of being selected.

And so on until we reach the nth 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!