A spanning tree is a tree that connects all the vertices of a graph through some edges. If a graph has N vertices, then its spanning tree will have N-1 edges. A minimum spanning tree is a spanning tree of a weighted graph with the minimum total edge weight. the lightest edge plays a crucial role in finding the MST. There are two algorithms for finding minimum spanning trees: Kruskal's algorithm and Prim's algorithm.

Applications:

• Communication networks
• Transportation networks

Prim's Algorithm​

• Prim's algorithm uses a greedy strategy.
• It starts with an arbitrary vertex v and chooses the minimum edge that connects v to a new vertex w.
• This process is repeated until the minimum spanning tree (MST) is found.
• Utilizes a binary heap to store the edges outside clusters.
• The running time is O(E log V) since the graph is connected.
• The space complexity is either O(E + V) using a binary heap or O(V) using a Fibonacci heap.

Kruskal's Algorithm​

• Scans the edges only once.
• Works with disconnected graphs
• Ensures that the result is a tree with no cycles.
• Utilizes a priority queue to store the edges outside clusters.
• Maintains a forest of trees.
• The running time is O(E log E) or O(E log V), whichever is smaller.
• The space complexity for storing the graph and the disjoint-set data structure is O(V + E).

Overview​

Buffers are memory storage regions that temporarily hold data while it is being transferred from one location to another.

Buffer overflow happens when data quantity exceeds memory buffer storage capacity. This can occur due to a programming mistake when a process tries to store data outside the limits of a fixed-sized buffer. Consequently, the program that attempts to write data to the buffer overwrites adjacent memory locations.

The consequence of a buffer overflow is the corruption of data, unexpected transfer of control, and possible memory access violations.

Exploiting​

To exploit a buffer overflow, the attacker needs to identify a buffer overflow vulnerability and understand how that buffer will be stored in the process memory.

For example, a buffer for login credentials may be designed to expect 8-byte inputs for both the username and password. If a transaction involves an input of 10 bytes (2 bytes more than expected), the program may write the excess data past the buffer boundary.

if attackers know the memory layout of a program, they can intentionally feed input that the buffer cannot store, and overwrite areas that hold executable code, replacing it with their own code

Types of buffer overflow attacks​

Stack-based attacks:

This type of attack is more common and leverages stack memory that only exists during the execution time of a function.

Heap-based attacks:

This type of attack can be difficult to carry out and may involve flooding the memory space allocated for a program beyond the memory used for current runtime operations.

Program Memory layout​

When a program runs, it needs memory space to store data. For a C program, its memory is divided into five segments, each with its own purpose:

Text Segment:

Stores the executable code. Usually read-only.

Data Segment:

Stores static/global variables.

BSS Segment:

Stores uninitialized static/global variables. Filled with zeros by the OS.

Heap:

Used to provide space for dynamic memory allocation.

Stack:

Used for storing local variables defined inside functions.

Prevent Strategy​

Address Space Randomization (ASLR):

ASLR randomly moves the address space location of data regions. Typically, buffer overflow attacks need to know the locality of executable code. Randomizing address spaces makes this virtually impossible.

Data Execution Prevention:

Data Execution Prevention is a security feature that flags certain areas of memory as non-executable or executable. This prevents an attacker from running code in a non-executable region.

Structured Exception Handler Overwrite Protection (SEHOP):

SEHOP is a built-in system that helps prevent malicious code from attacking structured exception handling. It manages hardware and software exceptions, thus preventing an attacker from using a stack-based buffer overflow to overwrite an exception registration record stored on a thread's stack.

Cases​

• Morris worm in 1988
• Code Red worm in 2001
• SQL Slammer in 2003
• Stagefright attack against Android phones in 2015
• CVE-2021-21017 (impacts Adobe Acrobat Reader)

Virtualization is the process of creating a simulated computing environment or a computer-generated computer. It provides an abstraction layer between computing, storage, and networking hardware and applications. Virtualization makes hardware independent of operating systems (OS) and applications and can be provisioned to any system. The OS can be encapsulated into one virtual system. Virtualization allows us to create multiple computing instances from a single machine. These instances could be computers in the traditional sense, or storage repositories, servers, or networking configurations.

