Google begins 2025 layoffs

Welcome back!

As Google kicks off its 2025 layoffs, we’ll solve a problem from Google interviews.

Today we’ll cover:

• Construct Binary Tree from Preorder and Inorder Traversal

• Consensus Algorithms

Let’s do this!

Read time: under 4 minutes

CODING CHALLENGE

Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

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

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Solve the problem here before reading the solution.

PRESENTED BY SUPERHUMAN AI

Start learning AI in 2025

Keeping up with AI is hard – we get it!

That’s why over 1M professionals read Superhuman AI to stay ahead.

• Get daily AI news, tools, and tutorials

• Learn new AI skills you can use at work in 3 mins a day

• Become 10X more productive

Sign up and start mastering AI

SOLUTION

To construct a binary tree from preorder and inorder traversals, we'll use a recursive approach.

The first element in preorder traversal is always the root. We can find this element's position in inorder traversal to determine which elements belong to left subtree and which belong to right subtree.

For each recursive call, we'll create a new node, recursively construct its left and right subtrees using the corresponding portions of preorder and inorder arrays.

We'll use a hashmap to store indices of elements in inorder traversal for O(1) lookup. This makes the time complexity O(n), where n is the number of nodes in the tree.

SYSTEM DESIGN

Consensus Algorithms

In distributed systems, multiple servers need to agree on data and actions even when some servers fail or network issues occur. This is where consensus algorithms come in. They help servers reach agreement despite these challenges.

Let's look at three popular consensus algorithms: Paxos, Raft, and Byzantine Fault Tolerance (BFT).

Paxos is the oldest and most proven consensus algorithm. It works by having servers play different roles - proposers suggest values, acceptors vote on proposals, and learners track the final decisions. While Paxos is very reliable, it's complex to understand and implement correctly. This complexity led to the development of simpler alternatives.

Raft makes consensus easier to understand by breaking it into smaller, more manageable parts. It uses a leader-based approach where one server is elected as leader and manages all changes. If the leader fails, a new election happens automatically. Other servers simply follow the leader's instructions. This simpler design makes Raft more practical to implement, though it may be slightly less efficient than Paxos.

Byzantine Fault Tolerance handles an even tougher problem - reaching consensus when some servers might be malicious or compromised. It requires more servers and message exchanges than Paxos or Raft, but can handle situations where servers might deliberately try to disrupt the system. This makes it valuable for blockchain and cryptocurrency systems.

Here's how these algorithms compare:

FEATURED COURSES

5 Courses of the Week

✅ Penn’s Python & Java Programming: Start with Python basics and advance to Java object-oriented programming. Build functional applications including banking systems and data analysis projects.

✅ Duke’s LLMOps Specialization: Deploy and manage large language models across cloud platforms. Gain practical experience building AI applications on Azure, AWS and Databricks.

✅ Imperial College’s Maths for ML: Master the essential math (linear algebra, calculus, dimensionality reduction) needed for advanced machine learning and data science.

✅ IBM Applied Data Science with R: Learn R programming for data analysis, SQL integration, and visualization. Build a complete data science portfolio with practical projects.

✅ IBM Data Analyst Certificate: Master Python, SQL, Excel and visualization tools for entry-level data analysis roles. Includes hands-on projects and earns college credits.

NEWS

This Week in the Tech World

Google Cuts Android and Pixel Jobs: Google laid off hundreds of employees in its platforms and devices unit, following January buyout offers. The cuts affect teams working on Android, Pixel phones, and Chrome, as part of Google's effort to operate "more effectively."

Meta Faces Historic Antitrust Trial: Meta's antitrust trial began Monday and could force the company to divest Instagram and WhatsApp. The FTC alleges Meta bought these platforms to eliminate competition, citing Zuckerberg's 2008 statement: "It is better to buy than compete."

Apple Airlifts iPhones from India Before Tariffs: Apple chartered flights to transport 600 tons of iPhones (about 1.5 million devices) from India to the US to beat Trump's tariffs. Production was boosted with Sunday shifts at Foxconn's Chennai factory, and customs clearance was cut from 30 to 6 hours.

Tech Companies Face Global Trade Tensions: Big Tech is caught in Trump's trade war despite early support. The EU is considering digital advertising levies, TikTok's US future looks uncertain amid US-China tensions, and Tesla has lost market value while facing tariff challenges.

Black Market Facebook Groups Selling Driver Accounts: A new report identified 80 Facebook groups with up to 800,000 members selling Uber and DoorDash accounts, allowing buyers to bypass background checks. Meta says it's reviewing the report and will remove content violating its policies.

Trump Exempts Electronics from China Tariffs: President Trump exempted smartphones, computers, and other electronics from steep China tariffs. The exclusions provide relief to tech companies like Apple while maintaining 20% fentanyl-related tariffs on all Chinese imports.

Tech Leaders Split on IP Law: Twitter co-founder Jack Dorsey called to "delete all IP law" on X, with Elon Musk agreeing. Former VP candidate Nicole Shanahan countered that IP law separates human creations from AI creations. The debate comes amid numerous copyright lawsuits against AI companies.

HEARD ABOUT AGENTIC AI?

You’ve heard the hype. It’s time for results.

For all the buzz around agentic AI, most companies still aren't seeing results. But that's about to change. See real agentic workflows in action, hear success stories from our beta testers, and learn how to align your IT and business teams.

Watch the product showcase now

BONUS

Just for laughs 😏

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.

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra