Buying Killer Robots?

Boston Dynamics has been purchased by an unexpected buyer. Amazon invests in a startup. The solution to yesterday's Dynamic Programming Interview question.

Hi Everyone!

Hope you’re all having a fantastic day!

Tech Dive

No tech dive for today! Our last tech dive was on Database Sharding!

Snippets

  • Amazing twitter thread by a Principal Engineer at Amazon about his experiences at Uber. Mostly focused on how he and his team managed to avert a massive engineering disaster (several disasters, actually). -> here.

  • French watchdog fines Google and Amazon $150 million dollars for breaking rules around HTTP cookies (not seeking consent before storing cookies). -> here.

  • Uber launches Uber Connect, a delivery service that allows users to send supplies and items to nearby friends and family. -> here.

Industry News

Hyundai purchases Boston Dynamics for $921 million dollars

Boston Dynamics is an engineering and robotics design company started in 1992, as a spinoff out of MIT. You’ve probably seen videos of their robot dog, Spot, doing tricks, opening doors, and killing people (if you’re a fan of Black Mirror).

The company has now been sold to Hyundai Motor Company for $921 million dollars.

Boston Dynamics has been owned by several conglomerates before this though. In 2013, Boston Dynamics was acquired by Google and became part of Google X. In 2017, Google announced that they were selling the company to Japan’s Softbank Group for an undisclosed sum. Now, Hyundai is buying Boston Dynamics from Softbank.

Since 2019, Spot (their robot dog) has been made commercially available. The company is also working on other robots like Cheetah, a four-footed robot that can run at up to 28 miles per hour (land speed record for a legged robot). Cheetah can also climb stairs and jump over obstacles.

They also have a 2 legged robot named Atlas that can do various flips, spins, and splits. Pretty cool video here.

AWS leads $36 million dollar investment for Kubernetes startup Weaveworks

Weaveworks is an extremely hot startup in the developer tools space. They build a platform for companies that want to go cloud-native (in terms of their infrastructure) and offer Kubernetes to help these companies with container management. Companies are investing heavily in cloud services and thus use containerized applications. The use of containerized applications brings the need for container orchestration, which is where Kubernetes comes in. Check out our tech dive on Docker if you want to learn more.

Weaveworks helps companies with this change through their GitOps platform.

Weaveworks is super hot, and they just raised $36 million dollars from AWS (yes, Amazon Web Services), Ericsson, and a couple of venture capital firms. This brings their total amount raised to $60 million dollars.

Interview Question

Write an algorithm that searches for a target value in an m x n integer matrix.

The matrix will have the following properties

  • integers in each row are sorted in ascending from left to right

  • integers in each column are sorted in ascending from top to bottom

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 previous question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character

  • Delete a character

  • Replace a character

Solution

This is a pretty typical Dynamic Programming question. What we’re calculating here is actually called the Levenshtein Distance.

We’ll use Top-Down Dynamic Programming to solve this.

We create two pointers, p1 and p2 which are pointers to letters in word1 and word2.

p1 and p2 both start at character 0 for word1 and word2 respectively.

We compare the letters at p1 and p2 and see if they’re the same. If they are, then we can just increment p1 and p2 and recursively call our function.

Otherwise, we have 3 operations.

  • replace

  • delete

  • insert

If we replace the character in word1 or word2, then that means we can increment p1 and p2.

If we delete the character in word1, then that means p1 will increment while p2 will stay the same. The same logic applies for insertion.

We test all three choices with a recursive call to our function. We’ll also increment the “edits” counter so that we know we made an edit.

Then, we’ll get back three edit counts for replace, delete, and insert and we’ll return the minimum of the three!