The software that enables virtualization is called a hypervisor. the hypervisor is a lightweight software layer that is installed on top of hardware to create virtualized environments., allowing multiple operating systems to run on the same hardware. The hypervisor acts as a middleman, pulling resources from the raw materials of the infrastructure and directing them to the various computing instances.

Types of hypervisor​

Type 1 - Bare Metal Hypervisor

A Type 1 Hypervisor, also known as a Bare Metal Hypervisor, runs directly on computer hardware instead of the operating system. Therefore, Type 1 Hypervisors offer better performance and are commonly used in enterprise applications.

Type 2 - Hosted Hypervisor

A Type 2 hypervisor runs as an application on an operating system. It is used when running various operating systems on a single machine.

Types of Virtualization​

OS-level virtualization.

Operating systems allow for the running of multiple secure virtual servers, making subsystems think they are running on their own operating system. Guest OSes are the same as the host OS but appear isolated. Examples include Docker, Linux Vserver, Solaris Containers, and FreeBSD Jails.

Application-level virtualization

The application behaves at runtime in a similar way to when it directly interfaces with the original operating system. The application provides its own copy of components that are not shared. The application virtualization layer replaces part of the runtime environment normally provided by the OS. Examples include the Java Virtual Machine (JVM)

Full/Native Virtualization

Virtual machines simulate enough hardware to allow an unmodified guest to run in isolation. Any software capable of executing on the hardware can be run in the virtual machine. Every operation performed within a given virtual machine must be kept within that virtual machine. Intercepting and simulating privileged operations is challenging. Examples include VirtualBox, Parallels, and Mac on Linux.

Paravirtualization

In paravirtualization, the virtual machine (VM) does not simulate hardware. Instead, it presents a software interface to the VM that is similar to, but not identical to, the underlying hardware. A special API (para-API) is used to achieve this, which the modified guest OS must also use. Hypervisor then traps hypercalls and services them. Example include Xen

Emulation

A virtual machine (VM) emulates complete hardware and software, while an emulator is a hardware or software tool that enables a system (host) to behave like another system (guest). Emulators are useful for reverse engineering, malware analysis, and forensics. Examples include VirtualPC for Mac and the Android emulator.

Virtual Machine

In the early days, software was written for specific hardware. Eventually, instruction sets became more standardized, but the software still requires a certain instruction set architecture and operating system that meets strict standards.

A virtual machine can be categorized as a “system virtual machine” or a “process virtual machine”. The former provides a full execution environment that can support multiple processes and I/O devices, as well as a GUI. The latter is instantiated for a single program and terminates when that process terminates.

Popular VM providers include VirtualBox, Xen Project, Microsoft Hyper-V, and VMware Workstation Player.

Java Virtual Machine

The Java Virtual Machine (JVM) interprets Java bytecode, allowing the same bytecode to run on all architectures. The JVM can also run multiple programs simultaneously.

Linux Containers(LXC)

LXC is an OS-level virtualization method for running multiple isolated Linux systems on a single control host. It does not provide a virtual machine but rather a virtual environment with its own CPU, memory, block I/O, network, etc. This is achieved through namespace and cgroups features in the Linux kernel on the LXC host.

Benefits​

This technology allows the execution of multiple operating systems on a single physical machine. This results in cost savings when compared to using separate physical machines. Furthermore, the technology has well-established functionality, robust management tools, and well-known security tools and controls.

Vulnerabilities​

Virtual Machines (VMs) are susceptible to various types of attacks. These include:

• Hardware-oriented attacks
• Management interface exploits
• Break out of jail attacks
• Almost-undetectable virtual-machine based rootkits (Blue Pill)
• Application privilege escalation
• Just-in-time spraying
• Untrusted native code execution

VM vs. Containers​

Namespaces​

Namespaces restrict what a container can see and provide process-level isolation of global resources. Processes have the illusion that they are the only process in the system. There are six namespaces:

• mnt (mount points)
• pid (processes)
• net (network stack)
• ipc (System V IPC)
• uts (hostname)
• user (UIDs)

Docker​

Docker is an open-source project that automates the deployment of applications inside software containers. It provides an additional layer of abstraction and automates OS-level virtualization on Linux. Docker uses resource isolation features of the Linux kernel, such as cgroups and kernel namespaces, to allow independent containers to run within a single Linux instance, avoiding the overhead of starting and maintaining virtual machines.

