☕ Be snowflake

Hey Guys,

Hope you’re all having a fantastic day! Here’s your interview question and industry news for the day!

Interview Question

Given two binary trees, write a function that checks if they are the same or not.

Two binary trees are considered the same if they are structurally identical and corresponding nodes have the same values.

We’ll send out the solution (with working code & test-cases) in our next email, 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

• Facebook’s Oculus Quest 2 leaks - Details about Facebook’s new Oculus Quest leaked after a pair of promotional videos were accidentally uploaded. The new headset will be powered by the Snapdragon XR2 platform (which is specifically designed for AR/VR hardware) and has an “almost 4K display”. The new headset has 6 GB of RAM (up from the last Quest’s 4 GB) and will be officially announced in mid September.

• Snowflake bumps expected IPO price by 30% - Snowflake is a cloud-based data warehousing company that is part of the “data warehouse as a service” trend. Their software now offers Data Engineering, Science, Exchange and other applications that you can run on top of AWS S3, GCP or Azure. The company is going public soon and has now increased their IPO price due to the large amount of demand. Snowflake could go public at a valuation of more than $30 billion dollars.

• Airtable raises $185M and launches new low-code and automation features - Airtable builds cloud collaborative software, with their main product being a spreadsheet-database hybrid, with the features of a database but applied to spreadsheets. The company is expanding into the very hot “no-code” and “low-code” areas, where you can do things that traditionally required programming (like sending API calls or writing to a database) with a GUI.The company has released Airtable Automations, an update that allows you to build custom, automated workflows to perform repetitive tasks. You can build these automations using the service’s GUI or by writing JavaScript code. If you’re familiar with “If This Then That” then you can think of this as IFTTT for Airtable.The company announced that it has raised a Series D funding round of $185 million, putting the company at a post-money valuation of $2.585 billion dollars.

Previous Solution

As a refresher, here’s the previous question

Given a reference to a node in a connected, undirected graph… return a deep copy of the graph.

You can assume that each node in the graph will contain a value (int) and a list (a list of nodes) of its neighbors.

Solution

We can solve this using a graph traversal algorithm. You can pick your favorite with BFS or DFS. We’ll be using DFS for the solution.

As you traverse the given graph, create the new graph simultaneously.

Use a hashmap to keep track of visited nodes and their corresponding mappings (to the new graph). The keys in the hashmaps are nodes that we’ve visited (in the original graph) and the values are the corresponding nodes in the deep-copy.

When we come across an unvisited node, we create its corresponding copy and add them to the hashmap. Then, we iterate through the original node’s neighbors and run the same process on each one of them (in a recursive DFS fashion).

You can view the Python 3 implementation of this here.

The time and space complexity are both linear.

Thanks for reading!

P.S.

Should I continue providing the solutions in Python? Or do you guys want a different programming language? Please reply to this email with what programming language you guys prefer the solutions in. Thanks!