Must-know Google problem

Welcome back!

This week’s problem will help you solve many other similar problems. We’ll learn one of the most popular binary tree traversals today. Let’s do this.

Here’s what to expect today:

• Binary Tree Level Order Traversal

• How Uber finds nearest driver?

Read time: under 4 minutes

CODING CHALLENGE

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Solve the problem here before reading the solution.

PRESENTED BY ONELEET

Want SOC 2 compliance without the Security Theater?

Question 🤔 does your SOC 2 program feel like Security Theater? Just checking pointless boxes, not actually building security?

In an industry filled with security theater vendors, Oneleet is the only security-first compliance platform that provides an “all in one” solution for SOC 2.

We’ll build you a real-world Security Program, perform the Penetration Test, integrate with a 3rd Party Auditor, and provide the Compliance Software … all within one platform.

Schedule a demo to get a quote! 🛡️

SOLUTION

To solve this problem, we'll use a breadth-first search (BFS) approach with a queue. We'll traverse the tree level by level, adding each node's value to the corresponding level's list.

We'll start by checking if the root is None. If it is, we return an empty list. Otherwise, we initialize a queue with the root node and an empty result list.

For each level, we'll process all nodes currently in the queue. We'll add their values to a level list and enqueue their children (if any). After processing all nodes at a level, we'll add the level list to our result.

This process continues until the queue is empty, meaning we've traversed all levels of the tree.

The time complexity of this solution is O(n), where n is the number of nodes in the tree.

COMMUNITY

InstaByte Question Bank

🧠 Help each other by sharing the actual questions you were asked in a recent interview. Use this form to submit your question.  

We will share the submitted questions on this weekly newsletter - stay tuned!

Note: Your submission is anonymous.

SYSTEM DESIGN

How Uber finds the nearest driver?

The constant movement of drivers makes it difficult to find the nearest driver. Doing a database query on all the available drivers would be very expensive.

To solve this problem, Uber uses the H3 library which is a hexagonal hierarchical geospatial indexing system. Here is how it works:

Imagine covering the whole Earth with tiny hexagon-shaped pieces. Each hexagon has a unique number, making it easy to find. These hexagons come in different sizes - small ones for crowded areas and large ones for sparsely populated areas.

When you request a ride, Uber looks at which hexagon you're in. Then it checks the neighboring hexagons to see if there are any drivers. This is much faster than calculating the exact distance to every driver. The hexagon shape makes it easy to check nearby areas evenly in all directions.

This system helps Uber quickly find drivers near you, even when millions of people are using the app at the same time.

NEWS

This Week in the Tech World

Amazon Mandates Office Return: Amazon CEO Andy Jassy requires corporate staff to work 5 days a week in office starting January 2025. Company also plans to flatten management structure by 15% to reduce bureaucracy.

Snap Unveils New AR Glasses: Snap announced 5th generation Spectacles AR glasses for developers. Monthly subscription required. Partnership with OpenAI to enable AI features on the smart glasses.

Samsung Workers Strike in India: Workers at Samsung's Chennai plant continue strike for 5th day, disrupting production. Demands include union recognition and better working conditions. Samsung shares fall 3% on news.

Microsoft Cuts Xbox Jobs: Microsoft lays off 650 employees in Xbox division, third round since Activision Blizzard acquisition. Cuts mainly affect corporate and support roles as part of post-merger restructuring.

YouTube Adds AI Features: YouTube launches AI tools from Google DeepMind for Shorts creators. New "Veo" features allow AI-generated backgrounds and 6-second video clips from text prompts. Full rollout expected by 2025.

Amazon Hikes Warehouse Pay: Amazon increases average hourly pay for US warehouse workers to over $22. Company also adds free Prime membership as new employee perk starting early 2025.

Uber Expands Driverless Rides: Uber partners with Waymo to offer autonomous rides in Austin and Atlanta starting 2025. Rides only available through Uber app, unlike in other cities where Waymo app is used.

HELP US

👋 Hi there! We are on a mission to provide as much value as possible for free. If you want this newsletter to remain free, please help us grow by referring your friends:

📌 Share your referral link on LinkedIn or directly with your friends.
📌 Check your referrals status here.

BONUS

Just for laughs 😏

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra