Google in big trouble

ALSO: Single-leader vs Multi-leader vs Leaderless replication

Author

InstaByte
November 27, 2024

In partnership with

Welcome back!

This week’s problem is not as easy as it looks … or is it? Let’s find out.

Today we will cover:

  • Permutations problem

  • Single-leader vs Multi-leader vs Leaderless replication

We also have an exciting news for you this week ❤️👇

Read time: under 5 minutes

JOIN OUR FREE COMMUNITY

Two weeks ago we announced that we’re launching a Discord community for programmers. The community is now open to all, for free!

We’re hosting an Ask-me-anything with Sahil (SWE@Google, ex-Amazon) this Saturday on Discord. Don’t miss it!

As a member of this community, you will get

  • daily coding challenges

  • weekly contests to win prizes

  • weekly system design problems and much more

CODING CHALLENGE

Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Solve the problem here before reading the solution.

SOLUTION

To find all permutations, we can use backtracking. We'll start with an empty list as our permutation. As we do backtracking, we’ll keep adding numbers to this list to build the permutation.

But we can not add the numbers that are already used in the permutation. So we need to track numbers that have been already used in the permutation.

For each unused number, we will append it to the current permutation and continue backtracking. When our permutation contains all the numbers, we add it to our answer and return.

The time complexity is O(n!), where n is the length of nums. This is because for n elements, we have n! possible permutations.

TRENDING AI TOOLS 

Writer RAG tool: build production-ready RAG apps in minutes

RAG in just a few lines of code? We’ve launched a predefined RAG tool on our developer platform, making it easy to bring your data into a Knowledge Graph and interact with it with AI. With a single API call, writer LLMs will intelligently call the RAG tool to chat with your data.

Integrated into Writer’s full-stack platform, it eliminates the need for complex vendor RAG setups, making it quick to build scalable, highly accurate AI workflows just by passing a graph ID of your data as a parameter to your RAG tool.

SYSTEM DESIGN

Single-leader vs Multi-leader vs Leaderless replication

When a database server fails, millions of users could be left unable to access their favorite apps. That's why modern systems copy their data across multiple servers. This is also called database replication. There are three main approaches to do replication.

In Single-leader replication, one database server is in charge - it's called the leader. When you want to update data, you have to go through this leader. The other servers (followers) just make copies of what the leader does. This approach is simple to understand and works well for most applications. But it can be tricky when your users are spread across the globe since everyone has to connect to that one leader. Additionally, having only one leader means reduced write throughput.

Multi-leader replication solves this by allowing multiple servers to accept updates. Each region can have its own leader server, so users can work with a nearby server instead of connecting to one far away. This setup gives better performance as things keep running smoothly even if some connections between regions fail. But multi-leader replication has its own challenges. For example, sometimes two leaders might update the same data differently, leading to a write conflict. You need special rules to figure out which update should win.

Leaderless replication takes a unique approach - any server can accept updates. When you want to save data, you send it to multiple servers at once. When reading data, you check with several servers and use the most recent version. To make sure this works, you need enough servers to agree on each update (this is called a quorum). This system is very flexible and handles server failures well, but it's a bit more complex to set up correctly.

PRESENTED BY CODEIUM

Unlock Windsurf Editor, by Codeium.

Introducing the Windsurf Editor, the first agentic IDE. All the features you know and love from Codeium’s extensions plus new capabilities such as Cascade that act as collaborative AI agents, combining the best of copilot and agent systems. This flow state of working with AI creates a step-change in AI capability that results in truly magical moments.

NEWS

This Week in the Tech World

Google Chrome Divestment Push: DOJ calls for Google to divest Chrome browser following monopoly ruling. Proposal aims to reduce Google's control over search access points. Google calls it "overbroad" and plans to appeal. Alphabet shares dropped 4% following the news.

Wall Street's Bitcoin Evolution: Major exchanges introduce spot bitcoin ETF options, opening new ways to bet on cryptocurrency. BlackRock's IBIT ETF sees strong debut with 353,716 contracts traded. Bitcoin nears $100,000 amid increased institutional interest.

OpenAI's New Funding: SoftBank invests $1.5 billion in OpenAI through tender offer, allowing employees to cash out shares. Deal values company at $157 billion and lets employees sell shares until December 24.

Orange Partners with AI Giants: French telecom Orange teams up with OpenAI and Meta to develop AI models for West African languages. The initiative will start with Wolof and Pulaar languages in early 2025, aiming to improve AI accessibility in Africa.

Huawei's New OS Launch: Huawei unveils Mate 70 series phones running HarmonyOS NEXT, its first fully self-developed mobile OS. The move marks a significant step toward independence from Android following U.S. sanctions. Base model starts at $759.

Amazon Deepens AI Investment: Amazon invests additional $4 billion in Anthropic, bringing total investment to $8 billion. Deal makes AWS Anthropic's primary cloud partner and gives customers early access to Claude AI model fine-tuning.

Reddit's Global Push: Reddit COO reveals international expansion plans focusing on India and Brazil. Platform aims to boost ad revenue by translating content into 20-30 languages by year-end. Currently, 50% of users are outside U.S.

TRENDING API

Instantly add file uploads to your app with Pinata’s API

Pinata’s File API lets developers integrate file uploads and retrieval in just minutes. No complex setup, no configuration headaches—just fast and scalable file management.

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

What did you think of this week's email?

Your feedback helps us create better emails for you!

Login or Subscribe to participate in polls.

Until next time, take care! 🚀

Cheers,