Docker includes the libcontainer library as a way to directly use virtualization facilities provided by the Linux kernel, in addition to using abstracted virtualization interfaces via libvirt, LXC, and systemd-nspawn. Docker implements a high-level API to provide lightweight containers that run processes in isolation. Unlike a traditional virtual machine, a Docker container does not require or include a separate operating system. Instead, it relies on the kernel's functionality and user's resource isolation, as well as separate namespaces to isolate the application view of the operating system.

References

• Amazon Web Services. (n.d.). What is Virtualization? AWS. https://aws.amazon.com/what-is/virtualization/

Functional programming creates new forms of values using type conversion and built-in functions.

It is possible to chain the results and ultimately make the code more concise.

Usage

type casting​

// List <-> Map <-> Set

// Cast in List
List<String> blackPink = ['a', 'b', 'c', 'd',];
final Map blackPinkMap = blackPink.asMap(); // {0: a, 1: b, 2: c, 3: d}
final Set blackPinkSet = blackPink.toSet(); // {a, b, c, d}

// Case in Map
final Map blackPinkAsMap = blackPink.asMap();
List<dynamic> keys = blackPinkAsMap.keys.toList(); // [0, 1, 2, 3]
List<dynamic> values = blackPinkAsMap.values.toList(); // [a, b, c, d]

// Cast in Set
Set blackPinkFronSet = Set.from(blackPink); // {a, b, c, d}
List balckSet = blackPinkFronSet.toList(); // [a, b, c, d]

map()​

• Methods of List
• Returns a new list after changing the format of all member variables.
• The list created by map() has a different address value even if the member variables are the same

iterable:​

A collection that can be iterated over (list, array)

Use the .toList() method to convert to a list

List<String> blackPink = ['a', 'b', 'c', 'd',]

blackPink.map((item){
	return 'this it $item'
});

// with arrow function
final blackPink2 = blackPink.map((item) => 'black pink $item')

mapping Map​

Map<String, String> harryPotter = {
  'harry potter': '해리포터',
  'ron': '론',
  'hermione': '헤르미온느'
};

// When mapping a map, you receive both key and value.
final result = harryPotter.map(
    (key, value) => MapEntry('harry potter character $key', '해리포터 캐릭터 $value'));

void main() {
  // key
  print(harryPotter.keys.map((item) => 'key is $item').toList());
	// value
  print(harryPotter.values.map((item) => 'value is $item').toList());
}

mapping Set​

Set blackPinkSet = {"rose",'jisu','jenny','lisa'};

final newSet = blackPinkSet.map((item) => 'this is $item').toSet();

where()​

Purpose of filtering

List<Map<String, String>> people = [
  {
    'name': '제니',
    'group': '블랙핑크',
  },
  {
    'name': '로제',
    'group': '블랙핑크',
  },
  {
    'name': 'RM',
    'group': 'BTS',
  }
];

final result = people.where((item) => item['group'] == 'BTS').toList();

reduce()​

• Only the first values of the previous and next are entered in the first time.
• After that, the return value of the callback function becomes the previous value of the next iteration.
• Reduce can only return results of the same type as instance variables.
• This problem can be solved with fold()

List<int> numbers = [1, 2, 3, 4, 5];

int resultInt = numbers.reduce((prev, next) {
  return prev + next;
});

// arrow function
numbers.reduce((prev, next) => prev + next);

fold()​

• Like reduce(), it allows you to set the return data type while setting an initial value
• The first parameter goes into prev, and the first member variable goes into next

List<int> numbers = [1, 2, 3, 4, 5];

// Specify the return type as Generic
numbers.fold<int>(0, (prev, next) => prev + next);

List<String> words = ['Hi', 'Hello'];

words.fold<String>('', (prev, next) => prev + next); // HiHello
words.fold<int>(0, (prev, next) => prev + next.length); // 7

…cascade operator​

• When combining lists
• The member variables are unpacked and added to the new list
• A new list is created

List<int> even = [2, 4, 6];
List<int> odd = [1, 3, 5];
List newArr = [...even, ...odd];

// `[...even]` and `even` are different.

About the Pattern​

The K-way merge pattern is a fundamental algorithmic strategy used to merge K sorted data structures—such as arrays and linked lists—into a single sorted structure. It extends the traditional merge sort algorithm, which combines two sorted structures into one.

