Google salaries fall down

Welcome back!

This week's coding challenge tackles a classic interview problem that has challenged generations of programmers. Let’s see if you can solve it.

Today we will cover:

• Search a 2D Matrix

• Data Partitioning vs Sharding

Read time: under 4 minutes

CODING CHALLENGE

Search a 2D Matrix

You are given an m x n integer matrix called matrix with the following two properties:

• Each row is sorted in non-decreasing order.

• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Solve the problem here before reading the solution.

PRESENTED BY SUPERHUMAN AI

Find out why 1M+ professionals read Superhuman AI daily.

AI won't take over the world. People who know how to use AI will.

Here's how to stay ahead with AI:

1. Sign up for Superhuman AI. The AI newsletter read by 1M+ pros.

2. Master AI tools, tutorials, and news in just 3 minutes a day.

3. Become 10X more productive using AI.

Join 1 million pros and start learning AI

SOLUTION

The matrix has special properties where each row is sorted and the first element of each row is greater than the last element of the previous row.

This means that matrix is sorted if you go from top left to bottom right, row by row. So we can treat this 2D matrix as a sorted 1D array and use Binary Search to find the target.

The key is to convert the middle index of binary search into corresponding row and column indices of the matrix.

To convert a 1D index to 2D indices, we can use:

• row = index / number of columns

• column = index % number of columns

The time complexity of this solution is O(log(m * n)) as we are performing binary search on m * n elements.

SYSTEM DESIGN

Data Partitioning vs Sharding

When your database grows too large to handle efficiently on a single server, you need to split it across multiple servers. This is where data partitioning and sharding come in. While these terms are often used interchangeably, they have some important differences.

Data partitioning is dividing data into smaller, more manageable pieces within the same database instance. Think of an e-commerce database where you partition order data by year. All orders from 2023 go into one partition, 2022 into another, and so on. The database still runs on a single server, but queries can run faster because they only need to look at relevant partitions.

Sharding takes partitioning a step further by spreading these data chunks across different database servers. Each server (called a shard) operates independently and handles its own portion of the data. For example, you might put all orders from North America on one server, European orders on another, and Asian orders on a third.

Sharding provides better scalability since each shard handles fewer requests and stores less data. It also improves availability because if one shard fails, others continue working. However, sharding is more complex to implement and maintain. You need to handle cross-shard queries, manage multiple database connections, and ensure data consistency across shards.

FEATURED COURSES

5 Courses of the Week

✅ DSA in Python: Get hands-on practice with over 100 data structures and algorithm exercises and guidance from a dedicated mentor.

✅ 100 Days of Code - Python Bootcamp: Master the Python programming language by building 100 unique projects over 100 days.

✅ Tools of the Trade: Linux & SQL: Learn essential Linux command line skills and SQL database querying for professionals. This covers file system management, user authentication, and database operations needed for entry-level positions.

✅ Amazon’s Software Developer Certificate: Dive into real-world software development. Expect to create desktop apps with integrated data handling and GUI features. Build a substantial portfolio that demonstrates your technical skills to potential employers.

✅ Microsoft’s Full-Stack Developer Certificate: Learn front-end and back-end development using .NET, C#, Blazor, and Microsoft Copilot. Build complete web apps with focus on security and deployment.

HEARD OF 1440? 

Fact-based news without bias awaits. Make 1440 your choice today.

Overwhelmed by biased news? Cut through the clutter and get straight facts with your daily 1440 digest. From politics to sports, join millions who start their day informed.

Sign up now!

NEWS

This Week in the Tech World

Google Revamps Compensation Structure: Google is changing its compensation strategy to better reward high performers with increased bonuses while reducing payouts for lower ratings. The new structure will take effect for 2025 reviews, allowing managers to award the "Outstanding Impact" rating to more employees.

Anthropic Offers Employee Buyback: Anthropic is offering its first share buyback program at a $61.5 billion valuation. Employees who've worked there at least two years can sell up to 20% of their equity, capped at $2 million each, as the company's revenue reaches $1.4 billion.

Uber Partners with Momenta on Robotaxis: Uber has partnered with Chinese self-driving startup Momenta to launch robotaxi services in Europe by early 2026. This marks Uber's first major push to deploy autonomous vehicles abroad after selling its own self-driving unit in 2020.

Nvidia CEO Gets First Raise in Decade: Nvidia CEO Jensen Huang is receiving his first salary increase in 10 years, with 2025 pay rising to $49.9 million. His base salary rose 49% to $1.5 million while his variable cash increased by 50% as Nvidia's revenue jumped 114%.

Google Launches NotebookLM App: Google is releasing its NotebookLM AI tool as a mobile app at Google I/O on May 20. The app creates queryable "AI experts" from uploaded documents and videos with a 500,000 token context window and supports files up to 200MB.

Claude Extends Research Capabilities: Anthropic has upgraded its AI assistant Claude with research capabilities that run up to 45 minutes before delivering reports. The system examines complex requests across hundreds of sources and compiles reports with citations to original sources.

Apple Approves Spotify Update: Apple has approved Spotify's app update allowing users to access pricing information and make purchases within the app. This follows a federal judge ordering Apple to stop imposing commissions on purchases through iPhone app web links.

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