Amazon ❤️ Anagrams

ALSO: Change Data Capture

Author

InstaByte
December 11, 2024

In partnership with

Welcome back!

This week’s coding challenge was asked by Amazon 34 times in the last 3 months. Are you ready for it?

Today we will cover:

  • Group Anagrams problem

  • Change Data Capture

Read time: under 4 minutes

NEXT WEEK IN INSTABYTE PRO

Thank you for the overwhelming response you gave to InstaByte Pro earlier this week. Next week, we will be sharing the following with InstaByte Pro members:

  1. 5 types of Binary Search problems. The last type will show you how to use Binary Search in unsorted arrays.

  2. Different types of Database Indexes and their trade-offs.

  3. Discussion session on Binary Search and Database Indexes with Sahil.

  4. Peer mock interviews will be set up starting next week.

If you’re interested, you can try out InstaByte Pro for 7 days for free here:

CODING CHALLENGE

Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

- There is no string in strs that can be rearranged to form "bat".
- The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
- The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Solve the problem here before reading the solution.

SOLUTION

To solve this problem, we'll use a dictionary to group anagrams together. Two words are anagrams if they have the same characters with the same frequencies.

For each string, we'll sort its characters. This sorted string will be our key in the dictionary. All anagrams will have the same sorted string.

For example, "eat" and "tea" both become "aet" when sorted. We'll use this sorted string as the key and store the original strings in a list as the value.

This approach has a time complexity of O(n*k*log k), where:

  • n is the number of strings in the input array

  • k is the maximum length of a string

  • k * log k comes from sorting each string

PRESENTED BY FYXER AI

Fyxer AI: Automate Emails, Meetings, and Team Tasks in Seconds

Fyxer AI automates daily email and meeting tasks:

  • Email Organization: It organizes your inbox so you see important emails first.

  • Automated Email Drafting: Crafts replies that sound like you—convincing, concise, and flawlessly written in any language.

  • Meeting Notes: Keeps you focused by taking notes, summarizing meetings, and drafting follow-ups.

Fyxer AI adapts to teams and sets up in just 30 seconds with Gmail or Outlook.

SYSTEM DESIGN

Change Data Capture (CDC)

Imagine you’re designing the architecture of Instagram. When users visit a profile, they need to instantly see who this person follows. This requires querying a database table containing follower-followed relationships. To make this lookup fast, we need an index on the follower column.

But here’s the problem. To generate a user's newsfeed, we need to quickly find all the people who follow a particular user. To make this query fast, we need an index on the followed column.

Running both these queries efficiently at the same time can be challenging. We could maintain two separate databases - one indexed by follower and another indexed by followed. But this creates unnecessary write overhead. When a user follows someone, we'd need to update both databases simultaneously. This synchronous update significantly slows down the follow action and introduces potential consistency issues if one update fails while the other succeeds.

Change Data Capture (CDC) solves this problem elegantly. Instead of updating both databases synchronously, we only write to the primary database indexed on follower. CDC monitors the database's transaction logs and captures every change made to the follower table. These changes are then pushed to Apache Kafka as events.

A stream processor like Apache Flink continuously processes these events from the Kafka queue and updates the secondary database indexed by followed. This asynchronous process ensures that the follow action remains fast since it only needs to write to one database. The second database eventually catches up through the CDC pipeline.

NEWS

This Week in the Tech World

Source: Google

Google's Quantum Advance: Google unveils Willow quantum chip, claiming breakthrough in error correction. Despite technical achievement, experts say practical applications still years away.

Meta Apps Down: Facebook, Instagram, and other Meta apps experience widespread outage on December 11th. Services disrupted for hours, affecting millions of users globally. Company cites technical issues.

Apple Adds ChatGPT: Apple integrates ChatGPT with Siri in latest iOS update. Feature requires iPhone 15 or newer models. Users don't need OpenAI account for basic access.

ChatGPT Outage Resolved: OpenAI's ChatGPT service recovers after 4-hour outage affecting main chatbot and Sora video generator. Company reaches 300 million weekly active users.

Meta Stock Hits Record: Meta shares rise 2.4% after court upholds TikTok ban law, pushing market cap to $1.6 trillion. The Facebook parent is up 77% in 2024. The ruling requires ByteDance to sell TikTok's U.S. operations or face restrictions. TikTok plans Supreme Court appeal.

Uber Expands Robotaxis to UAE: Uber partners with China's WeRide to launch robotaxi service in Abu Dhabi. Initial operations will include human safety drivers, with plans for fully autonomous service in 2025.

Weight Loss Drug Scams Surge: Online scammers are exploiting the high demand for GLP-1 drugs like Wegovy and Ozempic. McAfee reports a 183% increase in phishing attempts in 2024. Novo Nordisk reports 14 deaths from counterfeit drugs. FDA warns against unregulated online purchases.

STAY AHEAD OF AI 

Your daily AI dose

Mindstream is the HubSpot Media Network’s hottest new property. Stay on top of AI, learn how to apply it… and actually enjoy reading. Imagine that.

Our small team of actual humans spends their whole day creating a newsletter that’s loved by over 150,000 readers. Why not give us a try?

Learn how to make AI work for you

AI won’t take your job, but a person using AI might. That’s why 800,000+ professionals read The Rundown AI – the free newsletter that keeps you updated on the latest AI news and teaches you how to use it in just 5 minutes a day.

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,