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!

• Database Sharding Tech Dive

Snippets

• An awesome reading list on Distributed Systems

• Travis CI is no longer providing CI minutes for open source projects

• Hitchhiker’s Guide to Caching Patterns

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.

Here’s the Python 3 code.

If you have any feedback or questions, feel free to reply to this email!

Best,

Arpan