Hi Everyone!

Hope you’re all having a great weekend!

Here’s your Interview Problem, Yesterday’s Solution and Tech Snippets for the day!

Tech Snippets

• Microsoft invests $2 billion dollars in self-driving car startup Cruise

  • This investment brings Cruise’s valuation to $30 billion dollars and makes Microsoft an official partner.

  • As a result, Cruise will rely on Azure, Microsoft’s cloud computing platform, for their autonomous vehicles.

  • Sanjay Ravi, GM of Automotive Industry at Microsoft, detailed Microsoft’s strategy for Self-Driving cars in a blog post in 2019.

    • Microsoft aims to partner across the automotive industry. The company does not see building automobiles as a core competency, so they’d prefer joint ventures.

  • Microsoft also made a strategic partnership with OpenAI, investing more than $1 billion dollars into the company with a mission of developing a safe Artificial General Intelligence.

  • Much of Microsoft’s investments are in the form of Azure credits, so it’s a smart way of increasing adoption on their cloud computing platform.

• Porcupine - a compiler for homomorphic encryption

  • Homomorphic encryption is a technology that enables computational workloads to be performed directly on encrypted data.

  • This would enable secure remote computation, like allowing a cloud platform like AWS to compute on highly sensitive data without being able to directly view it.

  • Despite the promise, Homomorphic encryption has seen little adoption due to the performance overhead and compilation challenges.

  • Porcupine seeks to change that.

Interview Question

You are given an array of integers containing n + 1 integers.

All the integers in the array are in the range [1,n]

There is only one repeated number in the array.

Return this repeated number in the most efficient way possible.

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

Code an in-order traversal for a Binary Search Tree.

Can you write your function both recursively and iteratively?

Here’s the question in LeetCode.

Solution

When an inorder traversal is performed on a Binary Search Tree, it will extract all the numbers in the BST in order.

You do it by first exploring the left child (all numbers smaller), then the node’s value, and then the right child (all numbers greater).

You can code this exact logic in recursively, but what about iteratively?

In the iterative solution, you have to simulate the stack in some way, so we do that with a list (aptly called s).

We simulate exploring the left child (while appending the current node to s) and then popping off elements from s and exploring them (and their right children).

Time and space are linear for both solutions.

Here’s the Python 3 Code

There is, however, a solution that takes constant space time. Can you figure it out?

Best,

Arpan