Note: For simplicity, the term lists will refer to both arrays and linked lists in this discussion.

The core idea behind the K-way merge algorithm is simple: repeatedly select the smallest (or largest, for descending order) element from the first elements of the K input lists and append it to a new output list. This process continues until all elements are merged into the output list, maintaining the sorted order.

How the Algorithm Works​

The K-way merge algorithm has two main approaches for achieving its goal, each leading to the same result. Let's explore these approaches in detail.

Approach 1: Using a Min Heap​

1. Initialize the Heap
   Insert the first element of each list into a min heap. This heap helps efficiently track the smallest current element among the lists.

2. Build the Output List
   Remove the smallest element from the heap (always at the top) and add it to the output list.

3. Track Element Origins
   Keep track of which list each element in the heap originated from to determine the next element to add.

4. Replace Elements in the Heap
   After removing the smallest element, replace it with the next element from the same list.

5. Repeat Steps
   Repeat steps 2–4 until all elements are merged into the output list.

Approach 2: Grouping and Merging Pairs of Lists​

1. Divide into Pairs
   Divide the K sorted lists into pairs, grouping them for two-way merges.

2. Perform Two-Way Merges
   For each pair, perform a standard two-way merge to create a single sorted list for that pair.

3. Handle Odd Lists
   If there is an odd number of lists, leave one list unmerged for the current round.

4. Repeat Pairing and Merging
   Continue pairing and merging the resulting lists until only one sorted list remains.

Examples of Problems Solved with K-way Merge​

1. Median of K Sorted Arrays
   Find the median of K sorted arrays.

2. K-th Smallest Element Across Arrays
   Find the K-th smallest element among multiple sorted arrays.

Identifying Problems That Match This Pattern​

A problem likely fits this pattern if:

• Merging Sorted Structures: It involves merging multiple sorted arrays or matrices.
• Finding K-th Smallest/Largest: It requires identifying the K-th smallest or largest element across sorted collections.

Real-World Applications​

1. Patient Records Aggregation
   Combine sorted streams of patient data (lab results, notes, reports) into a unified, chronologically ordered record for comprehensive healthcare management.

2. Merging Financial Transaction Streams
   Merge sorted transactions (trades, payments, transfers) into a single stream for real-time analysis and fraud detection.

3. Log File Analysis
   Merge server logs into a single, time-ordered stream for performance monitoring, user behavior analysis, or error diagnosis.

Merge Sorted Array solution:​

The following example demonstrates merging two sorted arrays in place:

1. Initialize two pointers: p1 (last element of nums1) and p2 (last element of nums2).
2. Initialize a pointer p pointing to the last element of nums1.
3. Compare elements:
   • If nums1[p1] > nums2[p2], set nums1[p] = nums1[p1] and decrement p1 and p.
   • Otherwise, set nums1[p] = nums2[p2] and decrement p2 and p.
4. Repeat until all elements of nums2 are merged into nums1.

The algorithm processes the arrays in reverse order, starting from the largest elements and filling nums1 from the end. This approach prevents overwriting existing data in nums1 as it is merged in place. The merge only considers the first m elements in nums1 and the first n elements in nums2. Any extra space in nums1 beyond m + n is irrelevant for the merging process.

About the Pattern​

The two heaps pattern is a versatile and efficient approach for solving problems involving dynamic data processing, optimization, and real-time analysis. As the name suggests, this pattern uses two heaps, which could be:

• Two min heaps
• Two max heaps
• A combination of one min heap and one max heap

By exploiting the heap property, this pattern is often used to implement computationally efficient solutions.

Key Properties of Heaps​

• Insertion/Removal Complexity: O(log n), where n is the number of elements in the heap.
  • When adding a new element to the heap:
    • Insert it at the last position of the heap.
    • Restore the heap property by moving upward, comparing the element with its parent node (Heapify-Up).
• Access Root Element: O(1).
  • Min Heap: Root stores the smallest element.
  • Max Heap: Root stores the largest element.

Common Use Case​

Given a dataset, the two heaps pattern can be used to divide it into two parts and efficiently find:

• The smallest value from one part (using a min heap).
• The largest value from the other part (using a max heap).

Other scenarios include finding:

• The two largest numbers from two datasets (using two max heaps).
• The two smallest numbers from two datasets (using two min heaps).

