DS&A Flashcards
(88 cards)
1
Q
Process of returning to a previous state in the algorithm’s execution path when a terminal condition is reached to explore alternative possibilities
A
backtrack step
2
Q
this list type stores each node’s outgoing neighbors in its value array
A
An adjacency list
3
Q
Technique used to eliminate unnecessary exploration of the state space / Like taking shortcuts in our search by avoiding paths we know won’t lead to a solution
A
Pruning
4
Q
L._. nodes do not have any children.
A
Leaf nodes do not have any children.
5
Q
Condition telling us when to stop exploring a particular path. Could be due to a solution or because we’ve reached a dead end
A
terminal condition
6
Q
Potential choice or element that we can add to current partial solution
A
candidate
7
Q
the height of “p_____” binary trees grows logarithmically.
A
the height of “perfect” binary trees grows logarithmically.
8
Q
On average, searching for an element in a balanced Binary Search Tree takes O(_ ? _ ) time, where N is the number of nodes
A
On average, searching for an element in a balanced BST takes O(log N) time, where N is the number of nodes
9
Q
Full Binary Trees: Every node has either_ or_ children
A
Full Binary Trees: Every node has either zero or two children
10
Q
Complete Binary Trees: All levels are completely filled with nodes, except possibly for the l____ level (nodes are filled from l____ to r____ on the last level)
A
Complete Binary Trees: All levels are completely filled with nodes, except possibly for the last level (nodes filled from left to right on last level)
11
Q
Represent hierarchical structures or processes with a clear direction and no repetition;
No loops; once you go down a path, there’s no way back up;
A
acyclic graph
12
Q
At least one loop where you can start and end at same vertex; Useful for modeling systems that can return to their initial state
A
cyclic graph
13
Q
Balanced Binary Trees: the height of left and right subtrees of any node differs by at most ._.
A
Balanced Binary Trees: the height of left and right subtrees of any node differs by at most one
14
Q
Tree structure representing state space
A
state space tree
15
Q
B________ed Binary Trees: the height of left and right subtrees of any node differs by at most one
A
Balanced Binary Trees: the height of left and right subtrees of any node differs by at most one
16
Q
the height of perfect binary trees grows l________y.
A
the height of perfect binary trees grows logarithmically.
17
Q
N____ branching logic refers to the approach where we explore every possible option at each step without any early pruning or optimization
A
Naive branching logic refers to the approach where we explore every possible option at each step without any early pruning or optimization
18
Q
Set of all possible states in problem / all possible configurations or situations that may be encountered
A
state space
19
Q
the inner workings of which sorting algorithm does this snippet display:
if (arr[j] > arr[j + 1]) {
// Swapping elements
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
A
Bubble Sort
20
Q
Bubble sort has a time complexity of O(___)
A
Bubble sort has a time complexity of O(N^2)
Due to its nested loop structure, bubble sort is not considered efficient for large datasets. It performs a comparison and potential swap for every pair of elements in the array, leading to many unnecessary operations
21
Q
Due to its n____ed l___p structure, bubble sort is not considered efficient for large datasets. It performs a comparison and potential swap for every pair of elements in the array, leading to many un_____ operations
A
Due to its nested loop structure, bubble sort is not considered efficient for large datasets. It performs a comparison and potential swap for every pair of elements in the array, leading to many unnecessary operations
22
Q
However, when the array is already sorted or nearly sorted, the number of passes through the array will be significantly reduced. As soon as we iterate through the array without performing any swaps, we know that the array is already sorted. This means that in the best-case scenario, its time complexity is O(N), as we only need to perform one pass in a sorted array. This makes bubble sort a viable choice in practical scenarios involving n____ s____-ed arrays due to its simple implementation.
A
However, when the array is already sorted or nearly sorted, the number of passes through the array will be significantly reduced. As soon as we iterate through the array without performing any swaps, we know that the array is already sorted. This means that in the best-case scenario, its time complexity is O(N), as we only need to perform one pass in a sorted array. This makes bubble sort a viable choice in practical scenarios involving nearly sorted arrays due to its simple implementation.
23
Q
Describes which algorithm:
In each pass, the algorithm scans the unsorted part of the array to find the smallest element in that part.
A
selection sort
24
Q
Describes which algorithm:
Once the smallest element is identified, it is swapped with the leftmost element of the unsorted part (the element at the boundary of the sorted and unsorted parts).
A
selection sort
25
the inner workings of which sorting algorithm does this snippet display:
```
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// If the minimum element is already at
// index `i`, we don't need to swap
if (minIndex !== i) {
// Swap the first element of the unsorted portion
// with the element at `minIndex`
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
```
selection sort
26
Selection sort has a time complexity of O(___). This means that the time it takes to sort the array grows q_______ly with the input size.
Selection sort has a time complexity of **O(N^2)**. This means that the time it takes to sort the array grows **quadratically** with the input size.
27
Selection sort can be superior to Bubble sort in terms of performance when the cost of s_____ing elements is significantly higher than the cost of c______s, as it makes a maximum of N swaps for an array of size N.
Selection sort can be superior to Bubble sort in terms of performance when the cost of **swapping** elements is significantly higher than the cost of **comparisons**, as it makes a maximum of N swaps for an array of size N.
28
In bubble sort, swaps occur whenever adjacent elements are out of order, potentially leading to a relatively large number of swaps. On the other hand, s______ sort minimizes the number of swaps by performing only a single swap after finding the smallest element in each pass
In bubble sort, swaps occur whenever adjacent elements are out of order, potentially leading to a relatively large number of swaps. On the other hand, **selection sort** minimizes the number of swaps by performing only a single swap after finding the smallest element in each pass
29
Describes which algorithm:
We start with the second element (at index 1) and temporarily store it in the variable 'current', conceptually creating a gap.
insertion sort
30
When comparing Insertion Sort with Selection Sort and Bubble Sort in terms of worst-case time complexity, all three algorithms have the same O(____) time complexity.
When comparing Insertion Sort with Selection Sort and Bubble Sort in terms of worst-case time complexity, all three algorithms have the same **O(N^2)** time complexity.
31
the inner workings of which sorting algorithm does this snippet display:
```
while (j >= 0 && arr[j] > current) {
// Shift the element we're comparing to the right
arr[j + 1] = arr[j];
j--;
}
```
insertion sort
32
Insertion Sort excels when working with partially s____ed or nearly s_____ed arrays. In such scenarios, the algorithm benefits from significantly reducing the number of comparisons and shifts required, resulting in improved performance.
Insertion Sort excels when working with partially **sorted** or nearly **sorted** arrays. In such scenarios, the algorithm benefits from significantly reducing the number of comparisons and shifts required, resulting in improved performance.
33
While Insertion Sort, like Bubble Sort, involves a lot of swaps, it makes fewer c_______s overall. Therefore, in cases where c_________s are costly, Insertion Sort would be the preferred option.
While Insertion Sort, like Bubble Sort, involves a lot of swaps, it makes fewer **comparisons** overall. Therefore, in cases where **comparisons** are costly, Insertion Sort would be the preferred option.
34
Pointer-Based Mental Models offer an optimization strategy that can transform our naive algorithms from q_____ solutions O(N^2) to l_____ solutions O(N), all while preserving a constant space complexity O(1)
Pointer-Based Mental Models offer an optimization strategy that can transform our naive algorithms from **quadratic** solutions O(N^2) to **linear** solutions O(N), all while preserving a constant space complexity O(1)
35
The a_____-r______ pointer strategy is a widely-used approach for solving problems that **involve manipulating arrays in place**.
The **anchor-runner** pointer strategy is a widely-used approach for solving problems that involve manipulating arrays in place.
36
the anchor-runner pointer strategy provides an effective and efficient method for manipulating arrays in p____
the anchor-runner pointer strategy provides an effective and efficient method for manipulating arrays in **place**
37
the advantage of binary search becomes increasingly significant as the s___ of the array grows
the advantage of binary search becomes increasingly significant as the **size** of the array grows.
38
The time complexity of the binary search algorithm is O(____), which allows us to perform the search in a significantly faster time compared to linear search, especially for large arrays.
The time complexity of the binary search algorithm is **O(logN)**, which allows us to perform the search in a significantly faster time compared to linear search, especially for large arrays.
39
We'll need to use two binary searches to find where our negative numbers end from the b______-ing of the array and another binary search to find where our positive numbers begin from the e__ of our array.
We'll need to use two binary searches to find where our negative numbers end from the beginning of the array and another binary search to find where our positive numbers begin from the end of our array.
40
binary search problems depend on the array being s______-ed
binary search problems depend on the array being **sorted**
41
A s____ linked list is a data structure in which each node contains data and a reference to the next node in the sequence. This allows **traversal only in one direction**, from the head (first node) to the tail (last node), with the last node pointing to null.
A **singly linked list** is a data structure in which each node contains data and a reference to the next node in the sequence. This allows traversal only in one direction, from the head (first node) to the tail (last node), with the last node pointing to null.
42
a d____ linked list features nodes that contain data, a reference to the next node, and a reference to the previous node. This enables **traversal in both directions**, from head to tail and tail to head, with the first node's previous pointer and the last node's next pointer pointing to null.
a **doubly** linked list features nodes that contain data, a reference to the next node, and a reference to the previous node. This enables traversal in both directions, from head to tail and tail to head, with the first node's previous pointer and the last node's next pointer pointing to null.
43
a c____ linked list is similar to a singly linked list, but the last node points back to the first node, creating a continuous loop without any n____ references. This means t______ can start at any node and circularly proceed through the entire list.
a **circular** linked list is similar to a singly linked list, but the last node points back to the first node, creating a continuous loop without any **null** references. This means **traversal** can start at any node and circularly proceed through the entire list.
44
The Node class consists of two main components: the d___ we want to store in the node and a reference to the n___ node in the list.
The Node class consists of two main components: the **data** we want to store in the node and a reference to the **next** node in the list.
45
When it comes to deleting the final node of a linked list, the deletion itself requires only one step. We can accomplish this by modifying the link of the second-to-last node, making it n___
When it comes to deleting the final node of a linked list, the deletion itself requires only one step. We can accomplish this by modifying the link of the second-to-last node, making it **null**
46
When to use a Stack
R_______ Properties: If the problem involves reversing elements, such as in string reversal or undo operations in text editors.
B_______ing Symbols: Problems that require checking the balance of certain characters, like matching parenthesis, often benefit from a stack.
D____-First Search (DFS): Stacks can be used to perform a depth-first search through tree or graph data structures.
When to use a Stack
**Reversal** Properties: If the problem involves reversing elements, such as in string reversal or undo operations in text editors.
**Balancing** Symbols: Problems that require checking the balance of certain characters, like matching parenthesis, often benefit from a stack.
**Depth**-First Search (DFS): We'll explore DFS in upcoming lessons when discussing Binary Trees. For now, be aware that stacks can be used to perform a depth-first search through tree or graph data structures.
47
Note that if a problem requires a stack, another approach could be using r______, which uses a call stack to keep track of function calls
Note that if a problem requires a stack, another approach could be using **recursion**, which uses a call stack to keep track of function calls
48
When to use a Queue:
O____ Maintenance: When the problem requires maintaining elements in their original order, such as in task scheduling or managing print jobs, a queue is usually suitable.
B_____-First Search (BFS): As with DFS, we'll explore BFS in the upcoming lesson on Binary Trees. You'll learn what BFS is and how queues can help us implement it.
B____-ing or P_____ If the scenario requires a buffer of elements to be processed in the order they arrive, like in streaming data or load balancing, a queue offers the necessary structure.
When to use a Queue:
**Order** Maintenance: When the problem requires maintaining elements in their original order, such as in task scheduling or managing print jobs, a queue is usually suitable.
**Breadth**-First Search (BFS): As with DFS, we'll explore BFS in the upcoming lesson on Binary Trees. You'll learn what BFS is and how queues can help us implement it.
**Buffering** or **Pipeline** If the scenario requires a buffer of elements to be processed in the order they arrive, like in streaming data or load balancing, a queue offers the necessary structure.
49
The function call stack is implemented using the L___-__-___-__ (LIFO) principle
The function call stack is implemented using the **Last-In-First-Out (LIFO)** principle
50
For instance, if we want to introduce a c____ to optimize the Fibonacci function, we can use a helper function.
For instance, if we want to introduce a **cache** to optimize the Fibonacci function, we can use a helper function.
```
function fibonacci(num) {
return fibonacciHelper(num, {});
}
function fibonacciHelper(num, cache) {
// Define the base case and recursive case
}
```
51
When dealing with recursive algorithms, certain subproblems may be repeatedly solved with the same input, leading to duplicated efforts and increased computational overhead. Using a c____ in these problems is important because it helps avoid redundant calculations and improves the function's efficiency. This optimization method is called D____ P_____
When dealing with recursive algorithms, certain subproblems may be repeatedly solved with the same input, leading to duplicated efforts and increased computational overhead. Using a **cache** in these problems is important because it helps avoid redundant calculations and improves the function's efficiency. This optimization method is called **Dynamic Programming**
52
Due to this slicing operation, the time and space complexity of the solution become O(___). This is because, in the worst case, for each recursive call, we create a new substring that is nearly the same length as the original string
Due to this slicing operation, the time and space complexity of the solution become **O(N^2)**. This is because, in the worst case, for each recursive call, we create a new substring that is nearly the same length as the original string
53
The fundamental part of the QuickSort algorithm is p_______ing
The fundamental part of the QuickSort algorithm is **partitioning**
54
The fundamental part of the Q______ algorithm is partitioning
The fundamental part of the **QuickSort** algorithm is partitioning
55
using the first element as the pivot (in QuickSort) can lead to poor performance and selecting the m______ element improves efficiency.
using the first element as the pivot can lead to poor performance and how selecting the **middle** element improves efficiency.
56
By selecting a pivot (in QuickSort) that is more likely on average to be closer to the m_____ element, we reduce the chances of encountering arrays that are already sorted or nearly sorted.
By selecting a pivot that is more likely on average to be closer to the **median** element, we reduce the chances of encountering arrays that are already sorted or nearly sorted.
57
In Quicksort, the time complexity is influenced by two main factors: the p______ing step and the r_____ step.
In Quicksort, the time complexity is influenced by two main factors: the **partitioning** step and the **recursion** step.
58
the overall average-case time complexity of Quicksort is expressed as O(_____)
the overall average-case time complexity of Quicksort is expressed as **O(N log N)**
(O(N log N) time complexity represents the average-case scenario, which occurs when the input array is randomly ordered or has no specific patterns. In this case, Quicksort performs efficiently and sorts the array effectively.)
59
Remember, while DP can greatly optimize certain problems, it's not always the best solution. The trade-off is usually between t____ complexity and s____ complexity, as DP often requires additional memory to store intermediate results.
Remember, while DP can greatly optimize certain problems, it's not always the best solution. The trade-off is usually between **time** complexity and **space** complexity, as DP often requires additional memory to store intermediate results.
60
The process of DP works in three phases:
B____ Down
Solve and S____
R____ Solutions
The process of DP works in three phases:
**Break** Down
Solve and **Store**
**Reuse** Solutions
61
There are two main ways to approach a dynamic programming problem:
Top-Down (M______): The Recursive Approach
Bottom-Up (T______): The Iterative Approach
Top-Down (**Memoization**): The Recursive Approach
Bottom-Up (**Tabulation**): The Iterative Approach
62
when memoization is employed, the time complexity generally improves to O(_) if the problem has a linear number of states or O(__) if the problem states form a two-dimensional space. Both iterative and memoized recursive solutions share the same time complexity.
when memoization is employed, the time complexity generally improves to **O(N)** if the problem has a linear number of states or **O(N^2)** if the problem states form a two-dimensional space. Both iterative and memoized recursive solutions share the same time complexity.
63
Interview Tip: In job interviews, you often get problems similar to ones you have already solved, just ph____-ed differently.
Interview Tip: In job interviews, you often get problems similar to ones you have already solved, just **phrased** differently.
64
Usually, in DP problems, we use a h_____ or an array for memoization
Usually, in DP problems, we use a **hashmap** or an array for memoization
65
Remember these two important rules about caching:
Always check if the value is already in the c____ before performing any calculations. If it is, return the cached value.
If the value is not in the cache, calculate the value and then add it to the cache.
remember these two important rules about caching:
Always check if the value is already in the **cache** before performing any calculations. If it is, return the cached value.
If the value is not in the cache, calculate the value and then add it to the cache.
66
With memoization, we avoid repeated c_______s, and every subproblem is solved only o____, resulting in a time complexity of O(_).
With memoization, we avoid repeated **computations**, and every subproblem is solved only **once**, resulting in a time complexity of **O(N)**.
67
```
if (memo.has(n)) {
return memo.g__(n);
}
```
if (memo.has(n)) {
return memo.**get**(n);
}
68
A_____s are generally more performant than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.
**Arrays** are generally more performant than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.
69
Arrays are generally more p_______ than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.
Arrays are generally more **performant** than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.
70
The Map data structure also has a hashing o______, which refers to the extra time required to compute the hash value of a key and handle potential collisions.
The Map data structure also has a hashing **overhead**, which refers to the extra time required to compute the hash value of a key and handle potential collisions.
71
M___s (or similar hash-based structures) are more flexible than arrays
**Maps** (or similar hash-based structures) are more flexible than arrays
72
Maps (or similar hash-based structures) are more f_____ than arrays
Maps (or similar hash-based structures) are more **flexible** than arrays
73
In JavaScript, we can represent a binary tree using a Node class. Each Node object stores:
v__: The data or value associated with the node.
l__: A reference (pointer) to the node's left child (if any).
r__: A reference (pointer) to the node's right child (if any).
In JavaScript, we can represent a binary tree using a Node class. Each Node object stores:
**val**: The data or value associated with the node.
**left**: A reference (pointer) to the node's left child (if any).
**right**: A reference (pointer) to the node's right child (if any).
74
There are three different DFS traversal strategies, __order, __order, and ___order traversal.
There are three different DFS traversal strategies, **Pre**order, **In**order, and **Post**order traversal.
75
The search that uses 3 different traversal strategies (NLR, LNR, LRN) is the _ First-Search
The search that uses 3 different traversal strategies (NLR, LNR, LRN) is the **Depth First-Search**
76
NLR = __order
LNR = __order
LRN = __order
NLR = **pre**order
LNR = **in**order
LRN = **post**order
77
BFS uses a q_____ data structure to manage the order of node traversal.
BFS uses a **queue** data structure to manage the order of node traversal.
78
re: BSTs
The left subtree of a node contains only nodes with values l__ than the parent node's value, while the right subtree contains only nodes with values g____ than the parent node's value
The left subtree of a node contains only nodes with values **less** than the parent node's value, while the right subtree contains only nodes with values **greater** than the parent node's value
79
4 types of graphs:
un_____
d______
c_____
ac____
undirected
directed
cyclic
acyclic
80
An a______ list is a way to represent graph data structures where each vertex (or node) stores a list of vertices it is connected to. It's often implemented as a dictionary or a Map in JavaScript, where each key represents a vertex, and its value is an array of connected vertices.
An **adjacency** list is a way to represent graph data structures where each vertex (or node) stores a list of vertices it is connected to. It's often implemented as a dictionary or a Map in JavaScript, where each key represents a vertex, and its value is an array of connected vertices.
81
We can use a Map or an object to create our adjacency list in JavaScript. Just note that if we decide to use an object, the keys would have to be s_____s. Since we are working with integers, a M___ is a better choice.
We can use a Map or an object to create our adjacency list in JavaScript. Just note that if we decide to use an object, the keys would have to be **strings**. Since we are working with integers, a **Map** is a better choice.
82
With graphs, the most common DFS traversal is p___order traversal
With graphs, the most common DFS traversal is **preorder** traversal
83
An e____ list is a straightforward way to represent a graph using an array of arrays
An **edge** list is a straightforward way to represent a graph using an array of arrays
84
While an edge list is straightforward, it is often more convenient to work with an a______ list for various graph algorithms, as it makes it easier to traverse the graph, find neighbors of a node, and perform other graph operations efficiently.
While an edge list is straightforward, it is often more convenient to work with an **adjacency** list for various graph algorithms, as it makes it easier to traverse the graph, find neighbors of a node, and perform other graph operations efficiently.
85
Backtracking is particularly useful for problems where we need to find a__ possible s_____s or an o_____ solution among many possibilities.
Backtracking is particularly useful for problems where we need to find **all possible solutions** or an **optimal** solution among many possibilities.
86
B______ing is commonly applied to puzzles like Sudoku, problems like "N-Queens," or to generating all possible permutations or combinations of a set.
**Backtracking** is commonly applied to puzzles like Sudoku, problems like "N-Queens," or to generating all possible permutations or combinations of a set.
87
The d____-e__ condition, while often overlooked, is crucial for efficient backtracking. It helps us prune the search tree by identifying paths that can't lead to a valid solution early on.
The **dead-end** condition, while often overlooked, is crucial for efficient backtracking. It helps us prune the search tree by identifying paths that can't lead to a valid solution early on.
88
A h___-b___ed binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
A **height-balanced** binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
