DSA Patterns

Question 1

Pattern used to search or operate on a pair of elements in an array

Answer 1

Two pointers. Ex Two Sum II, 3 Sum, Container with most water.

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

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

Pattern to find or operate on a subset of an array

Answer 4

Sliding Window. Move two pointers to define the subset. Ex Max Avg Subarray, Longest Substring without Repeating Chars, Min Window Substring.

Question 5

Pattern to find cycles and dupes

Answer 5

Fast and Slow Pointers. Ex Linked List Cycle, Happy Number, Find duplicate number

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