Amazon asked this easy problem

Welcome back!

This week’s coding challenge is not as easy as it looks. Even if you know the solution, finding the time complexity is hard. Let’s see if you can solve it.

Today we will cover:

• Convert Sorted Array to Binary Search Tree

• Idempotency in Distributed Systems

Read time: under 4 minutes

CODING CHALLENGE

Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

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 convert a sorted array into a height-balanced BST, we can use a recursive approach. The middle element of the array will be the root of our tree. The left subtree will be constructed from elements before the middle element, and the right subtree from elements after the middle element.

The time complexity of this solution is O(n), where n is the number of elements in the array. That’s because we’re processing each element exactly once.

Many people might think that the time complexity should be O(log(n)) because we are splitting the array in half at each step. But if you notice, we are processing both the left and the right half of the array after splitting. This means that we are not cutting the search space in half at each step. So time complexity is not O(log(n)).

SYSTEM DESIGN

Idempotency in Distributed Systems

In distributed systems, network failures or timeouts can cause operations to be accidentally repeated. For example, when you click "Submit Payment" and get a network error, you might click again because you don’t know if the first payment went through. This can lead to double payments or other unwanted duplicates. Idempotency solves this problem.

An operation is idempotent if running it multiple times has the same effect as running it once. Here's how we implement idempotency in distributed systems:

1. Idempotency Keys: Each request gets a unique ID. When the server receives a request, it first checks if it has seen this ID before. If yes, it returns the cached response instead of processing the request again.

2. Request De-duplication: The server maintains a record of processed request IDs. This record can be stored in the cache. When a new request arrives, the server checks this record before processing.

3. Natural Idempotency: Some operations are naturally idempotent. Setting a user's name to "John" multiple times has the same effect as doing it once. But incrementing a counter isn't idempotent because each operation changes the result.

Here's a comparison of different types of operations:

Implementing idempotency adds complexity but it’s crucial for building reliable distributed systems. It prevents duplicate operations and gives users confidence that retrying failed requests is safe.

FEATURED COURSES

5 Courses of the Week

✅ Meta Front-End Developer Certificate: Master interactive web development with HTML5, CSS, and JavaScript. Learn in-demand skills including React, Bootstrap, GitHub, and professional page layouts. Complete practical projects culminating in a capstone web application to demonstrate your expertise.

✅ Google UX Design Certificate: Gain professional UX design skills through hands-on projects using Figma and Adobe XD. Learn the complete design process from user research to prototyping and usability testing. Build a portfolio with three end-to-end projects to showcase your skills to employers.

✅ Applied Data Science Specialization: Develop practical Python skills using NumPy, Pandas, and visualization libraries. Master predictive modeling, model selection, and compelling data storytelling techniques. Complete real-world projects including financial data analysis and flight reliability monitoring dashboards.

✅ Essential Linear Algebra for Data Science: Acquire fundamental linear algebra concepts specifically tailored for data science applications. Learn approachable methods without unnecessary proofs and complexity. Build a strong mathematical foundation to prepare for advanced data science studies.

✅ Microsoft Data Analyst Certificate: Learn to transform data into meaningful insights using Power BI. Master data preparation, modeling with Star schema, and DAX calculations. Create compelling dashboards to drive data-based decision making across organizations.

NEWS

This Week in the Tech World

Microsoft turns 50 amid challenges: Microsoft celebrates its 50th birthday as the world's second most valuable company, with all three CEOs attending. The milestone comes during stock troubles with four months of decline and disappointing Azure growth. The company generates $13 billion annually from AI, partly through its OpenAI partnership.

LinkedIn founder rejects work-life balance: Reid Hoffman claims seeking work-life balance signals you're "not committed to winning" as an entrepreneur. He expects employees to work after family dinner time, saying those who find this toxic "don't understand the startup game". The payoff? Early LinkedIn employees "don't need to work anymore".

YouTube enhances Shorts features: YouTube announced new tools for its TikTok competitor including precise video editing, automatic music syncing, and AI stickers. The platform is also changing view count calculations, eliminating minimum watch time requirements. The updates come as TikTok faces a potential US ban.

Amazon launches Kuiper satellites April 9: Amazon will launch its first operational Kuiper internet satellites, a crucial step toward competing with SpaceX's Starlink. The $10+ billion project aims to provide broadband via 3,000+ satellites, with the FCC requiring 1,618 satellites deployed by July 2026. The launch was delayed by prioritizing Space Force missions.

Meta releases Llama 4 AI models: Meta unveiled Llama 4 Scout and Llama 4 Maverick multimodal AI models capable of processing text, video, images, and audio. Both will be open source. Meta is also previewing Llama 4 Behemoth, which it calls "one of the smartest LLMs in the world."

Plaid raises funds at $6B valuation: Fintech startup Plaid raised $575 million at a $6 billion valuation, down from $13.4 billion in 2021. CEO Zach Perret says the company reached record revenue with positive margins. The funding allows employees to cash out stock units, following similar moves by Ramp, DataBricks, and OpenAI.

Microsoft creates AI-generated Quake: Microsoft released an AI-generated Quake II demo playable in browsers through Copilot. Using the Muse AI model, the game runs at improved frame rates but remains limited. Microsoft Gaming CEO Phil Spencer sees potential for AI to preserve classic games without original hardware or engines.

TikTok ban extended: Trump issued a second order delaying ByteDance's sale deadline to June 19, from previously April 5th. The US-China deal collapsed over tariffs. Multiple bidders including Amazon, Andreessen Horowitz, and a MrBeast consortium have expressed interest.

BONUS

Just for laughs 😏

WE NEED YOU!

👋 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