Patterns Full Description Flashcards
the sliding window pattern is used to process sequential data by maintaining a moving subset of elements, called a window. The pattern is aimed at reducing the use of nested loops in an algorithm. It may be viewed as a variation of the two pointers pattern, with the pointers being used to set the window bounds.
Sliding Window
Most of the problems requiring matrixes can be solved using the following operations: Matrix transformations:
A few transformations are scaling, translation, rotation, and reflection.
Matrix traversals: A few matrix traversals are simple, spiral, and diagonal traversals, as illustrated below.
Islands (Matrix Traversal) /Matrices
the two pointers pattern uses two pointers to iterate over an array or list until the conditions of the problem are satisfied. This is useful because it allows us to keep track of the values of two different indexes in a single iteration. Whenever there’s a requirement to find two data elements in an array that satisfy a certain condition, the two pointers pattern should be the first strategy to come to mind.
Two Pointers
“pattern uses two pointers to traverse an iterable data structure at different speeds. It’s usually used to identify distinguishable features of directional data structures, such as a linked list or an array.
Detect Cycles”
Fast & Slow Pointers
“the __ pattern deals with problems involving overlapping intervals. Each interval is represented by a start and an end time. For example, an interval of [10,20]
seconds means that the interval starts at 10 seconds and ends at 20
seconds, such that both 10 and time 20 are included in the interval.
The most common problems solved using this pattern are scheduling problems.”
Merge Intervals
___ is an in-place, unstable, comparison sort algorithm. Its Is based on the insights that subsequences of numbers in the input array that are not in sorted order acutally describes cycles, and the process of placing each number in its correct position removes these cycles
Cyclic Sort
The ____ of a linked list pattern allows us to reverse a linked list without any additional memory, using only the given nodes.
In-place Reversal of a LinkedList
“____ is a method to reduce the use of nested loops in our tree-related problems. ___ search in a ___ is usually implemented recursively. However, it can also be implemented iteratively with the help of a stack. The fundamental characteristic of this pattern is that it travels as far as possible along each tree branch before exploring the others.
There are three main methods to solving a problem with the depth-first search pattern—Preorder, Inorder, and Postorder.
Preorder - root, left, right
In order- left, root, right
Postorder - left, right, root
Therefore, we would prefer __ if the destination node were close to a leaf. Meanwhile, we would favor ___ if our goal is to search for a node that is more likely to be closer to the root itself.”
Tree Depth First Search
___ search is an important tree traversal algorithm for finding a node in a tree that satisfies the given constraints. It starts searching at the root node and moves down level by level, exploring adjacent nodes at level k+1 Essentially, it first visits nodes that are one edge away from the root, followed by nodes that are two edges away, and so on. This helps in efficiently finding neighbor nodes, particularly peer-to-peer networking systems.
Tree Breadth-First Search
As the name suggests, the____ pattern uses either two min-heaps, two max-heaps, or a min-heap and a max-heap simultaneously to solve the problem.
Two Heaps
“The__ pattern is useful in finding the permutations and combinations of elements in a data structure. The input data structure might be a set containing unique elements. It can also be an array, or a list, which may contain duplicate elements. We then make a series of subsets from the elements in this data structure. The specific subsets generated are based on the conditions that the problem provides us.
We use a programming technique, defined below, known as backtracking to generate the required subsets of a given data structure of elements. The method is to build the subsets incrementally, including or excluding each element of the original data structure, depending on the constraints of the problem. This process is continued recursively for the remaining elements until all desired subsets have been generated.”
Subsets
“The ___ pattern builds upon the basic binary search algorithm discussed above. It involves adapting the traditional binary search approach by applying certain conditions or transformations, allowing us to solve more complex problems.
A few common variations of the modified binary search pattern are:
__ on a modified array: Sometimes, the array may be modified in a certain way, which affects the search process. For example, the array might be sorted and then rotated around some unknown pivot. Alternatively, some elements in a sorted array might be modified based on a specific condition. To handle such scenarios, we can modify the basic binary search technique to detect anomalies in the sorted order.
__ with multiple conditions: When searching for a target satisfying multiple conditions, a modified binary search can be used. It involves adapting the comparison logic within the binary search to accommodate multiple conditions. Examples include finding a target range rather than a single target, or finding the leftmost, or the rightmost occurrence of a target value.”
Modified Binary Search
___ is the process of modifying bits algorithmically using bitwise operations. Logical bitwise operations are the fastest computations, because processors natively support them. This approach generally leads to efficient solutions in problems where we can efficiently transform the input into its binary form or manipulate it directly at the bit level to produce the required output.
Bitwise XOR / Bitwise Manipulation
“The __ pattern helps find some specific k number of elements from the given data with optimum time complexity.
Many problems ask us to find the top, the smallest, or the most/least frequent k
elements in an unsorted list of elements. To solve such problems, sorting the list takes O(nlog(n))
time, then finding the k elements takes O(k) time. However, the top k elements pattern can allow us to solve the problem using O(n.logk) time without sorting the list first.”
Top ‘K’ Elements
“The __ pattern is a common algorithmic technique used to merge K sorted data structures, such as arrays and linked lists, into a single data structure that maintains the sorted order. It’s an extension of the standard merge sort algorithm, which merges two sorted data structures into one.
The basic idea behind the __ algorithm is to repeatedly select the smallest (or largest, depending on the sorting order) element among the K input lists and add it to the output list (with the same data type as the inputs). This process continues until all elements from all input lists have been added to the output list.”
K-way Merge
