☕ Google making moves

G’ Morning!

Hope you’re having an awesome day!

Here’s your interview problem and industry news!

Interview Problem

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

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

• Sundar Pichai announces Google will try ‘hybrid’ work-from-home in the future - Google regularly surveys it’s workforce on their preferences regarding office protocol. In a recent survey, most Google employees said they want to return to the office at some point, but not be expected to come in every day. In response to this request, Sundar Pichai said the company is planning “hybrid” models for future work where employees can work-from-home a couple days of the week and then come in on the other days. Other tech companies are taking more drastic steps as Twitter has announced that employees can work remotely forever and Facebook announced that as much as 50% of the company’s workforce would be working remotely in the next 5 to 10 years. As of right now, all tech companies are currently WFH due to COVID-19. The current deadline for when tech offices will reopen is currently July 2021.

• Google’s Flutter is finally available for Windows Apps in alpha - Flutter is Google’s open source UI development kit. It was originally for Android and iOS app development, but has since expanded to cover the web, Linux and MacOS. Apps are developed using Google’s Dart programming language.Now, Flutter will support Windows 7 devices and above, and Google has stated that they will continue to stabilize Flutter for Windows in the coming months.

• GoodRx rose 53% in their trading debut - Another day, another crazy IPO. GoodRx, a telemedicine website and online marketplace for prescription drugs, began trading on Wednesday and shares closed at $50.50. This gave the company a market value of $19.4 billion. The target price was $24 - 28 and the shares opened on Wednesday at $46.00.GoodRx was originally founded to enable customers to shop for the best prices on prescription drugs. Prices can vary widely pharmacy to pharmacy and also between brand names vs. generics. The goal was to direct customers to the drugstore with the best deal and offer coupons (and make revenue off affiliate commissions).Last year, GoodRx acquired HeyDoctor LLC, and that gave it a property in the rapidly growing telemedicine space. Demand for this space has surged drastically since the start of the COVID-19 pandemic, helping the company grow extremely quickly.

Previous Solution

As a reminder, here’s the last question!

Write a program that solves a Sudoku puzzle by filling in the empty cells.

You’ll be given a 2-D array that represents a Sudoku board. The board will contain only the digits 1 - 9 or empty strings that represent spaces. The board will always be 9x9.

Fill in the empty spaces with integers to generate a valid Sudoku board and return the completed 2-D array.

A valid Sudoku board satisfies…

1. Each of the digits 1 - 9 must occur exactly once in each column.

2. Each of the digits 1 - 9 must occur exactly once in each row.

3. Each of the digits 1 - 9 must occur exactly once in each of the nine 3 x 3 sub-boxes in the grid.

Solution

So, this is a classic example of a Backtracking problem.

We incrementally build up our sudoku board by going row by row and looping through the numbers 1 - 9 for each box.

We start with the number 1 and place it in our box. Then, we check the row, column and 3 x 3 square to make sure our placement is valid.

• If it is valid, then we finalize the placement by updating our row, column and 3 x 3 square with the placement. After, we move on to the next square.

• If it’s invalid, then we remove 1 (we backtrack) and move on to the next possible placement number in our loop (which is 2). The loop continues until 9. If every possible integer in our loop fails to be placed, then we have an impossible Sudoku problem and should terminate.

We can terminate our program when there are no more squares left (assuming the Sudoku problem is not impossible). At that point, we will have a valid Sudoku board so we can return it.

If this question was too challenging for you, do you think you can write a function that takes in a completed Sudoku board and returns a boolean on whether the board is valid (satisfies all the rules around rows, columns and 3 x 3 squares)?

You can view our Python 3 code here. There's also a function for you to code that checks if the Sudoku board is valid!