LinkedList algorithm you must know

Welcome back!

Do you remember the story of the tortoise and the hare? This week's problem can be solved by using the strategy the tortoise used to catch up with the hare.

Today we will cover:

• Linked List Cycle problem

• Cache Writing Policies

📌 This is the last newsletter of 2024! Next week we're taking a break for the New Year. We wish you a joyous holiday season and happy New Year 🎊.
See you in 2025 😉

Read time: under 4 minutes

CODING CHALLENGE

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Solve the problem here before reading the solution.

PRESENTED BY WRITER

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.

Learn more about our production ready RAG tooling here.

SOLUTION

To detect a cycle in a linked list, we'll use the Floyd's Cycle Finding Algorithm, also known as the "tortoise and hare" algorithm.

We'll use two pointers: a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps.

The main idea is that if there's a cycle, the fast pointer will catch up to the slow pointer. If there's no cycle, the fast pointer will reach the end of the list.

The time complexity of this solution is O(n), where n is the number of nodes in the linked list.

NEXT WEEK IN INSTABYTE PRO

Thanks a lot to everyone who participated in InstaByte Pro discussion sessions last week. Next week, we will be sharing the following with InstaByte Pro members:

1. 3 Problem Patterns for Queues. These patterns are used to solve many Sliding Window and Graph problems that are commonly asked in the interviews.

2. For System Design, we will cover Database Replication. Understanding different types of replication strategies will help you chose the right database in an interview.

3. Sahil will conduct discussion sessions on Queue patterns and Database replication.

4. Peer mock interviews will provide you actionable feedback for the interviews.

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

SYSTEM DESIGN

Cache Writing Policies

Imagine you’re running a large e-commerce platform where millions of users are constantly checking product prices and inventory. Every time a user requests information, your system needs to fetch it from the main database. Database queries are slow, and with millions of requests, your system becomes frustratingly sluggish. This is where caching comes in. By storing frequently accessed data in a faster, in-memory storage (cache), you can serve requests much faster. Instead of hitting the database every time, your system first checks the cache. If the information is not found in the cache, then it queries the database. While reading from a cache is straightforward, managing data updates in a cache can be challenging. This is where cache writing policies become important.

Let's start with the simplest writing policy: Write-Through. In this approach, when data needs to be updated, we write it to both the cache and the main database simultaneously. Only when both writes are complete does the system confirm the update. This policy ensures that the cache and database stay perfectly synchronized, making it ideal for systems where data consistency is critical, like financial applications or inventory management. But Write-Through has a significant drawback. Every write operation must wait for both the cache and database updates to complete, which can make write operations slower.

To address the performance limitation of Write-Through, some systems use Write-Back (also called Write-Behind). With Write-Back, data is initially written only to the cache, and the system immediately confirms the update. The modified data is written to the database later, usually in batches. This makes write operations much faster since they don't have to wait for the slower database write. Write-Back is perfect for systems that need high write performance, like real-time analytics or gaming applications. But there's a risk. If the system crashes before cached data is written to the database, you could lose updates.

Write-Around is another policy that takes a different approach. When updating data, Write-Around bypasses the cache completely and writes directly to the database. This policy works well when the updated data isn't likely to be read again soon, like log entries. The downside is that if the same data is needed again quickly, it must be fetched from the database, causing a cache miss. But once we hit the database, we’ll store this data in the cache so that we don’t have another cache miss.

FEATURED COURSES

5 Courses of the Week

✅ Building A Brain in 10 Minutes: Learn the fundamental concepts of neural networks by building a simple neuron from scratch using TensorFlow 2.

✅ Developing AI Applications: Learn to build practical AI applications using modern tools like OpenAI API, Hugging Face, and LangChain to create chatbots, search engines, and recommendation systems.

✅ Building RAG Agents with LLMs (free for a limited time): Build a complete Retrieval-Augmented Generation (RAG) system that can intelligently answer questions from documents using LangChain, vector stores, and large language models.

✅ Learn Data Science in Python: Master data science by manipulating, visualizing, and analyzing data using Python's key libraries (pandas, Seaborn, scikit-learn). Build real predictive models that prepare you for data scientist certification.

✅ Generative AI with Diffusion Models: Create your own text-to-image generation system by implementing diffusion models and CLIP, with hands-on practice building U-Net architectures.

🎁 New Year gift 🎁 Get 10% discount with code “POWERCOUPLE” at checkout - applicable to any NVIDIA courses or certifications!

NEWS

This Week in the Tech World

Amazon Workers' Holiday Strike: Workers at seven Amazon facilities across four states staged a Teamsters-organized strike during peak holiday season. While union claims 10,000 members, this represents less than 1% of Amazon's 1.53M workforce. Amazon says protesters are mostly outsiders.

Google Cuts Management: Google CEO Sundar Pichai has reduced managerial roles by 10% across managers, directors, and VPs. Some were shifted to individual contributor roles while others were laid off, continuing the company's efficiency drive after cutting 12,000 jobs in 2023.

Trump's Tech Team: President-elect Trump taps Silicon Valley leaders for key positions, including Andreessen Horowitz partners Scott Kupor and Sriram Krishnan. Elon Musk emerges as close advisor in new administration.

Biden Probes Chinese Chips: US launches investigation into Chinese legacy semiconductors used in cars and household goods. The probe could lead to new tariffs as Biden administration escalates pressure on China's tech sector.

Meta's AI Push: Mark Zuckerberg invested heavily in AI in 2024, spending $10B on infrastructure. Meta AI reached 600M monthly users, while company stock hit record highs as investors embraced its AI strategy despite initial skepticism.

Musk Backs AfD: Tesla CEO Elon Musk endorsed Germany's far-right AfD party, claiming "Only the AfD can save Germany." The endorsement drew criticism from German Chancellor Scholz and US Senator Chris Murphy.

Digital Health Downturn: Digital health companies faced significant losses in 2024 despite Nasdaq's 32% gain. Two-thirds of 39 public digital health firms lost value as post-pandemic demand declined, though Hims & Hers stood out with 200% growth.

HOLIDAY SPECIAL

This Holiday Season, Give Yourself the Gift of Nike Air Max.

This winter, take your footwear game to the next level with Nike's Air Max collection for men. With a diverse range of models, this collection prioritizes comfort and functionality, perfectly tailored to meet your everyday needs. Whether you're hitting the gym or heading out for a casual outing, these sneakers deliver the support you crave without compromising on style.

Find the perfect pair that matches your lifestyle and get ready to make a statement with every step. Treat yourself to a fresh pair from the collection this holiday season—you deserve it.

Shop the Men’s Air Max Collection

IN THE AI WORLD

Learn AI in 5 minutes a day

What’s the secret to staying ahead of the curve in the world of AI? Information. Luckily, you can join 800,000+ early adopters reading The Rundown AI — the free newsletter that makes you smarter on AI with just a 5-minute read per day.

Sign up to start learning.

BONUS

Just for laughs 😏

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.

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra