Meta paid $100M signing bonus?

Welcome back!

This week, we’ll solve one of the most popular interview problems. Are you up for the challenge?

Today we will cover:

• Coin Change

• Write-Ahead Logging

Read time: under 4 minutes

CODING CHALLENGE

Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Solve the problem here before reading the solution.

PRESENTED BY HUBSPOT

The Future of AI in Marketing. Your Shortcut to Smarter, Faster Marketing.

This guide distills 10 AI strategies from industry leaders that are transforming marketing.

• Learn how HubSpot's engineering team achieved 15-20% productivity gains with AI

• Learn how AI-driven emails achieved 94% higher conversion rates

• Discover 7 ways to enhance your marketing strategy with AI.

Outpace your competitors by mastering AI.

Get Your Free Guide

SOLUTION

To solve this problem, we'll use dynamic programming. We'll create a dp array where dp[i] represents the minimum number of coins needed to make up amount i.

We'll initialize the dp array with a large value (amount + 1) to represent an impossible state. The base case is dp[0] = 0, as it takes 0 coins to make an amount of 0.

For each amount from 1 to the target amount, we'll try using each coin denomination. If a coin's value is less than or equal to the current amount, we'll update the minimum number of coins needed.

The recurrence relation is:

dp[i] = min(dp[i], dp[i - coin] + 1) for each coin in coins.

If the final dp[amount] is still greater than amount, it means we couldn't make up the amount, so we return -1.

The time complexity is O(amount * len(coins)), and the space complexity is O(amount).

SYSTEM DESIGN

Write-Ahead Logging

When a database crashes in the middle of updating data, it can leave the data in an inconsistent state. Write-Ahead Logging (WAL) is a technique that ensures database reliability even when things go wrong.

Here's how WAL works: Before making any changes to the actual data files, the database first writes details of the changes to a log file. This log entry contains enough information to either redo the change (if the crash happened after writing to the log but before updating the data) or undo it (if we need to rollback a transaction).

Think about updating a user's account balance. Instead of directly changing the balance in the data file, the database first writes to the WAL: "Update user 123's balance from $100 to $80". Only after this log entry is safely on disk does the database proceed to update the actual balance. If the system crashes before the balance update is complete, the database can check the WAL during recovery and ensure the update is properly applied.

WAL provides several key benefits:

1. Durability: No data changes are lost, even if the system crashes

2. Atomic Transactions: Multiple related changes either all happen or none happen

3. Better Performance: WAL allows the database to batch multiple data file updates together

But WAL also comes with some trade-offs:

1. Extra Storage: Maintaining logs requires additional disk space

2. Slight Write Delay: Writing to the log first adds a small overhead

3. Recovery Time: After a crash, the database needs time to replay the log

Most modern databases like PostgreSQL and MySQL use WAL because its benefits far outweigh its costs. The mechanism provides a good balance between performance and reliability.

Here's how WAL compares with direct writes:

FEATURED COURSES

5 Courses of the Week

✅ Intro to ML w/ Pytorch: Build programs that predict and find data patterns. Learn basic methods like linear regression and decision trees. Advance to neural networks for images. Practice with Python tools like PyTorch and scikit-learn.

✅ Agentic AI Engineering: Build 8 AI projects in 30 days. Use OpenAI Agents and CrewAI tools. Create independent AI systems. Build chatbots and automation helpers.

✅ AI w/ Python & R + ChatGPT: Create algorithms in two programming languages. Expert-led step-by-step training. Includes ready-made code templates. Easy start for beginners.

✅ Python for Data Science & Machine Learning Bootcamp: Learn key Python libraries. NumPy for calculations. Pandas for data. Matplotlib for charts. Scikit-Learn for machine learning. TensorFlow for deep learning.

✅ AWS ML Engineering: Deploy machine learning models using Amazon's cloud platform. Learn data preparation and model training. Work on real projects. Master automated deployment tools.

MASTER AI 

Learn AI in 5 minutes a day

This is the easiest way for a busy person wanting to learn AI in as little time as possible:

1. Sign up for The Rundown AI newsletter

2. They send you 5-minute email updates on the latest AI news and how to use it

3. You learn how to become 2x more productive by leveraging AI

Sign up to start learning.

NEWS

This Week in the Tech World

Meta Hits Record High on AI Hiring: Meta shares reached an all-time high as CEO Mark Zuckerberg continues his AI hiring spree. The company acquired Scale AI and brought on its CEO in a $14.3 billion deal. Reports also suggested that Meta offered signing bonuses of up to $100 million to some OpenAI researchers. Lucas Beyer, who recently joined Meta from OpenAI, publicly refuted this claim on Twitter.

Microsoft Lays Off 9,000 in Latest Cuts: Microsoft eliminated about 9,000 jobs (4% of workforce) as it continues major layoffs that started in May. The company has now cut over 15,000 employees in 2025 while spending $80 billion on AI infrastructure, with gaming and sales teams hit hardest in this round.

Amazon CEO on AI Job Impact: Amazon CEO Andy Jassy says AI will eliminate some jobs but create others. He believes AI will free workers from routine tasks and make jobs more interesting, though Amazon's workforce may shrink overall.

Robinhood Offers Private Company Tokens: Robinhood now lets European users trade tokenized shares of OpenAI and SpaceX. This marks the first time private company equity is available via blockchain, though US users can't access it yet.

OpenAI Uses Google's AI Chips: OpenAI started renting Google's AI chips to power ChatGPT, marking its first major move away from Nvidia chips. The switch could help OpenAI reduce costs but Google isn't sharing its most powerful chips.

Cloudflare Blocks AI Bots by Default: Cloudflare will now ask new website owners if they want to block AI crawlers from scraping their content. The move affects 16% of global internet traffic and could hurt AI companies' ability to train models.

Countries Push for Sovereign AI: Nations want control over their own AI systems rather than relying on English-based models. Open-source AI and cloud computing are helping countries build localized AI that fits their languages and cultures.

Huawei Open-Sources AI Models: China's Huawei released two AI models as open-source to boost adoption of its Ascend AI chips. The move helps Huawei compete with Nvidia despite US export restrictions on advanced chips.

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