Hey Guys,

Here’s your Tech Snippets and Interview Problem for the Day!

Tech Snippets

• Ben Thompson of Stratechery wrote a fascinating article on Roblox.

  • The biggest questions in tech revolve around the next platform. Facebook, YouTube, Twitter, Instagram and other platforms have dominated the web 2.0 era.

  • The next step is to create The Metaverse. The Metaverse was coined in Neal Stephensen’s 1992 science fiction novel Snow Crash. It’s the online analog of the physical world, where you can do anything (except now in virtual reality).

  • Ben Thompson sees Roblox as a company that is close to creating this vision (and thus establishing them as the dominant platform of the next decade).

  • Roblox has their own economy, identity system, social graph and has a variety of content/experiences.

• Become a better programmer by reading Git!

  • Reading, analyzing and understanding high quality codebases is a fantastic way to improve your programming skills.

  • The Git version control system’s codebase is a fantastic place to start.

    • It’s one of the most popular software dev tools on the planet. Understanding how Git works internally will give you awesome insights when using the tool.

    • Git is written in C, which allows many developers to branch out into an important language that they might not have much experience with.

    • Git makes use of many important concepts like hash functions, caching and file compression.

    • Git’s initial commit is quite small. It’s less than 1,000 total lines of code.

  • Jack Stopak created the repo Baby Git to aid with this.

Interview Question

You are given the root of a binary tree, where every node in the tree has a distinct value. You are also given a list named to_delete, which contains the values of nodes that you need to delete.

After deleting all the nodes with a value in the to_delete list, you’ll be left with a forest (a disjoint union of trees).

Return the roots of all the trees in the remaining forest.

Here’s the question in LeetCode.

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

You are given the root of a binary tree.

We define the “difference” of nodes A and B as

difference = |A.val - B.val|

Find the largest difference between any two nodes A and B in the tree, as long as A is an ancestor of B.

Here’s the question in LeetCode.

Solution

The “brute force” way of solving this would be with a depth first traversal.

We use a depth first traversal to visit every node in the tree.

Then, for each node we do another depth first traversal of that node and find the difference with that node as node A (explore that node’s descendents for a node B that maximizes the difference).

The time complexity of this approach is O(N^2).

Can we do better?

Yes!

We can solve this question faster by keeping track of the maximum and minimum nodes seen so far.

Then, as we search our tree, we look for the largest possible difference with the current node and either the current max/min.

This way, we’ve “flipped” the problem around as we’re keeping track of the largest/smallest possible node A values and then we check each node as a node B.

This way, we only have to do one tree traversal.

Here’s the Python 3 code.

Can you analyze the time complexity of our solution?

Reply back with your estimate!

We’ll tell you if you’re correct (or we’ll tell you the answer if you’re wrong).