❤️ Meta and TikTok love this

Welcome back, Interview Masters!

Today’s coding challenge is a Meta and TikTok favorite. Can you “sort” this out? 😁

In today’s newsletter, we’ll cover:

• Edit Distance problem

• How to design an Authentication System

Read time: under 4 minutes

CODING CHALLENGE

Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character

• Delete a character

• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Solve the problem here before reading the solution.

REFER FOR THE WIN

🚨 We will host a Career Chat with Sahil this Saturday July 20th. You have few more days to refer 10+ people to join this 30-minute Q&A session with Sahil. Looking forward to seeing many of you!

📌Share your referral link on LinkedIn or with your friends to unlock the treasures quicker!
📌 Check your referrals status here.

SOLUTION

To solve this problem, we'll use dynamic programming. We'll create a 2D array where dp[i][j] represents the minimum number of operations needed to convert the first i characters of word1 to the first j characters of word2.

We'll start by initializing the first row and column of the dp array. First row would be dp[0][j]. dp[0][j] is equal to number of operations needed to convert first 0 characters of word1 to the first j characters of word2 .

First 0 characters of word1 would be an empty string. To convert j characters into an empty string, we will have to delete all the j characters. So, dp[0][j] is equal to j . Similarly for the first column, dp[i][0] is equal to i .

After this, we'll iterate through both strings. For each pair of characters, we'll do the following:

1. If characters are same, we don’t need to do any operation.

2. If characters are different, we will consider insert, delete, or replace. We'll choose the operation that gives the minimum edit distance.

The time complexity of this solution is O(m*n), where m and n are the lengths of word1 and word2 respectively.

SYSTEM DESIGN EXPLAINED

How to design an Authentication System?

Let's design a secure authentication system that can handle user registration, login, and access control.

The main components are:

1. User Management Service for handling registrations and profiles

2. Authentication Service for verifying credentials and generating tokens

3. Authorization Service for managing permissions

4. Session Management Service for tracking user sessions.

The system uses RESTful APIs for communication between services and JSON Web Tokens (JWTs) for secure data exchange.

For data storage, the system uses multiple database tables: User Table for basic user info, Credentials Table for login data, and Session Table for active sessions. This separation allows for better security and performance.

For enhanced security, the system supports multi-factor authentication (MFA) and uses password hashing to protect user credentials. It also employs token-based authentication to manage user sessions securely.

You can dive into more details here.

NEWS

This week in the tech world

Meta Lifts Trump Restrictions: Meta has lifted all penalties on Donald Trump's Facebook and Instagram accounts ahead of the 2024 election. He now faces standard short-term suspensions for violations.

Anthropic Launches $100M AI Fund: Anthropic and Menlo Ventures launched a $100M fund to support early-stage AI startups. The Anthology Fund offers funding and $25,000 in AI model credits.

Google's Potential Wiz Acquisition: Google is in talks to acquire cybersecurity startup Wiz for about $23 billion, doubling Wiz's $12 billion valuation. This would be Google's largest acquisition, enhancing its cloud security against Microsoft and Amazon.

AI Reshaping Food Industry: Food companies are investing heavily in AI and automation to cut costs. McDonald's plans to spend $2 billion on AI for restaurants, while grocery stores invested $13 billion in 2022, with spending set to increase 400% by 2025.

Stratospheric Balloon Tourism: Startups Zephalto, Space Perspective, and World View are offering 6-hour stratospheric balloon rides for $50,000-$184,000. These 15-19 mile-high trips are drawing strong interest.

Inceptive Launched: Jakob Uszkoreit, a former Google researcher, launched Inceptive to apply AI to drug development. The biotech startup, backed by $100M from Andreessen Horowitz and Nvidia, aims to design RNA molecules with generative AI for more effective medicines.

BONUS

Just for laughs😏

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra