/* Reverse Array
when reversing, you need to keep track of both the leftIndex and the rightIndex
*/
/* Merge 2 Sorted Arrays
in this case, you need to keep track of the 3 indeces as well as all the of the edge cases
array1, array2, sortedArray
make sure neither array gets exhausted (aka bool array1Exhausted = array1Index >= array1.Length )
/* Merge Meeting Times
sort all meetings by start times first
add the first meeting to the mergedMeetings List
compare every subsequent Meeting to the last meeting in mergedMeetings
/* Binary Trees
"perfect tree" means every node has two full nodes
the number of nodes on the last level is equal to the sum of nodes on all other levels MINUS 1
n = number of nodes
h = height of tree
n = 2^h => number of nodes at height h
log(n+1) = h
/* Graphs + Algorithms
Edge Lists
Edge Lists list all edges in a graph
ex. int[][] graph = new int[][] { new[] {0, 1}, new[] {1, 2}, new[] {1, 3}, new[] {2, 3} };
Adjacency List
A list where the INDEX represents the node and the value at that index is a list of the node's neighbors:
ex.
int[][] graph = new int[][]
{
new[] {1}, //index 0 (aka node 0) connects to node 1
new[] {0, 2, 3}, //index aka node 1 connects to 0, 2, and node 3
new[] {1, 3},
new[] {1, 2}
};
ANOTHER WAY to represent graphs is via Dictionaries
var graph = new Dictionary<int, int[]>
{0, new[] {1}},
{1, new[] {0, 2, 3}},
{2, new[] {1, 3}},
{3, new[] {1, 2}},
Adjacency Matrix
A matrix of 0's and 1's indicating (with a 1 or 0) if node x connects to node y
new[] {0, 1, 0, 0},
new[] {1, 0, 1, 1},
new[] {0, 1, 0, 1},
new[] {0, 1, 1, 0},
Questions we can answer with Graphs
Q. Is there a path between two nodes in this undirected graph?
A. Run DFS or BFS from one node and see if you reach the other one.
Q. What's the shortest path between two nodes in this undirected, unweighted graph?
A. Run BFS from one node and backtrack once you reach the second. Note: BFS always finds the shortest path, assuming the graph is undirected and unweighted. DFS does not always find the shortest path.
Q. Can this undirected graph be colored with two colors?
A. Run BFS, assigning colors as nodes are visited. Abort if we ever try to assign a node a color different from the one it was assigned earlier.
Q. Does this undirected graph have a cycle?
A. Run BFS, keeping track of the number of times we're visiting each node. If we ever visit a node twice, then we have a cycle.
using System;
public class Program
public static void Main()
}
