Uber gives up?
Uber sells its self-driving group (Uber ATG) to another competitor. Plus, a System Design Interview question and a solution to our last question on BST Iterators.
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
Industry News
Uber sells self-driving unit to Aurora
Uber Advanced Technologies Group (ATG) is being acquired by Uber competitor Aurora Innovation.
Uber ATG is a subsidiary of Uber that is focused on building self-driving cars. The group was first formed in 2015 when Uber hired 50 researchers/engineers from the robotics department at Carnegie Mellon University. In 2016, ATG launched its first self-driving car service to select customers in Pittsburgh, using a fleet of Ford Fusion cars. The cars used a combination of LIDAR, HD Mapping, and Computer Vision to navigate the streets.
In March 2018, the group came under heavy criticism when a pedestrian, Elaine Herzberg, was killed by Uber’s self-driving vehicle in Tempe Arizona. The Uber employee in the vehicle was distracted (watching YouTube videos on her phone) and Uber’s self-driving vehicle failed to detect the pedestrian.
Uber ATG has been sold to Aurora for a valuation of approximately $4 billion USD. This is nearly half of their valuation in April 2019, when Softbank, Toyota, and Denso bought a stake in ATG at a valuation of $7.25 billion USD.
Uber is still maintaining a 26% stake in ATG however, so they still have a stake in the subsidiary.
Interview Question
What are Data Models in Software Engineering?
What is the Relational Model and what is the Document Model?
What are some of the tradeoffs and benefits when comparing the models?
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
Implement a BSTIterator class that represents an iterator over the in-order traversal of a Binary Search Tree.
You should implement three functions
BSTIterator - the constructor of the class
hasNext - returns True if there is a number in the traversal to the right of the pointer.
next - moves the pointer to the right and then returns the number at the pointer.
Here’s the question in LeetCode.
Solution
The way we can solve this is by simulating an inorder traversal. When you do an inorder traversal, you typically code it recursively and take advantage of the call stack as a way to keep track of which node you’re on in the BST.
Since we’re building an iterator that does this, we can’t use recursion (and can’t take advantage of the call stack).
Instead, we have to simulate an interative inorder traversal.
For the iterative inorder traversal, we maintain an array s that simulates the call stack. As we traverse the BST, we follow the inorder pattern of exploring to the left, exploring the node, and then exploring to the right.
Here's the Python 3 code for an iterative inorder traversal.
Once you understand how to write an iterative inorder traversal, creating the inorder iterator is simple.
We create instance variables for our stack and current node and then implement our iterative inorder traversal logic in the next function. Our hasNext function can just check the length of our stack and the current node to see if we’ve ended the traversal yet.
If you have any feedback or questions, feel free to reply to this email!
Best,
Arpan