Hey Guys,

Tech Snippets

• Rest In Peace Daniel Kaminsky

  • Daniel Kaminsky is a legend in the cybersecurity space.

  • He’s best known for finding (and helping to fix) The Great DNS Vulnerability of 2008, a vulnerability in DNS that allowed an attacker to impersonate any legitimate website in about 10 seconds.

  • Here’s an awesome video (narrated by Dan Kaminsky) on what the issue was and how they “patched” it (they had to fly security researchers from around the world to a secret meeting at Microsoft headquarters to create a patch).

  • He passed away on April 23rd.

• O’Reilly is heavily discounting their book bundles for the next week ~ all proceeds get donated to Code for America.

  • Head First books on Go, Java, Python, Kotlin, Android Development, JavaScript, C#, Ruby, SQL, and C are all in an $18 dollar bundle. Pretty good deal!

Industry News

Lyft sells self-driving unit to Toyota

Lyft Level 5 is Lyft’s self-driving car unit that was first established in mid-2017.

They took an approach similar to Uber, Waymo, and Cruise, where they focused on the self-driving stack with LIDAR sensors, HD mapping, Radar, and Cameras. Lyft Level 5 then integrated this technology into Ford Fusions and Chrysler Pacificas. Their fleet is only accessible to Lyft employees in Palo Alto, California.

The Lyft Level 5 team numbered more than 400 engineers as of last year.

Toyota’s Woven Planet Holdings subsidiary has now purchased the Level 5 division from Lyft for $550 million dollars ($200 million paid upfront with $350 million made in payments over 5 years).

Woven Planet is a new entity created by Toyota in January 2021. It includes Toyota’s research group TRI-AD (Toyota Research Institute - Advanced Development) and has already invested in Nuro, a company developing cargo-only self-driving cars (we talked about Nuro here.)

Due to the acquisition, Woven Planet will be getting a talented engineering team and also a huge amount of Lyft’s data.

For Lyft, they’ll get the $550 million dollars but they’ll also be able to improve their profitability metrics. Lyft was spending $100 million dollars a year on operating expenses for their Level 5 division, and now Lyft can remove that spending from their income statement and improve profitability.

Previous Solution

As a refresher, here’s the last question

You are given an N x N matrix that contains positive and negative integers.

Write a function that finds the submatrix with the largest possible sum.

Solution

In order to keep today’s email to a reasonable length, we’ll give you the optimized solution tomorrow.

The brute force solution is to look at every possible submatrix and calculate the sum.

We then pick the submatrix with the largest sum.

In order to do this, we’ll have to use 4 nested loops.

The first loop will iterate through the rows in our matrix and use that row as the starting row of our submatrix.

The second loop (nested in the first) will iterate through all the rows after the starting row and use this row as the end row of our submatrix.

The third loop (nested in the second) will iterate through all the columns in our matrix and use that column as the start column of our submatrix.

The fourth loop (nested in the third) will iterate through all the columns after the starting column and use that column as the end column of our submatrix.

Inside the fourth loop, we’ll have our submatrix and we can calculate the sum of all the elements inside it.

Calculating the sum of the elements in our submatrix will take O(N^2) time.

Therefore, running the brute force algorithm takes O(N^6) time as we also had 4 nested loops.

Here’s the Python 3 code.

Interview Question

You are given an N x N matrix that contains positive and negative integers.

Write a function that finds the submatrix with the largest possible sum.

We’ve given the brute force solution above. Can you find the optimized solution?

Hint - look for repeated subproblems