☕ Amazon bets big

Good Morning Planet Earth!

Hope you’re all having a great day!

Here’s your interview problem and industry news!

Interview Problem

You’re given a sorted array of integers as input (sorted in ascending order).

Convert the array to a height balanced BST.

We’ll send out the solution (with working code & test-cases) 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 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”

Industry News

• Amazon enters the Cloud Gaming space with Luna - Amazon has announced a cloud gaming platform called Luna, that will be in direct competition with Google’s Stadia and Microsoft’s xCloud. While the launch date is unclear, Amazon has stressed that the service will be available on PC, Mac, Fire TV and iPhone and iPad. An Android version will be released after the launch. The service will be available for an introductory price of $5.99 a month during the early access phase, which gives subscribers the ability to play Luna Plus channel games across two devices simultaneously and offers 4K / 60 FPS resolution for “select titles”.Obviously, the service will be powered using AWS but Amazon is making an interesting design choice with the iPhone/iPad apps. The Luna apps on iOS are actually PWAs (Progressive Web Apps), so they’re browser-based apps as opposed to native iOS applications. As with all other PWAs, you’ll download the PWA in your browser (from Amazon’s Luna website in this case) and the icon on your home screen will be a shortcut to Amazon’s cloud gaming portal on the web. The Luna app will not be available in the iOS App Store. This allows Amazon to avoid Apple’s App Store fees.

• Palantir releases more details on their IPO - Palantir is a company that specializes in data mining and analytics and was founded by Peter Thiel and Alex Karp. The company plans to debut on September 30th with shares trading at around $10. This results in a valuation of nearly $22 billion dollars.2020 is shaping up to be one of the busiest years for IPOs on record, especially for companies in the tech space. There’s been massive investor interest in fast-growing technology upstarts and the public markets have been very strong due to the Federal Reserve’s policy on interest rates. Newly public shares are rising an average of 22% on their first day of trading, which is the best average first-day performance since the tech boom.

Previous Solution

As a refresher, here’s the previous question

Given a Binary Tree, determine if the tree is a valid Binary Search Tree.

Remember that the properties of a BST are

• The left subtree contains only nodes with keys less than the current key

• The right subtree contains only nodes with keys greater than the current key

• The left and right subtrees are both also BSTs

Solution

As with many tree problems, it’s a good idea to start thinking of a recursive solution.

For each node, there is a lowerBound and an upperBound that the node’s value must be within (for the root, the lowerBound is negative infinity and the upperBound is infinity).

Therefore, the parameters of our function will be the root, lowerBound and upperBound.

In our function, we first check to make sure the root isn’t None. If it is, then we can just return True (we’re assuming None counts as a valid BST).

We then check to make our node’s value is within the bounds. If it’s not, we can immediately return False.

Otherwise, we check to make sure that the left subtree is a BST. Since we’re going to the left subtree of our node, every value in the left subtree must be less than our current node’s key. Therefore, we should set our upperBound to the current node’s value. We then recursively call our function on the left subtree to check if it’s a BST.

We repeat the same process on the right subtree. Every value in the right subtree must greater than our current node’s key. Therefore, we set our lowerBound to the current node’s value. We then recursively call our function on the right subtree to check if it’s a BST.

Then, if both the left and right subtrees are also BSTs, we can return True.

Otherwise, we return False.

Here’s the solution in Python.