Google asked this DP problem

Welcome back!

You need to brush up on your dynamic programming skills to solve today’s challenge. Let’s do this.

Here’s what to expect:

• Maximal Square problem

• B-tree vs LSM tree index

Read time: under 4 minutes

CODING CHALLENGE

Maximal Square

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Solve the problem here before reading the solution.

PRESENTED BY ONELEET

Want SOC 2 compliance without the Security Theater?

• Get the all-in-one platform for SOC 2

• Build real-world security 💪

• Penetration testing, compliance software, 3rd party audit, & vCISO

Schedule a demo for pricing!

SOLUTION

To solve this problem, we'll use dynamic programming. We'll create a 2D array dp where dp[i][j] represents the side length of the largest square ending at position (i, j).

For each cell, if it's '1', we'll check the squares to its left, top, and top-left. The largest square ending at the current cell will be the minimum of these three squares plus 1.

We'll keep track of the maximum square side length as we go. The area of this maximum square will be our answer.

The time complexity of this solution is O(m*n), where m and n are the dimensions of the matrix.

SYSTEM DESIGN

B-tree vs LSM tree index

B-trees and LSM trees are both data structures that are used to index data in a database. B-trees are older and more traditional, while LSM trees are newer and more modern. Let’s see how both of them work.

B-trees are set up like a tree, where each node holds a series of keys and pointers, one after the other: |K|P|K|P|K|. The keys in the array are sorted and each pointer points to the next node that contains values between the pointer’s adjacent keys.

This structure enables fast retrieval of data by traversing the tree from the root to the leaf nodes, which contain the actual data records. The B-tree are self-balancing so that no branch can become too long and degrade performance. B-trees are stored on disk.

LSM trees are also organized as a tree, but they are stored in memory. They are composed of a number of levels, each of which contains a sorted list of data. The top level is the smallest level, and it contains the most recent data. The bottom level is the largest level, and it contains the oldest data.

When new data is inserted into the LSM tree, it is inserted into the top level. If the top level is full, it is merged with the level below it. This process continues until the data is merged into the bottom level. When the bottom level is full, it is written to disk as an SSTable. SSTables are immutable, which means that they cannot be modified once they are written to disk.

LSM trees are more efficient for inserting and updating data than B-trees because they do not need to modify existing nodes in the tree. Instead, they simply insert the new data into the top level in memory. This means that LSM trees can write faster than B-trees.

But LSM trees are less efficient for reading and searching data than B-trees. This is because they need to search through multiple levels of the tree in memory and then on the SSTables in the disc. B-trees, on the other hand, only need to search through a tree which has only a few levels. This means that B-trees can read faster than LSM trees.

NEWS

This Week in the Tech World

Zuckerberg Becomes World's Second-Richest Person: Meta CEO Mark Zuckerberg surpasses Jeff Bezos as the world's second-richest person with a net worth of $206.2B. Meta shares hit a record high, boosted by strong ad revenue and cost-cutting measures. The richest person in the world remains Elon Musk, with a net worth of $269 billion.

Amazon to Cut 14,000 Manager Jobs by 2025: Amazon plans to eliminate 14,000 managerial positions by 2025, aiming to save $3B annually. CEO Andy Jassy's strategy focuses on streamlining operations and enhancing efficiency across the company.

AI Startup Writer Launches OpenAI Competitor: Writer debuts a large AI model to rival enterprise offerings from OpenAI and others. The company spent just $700,000 on training, compared to millions for competitors. Writer is raising $200M at a $1.9B valuation.

LinkedIn Expands Puzzle Games with Tango: LinkedIn launches Tango, a new logic puzzle game, following the success of Queens. The game will start easy on Mondays and get harder through the week. 40% of players come through shared links.

Apple Ring Predicted by 2026: CCS Insight forecasts Apple could launch a smart ring by 2026 to rival Samsung's Galaxy Ring. The move would align with CEO Tim Cook's focus on health and expand Apple's ecosystem of devices.

Uber Adds Electric-Only Ride Option: Uber introduces an "EV preference" for customers to hail only full-electric vehicles. The company also launches an AI chatbot to answer EV questions for drivers and adds farmers' market produce to Uber Eats in NYC and LA.

Amazon Tests Mini-Warehouses in Whole Foods: Amazon adds automated warehouses to Whole Foods stores, allowing customers to buy items from its online store and pick them up at checkout. The move aims to capture more grocery dollars from rivals.

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