Graphs
In an adjacency list representation, how many linked lists are needed for a graph with N vertices and M edges?
N
This data structure stores key-value pairs and allows for fast lookups by key. (In C++)
What is a Unordered Map?
This type of binary tree property ensures that every node's left child is smaller, and the right child is larger.
What is a Binary Search Tree (BST)?
List two graph search algorithms.
Are you going to ace this final?
YES
What is the term for how many edges are going into a vertex?
What is in-degree?
The process of mapping a key to an index in a hash map is known as this.
What is hashing?
Which binary tree traversal technique could produce the following sequence: Current, LeftChild, RightChild
Pre-order traversal
Name a graph search algorithm uses a stack?
What is DFS?
How many quizzes has Peralta assigned?
Given a pair of vertices, I want to determine if there is an edge between them. Which graph representation would enable me to do this fastest?
Adjacency matrix
This term describes the situation where two different keys map to the same index in a hash map.
What is a collision?
Explain the steps for an In-Order Tree Traversal.
binary tree traversal method visits the left subtree first, then the right subtree, and finally the root.
What is the time complexity to perform a BFS?
What is O(V + E)
What does the tech stock acronym MAMAA stand for?
Meta, Amazon, Apple, Microsoft, Alphabet
Recursively:
Create a visited set.
Call the search recursive function on the first node.
Recursively call the search function on the neighbors if they haven't been visited, ensure that they are added to visited at the beginning of the call.
This technique is used to resolve collisions in a hash map by storing multiple values at the same index.
What is chaining?
What is the amortized and worst case time complexity of searching for a node in a BST with N nodes?
O(logN) and O(N)
What is the most optimal search to perform on a sorted list.
Binary search
What is the class average between all of my SI Students for this semester?
What is 83%?
Which algorithm can be used to compute the shortest path in a weighted graph?
Dijkstra's Algorithm
List three ways to handle collisions and a few of the steps involved in them.
What is Chaining, Linear Probing, Double Hashing, and Polynomial Probing?
This kind of binary search tree ensures that the tree is always balanced (List two of them)
Red-black trees, AVL trees
List all of the steps required to perform a BFS.
Queue, visited set
while q:
store the length
loop through this length at each interval visited the node in the q, add its neighbors to visited and the q if they aren't already visited.
How many SI sessions have I hosted ever?
What is 83?