These examples highlight the pattern's flexibility for solving various problems by enabling quick access to minima and maxima as needed.

Examples​

1. Sliding Window Median​

Given an array of integers and a window size k, find the median of each sliding window of size k as it moves from left to right through the array.

2. Find Median of a Number Stream​

Given a continuous stream of numbers, efficiently find the median of the numbers seen so far after any insertion.

1. Insert the new data into the Max-Heap first.
2. If the root value of the Max-Heap is greater than the root value of the Min-Heap, move the largest value from the Max-Heap to the Min-Heap to maintain the correct order.
3. Adjust the sizes of the two heaps to maintain balance:
4. The size of the Max-Heap should be at most 1 greater than the size of the Min-Heap. Median Calculation: If the sizes of the two heaps are equal, return (Max-Heap root+Min-Heap root)/2 If the Max-Heap is larger, return the root of the Max-Heap.

Does Your Problem Match This Pattern?​

Applicable Scenarios​

The two heaps pattern applies if:

1. Static or Streaming Data:
   • Linear Data: Input data is linear but not sorted. (If sorted, this pattern isn’t required.)
   • Stream of Data: Input is a continuous data stream.
2. Maxima and Minima Calculation:
   • The input can be divided into two parts, requiring repeated calculations for:
     • Two maxima.
     • Two minima.
     • One maximum and one minimum.

Real-World Problems​

1. Video Platforms​

For demographic studies, calculate the median age of viewers efficiently as new users sign up for video streaming.

2. Gaming Matchmaking​

Match players of similar skill levels for a balanced gaming experience. Use:

• One heap for minimum skill levels.
• One heap for maximum skill levels.

3. IPO Solution​

Efficiently select projects to maximize profits with the following steps:

1. Initialize a Min-Heap: Store the project capital requirements.
2. Identify Feasible Projects: Find projects investable within the current capital range.
3. Select the Most Profitable Project: Choose the project yielding the highest profit.
4. Update Capital: Add the earned profit to the current capital.
5. Repeat Until Target Achieved: Continue until k projects are selected.

In this guide, we'll explore the In-Place Manipulation of a Linked List pattern, its real-world applications, and the problems it helps solve.

About the Pattern​

The in-place manipulation of a linked list allows us to modify a linked list without using additional memory. "In-place" refers to an algorithm that processes or modifies a data structure using only existing memory space, without requiring extra memory proportional to the input size.

This pattern is especially useful for problems that involve modifying the structure of a linked list, such as changing the order of node connections. For instance, certain problems require reversing a set of nodes or even the entire linked list. Instead of creating a new linked list with reversed links, we can achieve this in place without extra memory usage.

A naive approach to reversing a linked list involves traversing it and creating a new linked list with reversed links. This method has a time complexity of O(n), but it consumes O(n) extra space.

How can we implement in-place reversal efficiently?​

We iterate over the linked list while keeping track of three nodes:

• The current node
• The next node
• The previous node

Tracking these three nodes allows us to efficiently reverse the links between each pair of nodes. This in-place reversal operates in O(n) time and consumes only O(1) space.

Examples​

Below are some problems that can be solved using this approach:

1. Reverse the second half of a linked list

   • Given a singly linked list, reverse only the second half.

2. Rotate a linked list clockwise k times

   • Given a singly linked list and an integer k, rotate the linked list clockwise k times.

Does Your Problem Match This Pattern?​

Yes, if the following conditions are met:

1. Linked list restructuring

   • The input is a linked list, and the task requires modifying its structure rather than the data in individual nodes.

2. In-place modification

   • The changes must be made in place, meaning we cannot use more than O(1) additional space.

Real-World Applications​

Many real-world problems utilize the in-place manipulation of a linked list pattern. Here are some examples:

1. File System Management​

• File systems often rely on linked lists to organize directories and files.
• Operations like rearranging files within a directory can be efficiently handled by modifying the linked list in place.

2. Memory Management​

• In low-level programming and embedded systems, dynamic memory allocation and deallocation often involve manipulating linked lists of free memory blocks.
• Tasks such as merging adjacent free blocks or splitting large blocks can be optimized using in-place operations.

Reverse Linked List Solution​

Follow these steps to reverse a linked list in place:

1. Initialize

   • Set prev and next pointers to NULL.
   • Set the curr (current pointer) to the head node.

