Lectures on Distributed Systems

An awesome series of lectures on Distributed Systems. Plus a deep dive into what your web browser is doing when you type in a webpage. Also, Dan Abramov's comments on why npm audit is broken.

July 29, 2021

Hey Everyone,

Today we’ll be talking about

  • The Journey of a Web Page - How Web Browsers Work

    • A common interview question is “what happens when I type in www.google.com into a web browser”?

    • Read this for a detailed answer

  • Dan Abramov (co-creator of Redux and Create-React-App) blogs about why npm audit is broken

    • If you currently have 20+ issues whenever you run npm audit, you probably know what he’s talking about.

  • A fantastic series of lectures on Distributed Systems by Robert Morris (co-founder of Y-Combinator)

    • The lectures dive deep into real-world applications like Google Cloud Spanner and Apache ZooKeeper.

Plus, we talk about Dynamic Programming for the solution to our last coding interview question.

Don’t forget to 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

  • A pop-up will ask you “Do you want to do this for future messages from [email protected]” - please select yes

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

The Journey of a Web Page - How Browsers Work

A popular interview question is “what happens when I type www.google.com into my web browser?”

Your web browser goes through 5 main steps. Here’s each of the steps broken down…

Navigation

  • Resolve the web address through DNS Lookup. In order words, convert www.google.com to the IP address for Google’s servers.

  • Establish a connection to the server via a TCP 3-way handshake.

  • Establish a security protocol with the TLS negotiation (this only happens when you’re using HTTPS)

Fetching

  • Send an HTTP Request to Google’s servers.

  • Google’s servers send back an HTTP Response

Parsing

  • Parse the HTML from the HTTP Response and use it build the DOM Tree (the DOM tree is the data structure that represents your HTML document)

  • Parse the CSS from the HTTP Response and use it to build the CSSOM (CSS Object Model). It’s like the DOM, but for the CSS rather than the HTML.

  • Combine the DOM and CSSOM trees into the Render tree.

  • Compile the JavaScript code. The JavaScript source is first converted to an AST (Abstract Syntax Tree) and then compiled to bytecode by the JavaScript Engine.

  • Build an accessibility tree that assistive devices use to parse and interpret content. The AOM (Accessibility Object Model) is like a semantic version of the DOM.

Rendering

  • Determine the geometry and positioning of the nodes in the Render tree. This is the Layout step of the Critical Rendering Path (CRP).

  • Convert each box calculated in the Layout step to actual pixels on the screen. Draw every visual part of the elements on the screen (text, colors, borders, shadows, etc.). This is the Paint step of the CRP.

Finalising

  • Finish executing any deferred JavaScript code.

Once the browser accomplishes all of this, you have your finalized web page!

Read the full article for a much more detailed explanation of each step.

Tech Snippets

Dan Abramov on why npm audit is broken

Dan Abramov is co-creator of Redux and Create-React-App. He’s been part of the React Core team at Facebook since 2015.

He recently published a blog criticizing npm’s audit feature for its lack of context and severity in its warning messages.

How does npm audit work?

Npm Inc maintains a special registry that keeps track of any security vulnerabilities that are found on npm packages.

Anytime you run npm audit, npm will check all your packages against that registry for vulnerabilities.

If any vulnerabilities are found, then npm will inform you and check if upgrading the package will result in breaking changes.

Why is npm audit broken?

The issue with npm audit is that a huge amount of the warnings are complete non-issues and just false alarms.

npm’s default behavior leads to, in many situations, a 99% false positive rate. This results in a confusing experience for new developers and a nightmare for open source project maintainers.

Interview Question

You are given a string s which consists of lowercase or uppercase letters.

Return the length of the longest palindrome that can be built with those letters.

The letters are case sensitive. “Aa” is not considered a palindrome.

We’ll send the solution in our next email, 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

  • A pop-up will ask you “Do you want to do this for future messages from [email protected]” - please select yes

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

Here’s the previous question

Given an integer n, return the least number of perfect squares that sum to n.

Solution

The first step for solving this question is to create a list of all the perfect squares from 0 to n.

This is quite simple and can be done with the code below.

Now that we have our perfect squares, we can focus on solving the question.

The way we’ll solve it is with Dynamic Programming.

The essence of Dynamic Programming is that you have a problem that can be broken up into subproblems.

However, naively breaking up your question into subproblems results in a lot of repeated subproblems, which means repeated computation.

Therefore, you cache the solutions to your subproblems, so you don’t have repeated computation.

In terms of finding the fewest number of perfect squares that sum to n, let’s first look at an example.

Let’s say n is 20.

The perfect squares that are smaller than 20 are

[1, 4, 9, 16]

We’ll go through each of these squares and try all of them out as a square that we’ll use in our perfect squares sum. While doing this, we’ll keep track of the fewest number of perfect squares in the variable minSquares.

We’ll first try 1.

If we include 1 in our perfect squares sum, then we’re left with (20 - 1) or 19 as our new value for n.

We can then recursively call our function to find the fewest number of perfect squares that sum to 19.

We’ll increment that solution by 1 since we already have a 1 in our perfect square sum. We can set minSquares equal to this number.

Now, we’ll try 4.

If we include 4 in our perfect squares sum, then we’re left with (20 - 4) or 16 as our new value for n.

We can now recursively call our function to find the fewest number of perfect squares that sum to 16. That solution will obviously be 1 since 16 is a perfect square.

Now, we increment 1 by 1 since we already have a 4 in our perfect square sum. We can now set minSquares to the minimum of minSquares or 2.

We’ll continue this process for 9 and 16 in our perfect squares list.

After, we can return minSquares as our final answer.

There are two ways of implementing DP here. We can go with the top down approach or the bottom up approach.

The top down approach would be to have our recursive function and add a hash table to cache the possible values for n and their solutions.

The bottom up approach would be to calculate the fewest number of perfect squares that sum to k for all the values of k from 1 to n.

We’ll keep track of all these solutions in an array, and we can refer back to our array instead of using a hash table for our cache.

Here’s the Python 3 code for the bottom up approach

What’s the time and space complexity of this approach?

Reply back to this email with your answer, and we’ll tell you if you’re right or wrong!