FAANG asked this 59 times

Welcome back!

Today’s problem is a popular one at FAANG interviews. Get ready to brush up on your graph algorithms!

Here’s what to expect this week:

• Course Schedule problem

• Batch vs Stream processing

Read time: under 4 minutes

CODING CHALLENGE

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Solve the problem here before reading the solution.

SOLUTION

To solve this problem, we'll use a depth-first search (DFS) approach to detect cycles in the course dependency graph. If there's a cycle, it means we can't finish all courses.

We'll represent the graph using an adjacency list. Then, we'll perform DFS for each course. During DFS, we'll keep track of visited courses and courses in the current path. If we encounter a course that's already in the current path, we've found a cycle.

The time complexity of this solution is O(V + E), where V is the number of courses and E is the number of prerequisites. That’s because we visit each course once and each prerequisite once.

LATEST DEV TOOLS 

Why struggle with file uploads? Pinata’s File API is your fix

Simplify your development workflow with Pinata’s File API. Add file uploads and retrieval to your app in minutes, without the need for complicated configurations. Pinata provides simple file management so you can focus on creating great features.

Build now!

SYSTEM DESIGN

Batch vs Stream processing

There are two popular methods to process data: Batch processing and Stream processing. Let’s understand the main differences between the two.

In Batch processing, we collect data over time and processes it in large chunks at set intervals. This approach shines when you need to analyze historical data, generate periodic reports, or perform large-scale data migrations. It's more cost-effective and simpler to implement since you do not need constant processing power.

Stream processing, on the other hand, handles data in real-time as it arrives. Think of monitoring live traffic or detecting fraud in banking transactions. It's ideal when immediate insights are needed. Batch processing requires more complex infrastructure and higher costs to maintain continuous processing capabilities.

Batch processing often uses tools like Apache Spark or Apache Airflow, while stream processing relies on platforms like Apache Kafka or RabbitMQ.

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.

Download It Free Today

NEWS

This Week in the Tech World

Tesla Stock Jumps on Trump Plans: Tesla shares up 5% based on a report that Trump's team plans to prioritize federal framework for self-driving vehicles. Trump picked Musk to lead new Department of Government Efficiency.

AMD Announces Layoffs: AMD cuts 4% of workforce (1,000 jobs) while focusing on AI chip market. Company expects $5B in AI sales for 2024, competing with dominant Nvidia's projected $125.9B revenue.

TikTok Ban May Be Lifted: Trump's victory could provide lifeline for TikTok, which faces January U.S. ban. Trump previously opposed ban, saying it would only benefit Meta, which he called "enemy of the people."

Amazon Enters Healthcare Market: Amazon launches fixed-price treatments for conditions like hair loss through Prime membership. Move sends Hims & Hers stock down 24% as Amazon undercuts prices by up to 42%.

Canva Recruits Zoom Veteran: Design software startup Canva hires former Zoom CFO Kelly Steckelberg ahead of potential IPO. Company generates $2.5B in annual revenue and was recently valued at $32B, down from $40B peak.

Bluesky Gains Users After Election: Twitter alternative Bluesky adds 1.25M new users following U.S. election, reaching 15.2M total users. Growth driven by users seeking alternatives to Musk-owned X platform.

xAI's Major Chip Purchase: Elon Musk's xAI raising $6B at $50B valuation, with $5B from Middle East sovereign funds. Funds will purchase 100,000 Nvidia chips for new Memphis data center to power Tesla's Full Self Driving.

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