DSA Patterns

Question 1

Two Pointers

Answer 1

Definition
Use two indices (pointers) that move through a data structure (often an array) at different speeds or directions to solve problems involving pair-sums, sorting, or partitioning.

Common Use Cases
• Finding pairs/triplets in a sorted array that sum to a specific value (e.g., 2-sum, 3-sum).
• Removing duplicates or elements in-place (e.g., “Remove Duplicates from Sorted Array”).
• Partitioning arrays (e.g., “Dutch National Flag”).

Question 2

Pattern to more optimally calculate the sum of a subset of elements in an array

Answer 2

Prefix Sum. Ex Range Sum Query, Contiguous Array, Subarray Sum. Takes only one pass to create the array, then 0(1) retrieval of sums

Question 3

Prefix Sum initialization and formula to find sum of subset

Answer 3

Initialization:
new Array(nums.length + 1).fill(0)

This sets up an array with an extra space for the initial sum of 0, and sets all other values to zero until they are summed.

Formula:
Sum(l, r) = prefixSum[r + 1] - prefixSum[l]

Subtracts the total sum just before the left pointer from the sum at the right pointer

Question 4

Sliding Window

Answer 4

Definition
Maintain a window (subarray or substring) that moves (slides) through the data, expanding or shrinking to satisfy conditions like sum, distinct characters, or maximum average.

Common Use Cases
• Subarray sums (e.g., “Subarray Sum Equals K” when all positives).
• Longest substring with certain constraints (e.g., “Longest Substring Without Repeating Characters”).
• Maximum average subarray, minimum window substring, etc.

Question 5

Fast and Slow Pointers

Answer 5

Definition
Use two pointers that move at different speeds (commonly in linked lists) to detect cycles or find middle points.

Common Use Cases
• Detecting cycles in a linked list.
• Finding the cycle start or the middle node of a linked list.
• Checking if a linked list is palindrome by splitting and reversing second half.

Question 6

Properties of a Linked List and Node

Answer 6

LinkedList: head, size
Node: data, next

Question 7

Linked List Insert First

Answer 7

Create a new node with the data and the current head as it’s next, then set the new node as the head.

Question 8

Linked List Insert Last

Answer 8

Set a current variable to the head. Then loop through while the current node has a next value and if it does setting next as the new current. When the current.next is null you are at the end of the list and can set current.next to a new node

Question 9

Linked List Insert at Index

Answer 9

If the index is greater than size exit function. If index is 0 then just invoke insert first method. Initialize variables for the current node, the previous node, and a count. While looping, set previous to current, increment count, and set current to next. Once count == index exit loop. Set new node next to current, set previous.next to new node.

Question 10

Linked List GetAt

Answer 10

Initialize count variable and loop while count < index then return current

Question 11

Linked List Remove At

Answer 11

Use current, previous, count and while loop to find node at index and identify its previous and next nodes. Then set previous.next to current.next, effectively removing current from the list

Question 12

Linked List Reversal

Answer 12

Cur, prev, next variables. While there is a cur:
next = cur.next
cur.next = prev
prev = cur
cur = next

After loop, prev will be the new head so set this.head to prev

Question 13

Linked List Reverse with Stack

Answer 13

Push all nodes into stack, then while the stack has elements, pop them off and set to the current.next then set current to current.next (the popped off element). Set last next pointer to null

Question 14

Linked List Clear

Answer 14

this.head = null

Question 15

Reverse Doubly Linked List

Answer 15

While (current)
temp = current.prev
current.prev = current.next
current.next = temp

current = current.prev

at the end temp will be pointing to new head
this.head = temp.prev

Question 16

Pattern to find the k smallest or k largest

Answer 16

Heaps. Min heap for k largest, max heap for k smallest.

Question 17

Formula to calculate the distance between two points on a plot

Answer 17

Math.sqrt((x1 - x2)^2 + (y1 - y2)^2) = distance

Question 18

Get parent, right child, left child in a heap or binary tree

Answer 18

Parent idx = Math.floor((i- 1) / 2)

Left child idx = 2 * i + 1

Right child idx = 2 * i + 2

Question 19

Adding to a heap

Answer 19

Push to heap (add lead) and heapify up

Set idx to last idx. While idx > 0

Get parent idx. Compare heap[idx] to heap[parentIdx] and switch them if needed. If not needed, break the loop

Question 20

Replacing an element in a heap (heap already has k elements and new element is larger/smaller than max/min)

Answer 20

Set root (heap[0]) to new element then heapify down

Set idx to 0. While true
Set largest/smallest idx for min/max heap respectively to idx. Get idx for left and right children. Compare left child the right child to largest/smallest and reassign largest/smallest as necessary. If largest/smallest still equals idx then break. If not switch element at idx with element at largest/smallest and set idx to largest/smallest idx

Question 21

Binary tree pre order

Answer 21

DFS - root, left, right

Question 22

Binary tree in order

Answer 22

DFS - left, root, right

Question 23

Binary tree post order

Answer 23

DFS - left, right, root

Question 24

Binary tree level order

Answer 24

BFS

Question 25

How to determine binary tree DFS order

Answer 25

“When processing a node, do I need information from the children first?” If yes - post order If no and tree is BST - in order If no and need to decide process at parent - pre order

Question 26

Binary tree DFS process

Answer 26

Recursively call method with each child as the new root

Question 27

Binary tree BFS

Answer 27

Set a queue and add root. While queue has elements Initialize current level array Set levelsize to queue length Loop levelsize amount of times, dequeue (shift) node and if not null push val to current level and push left and right children to queue. Exit inner loop and restart outer loop

Question 28

DFS

Answer 28

Depth first search. Recursively call on child or top/bottom/left/right element in a matrix

Question 29

BFS

Answer 29

Use queue to add children or top/bottom/left/right elements of matrix. Use whole loop, then set queue size to a variable (because size will change) and do a for loop where you pop off the next in line, process it, and potentially add more to the queue. Then the while loop starts again with new queue size

Question 30

Matrix directions

Answer 30

