Graph: n nodes, m edges
Representation
Adjacency Matrix: O(n^2) space, not efficient for sparse graph
Adjacency List: O(n + m) space, efficient for sparse graph
Traversal
BFS: Runtime: O(n + m)
application: unweighted graph shortest path computation, connected components of undirected graph detection
1 import java.util.ArrayList;
2 import java.util.HashSet;
3 import java.util.LinkedList;
4 import java.util.Queue;
5 import java.util.List;
6
7 class UndirectedGraphNode {
8 int label;
9 int shortestPathToSrc;
10 ArrayList<UndirectedGraphNode> neighbors;
11 UndirectedGraphNode(int x) {
12 label = x;
13 neighbors = new ArrayList<UndirectedGraphNode>();
14 }
15 }
16 public class Graph {
17 //breath first search traversal of the entire graph
18 //O(n + m) runtime, O(n) space
19 public static void bfsUnweighted(UndirectedGraphNode node) {
20 HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
21 Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
22 queue.add(node);
23 visited.add(node);
24 while(!queue.isEmpty()) {
25 UndirectedGraphNode currNode = queue.poll();
26 for(UndirectedGraphNode neighbor : currNode.neighbors) {
27 if(!visited.contains(neighbor)) {
28 queue.add(neighbor);
29 visited.add(neighbor);
30 }
31 }
32 }
33 }
34 //single source multiple destinations using bfs
35 //O(n + m) runtime, O(n) space
36 public static void shortestPathUnweighted(UndirectedGraphNode source) {
37 //Assume shortestPathtoSrc is set to Integer.MAX_VALUE in initialization
38 source.shortestPathToSrc = 0;
39 HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
40 Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
41 queue.add(source);
42 visited.add(source);
43 while(!queue.isEmpty()) {
44 UndirectedGraphNode currNode = queue.poll();
45 for(UndirectedGraphNode neighbor : currNode.neighbors) {
46 if(!visited.contains(neighbor)) {
47 neighbor.shortestPathToSrc = currNode.shortestPathToSrc + 1;
48 queue.add(neighbor);
49 visited.add(neighbor);
50 }
51 }
52 }
53 }
54 private static void bfsHelper(UndirectedGraphNode node,
55 HashSet<UndirectedGraphNode> visited,
56 List<Integer> component) {
57 Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
58 queue.add(node);
59 visited.add(node);
60 component.add(node.label);
61 while(!queue.isEmpty()) {
62 UndirectedGraphNode currNode = queue.poll();
63 for(UndirectedGraphNode neighbor : currNode.neighbors) {
64 if(!visited.contains(neighbor)) {
65 queue.add(neighbor);
66 visited.add(neighbor);
67 component.add(neighbor.label);
68 }
69 }
70 }
71 }
72 //connected components on undirected graph via bfs
73 //O(n + m) runtime
74 public static List<List<Integer>> undirectedConnect(List<UndirectedGraphNode> nodes) {
75 HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
76 List<List<Integer>> components = new ArrayList<List<Integer>>();
77 for(UndirectedGraphNode node : nodes) {
78 if(!visited.contains(node)) {
79 List<Integer> component = new ArrayList<Integer>();
80 bfsHelper(node, visited, component);
81 components.add(component);
82 }
83 }
84 return components;
85 }
86 }
DFS: Runtime: O(n + m)
application: topological sorting of directed acyclic graph; strongly connected components of directed graphs
1 private static int topoOrder;
2
3 private static void dfsHelper(UndirectedGraphNode node, HashSet<UndirectedGraphNode> explored) {
4 explored.add(node);
5 for(UndirectedGraphNode neighbor : node.neighbors) {
6 if(!explored.contains(neighbor)) {
7 dfsHelper(neighbor, explored);
8 }
9 }
10 }
11 public static void dfs(UndirectedGraphNode node) {
12 dfsHelper(node, new HashSet<UndirectedGraphNode>());
13 }
14
15 private static void topoSortDFS(DirectedGraphNode node, HashSet<DirectedGraphNode> explored) {
16 explored.add(node);
17 for(DirectedGraphNode neighbor: node.neighbors) {
18 if(!explored.contains(neighbor)) {
19 topoSortDFS(neighbor, explored);
20 }
21 }
22 node.topoOrder = topoOrder;
23 topoOrder -= 1;
24 }
25 public static void topoSort(ArrayList<DirectedGraphNode> graph) {
26 topoOrder = graph.size();
27 HashSet<DirectedGraphNode> explored = new HashSet<DirectedGraphNode>();
28 for(DirectedGraphNode node : graph) {
29 if(!explored.contains(node)) {
30 topoSortDFS(node, explored);
31 }
32 }
33 }
Topologoical Sorting (Graph has no directed cycle: O(n + m) runtime to compute topological ordering) && Cycle Detection
Can be done using DFS or BFS.
Practice problems:
1. Directed Graph: convert to topological sorting problem
a. DFS: Using 3 sets: white, gray and black. white set contains vertices that have not been explored; gray set contains vertices that are being explored; black set contains vertices that have already been
completely explored. O(n + m) runtime, O(n) space
b. BFS: Use the number of incoming edges as a criterion to determine which vertices should be put in topological order. If there is any cycles, then these vertices in cycles would never be explored. Keeping a traversed vertex count tells us if there is any cycle or not. O(n + m) runtime, O(n) space
2. Undirected Graph:
a. DFS: O(n + m) runtime, O(n) space if not considering recursive call stack memory usage.
Algorithm: 1. create a hash set that tracks which vertices have been visited; 2. for each vertex, if it has not been visited, do a dfs starting from this vertex. At each dfs call, pass the source node so that following dfs calls do not go back to already visited source vertices. For a current vertex, if it finds one of its neighboring vertex is already visited and this neighbor is not the source vertex, there is a cycle.
1 private static boolean undirectedGraphDfsHelper(UndirectedGraphNode currNode, UndirectedGraphNode srcNode,
2 HashSet<UndirectedGraphNode> explored) {
3 explored.add(currNode);
4 for(UndirectedGraphNode neighbor : currNode.neighbors) {
5 if(neighbor == srcNode) {
6 continue;
7 }
8 if(explored.contains(neighbor)) {
9 return true;
10 }
11 if(undirectedGraphDfsHelper(neighbor, currNode, explored)) {
12 return true;
13 }
14 }
15 return false;
16 }
17 public static boolean detectCycleInUndirectedGraphDfs(ArrayList<UndirectedGraphNode> graph) {
18 HashSet<UndirectedGraphNode> explored = new HashSet<UndirectedGraphNode>();
19 for(UndirectedGraphNode node: graph) {
20 if(explored.contains(node)) {
21 continue;
22 }
23 if(undirectedGraphDfsHelper(node, null, explored)) {
24 return true;
25 }
26 }
27 return false;
28 }
b. Union Find: O(n + m) runtime, O(n) space
Algorithm:
1. create a map from vertex label to union find index for convenience purpose.
2. create an union find data structure for all vertices, with each's parent initialized to be itself.
3. iterate through all edges: check if the vertices on both end are part of the same union. If they are, it means there is another path between these two vertices. The current edge forms a cycle. If not, connect the two unions that these two vertices belong to.
1 public static boolean detectCycleInUndirectedGraphUf(ArrayList<UndirectedGraphNode> graph, ArrayList<Edge> edges) {
2 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
3 for(int i = 0; i < graph.size(); i++) {
4 map.put(graph.get(i).label, i);
5 }
6 UnionFind uf = new UnionFind(graph.size());
7 for(Edge edge : edges) {
8 UndirectedGraphNode node1 = edge.node1;
9 UndirectedGraphNode node2 = edge.node2;
10 int id1 = map.get(node1.label);
11 int id2 = map.get(node2.label);
12 if(uf.find(id1) == uf.find(id2)) {
13 return true;
14 }
15 else {
16 uf.connect(id1, id2);
17 }
18 }
19 return false;
20 }
c. BFS needs some modification to make it work. If a neighbor vertex is not the current vertex's source and this neighbor has already been explored, it means there is another shorter bfs route to this neighbor, thus the edge between the current vertex and this neighbor makes up one edge of a cycle.
O(n + m) runtime, O(n) space
1 private static boolean undirectedGraphBfsHelper(UndirectedGraphNode node,
2 HashSet<UndirectedGraphNode> explored) {
3 Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
4 Queue<UndirectedGraphNode> source = new LinkedList<UndirectedGraphNode>();
5 queue.add(node);
6 source.add(null);
7 explored.add(node);
8 while(!queue.isEmpty()) {
9 UndirectedGraphNode curr = queue.poll();
10 UndirectedGraphNode src = source.poll();
11 for(UndirectedGraphNode neighbor : curr.neighbors) {
12 if(neighbor == src) {
13 continue;
14 }
15 if(explored.contains(neighbor)) {
16 return true;
17 }
18 queue.add(neighbor);
19 source.add(curr);
20 explored.add(neighbor);
21 }
22 }
23 return false;
24 }
25 public static boolean detectCycleInUndirectedGraphBfs(ArrayList<UndirectedGraphNode> graph) {
26 HashSet<UndirectedGraphNode> explored = new HashSet<UndirectedGraphNode>();
27 for(UndirectedGraphNode node : graph) {
28 if(explored.contains(node)) {
29 continue;
30 }
31 if(undirectedGraphBfsHelper(node, explored)) {
32 return true;
33 }
34 }
35 return false;
36 }
Shortest Paths Algorithms
Unweighted graph: BFS to get the fewest number of edges;
Weighted graph:
Single source shortest path:
Dijkstra's shortest path algorithm: works on both directed and undirected graph as long as all edge weights are non-negative. Greedy algorithm, similar with Prim's MST algorithm.
To get the optimized O(m log n) runtime solution, we need a modified heap data structure that supports O(logn) extractMin, O(logn) decrease key, O(1) node look up.
package com.interview.graph;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graph<T> {
private List<Edge<T>> allEdges;
private Map<Integer, Vertex<T>> allVertex;
private boolean isDirected;
public Graph(boolean isDirected) {
this.allEdges = new ArrayList<Edge<T>>();
this.allVertex = new HashMap<Integer, Vertex<T>>();
this.isDirected = isDirected;
}
public void addEdge(int id1, int id2) {
addEdge(id1, id2, 0);
}
public void addVertex(Vertex<T> vertex) {
if(allVertex.containsKey(vertex.getId())) {
return;
}
allVertex.put(vertex.getId(), vertex);
}
public Vertex<T> getVertex(int id) {
return null;
}
public void addEdge(int id1, int id2, int weight) {
}
public List<Edge<T>> getAllEdges() {
return null;
}
public Collection<Vertex<T>> getAllVertex() {
return allVertex.values();
}
public void setDataForVertex(int id, T data) {
}
public String toString() {
return null;
}
}
class Vertex<T> {
int id;
private T data;
private List<Edge<T>> edges = new ArrayList<>();
private List<Vertex<T>> adjacentVertex = new ArrayList<>();
Vertex(int id) {
this.id = id;
}
public int getId() {
return this.id;
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return this.data;
}
public void addAdjacentVertex(Edge<T> e, Vertex<T> v) {
edges.add(e);
adjacentVertex.add(v);
}
public String toString() {
return String.valueOf(id);
}
public List<Edge<T>> getEdges() {
return edges;
}
public int getDegree() {
return edges.size();
}
public int hashCode() {
int hash = 1;
hash = hash * 31 + id;
return hash;
}
public boolean equals(Object obj) {
//reference equality
if(this == obj) {
return true;
}
if(obj == null) {
return false;
}
//if(getClass() != obj.getClass())
if(!(obj instanceof Vertex<?>)) {
return false;
}
Vertex<T> other = (Vertex<T>) obj;
if(id != other.id) {
return false;
}
return true;
}
}
class Edge<T> {
private boolean isDirected = false;
private Vertex<T> vertex1;
private Vertex<T> vertex2;
private int weight;
Edge(Vertex<T> v1, Vertex<T> v2) {
vertex1 = v1;
vertex2 = v2;
}
Edge(Vertex<T> v1, Vertex<T> v2, boolean directed, int weight) {
this(v1, v2);
this.isDirected = directed;
this.weight = weight;
}
Edge(Vertex<T> v1, Vertex<T> v2, boolean directed) {
this(v1, v2);
this.isDirected = directed;
}
Vertex<T> getVertex1() {
return vertex1;
}
Vertex<T> getVertex2() {
return vertex2;
}
int getWeight() {
return weight;
}
boolean isDirected() {
return isDirected;
}
public int hashCode() {
int hash = 1;
hash = hash * 31 + ((vertex1 == null) ? 0 : vertex1.hashCode());
hash = hash * 31 + ((vertex2 == null) ? 0 : vertex2.hashCode());
return hash;
}
public boolean equals(Object obj) {
if(this == obj) {
return true;
}
if(obj == null) {
return false;
}
if(getClass() != obj.getClass()) {
return false;
}
Edge<T> other = (Edge<T>) obj;
if(!vertex1.equals(other.vertex1) || !vertex2.equals(other.vertex2)) {
return false;
}
return true;
}
public String toString() {
return "Edge [isDirected = " + isDirected + ", vertex1 = " + vertex1 + ", vertex2 = " + vertex2
+ ", weight = " + weight + "]";
}
}
package com.interview.graph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/*
* poll(): O(logn)
* add(): O(logn)
* containsData: O(1)
* decreaseDataWeight: O(logn)
* getDataWeight: O(1)
*/
public class BinaryMinHeap<T> {
private List<Node> allNodes = new ArrayList<>();
private Map<T, Integer> nodePosition = new HashMap<>();
class Node {
int weight;
T data;
}
public boolean containsData(T data) {
return nodePosition.containsKey(data);
}
public void add(T data, int weight) {
Node node = new Node();
node.data = data;
node.weight = weight;
allNodes.add(node);
//percolate up
int currentIdx = allNodes.size() - 1;
while(currentIdx > 0 && weight < allNodes.get((currentIdx - 1) / 2).weight) {
Node temp = allNodes.get((currentIdx - 1) / 2);
allNodes.set(currentIdx, temp);
nodePosition.put(temp.data, currentIdx);
currentIdx = (currentIdx - 1) / 2;
}
allNodes.set(currentIdx, node);
nodePosition.put(node.data, currentIdx);
}
public T peek() {
return allNodes.get(0).data;
}
public Node pollMinNode() {
Node min = allNodes.get(0);
nodePosition.remove(min.data);
//swap the min node with the last node
Node lastNode = allNodes.get(allNodes.size() - 1);
allNodes.set(0, lastNode);
allNodes.remove(allNodes.size() - 1);
//percolate down
int currIdx = 0, minIdx;
int leftChildIdx, rightChildIdx;
while(true) {
minIdx = currIdx;
leftChildIdx = 2 * currIdx + 1;
rightChildIdx = 2 * currIdx + 2;
if(leftChildIdx >= allNodes.size()) {
break;
}
else if(allNodes.get(leftChildIdx).weight < allNodes.get(currIdx).weight) {
minIdx = leftChildIdx;
}
if(rightChildIdx < allNodes.size() && allNodes.get(rightChildIdx).weight < allNodes.get(minIdx).weight) {
minIdx = rightChildIdx;
}
if(minIdx != currIdx) {
Node currNode = allNodes.get(currIdx);
Node minNode = allNodes.get(minIdx);
allNodes.set(currIdx, minNode);
allNodes.set(minIdx, currNode);
nodePosition.put(minNode.data, currIdx);
currIdx = minIdx;
}
else {
break;
}
}
return min;
}
public T poll() {
return pollMinNode().data;
}
public boolean isEmpty() {
return allNodes.size() == 0;
}
public void decreaseDataWeight(T data, int newWeight) {
int currentIdx = nodePosition.get(data);
Node changedNode = allNodes.get(currentIdx);
changedNode.weight = newWeight;
//percolate up
while(currentIdx > 0 && newWeight < allNodes.get((currentIdx - 1) / 2).weight) {
Node temp = allNodes.get((currentIdx - 1) / 2);
allNodes.set(currentIdx, temp);
nodePosition.put(temp.data, currentIdx);
currentIdx = (currentIdx - 1) / 2;
}
allNodes.set(currentIdx, changedNode);
nodePosition.put(changedNode.data, currentIdx);
}
public int getDataWeight(T data) {
return nodePosition.get(data);
}
}
package com.interview.graph;
import java.util.HashMap;
import java.util.Map;
public class DijkstraShortestPath {
public Map<Vertex<Integer>, Integer> shortestPath(Graph<Integer> graph, Vertex<Integer> sourceVertex) {
//min heap that supports O(1) look up
BinaryMinHeap<Vertex<Integer>> minHeap = new BinaryMinHeap<>();
//stores shortest distance from source to every vertex
Map<Vertex<Integer>, Integer> distance = new HashMap<>();
Map<Vertex<Integer>, Vertex<Integer>> parent = new HashMap<>();
for(Vertex<Integer> vertex : graph.getAllVertex()) {
minHeap.add(vertex, Integer.MAX_VALUE);
}
minHeap.decreaseDataWeight(sourceVertex, 0);
distance.put(sourceVertex, 0);
parent.put(sourceVertex, null);
while(!minHeap.isEmpty()) {
BinaryMinHeap<Vertex<Integer>>.Node heapNode = minHeap.pollMinNode();
Vertex<Integer> currVertex = heapNode.data;
distance.put(currVertex, heapNode.weight);
for(Edge<Integer> e : currVertex.getEdges()) {
Vertex<Integer> neighbor = getVertexForEdge(currVertex, e);
if(!minHeap.containsData(neighbor)) {
continue;
}
int newDistance = distance.get(currVertex) + e.getWeight();
if(newDistance < minHeap.getDataWeight(neighbor)) {
minHeap.decreaseDataWeight(neighbor, newDistance);
parent.put(neighbor, currVertex);
}
}
}
return distance;
}
private Vertex<Integer> getVertexForEdge(Vertex<Integer> v, Edge<Integer> e) {
return e.getVertex1().equals(v) ? e.getVertex2() : e.getVertex1();
}
}
Bellman-Ford shortest path algorithm: O(n * m) runtime, O(n) space, works with negative edge weight as long as there is no negative cycle. Similar with Dynamic Programming Principle.
1 package com.interview.graph;
2 import java.util.HashMap;
3 import java.util.Map;
4
5 public class BellmanFord {
6 private static final int INF = 10000000;
7 public Map<Vertex<Integer>, Integer> BellmanFordShortestPath(Graph<Integer> graph, Vertex<Integer> sourceVertex) {
8 Map<Vertex<Integer>, Integer> distance = new HashMap<>();
9 Map<Vertex<Integer>, Vertex<Integer>> parent = new HashMap<>();
10
11 for(Vertex<Integer> v : graph.getAllVertex()) {
12 distance.put(v, INF);
13 parent.put(v, null);
14 }
15 distance.put(sourceVertex, 0);
16 int n = graph.getAllVertex().size();
17 boolean isUpdated = false;
18 for(int i = 0; i < n - 1; i++) {
19 for(Edge<Integer> e : graph.getAllEdges()) {
20 Vertex<Integer> u = e.getVertex1();
21 Vertex<Integer> v = e.getVertex2();
22 if(distance.get(u) + e.getWeight() < distance.get(v)) {
23 distance.put(v, distance.get(u) + e.getWeight());
24 parent.put(v, u);
25 isUpdated = true;
26 }
27 }
28 //terminate early if there is no path updates between two iterations
29 if(!isUpdated) {
30 return distance;
31 }
32 }
33
34 //do one more iteration for possible negative cycle detection
35 for(Edge<Integer> e : graph.getAllEdges()) {
36 Vertex<Integer> u = e.getVertex1();
37 Vertex<Integer> v = e.getVertex2();
38 if(distance.get(u) + e.getWeight() < distance.get(v)) {
39 return null;
40 }
41 }
42 return distance;
43 }
44 }
Prim Minimum Spanning Tree(one solution is to use union find)
Pratice problem: Minimum Spanning Tree
More Graph practice problems
Connected Component in Undirected Graph
Find the Weak Connected Component in the Directed Graph
Union Find(Disjoint Sets)
Operations:
makeSet() or UnionFind(): O(1) runtime
findSet() or find(): O(1) runtime on average
union() or connect(): O(1) runtime
Tree Implementation using union rank and path compression
1 import java.util.HashMap;
2 import java.util.Map;
3
4 public class UnionFind {
5 private Map<Integer, Node> map = new HashMap<Integer, Node>();
6
7 class Node {
8 int data;
9 int rank;
10 Node parent;
11 }
12 public UnionFind(int data) {
13 Node node = new Node();
14 node.data = data;
15 node.rank = 0;
16 node.parent = node;
17 map.put(data, node);
18 }
19 //Combines two sets together to one by rank
20 public void union(int data1, int data2) {
21 Node node1 = map.get(data1);
22 Node node2 = map.get(data2);
23
24 Node parent1 = find(node1);
25 Node parent2 = find(node2);
26
27 //if they are part of the the same set, do nothing
28 if(parent1.data == parent2.data) {
29 return;
30 }
31 //else whoever's rank is higher becomes parent of the other set
32 if(parent1.rank >= parent2.rank) {
33 //increment rank only if both sets have the same rank
34 parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1 : parent1.rank;
35 parent2.parent = parent1;
36 }
37 else {
38 parent1.parent = parent2;
39 }
40 }
41 //Find the representative of this set
42 public int find(int data) {
43 return find(map.get(data)).data;
44 }
45 //Find the representative recursively and does path compression as well
46 private Node find(Node node) {
47 Node parent = node.parent;
48 if(parent == node) {
49 return parent;
50 }
51 node.parent = find(node.parent);
52 return node.parent;
53 }
54 }
Simplified Array Implementation using path compression
1 public class UnionFind {
2 private int[] parent = null;
3 private int unionCount = 0;
4
5 public UnionFind(int n){
6 unionCount = 0;
7 parent = new int[n];
8 for(int i = 0; i < n; i++){
9 parent[i] = i;
10 }
11 }
12
13 public int find(int x){
14 if(parent[x] == x){
15 return x;
16 }
17 return parent[x] = find(parent[x]);
18 }
19
20 public void connect(int a, int b){
21 int root_a = find(a);
22 int root_b = find(b);
23 if(root_a != root_b){
24 parent[root_a] = root_b;
25 unionCount--;
26 }
27 }
28
29 public int getTotalUnionNum(){
30 return unionCount;
31 }
32 }
Heap(PriorityQueue)
Practice Problems
Heapify
HeapSort
High Five
Top K Largest Numbers
Top K Largest Numbers II
K Closest Points
K Closest Numbers in Sorted Array
Kth Largest Element
Kth Largest Element II
Merge K Sorted Lists
Merge K Sorted Arrays
Top K Frequent Words
Ugly Number II
Longest Consecutive Sequence
Trie
Trie vs Hash
Practice Problems
Implement Trie
package com.interview.trie;
import java.util.HashMap;
class TrieNode {
char c;
HashMap<Character, TrieNode> children = null;
boolean endOfWord;
TrieNode() {
children = new HashMap<Character, TrieNode>();
}
TrieNode(char c) {
children = new HashMap<Character, TrieNode>();
this.c = c;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
//insert a word into trie
public void insert(String word) {
TrieNode curr = root;
HashMap<Character, TrieNode> currChildren = curr.children;
char[] wordArray = word.toCharArray();
for(int i = 0; i < wordArray.length; i++) {
char currChar = wordArray[i];
if(currChildren.containsKey(currChar)) {
curr = currChildren.get(currChar);
}
else {
TrieNode newNode = new TrieNode(currChar);
currChildren.put(currChar, newNode);
curr = newNode;
}
currChildren = curr.children;
if(i == wordArray.length - 1) {
curr.endOfWord = true;
}
}
}
//search if a word is in trie
public boolean search(String word) {
TrieNode lastCharNode = searchLastWordNode(word);
return lastCharNode != null && lastCharNode.endOfWord == true;
}
//check if there is any word in trie that starts with a given prefix
public boolean startsWith(String prefix) {
TrieNode lastCharNode = searchLastWordNode(prefix);
return lastCharNode != null;
}
//return the trie node corresponding to the last character of given string s
//return null if no match
private TrieNode searchLastWordNode(String s) {
TrieNode curr = root;
HashMap<Character, TrieNode> currChildren = root.children;
char[] chars = s.toCharArray();
for(int i = 0; i < chars.length; i++) {
char currChar = chars[i];
if(currChildren.containsKey(currChar)) {
curr = currChildren.get(currChar);
currChildren = curr.children;
}
else {
return null;
}
}
return curr;
}
}
Tree
Binary Tree preorder, inorder and postorder traversal, recursion and iteration
1 package com.interview.tree;
2
3 import java.util.Stack;
4
5 class BinaryTreeNode<T> {
6 T data;
7 BinaryTreeNode<T> left;
8 BinaryTreeNode<T> right;
9 BinaryTreeNode(T data) {
10 this.data = data;
11 left = null;
12 right = null;
13 }
14 }
15 public class BinaryTree<T> {
16 public void preOrderRecursion(BinaryTreeNode<T> root) {
17 if(root == null) {
18 return;
19 }
20 visitNode(root);
21 preOrderRecursion(root.left);
22 preOrderRecursion(root.right);
23 }
24 public void preOrderIteration(BinaryTreeNode<T> root) {
25 if(root == null) {
26 return;
27 }
28 Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
29 BinaryTreeNode<T> currNode = root;
30
31 while(currNode != null || !stack.empty()) {
32 if(currNode != null) {
33 visitNode(currNode);
34 stack.push(currNode);
35 currNode = currNode.left;
36 }
37 else {
38 currNode = stack.pop();
39 currNode = currNode.right;
40 }
41 }
42 }
43 public void inOrderRecursion(BinaryTreeNode<T> root) {
44 if(root == null) {
45 return;
46 }
47 inOrderRecursion(root.left);
48 visitNode(root);
49 inOrderRecursion(root.right);
50 }
51 public void inOrderIteration(BinaryTreeNode<T> root) {
52 if(root == null) {
53 return;
54 }
55 Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
56 BinaryTreeNode<T> currNode = root;
57
58 while(currNode != null || !stack.empty()) {
59 if(currNode != null) {
60 stack.push(currNode);
61 currNode = currNode.left;
62 }
63 else {
64 currNode = stack.pop();
65 visitNode(currNode);
66 currNode = currNode.right;
67 }
68 }
69 }
70 public void postOrderRecursion(BinaryTreeNode<T> root) {
71 if(root == null) {
72 return;
73 }
74 postOrderRecursion(root.left);
75 postOrderRecursion(root.right);
76 visitNode(root);
77 }
78 public void postOrderIteration(BinaryTreeNode<T> root) {
79 if(root == null) {
80 return;
81 }
82 Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
83 BinaryTreeNode<T> currNode = root;
84 BinaryTreeNode<T> prevNode = null;
85 BinaryTreeNode<T> topNode = null;
86
87 while(currNode != null || !stack.empty()) {
88 if(currNode != null) {
89 stack.push(currNode);
90 currNode = currNode.left;
91 }
92 else {
93 topNode = stack.peek();
94 //first time traversing back to parent node
95 //parent node has a non-null right child node and the previously visited node is not
96 //this right child node. This is the first time currnet parent is visited, time to
97 //visit its right child node
98 if(topNode.right != null && prevNode != topNode.right) {
99 currNode = topNode.right;
100 }
101 //either the current parent node has no right child node or the previously visited node
102 //is the non-null right child node
103 //this is the second time current parent node is visited, time to visit this parent node
104 else {
105 visitNode(topNode);
106 prevNode = topNode;
107 stack.pop();
108 }
109 }
110 }
111 }
112 private void visitNode(BinaryTreeNode<T> node) {
113
114 }
115 }
Binary Search Tree Implementation
package com.interview.tree;
public class BinarySearchTree {
public void insert(BinaryTreeNode<Integer> root, int data) {
BinaryTreeNode<Integer> curr = root;
while(curr.data != data) {
if(curr.data > data) {
if(curr.left == null) {
curr.left = new BinaryTreeNode<Integer>(data);
return;
}
curr = curr.left;
}
else {
if(curr.right == null) {
curr.right = new BinaryTreeNode<Integer>(data);
return;
}
curr = curr.right;
}
}
}
public boolean search(BinaryTreeNode<Integer> root, int data) {
if(data < root.data) {
return search(root.left, data);
}
else if(data > root.data) {
return search(root.right, data);
}
return true;
}
public void remove(BinaryTreeNode<Integer> root, int data) {
}
}
Stack && Queue
Hash Table
Array && Linked List && Two Pointers && Sorting
Merge sort, quick sort and heap sort implementation
Two Pointers practice problems, two sums, 3 sums
1 package com.interview.sort;
2
3 import java.util.Random;
4
5 public class Sort {
6 //O(nlogn) runtime, O(n) space
7 public static void mergeSort(int[] a) {
8 if(a == null || a.length <= 1) {
9 return;
10 }
11 int[] aux = new int[a.length];
12 mergeSortHelper(a, aux, 0, a.length - 1);
13 }
14 private static void mergeSortHelper(int[] a, int[] aux, int start, int end) {
15 if(start >= end) {
16 return;
17 }
18 int mid = start + (end - start) / 2;
19 mergeSortHelper(a, aux, start, mid);
20 mergeSortHelper(a, aux, mid + 1, end);
21 merge(a, aux, start, end);
22 }
23 private static void merge(int[] a, int[] aux, int start, int end) {
24 for(int k = start; k <= end; k++) {
25 aux[k] = a[k];
26 }
27 int i = start, mid = start + (end - start) / 2, j = mid + 1;
28 for(int k = start; k <= end; k++) {
29 if(i > mid) {
30 a[k] = aux[j++];
31 }
32 else if(j > end) {
33 a[k] = aux[i++];
34 }
35 else if(aux[i] < aux[j]) {
36 a[k] = aux[i++];
37 }
38 else {
39 a[k] = aux[j++];
40 }
41 }
42 }
43
44 //O(nlogn) runtime on average, O(1) space
45 public static void quickSort(int[] a) {
46 Random rand = new Random();
47 quickSortHelper(a, rand, 0, a.length - 1);
48 }
49 private static void quickSortHelper(int[] a, Random rand, int start, int end) {
50 if(start >= end) {
51 return;
52 }
53 //choose pivot
54 int p = rand.nextInt(end - start + 1) + start;
55
56 //partition a around a[p]
57 int pivot_sort_idx = partition(a, p, start, end);
58 quickSortHelper(a, rand, start, pivot_sort_idx - 1);
59 quickSortHelper(a, rand, pivot_sort_idx + 1, end);
60 }
61 private static int partition(int[] a, int pivot_index, int start, int end) {
62 int pivot = a[pivot_index];
63 swap(a, pivot_index, start);
64
65 int i = start + 1, j = i;
66 for(; j <= end; j++) {
67 if(a[j] < pivot) {
68 swap(a, i, j);
69 i++;
70 }
71 }
72 swap(a, start, i - 1);
73 return i - 1;
74 }
75
76 private static void swap(int[] a, int i, int j) {
77 int temp = a[i];
78 a[i] = a[j];
79 a[j] = temp;
80 }
81
82 //O(nlogn) runtime, O(1) space
83 public static void heapSort(int[] a) {
84 if(a == null || a.length <= 1) {
85 return;
86 }
87 int n = a.length;
88
89 //Build max heap, O(n) runtime
90 for(int i = n / 2 - 1; i >= 0; i++) {
91 heapify(a, n, i);
92 }
93
94 //one by one extract the largest element from heap, O(nlogn) runtime
95 for(int i = n - 1; i > 0; i++) {
96 //move current root of heap to end
97 swap(a, 0, i);
98 heapify(a, i, 0);
99 }
100 }
101 private static void heapify(int[] a, int len, int rootIdx) {
102 int largestIdx = rootIdx;
103 int leftChildIdx = 2 * rootIdx + 1;
104 int rightChildIdx = 2 * rootIdx + 2;
105
106 //if left child is larger than root
107 if(leftChildIdx < len && a[leftChildIdx] > a[largestIdx]) {
108 largestIdx = leftChildIdx;
109 }
110 //if right child is larger than largest so far
111 if(rightChildIdx < len && a[rightChildIdx] > a[largestIdx]) {
112 largestIdx = rightChildIdx;
113 }
114 if(largestIdx != rootIdx) {
115 swap(a, rootIdx, largestIdx);
116
117 heapify(a, len, largestIdx);
118 }
119 }
120 }
Binary Search
1. Recursion vs Iterative: if not using recursion, will the implementation becomes complex? Can the depth of recursion calls get big?
2. How to avoid dead loop?
3. O(logn) runtime
4. Binary search 3 different application scenarios.
a. Binary search on Index: Find the first or last position that meets certain conditions.
practice problems:
First/Last Position of Target
Classic Binary Search
Search a 2D Matrix: Convert the 2D matrix's index into a 1D array then apply binary search. mid value should be declared as type long.
Search a 2D Matrix II
Search in Rotated Sorted Array
Search in Rotated Sorted Array II
Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array II
Search in a Big Sorted Array
First Bad Version
b. Binary search to cut half of the exploring sets. Either keep the half that has an answer, or get rid of the half that does not have an answer.
practice problems:
Closet Number in Sorted Array
K Closest Numbers in Sorted Array
Maximum Number in Mountain Sequence
Find Peak Element
c. Binary Search on Result.
Recursion && Dynamic Programming
Two important principles of dynamic programming: 1. optimal substructure; 2. overlapping subproblems
Practice Problems
Unique Paths
Unique Paths II
Climbing Stairs
Minimum Path Sum
Triangle
Binary Tree Maximum Path Sum
Largest Divsible Subset
Knight Shortest Path
Knight Shortest Path II
Perfect Squares
Jump Game
Longest Increasing Subsequence
Drop Eggs
Drop Eggs II
Bit Manipulation
Practice Problems
+ operation can be simulated with bitwise xor ^ and bitwise and & operations. ^ takes care of bits addition; & takes care of carry bits.