☕ Self Driving Acquisition?

A self-driving car company was just acquired. A dev tools startup is now valued at $95 billion dollars. Plus, an answer to our last Google Interview Question.

Hey Guys,

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

Tech Snippets

• Performance Comparison between Python, Go, C++, C, AWK, Forth and Rust.

  • You’ve probably heard of the classic interview problem of counting frequencies of unique words and returning the frequencies in order.

  • Ben Hoyt solves this interview problem in several programming languages and compares the performance between languages.

• Cruise acquires Voyage

  • Voyage is the autonomous vehicle startup that spun out of Udacity ( an education platform for Software Engineers and Data Scientists).

  • The company was founded in 2017 and raised $52 million dollars to date.

  • Voyage is best known for their operations in two senior living communities. They’ve tested and give rides to people within a 40 square mile, 125,000 resident retirement city in Florida.

  • Cruise has acquired the company for an undisclosed sum and the majority of Voyage’s 60 person team will be moving to Cruise.

• Stripe valued at $95 billion dollars ahead of IPO

  • Stripe is a devtools startup that was founded 10 years ago (part of YC’s Summer 2009 class) by Patrick and John Collison.

  • The company’s core product is a payment processing API that makes it easy for developers to add payments to their applications. The stated mission of the company is to “increase the GDP of the internet”

  • The company has raised $600 million dollars at a $95 billion dollar valuation from Sequoia Capital, Fidelity, Ireland’s National Treasury Management Agency and Alliancz.

  • This triples it’s last valuation of $36 billion dollars from April 2020.

Interview Question

You are given an array nums of distinct positive integers.

Return the number of tuples (a, b, c, d) such that

a * b = c * d

where a, b, c and d are elements of nums and

a != b != c != d

Here’s the question in LeetCode.

We’ll send a detailed 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

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, 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.

Solution

We can solve this question recursively.

We recurse through our binary tree and check each node to see if it has to be deleted. If it doesn’t have to be deleted, we’ll see if it is a root.

If the node doesn’t have to be deleted and it is a root, then we add it to our forest.

Since we have to keep checking whether a node has to be deleted, we should convert our list to_delete to a set for faster lookups.

In our recursive function, we’ll take in two parameters. One is the current node that we’re iterating on. The other parameter is a boolean that tells us whether the current node is the root of a tree.

Then, we check if our current node needs to be deleted.

If it does, then we’ll call our recursive function on current node’s children and also set their boolean parameters to True (since they’re now the root of their own trees).

If the current node doesn’t have to be deleted, then we check if it’s the root of its tree.

If so, then we add the current node to our forest.

Then, we can run our recursive function on our current node’s children. This time, however, the parameter for whether the children are roots will be False.

Finally, we check if either of our current node’s children had to be deleted.

If so, we’ll set that child to None since we have to remove it.

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).