☕ Self Driving Pizza
Nuro partners with Dominos to deliver pizza with their self-driving robot. Tiger Global is investing heavily in the Indian startup ecosystem. Plus, a great website on Design Patterns in Python!
Hey Guys,
Industry News
Nuro partners with Dominos for Pizza delivery in the Houston Area
Dominos will start delivering pizzas using Nuro’s driverless cars in Houston this week as part of a pilot program. Customers can place orders online and their pizza will be delivered with Nuro’s R2 robot car.
So, if you’re in the Houston area, be sure to carry around a crowbar. If you’re lucky, you might spot one of Nuro’s cars and be able to snag yourself a free pizza! Just kidding.
Nuro was founded in 2016 by Jiajun Zhu and Dave Ferguson. Zhu was a principle software engineering at Waymo (Google’s Self Driving car project) and Ferguson was a principle machine learning engineer.
Both Zhu and Ferguson left Waymo in 2016 and founded Nuro that September. By January 2018, Nuro had brought their robotic delivery vehicles to market with $92 million dollars in funding from Greylock Partners.
Nuro also raised $940 million dollars from Softbank in 2019, valuing the company at $2.7 billion dollars. Currently, Nuro is valued at $5 billion dollars based off their Series C fundraising round. The company currently has more than 800 employees.
Nuro’s delivery car relies on a combination of vision (through convolutional neural networks), LIDAR and high definition maps of a location. They’re following the path of Waymo and Cruise by integrating LIDAR as part of their system (as opposed to Tesla which has decided against using LIDAR as part of their stack).
Nuro is quite unique in that they’re also building their own vehicle (not just a self-driving system like Waymo or Cruise). Their vehicle is specially built for deliveries with space for ~12 grocery bags.
The company’s R2 car is also being used in other places. Some medical facilities in California use Nuro to transfer medical supplies and their R1 car (previous version) was used in a pilot program in Scottsdale, Arizona.
Tiger Global goes super aggressive in India
If you follow the Venture Capital game, you’ve probably heard of Tiger Global. They’re a NYC-based hedge fund started by Chase Coleman, a protege of Julian Robertson ( founder of the famous Tiger Management hedge fund). They have around $50 billion dollars in assets under management.
The hedge fund has been taking Silicon Valley by storm with an incredibly aggressive approach to investing in technology companies. They’re known for moving extremely quickly in terms of due diligence (sometimes it’s just a day) and offering companies very attractive fundraising terms.
If you’d like to read more about Tiger’s approach in general, Everett Randall (a venture capitalist at Founders Fund) wrote an awesome piece on their strategy and why they’re pissing off a bunch of VCs.
Now, Tiger Global has the Indian startup ecosystem in their sights. They’ve finalized more than 25 deals with Indian startups this year.
Last week, they led investments in social network ShareChat, business messaging platform Gupshup and investment app Groww. All of these investments were at valuations more than $1 billion dollars.
However, Tiger Global isn’t new to the Indian startup ecosystem. In 2009 they were big investors in Flipkart and they invested in Ola in 2012.
They also backed music streaming service Saavn, fintech startup Razorpay and online grocer Grofers.
India is currently the world’s third largest startup hub and is rapidly growing (poised to produce more than 100 unicorns in the coming years according to Credit Suisse),
Tech Snippets
An awesome resource on Design Patterns in Python.
Talks about the 3 categories of Design Patterns - Creational, Structural, Behavioral
Those 3 categories break down into 22 Design Patterns, all detailed on the site.
Here’s another fantastic resource on Design Patterns in Python that is a bit more advanced. It directly references the famous Gang of Four book on DP.
An awesome blog post on how Emojis work!
Interview Question
You are given a dictionary of words.
Write a function that finds the longest word in the dictionary that is made up of other words in the list.
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl". 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 an array and an integer K where K is less than size of the array.
Return the smallest K numbers in the array.
Solution
The brute force solution is to just sort the array and then return the first K elements.
Using an algorithm like quicksort, this would take N log N where N is the number of items in the array.
Can we do better?
We can!
We only care about the K smallest numbers in the array. We don’t care about the ordering of the rest of the elements in the array. We also don’t care about the relative ordering of the K smallest numbers.
Therefore, we can use a max heap to keep track of the K smallest numbers.
We can check the largest element in our max heap in O(1) time, so we can quickly check if an element is small enough to be one of the smallest K numbers (it should be smaller than the largest element in the heap).
We’ll start by adding the first K elements in our array to our max heap. Then, we’ll iterate through the rest of the array.
For each element in our array, we’ll first check if it is smaller than the largest element in our max heap. If it is, then that means our element is one of the smallest K integers (that we’ve seen so far).
Therefore, we’ll insert it into our max heap. That is a log K operation. We’ll also have to remove the largest element in our max heap (since it should only be K elements). That’ll be another log K operation.
After we iterate through the entire array, then we can just return the elements in our heap.
The time complexity of our solution is N log K where K will always be less than or equal to N. This means it’s an improvement over N log N.
Note: for our Python 3 code, we make use of the heapq library. Unfortunately, heapq’s implementation is a min heap (we need a max heap). Therefore, we use a little “hack” where we multiply each number we insert by -1 (thereby reversing the order).
Here’s the Python 3 code
from heapq import heappushpop, heapify
from random import randint
def smallestKElements(nums, k):
# Take first K elements and heapify (linear time)
maxheap = [-1 * i for i in nums[:k]]
heapify(maxheap)
for i in nums[k:]:
if i < -1 * maxheap[0]:
heappushpop(maxheap, -1 * i)
return [-1 * i for i in maxheap]
There’s also an even faster solution using the Quickselect algorithm!
Quickselect is a variant of Quicksort, specifically meant to find the Kth smallest item.
In Quicksort, we select a pivot, reorder the numbers so that all the numbers smaller than the pivot are to the left and all the numbers larger than the pivot are to the right.
Then, we recurse on both sides.
In Quickselect, we only recurse on one side (the side that contains the Kth smallest element).
Once we find a pivot that divides the list into K elements on one side, then we’ve found the K smallest elements!
Quickselect runs in an average of O(n) time complexity, but it is O(n^2) in the worst case.