2. Traverse the linked list

   • Continue until the curr pointer reaches the end.

3. Reverse pointers

   • Set the next pointer to the next node.
   • Reverse the current node’s pointer to point to the previous node.

4. Update pointers

   • Move prev and curr forward.

5. Update head

   • After traversal, prev points to the last node of the original list.
   • Set the head pointer to prev.

This efficient approach allows us to reverse a linked list in O(n) time using only O(1) space.

Let's explore the Merge Intervals pattern, its real-world applications, and the types of problems it helps solve.

About the Pattern​

The Merge Intervals pattern addresses problems involving overlapping intervals. Each interval is defined by a start and an end time. For example, an interval [10, 20] represents a time span starting at 10 seconds and ending at 20 seconds.

This pattern is commonly used for tasks such as:

• Merging overlapping intervals
• Inserting new intervals into existing sets
• Determining the minimum number of intervals required to cover a given range

Typical problems solved using this approach include event scheduling, resource allocation, and time slot consolidation.

Understanding Overlapping Intervals​

The key to mastering this pattern is understanding how two intervals may overlap.

Examples​

Here are some problems that can be solved using this method:

1. Merge Intervals
   Given a sorted list of intervals, merge all overlapping ones into a single interval.

2. Meeting Rooms
   Given an array of meeting time intervals with start and end times, determine if a person can attend all meetings.

Does Your Problem Match This Pattern?​

Your problem likely fits the Merge Intervals pattern if both of these conditions apply:

• Array of intervals: The input is an array of intervals.
• Overlapping intervals: The problem involves finding the union, intersection, or gaps between overlapping intervals.

Real-World Applications​

This pattern has many practical applications, such as:

• Displaying a busy schedule: Show a user's busy hours without revealing individual meeting details in a calendar.
• Scheduling a new meeting: Insert a new meeting into a schedule while ensuring no conflicts.
• Task scheduling in operating systems (OS): Allocate tasks based on priority and available processing time slots.

Merge Intervals Solution​

1. Insert the first interval from the input list into the output list.
2. Iterate through the remaining intervals in the input list.
3. If the current interval overlaps with the last interval in the output list:
   • Merge them.
   • Replace the last interval in the output list with the merged interval.
4. If the current interval does not overlap, add it to the output list.

By following this approach, we can efficiently handle problems involving merging and managing intervals.

Overview​

The Sliding Window pattern is a powerful technique used for efficiently solving problems related to sequential data, including arrays and strings. This approach allows us to process subarrays or substrings dynamically by maintaining a window that adjusts as it slides across the data.

Understanding the Pattern​

The Sliding Window technique helps in solving problems that involve sequential data by maintaining a dynamic window that moves through an array or string. Instead of recalculating values from scratch, the window adjusts by adding new elements and removing old ones as it slides.

Think of it as looking through a narrow frame while walking down a long hallway filled with paintings. As you move, new paintings come into view while others disappear. Similarly, this technique processes only a subset of the data at any time, improving efficiency.

Why is Sliding Window Efficient?​

Consider a problem where we need to find k consecutive integers with the highest sum in an array. A naive approach would involve calculating the sum of all possible subarrays of size k, resulting in a time complexity of O(kn).

However, using the Sliding Window technique, instead of recalculating sums entirely, we update the sum dynamically:

• Subtract the element that leaves the window.
• Add the element that enters the window.
• Update the maximum sum accordingly.

This reduces the time complexity to O(n), as each window update takes constant time O(1). The goal is to ensure that the computation per window move remains minimal, ideally in O(1) or a slow-growing function like log(n).

Example Problems​

1. Maximum Sum Subarray of Size K​

Given an array of integers and a positive integer k, find the maximum sum of any contiguous subarray of size k.

2. Longest Substring Without Repeating Characters​

Given a string, determine the length of the longest substring that does not contain duplicate characters.

Does Your Problem Fit This Pattern?​

Your problem likely benefits from the Sliding Window approach if:

• Contiguous Data: The input is stored as a contiguous structure, such as an array or string.
• Processing Subsets: The problem requires computations on a contiguous subset of elements that slide through the data. The window size may be fixed or dynamic.
• Efficient Computation: The per-move calculations should be constant-time or nearly constant.

Real-World Applications​

