Meta asked this HARD problem

Welcome back!

This week we’ll solve a tricky problem that comes up a lot in interviews. Are you ready for the challenge?

Today we will cover:

• Minimum Window Substring problem

• SQL vs NoSQL databases

Read time: under 4 minutes

CODING CHALLENGE

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The test cases will be generated such that the answer is unique.

Could you find an algorithm that runs in O(m + n) time?

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Solve the problem here before reading the solution.

PRESENTED BY PINATA

Add file uploads instantly with Pinata’s developer-friendly File API

As a developer, your time is valuable. That’s why Pinata’s File API is built to simplify file management, letting you add uploads and retrieval quickly and effortlessly. Forget the headache of complex setups—our API integrates in minutes, so you can spend more time coding and less time on configurations. With secure, scalable storage and easy-to-use endpoints, Pinata takes the stress out of file handling, giving you a streamlined experience to focus on what really matters: building your app.

Start building!

SOLUTION

To solve this problem, we'll use a sliding window approach with two pointers. We'll maintain a dictionary to keep track of the characters we need and their frequencies.

We'll move the right pointer to expand the window until we have all the required characters. Then, we'll move the left pointer to shrink the window while maintaining the required characters.

We'll update the minimum window whenever we find a valid window. This process continues until we've examined all characters in s.

The time complexity of this solution is O(m + n), where m is the length of s and n is the length of t.

SYSTEM DESIGN

SQL vs NoSQL databases

One of the biggest myths about databases is that SQL databases use Structured Query Language (SQL) whereas NoSQL databases do not. It's better to think of SQL and NoSQL databases as relational and non-relational databases, since this tells us more about how they actually work.

Relational databases (SQL) organize data into separate tables, with each table representing a specific type of data. Imagine you have a Products table and a Suppliers table. Products table contains a SupplierID which is also present in Suppliers table. SupplierID is also called a ‘foreign key’ because it connects both the tables. This way, supplier information is stored just once, and we use SupplierID to piece everything together when needed.

Non-relational databases (NoSQL) take a different approach. Instead of using separate tables, they store data as individual documents or records. In our products example, each product record would look like this:

{
    "productId": "123",
    "name": "Laptop",
    "price": 999,
    "supplier": {
        "name": "Tech Supplies Inc",
        "address": "123 Tech Street",
        "contact": "[email protected]"
    }
}

This means some supplier information gets repeated across different products, but it's easier to access everything about a product in one go.

Each approach has its strengths. Relational databases are great when your data naturally has lots of relationships. They keep things organized and consistent, since you only need to update information in one place.

But relational databases can be slower in distributed systems where data is spread across multiple database servers. This is because getting all the related data might require checking multiple servers, which takes time.

Non-relational databases shine when you need quick access to all related data at once, since everything's stored together. They're often better for data that doesn't have many relationships - like social media posts, which mostly stand alone. The trade-off is that when you need to update something that's stored in multiple records, you have to update each copy, which can be complicated.

CONGRATS!

Join us to congratulate Abhishek from India for winning a $90 NVIDIA AI Course. Abhishek is a student pursuing his bachelor of technology at the Starex University, with a focus in AI. In his own words: Winning this course excites me, as it perfectly aligns with my specialization in AI and ML within my Computer Science program. Having completed an internship in AI, I’m eager to deepen my knowledge in this field. I also really appreciate the coding challenges that InstaByte provides, as they challenge me and help improve my problem-solving skills.

Special thanks to all the participants in last week’s survey - Keep an eye out for more giveaways in the future 😉 

NEWS

This Week in the Tech World

Anthropic Launches AI Agents: Amazon-backed AI startup Anthropic unveils Computer Use capability, allowing AI to operate computers like humans. Early access given to Amazon, Asana, and Canva, with public release planned for early 2024.

Apple Releases AI Features: Apple debuts ChatGPT integration and new AI tools in iOS 18.2 beta, including image generation and text rewriting capabilities. The official public release comes next week in iOS 18.1, marking Apple's major push into AI.

23andMe Faces Crisis: DNA testing company 23andMe has lost 98% of its value since going public, now worth just 2% of its former $6B valuation. All independent board members resigned in September amid privacy concerns and a major data breach.

Uber Eyes Expedia: Uber has discussed potential acquisition of travel booking company Expedia, led by former Expedia CEO Dara Khosrowshahi. Early-stage talks could expand Uber beyond rides and food delivery.

Amazon Cloud Chief's Office Mandate: AWS CEO Matt Garman tells employees unhappy with new five-day office requirement they can leave. The policy takes effect January 2, affecting all corporate workers despite internal pushback.

Stripe Acquires Bridge: Payment giant Stripe buys crypto infrastructure startup Bridge Network for $1.1B, marking a 200% valuation increase from August. The deal signals Stripe's serious push into stablecoin payments and crypto infrastructure.

Google Leadership Changes: Google replaces search and ads chief Prabhakar Raghavan with Nick Fox. Raghavan becomes chief technologist as company restructures for AI focus. Gemini app team moves to Google DeepMind.

Microsoft's AI Agent Push: Microsoft announces autonomous AI agents rollout in Copilot Studio next month, plus 10 new agents in Dynamics 365. Move aims to counter Salesforce's recent entry into the AI agent market.

SAP CEO on AI Regulation: SAP's CEO Christian Klein warns against AI regulation in Europe, arguing it could hurt competitiveness with US and China. He advocates focusing on AI outcomes rather than restricting the technology itself.

TRENDING AI TOOLS

The fastest way to build AI apps

Writer is the full-stack generative AI platform for enterprises. Quickly and easily build and deploy AI apps with Writer AI Studio, a suite of developer tools fully integrated with our LLMs, graph-based RAG, AI guardrails, and more.

Use Writer Framework to build Python AI apps with drag-and-drop UI creation, our API and SDKs to integrate AI into your existing codebase, or intuitive no-code tools for business users.

Start building with AI Studio

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