Graphs

Question 1

Legal Graph Coloring

Answer 1

No adjacent nodes can have the same color

Question 2

Adjacency List

Answer 2

A 2D array where the first index represents the node and the second index is a list of that node’s neighbors. (Can use a hashmap if the node is an object rather than an int.)

Question 3

Adjacency Matrix

Answer 3

A matrix of 1’s and 0’s indicating if node x connects to node y.

Question 4

How do you determine if an undirected graph be colored with two colors?

Answer 4

Run BFS assigning colors as you visit nodes. Abort if you ever try to assign a different color to the same node.

Question 5

Does this undirected graph have a cycle?

Answer 5

Run BFS keeping track of the number of times we visit each node. If you ever visit a node twice, you’ve found a cycle.

Question 6

Dijkstra’s Algorithm

Answer 6

Finds the shortest path from a node to all other nodes in a *weighted* graph.

Question 7

Degree

Answer 7

Number of edges connected to the node

Question 8

Binary Search

Answer 8

Find an item in a SORTED array in log n time.

Question 9

invert a binary tree

Answer 9

flip each row
imagine flipping the tree around a center axis
O(n) because you visit each node once
The space complexity is O(height) because you call the function once for each level of the tree. That means the worst case space complexity is O(n). That would be a fully balanced tree or a tree with only one child node for each node.