DS&A Flashcards

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

this list type stores each node’s outgoing neighbors in its value array

A

An adjacency list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

L._. nodes do not have any children.

A

Leaf nodes do not have any children.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Potential choice or element that we can add to current partial solution

A

candidate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

the height of “p_____” binary trees grows logarithmically.

A

the height of “perfect” binary trees grows logarithmically.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Full Binary Trees: Every node has either_ or_ children

A

Full Binary Trees: Every node has either zero or two children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Tree structure representing state space

A

state space tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

the height of perfect binary trees grows l________y.

A

the height of perfect binary trees grows logarithmically.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Set of all possible states in problem / all possible configurations or situations that may be encountered

A

state space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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]];
    }
  }
A

selection sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Describes which algorithm:

We start with the second element (at index 1) and temporarily store it in the variable ‘current’, conceptually creating a gap.

A

insertion sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

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–;
}
~~~

A

insertion sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

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)

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

The a_____-r______ pointer strategy is a widely-used approach for solving problems that involve manipulating arrays in place.

A

The anchor-runner pointer strategy is a widely-used approach for solving problems that involve manipulating arrays in place.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

the anchor-runner pointer strategy provides an effective and efficient method for manipulating arrays in p____

A

the anchor-runner pointer strategy provides an effective and efficient method for manipulating arrays in place

37
Q

the advantage of binary search becomes increasingly significant as the s___ of the array grows

A

the advantage of binary search becomes increasingly significant as the size of the array grows.

38
Q

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.

A

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
Q

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.

A

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
Q

binary search problems depend on the array being s______-ed

A

binary search problems depend on the array being sorted

41
Q

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

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
Q

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

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
Q

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

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
Q

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.

A

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
Q

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___

A

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
Q

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.

A

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
Q

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

A

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
Q

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.

A

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
Q

The function call stack is implemented using the L___-__-___-__ (LIFO) principle

A

The function call stack is implemented using the Last-In-First-Out (LIFO) principle

50
Q

For instance, if we want to introduce a c____ to optimize the Fibonacci function, we can use a helper function.

A

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
Q

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_____

A

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
Q

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

A

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
Q

The fundamental part of the QuickSort algorithm is p_______ing

A

The fundamental part of the QuickSort algorithm is partitioning

54
Q

The fundamental part of the Q______ algorithm is partitioning

A

The fundamental part of the QuickSort algorithm is partitioning

55
Q

using the first element as the pivot (in QuickSort) can lead to poor performance and selecting the m______ element improves efficiency.

A

using the first element as the pivot can lead to poor performance and how selecting the middle element improves efficiency.

56
Q

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.

A

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
Q

In Quicksort, the time complexity is influenced by two main factors: the p______ing step and the r_____ step.

A

In Quicksort, the time complexity is influenced by two main factors: the partitioning step and the recursion step.

58
Q

the overall average-case time complexity of Quicksort is expressed as O(_____)

A

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
Q

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.

A

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
Q

The process of DP works in three phases:

B____ Down
Solve and S____
R____ Solutions

A

The process of DP works in three phases:

Break Down
Solve and Store
Reuse Solutions

61
Q

There are two main ways to approach a dynamic programming problem:

Top-Down (M______): The Recursive Approach

Bottom-Up (T______): The Iterative Approach

A

Top-Down (Memoization): The Recursive Approach

Bottom-Up (Tabulation): The Iterative Approach

62
Q

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.

A

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
Q

Interview Tip: In job interviews, you often get problems similar to ones you have already solved, just ph____-ed differently.

A

Interview Tip: In job interviews, you often get problems similar to ones you have already solved, just phrased differently.

64
Q

Usually, in DP problems, we use a h_____ or an array for memoization

A

Usually, in DP problems, we use a hashmap or an array for memoization

65
Q

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.

A

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
Q

With memoization, we avoid repeated c_______s, and every subproblem is solved only o____, resulting in a time complexity of O(_).

A

With memoization, we avoid repeated computations, and every subproblem is solved only once, resulting in a time complexity of O(N).

67
Q
if (memo.has(n)) {
      return memo.g\_\_(n);
    }
A

if (memo.has(n)) {
return memo.get(n);
}

68
Q

A_____s are generally more performant than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.

A

Arrays are generally more performant than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.

69
Q

Arrays are generally more p_______ than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.

A

Arrays are generally more performant than hashes (e.g., Map) because they provide better memory locality and avoid hashing overhead.

70
Q

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.

A

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
Q

M___s (or similar hash-based structures) are more flexible than arrays

A

Maps (or similar hash-based structures) are more flexible than arrays

72
Q

Maps (or similar hash-based structures) are more f_____ than arrays

A

Maps (or similar hash-based structures) are more flexible than arrays

73
Q

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).

A

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
Q

There are three different DFS traversal strategies, __order, __order, and ___order traversal.

A

There are three different DFS traversal strategies, Preorder, Inorder, and Postorder traversal.

75
Q

The search that uses 3 different traversal strategies (NLR, LNR, LRN) is the _ First-Search

A

The search that uses 3 different traversal strategies (NLR, LNR, LRN) is the Depth First-Search

76
Q

NLR = __order
LNR = __order
LRN = __order

A

NLR = preorder
LNR = inorder
LRN = postorder

77
Q

BFS uses a q_____ data structure to manage the order of node traversal.

A

BFS uses a queue data structure to manage the order of node traversal.

78
Q

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

A

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
Q

4 types of graphs:

un_____
d______
c_____
ac____

A

undirected
directed
cyclic
acyclic

80
Q

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.

A

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
Q

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.

A

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
Q

With graphs, the most common DFS traversal is p___order traversal

A

With graphs, the most common DFS traversal is preorder traversal

83
Q

An e____ list is a straightforward way to represent a graph using an array of arrays

A

An edge list is a straightforward way to represent a graph using an array of arrays

84
Q

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.

A

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
Q

Backtracking is particularly useful for problems where we need to find a__ possible s_____s or an o_____ solution among many possibilities.

A

Backtracking is particularly useful for problems where we need to find all possible solutions or an optimal solution among many possibilities.

86
Q

B______ing is commonly applied to puzzles like Sudoku, problems like “N-Queens,” or to generating all possible permutations or combinations of a set.

A

Backtracking is commonly applied to puzzles like Sudoku, problems like “N-Queens,” or to generating all possible permutations or combinations of a set.

87
Q

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.

A

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
Q

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

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.