let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] for (let [dr, dc] of directions

Question 31

How do you implement a Queue with O(1) retrieval?

Answer 31

Set the data property to a hash map. Add a front idx and back idx property and initialize at 0 for both. When adding an element, add the current back idx as the key and the element as the value, then increment back idx. When retrieving an element, retrieve the front idx key, save the value to a variable. Delete the element (delete this.data[this.front]) then increment front idx. Can also add size property. Check if it’s clear when front idx == back idx

Question 32

What is an adjacency list?

Answer 32

It’s a list representation of a graph, usually a hash map or array. For hash map the key is the vertex and the value is a list of vertices connected to that vertex by an edge. For array the index is the vertex and subarray is list of vertices

Question 33

Graph vertices and edges

Answer 33

A vertex or vertices are nodes or points on the graph. Edges are the connection between two vertices and they can be directed (one way) or undirected

Question 34

LRU Cache

Answer 34

Initialize with capacity property and cache property (Map). Get method checks if cache has key. If so it sets value to a variable, deletes the key, sets the key again with the value from the v variable then return the value. Put method checks for key and deletes if it exists. If it doesn’t exist but cache is at capacity then use Map iterator (this.cache.keys()) to get least recent (iterator.next().value) and delete it. Then add the new key and value. This can also be implemented with a doubly linked list.

Question 35

What makes a graph tree valid?

Answer 35

All nodes connected, no cycles

Question 36

What makes a graph tree valid?

Answer 36

All nodes connected, no cycles

Question 37

Backtracking

Answer 37

Build a solution incrementally and backtrack when the current path of choices won’t lead to a valid solution. Used for search, permutation, combination

Question 38

SOLID

Answer 38

Single responsibility principle - every class has one responsibility Open-closed principle - classes should be open for extension but closed for modification Liskov substitution principle - functions with references to base classes must be able to use objects of derived classes without knowing it Interface segregation principle - clients should not be forced to depend on interfaces they don’t use Dependency inversion principle - depend upon abstractions not concretes

Question 39

Merge Intervals

Answer 39

Definition Work with intervals (ranges) on a timeline. Often involves sorting intervals by start time and merging overlapping ones or inserting new intervals. Common Use Cases • Merging overlapping intervals (e.g., meeting room scheduling). • Finding intersection or union of intervals (e.g., “Interval List Intersections”). • Inserting intervals into existing schedules.

Question 40

Cyclic Sort

Answer 40

Definition A pattern that uses array indices as references to place each element in its correct position (usually in an array containing the range [1...n]). Common Use Cases • Finding missing/duplicate numbers in an unsorted array of a known range. • Kth missing positive style problems. • Cleaning up an array where each element ideally sits at its matching index.

Question 41

In Place Reversal of LinkedIn List

Answer 41

Definition Reverse linked list nodes or sublists in-place by adjusting pointers (no extra data structure). Often done by iteratively re-linking node pointers. Common Use Cases • Reversing an entire linked list (classic). • Reversing every k-group or rotating the list. • Reversing sublists (e.g., positions m through n).

Question 42

Stack

Answer 42

Definition A Last-In-First-Out (LIFO) data structure. Push items in, pop them out in reverse order. Common Use Cases • Expression evaluation (e.g., “Basic Calculator,” parentheses matching). • Backtracking or undo operations. • Reversing strings, validating parentheses, etc.

Question 43

Monotonic Stack

Answer 43

Definition A stack that keeps elements in either non-decreasing or non-increasing order, allowing quick access to next/previous greater/smaller elements. Common Use Cases • Finding next/previous greater or smaller elements (e.g., “Daily Temperatures,” “Next Greater Element”). • Largest Rectangle in Histogram. • Asteroid collision or ocean view type problems.

Question 44

Hash Map

Answer 44

Definition Store key-value pairs for efficient lookups and insertions, often in O(1) average time. Common Use Cases • Counting frequencies (e.g., top-K frequent elements). • Lookup sets for fast existence checks (e.g., “Two Sum”). • String grouping (e.g., “Group Anagrams”).

Question 45

Tree BFS

Answer 45

Definition Traverse a tree level by level, often using a queue to process all nodes at a given depth before moving to the next. Common Use Cases • Level order traversals (e.g., binary tree level order, right side view). • Finding shortest path in an unweighted tree/graph. • Connecting next pointers in a binary tree.

Question 46

Tree DFS

Answer 46

Definition Traverse a tree branch by branch (preorder, inorder, or postorder) often using recursion or an explicit stack. Common Use Cases • Path sums, diameter, lowest common ancestor in a binary tree. • Backtracking in tree-based problems. • Calculating max/min path sums or counting paths.

Question 47

Graphs

Answer 47

Definition Nodes connected by edges. Problems revolve around traversals (DFS/BFS), connected components, shortest paths, or cycles. Common Use Cases • Finding connected components or detecting cycles. • Shortest path in unweighted graphs (BFS). • Cloning or topological sorting for directed acyclic graphs.

Question 48

Island / Matrix Traversal

Answer 48

Definition View a grid/matrix as a graph. Each cell has potential edges (usually up, down, left, right). Perform BFS/DFS to explore connected regions. Common Use Cases • Counting islands or max area of islands. • Flood fill or searching for sub-regions. • Shortest path in a 2D grid.

Question 49

Two Heaps

Answer 49

Definition Maintain two heaps (a max-heap and a min-heap) to keep track of different portions of a data stream, often to find medians dynamically. Common Use Cases • Median of a running data stream. • Divide data into a “small half” and a “large half.” • Maximize capital or scheduling tasks with priorities.

Question 50

Subsets

Answer 50

Definition Generating all combinations or subsets of a given set, usually via backtracking or iterative BFS-like approach in the powerset. Common Use Cases • All subsets of a set/array. • Subsets with duplicates, permutations, or combinations. • Power set generation.

Question 51

Modified Binary Search

Answer 51

Definition Applying binary search logic to problems that aren’t simply “find an element in a sorted array.” Often searching in rotated arrays, infinite arrays, or searching for thresholds. Common Use Cases • Search in rotated sorted array. • Find first/last occurrence (lower bound, upper bound). • Peak finding, median of two sorted arrays.

Question 52

Bitwise XOR

Answer 52

Definition Use properties of XOR (like x ^ x = 0, x ^ 0 = x) to solve problems about finding single/missing numbers. Common Use Cases • Finding the single element in an array of duplicates (e.g., “Single Number”). • Finding 2 unique numbers in an array where others appear in pairs. • Base-10 complement or flipping bits.

Question 53

Top K Elements

Answer 53

Definition Use a data structure (often a heap or partial sort) to quickly find or maintain the top/bottom K items in a collection. Common Use Cases • Kth largest/smallest element in an unsorted array. • Top K frequent items (words, numbers). • K closest points to the origin.

Question 54

K-Way Merge

Answer 54

Definition Simultaneously merge data from multiple sorted lists/arrays, often using a min-heap to track the next smallest element. Common Use Cases • Merge k sorted linked lists. • Find smallest number range containing elements from k lists. • Kth smallest number from multiple sorted lists or a sorted matrix.

Question 55

Greedy Algorithms

Answer 55

Definition At each step, make the locally optimal choice with the hope it leads to a global optimum. Usually no backtracking. Common Use Cases • Interval scheduling, max profit in stock trading (simple repeated buys/sells). • Minimum number of platforms or meeting rooms needed. • Valid palindrome with limited removals (some are greedy).

Question 56

0/1 Knapsack (Dynamic Programming)

Answer 56

Definition Classic DP approach where we decide to include or exclude each item from a subset to achieve some target (like max value or exact sum). Common Use Cases • Subset sum, equal partition. • Target sum (rearranging plus/minus to match a goal). • Minimum subset difference or the general knapsack problem.

Question 57

Backtracking

Answer 57

Definition Systematically build all possible solutions by exploring partial solutions, then backtrack if constraints aren’t met. Common Use Cases • Generate permutations/combination sums. • N-Queens, sudoku solver, word search. • Expression operators (e.g., “Expression Add Operators”).

Question 58

Trie

Answer 58

Definition A tree-like data structure for storing strings (or sequences) character by character, enabling prefix-based lookups. Common Use Cases • Prefix searches, auto-complete suggestions. • Implementing dictionary lookups. • Storing large sets of strings efficiently.

Question 59

Topological Sort (Graph)

Answer 59

Definition A linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, node u comes before v in the ordering. Common Use Cases • Scheduling tasks with dependencies. • Alien dictionary (derive order of letters from words). • Course schedule problems.

Question 60

Union Find / Disjoint Set

Answer 60

Definition Data structure to keep track of elements partitioned into disjoint sets. Allows quick unions and finds of sets. Common Use Cases • Detect cycles in undirected graphs. • Counting connected components (e.g., number of provinces, dynamic islands). • Merging accounts or grouping objects.

Question 61

Ordered Sets

Answer 61

Definition A set (or balanced BST structure) that keeps elements in a sorted order, allowing queries like “find next higher element” or “range queries.” Common Use Cases • Scheduling or calendar problems (inserting intervals, finding overlaps). • Finding rank of an element in real-time. • Storing unique elements with the ability to do ordered iteration.

Question 62

Multi-Thread

Answer 62

Definition Patterns for concurrency: dividing tasks among multiple threads, ensuring safety and synchronization, or distributing work. Common Use Cases • Parallelizing large computations. • Producer-consumer or readers-writers patterns. • Synchronized iteration through shared data.