• Telecommunications: Determine the peak number of users connected to a cellular network’s base station within a k-millisecond window.
• Video Streaming: Compute the median buffering events over each one-minute interval in a streaming session.
• Social Media Mining: Identify the shortest sequence of posts by one user that includes all topics mentioned by another user.

Example: Repeated DNA Sequences​

Given a DNA sequence (dna) and an integer k, return all contiguous subsequences of length k that appear more than once. If no such sequence exists, return an empty set.

Solution Approach​

1. Iterate through all substrings of length k in the given string.
2. Store the hash of each substring to track uniqueness.
3. If a hash is found again, the substring is repeated and should be added to the output.
4. Return the set of repeated substrings after processing the entire string.

Overview​

The Fast and Slow Pointers pattern is a technique used in problem-solving, particularly for detecting cycles and identifying key structural properties in data structures. This pattern finds application in real-world scenarios and various algorithmic problems.

About the Pattern​

The fast and slow pointers method, similar to the two-pointers approach, involves two pointers traversing an iterable data structure at different speeds. However, unlike the two-pointers technique, which mainly focuses on comparing values, this method is used for analyzing structure and properties.

Key Concept​

• The pointers start at the same position but move at different speeds.
• The slow pointer advances one step at a time.
• The fast pointer moves two steps at a time.
• Due to their differing speeds, this technique is often referred to as the Hare and Tortoise Algorithm, where the hare (fast pointer) moves faster than the tortoise (slow pointer).
• If a cycle exists, the two pointers will eventually meet, making it useful for detecting cycles, midpoints, or intersections.

Visualization​

Imagine two runners on a circular track starting from the same position. If one runs faster than the other, the faster runner will eventually overtake the slower one. This concept mirrors how cycle detection works in linked lists and arrays.

Examples​

Here are some problems that can be solved using this approach:

1. Finding the Middle of a Linked List: Given a singly linked list, return its middle node.
2. Detecting a Cycle in an Array: Given an array of non-negative integers where elements act as indices pointing to the next element, determine if a cycle exists.

When to Use This Pattern?​

Use this pattern if the following condition holds:

• The problem involves a linear data structure such as an array, linked list, or string.

Additionally, consider this approach if either of these conditions is met:

• Cycle or Intersection Detection: The problem involves detecting loops in linked lists or arrays or finding intersections between two linked lists or arrays.
• Finding a Key Element in a Segment: This includes finding the middle element of a data structure, such as the second half, second tertile, or second quartile.

Real-World Applications​

The fast and slow pointers technique is widely used in real-world scenarios. Below are a couple of examples:

1. Symlink Verification​

As an IT administrator managing a large server, you may encounter symbolic links (symlinks) pointing to other files. Sometimes, a loop may form—where symlink A points to B, and B eventually links back to A.

Using fast and slow pointers:

• The slow pointer follows links one step at a time.
• The fast pointer jumps two steps.
• If both pointers meet, a cycle is detected, indicating an infinite loop in the symlink structure.

2. Detecting Cyclic Dependencies in Object-Oriented Compilation​

During compilation, object-oriented modules may depend on one another. If module A depends on B, and B depends on A, a cycle is formed.

By applying fast and slow pointers:

• The slow pointer moves one module at a time.
• The fast pointer moves two modules at a time.
• If the pointers meet, a cyclic dependency exists, which needs to be resolved for successful compilation.

Example: Happy Number Problem​

A Happy Number is a number that eventually reaches 1 when replaced by the sum of the squares of its digits. If it enters a cycle instead, it is not a happy number.

Solution Approach​

1. Initialize two pointers:

   • slow_pointer: Starts at the input number.
   • fast_pointer: Starts at the sum of squared digits of the input number.

2. Loop until:

   • fast_pointer reaches 1 (indicating a happy number).
   • Both pointers meet, indicating a cycle.

3. Update pointers:

   • Move slow_pointer by replacing it with the sum of the squares of its digits.
   • Move fast_pointer in the same manner, but twice.

4. Check for happiness:

   • If fast_pointer equals 1, return TRUE (happy number).

5. Detect a cycle:

   • If the loop exits without reaching 1, return FALSE, confirming the presence of a cycle (not a happy number).

By leveraging the Fast and Slow Pointers approach, many problems can be efficiently solved with minimal space complexity.