Mastering the Coding Interview: 3 Essential Algorithms for Graph Search
There are many possible interview questions. Let's explore some powerful algorithms that can help us overcome any challenges we may encounter during interviews or work.
1. Depth-First Search (DFS)
Depth-First Search (DFS) can be used to search elements in a graph.
This algorithm explores as far as possible along each branch before backtracking. It starts from a source node and visits as far as possible along each branch before backtracking. DFS is often implemented using recursion or a stack data structure to allow backtracking.
In case you want to find connected components in a graph, and you intend to go deep into each connected vertices, then the DFS could be a nice choice.
Problem: Finding users from a community
Consider a social network where users are represented as nodes and friendships as edges. DFS can be applied to find all users who are part of a specific friend group or community. The algorithm starts with a user and explores their friends, then friends of friends, and so on, marking visited users along the way.
Solution with Java
static class SocialGraph {
private final int vertices;
private final Map<Integer, List<Integer>> adjacencyList;
public SocialGraph(int vertices) {
this.vertices = vertices;
this.adjacencyList = new HashMap<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.put(i, new ArrayList<>());
}
}
public void addFriendship(int user1, int user2) {
adjacencyList.get(user1).add(user2);
adjacencyList.get(user2).add(user1); // For undirected graph
}
public Set<Integer> findFriendGroup(int startUser, boolean[] visited) {
Set<Integer> friendGroup = new LinkedHashSet<>();
depthFirstSearch(startUser, visited, friendGroup);
return friendGroup;
}
private void depthFirstSearch(int currentUser, boolean[] visited, Set<Integer> friendGroup) {
visited[currentUser] = true;
friendGroup.add(currentUser);
for (int friend : adjacencyList.get(currentUser)) {
if (!visited[friend]) {
depthFirstSearch(friend, visited, friendGroup);
}
}
}
}
public static void main(String[] args) {
SocialGraph socialGraph = new SocialGraph(7);
socialGraph.addFriendship(0, 1);
socialGraph.addFriendship(0, 2);
socialGraph.addFriendship(1, 3);
socialGraph.addFriendship(2, 3);
socialGraph.addFriendship(4, 5);
socialGraph.addFriendship(5, 6);
int startUser = 1;
boolean[] visited = new boolean[socialGraph.vertices];
Set<Integer> friendGroup = socialGraph.findFriendGroup(startUser, visited);
System.out.println("Friend Group for User " + startUser + ": " + friendGroup); //Friend Group for User 1: [1, 0, 2, 3]
}
This algorithm uses recursion and backtracking.
In the recursive implementation of DFS, the algorithm explores a branch of the graph as deeply as possible before backtracking.
Backtracking is a mechanism that allows the algorithm to undo or "backtrack" from decisions when necessary. In DFS, backtracking is used to explore other branches of the graph when the current branch has been fully explored.
Note: If the graph is huge, the stack may be a better solution, providing better memory efficiency.
The time complexity of Depth-First Search (DFS) is typically expressed in terms of the number of vertices (nodes) and edges in the graph, so the time complexity of DFS is O(V+E). DFS often performs well and is efficient for many graph-related problems.
2. Breadth-First Search (BFS)
Breadth-First Search (BFS) can also be used to search elements in a graph.
This algorithm explores a graph level by level, visiting all the neighbours of a node before moving on to the next level. It starts from a source node and systematically explores its neighbours, then the neighbours of its neighbours, and so on. BFS is often implemented using a queue data structure to keep track of the nodes to visit.
In case you want to find the shortest path with connected components in a graph, then the BFS could be a nice choice.
Problem: Finding the shortest chain of connections between users
Suppose you want to find the shortest chain of connections between two users in a social network. BFS can help identify the shortest path, considering that each user is a node, and connections between users are edges in the graph.
Solution with Java
static class SocialGraph {
private final int vertices;
private final Map<Integer, List<Integer>> adjacencyList;
public SocialGraph(int vertices) {
this.vertices = vertices;
this.adjacencyList = new HashMap<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.put(i, new ArrayList<>());
}
}
public void addFriendship(int user1, int user2) {
adjacencyList.get(user1).add(user2);
adjacencyList.get(user2).add(user1); // For undirected graph
}
public List<Integer> shortestPath(int startNode, int endNode) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[vertices];
int[] parent = new int[vertices];
queue.add(startNode);
visited[startNode] = true;
parent[startNode] = -1;
while (!queue.isEmpty()) {
int currentNode = queue.poll();
for (int neighbor : adjacencyList.get(currentNode)) {
if (!visited[neighbor]) {
queue.add(neighbor);
visited[neighbor] = true;
parent[neighbor] = currentNode;
if (neighbor == endNode) {
// Reconstruct the path
return reconstructPath(parent, endNode);
}
}
}
}
return Collections.emptyList(); // No path found
}
private List<Integer> reconstructPath(int[] parent, int endNode) {
List<Integer> path = new ArrayList<>();
int currentNode = endNode;
while (currentNode != -1) {
path.add(currentNode);
currentNode = parent[currentNode];
}
Collections.reverse(path);
return path;
}
}
public static void main(String[] args) {
SocialGraph socialGraph = new SocialGraph(7);
socialGraph.addFriendship(0, 1);
socialGraph.addFriendship(0, 2);
socialGraph.addFriendship(1, 3);
socialGraph.addFriendship(2, 3);
socialGraph.addFriendship(1, 5);
socialGraph.addFriendship(3, 5);
socialGraph.addFriendship(5, 4);
socialGraph.addFriendship(4, 6);
socialGraph.addFriendship(5, 6);
int startNode = 0;
int endNode = 6;
List<Integer> shortestPath = socialGraph.shortestPath(startNode, endNode);
System.out.println("Shortest path from node " + startNode + " to node " + endNode + ": " + shortestPath);
//Shortest path from node 0 to node 6: [0, 1, 5, 6]
}
The time complexity of the Breadth-First Search (BFS) is typically expressed in terms of the number of vertices (nodes) and edges in the graph, so the time complexity of BFS is O(V+E). BFS tends to be efficient for many graph-related problems, especially when the graph is represented using an adjacency list.
3. Dijkstra's Algorithm
Dijkstra's Algorithm is a popular algorithm in computer science and graph theory for finding the shortest path between nodes in a weighted graph, where the edges have non-negative weights.
The big difference between Dijkstra and BFS is weight. When the nodes are weighted, then Dijkstra is a good option.
Problem: Finding the Shortest Path in a Network
Consider a computer network with routers connected by communication links, each link having a specific cost or latency. We want to find the shortest path from one node (router) to another in terms of the total communication link cost.
Solution with Java
static class Graph {
private final Map<Integer, List<Edge>> adjacencyList;
public Graph(int vertices) {
this.adjacencyList = new HashMap<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.put(i, new ArrayList<>());
}
}
public void addEdge(int source, int destination, int weight) {
adjacencyList.get(source).add(new Edge(destination, weight));
adjacencyList.get(destination).add(new Edge(source, weight)); // For undirected graph
}
public Map<Integer, Integer> dijkstra(int source) {
PriorityQueue<NodeDistance> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));
Map<Integer, Integer> distances = new HashMap<>();
priorityQueue.add(new NodeDistance(source, 0));
distances.put(source, 0);
while (!priorityQueue.isEmpty()) {
NodeDistance currentNode = priorityQueue.poll();
for (Edge neighbor : adjacencyList.get(currentNode.node)) {
int newDistance = currentNode.distance + neighbor.weight;
if (newDistance < distances.getOrDefault(neighbor.destination, Integer.MAX_VALUE)) {
distances.put(neighbor.destination, newDistance);
priorityQueue.add(new NodeDistance(neighbor.destination, newDistance));
}
}
}
return distances;
}
public List<Integer> shortestPath(int source, int target) {
Map<Integer, Integer> distances = dijkstra(source);
List<Integer> path = new ArrayList<>();
// Reconstructing the path from source to target
int current = target;
while (current != source && distances.containsKey(current)) {
path.add(current);
current = getParentWithMinDistance(current, distances);
}
path.add(source);
Collections.reverse(path);
return path;
}
private int getParentWithMinDistance(int node, Map<Integer, Integer> distances) {
int parent = -1;
int minDistance = Integer.MAX_VALUE;
for (Edge edge : adjacencyList.get(node)) {
if (distances.containsKey(edge.destination) && distances.get(edge.destination) + edge.weight < minDistance) {
minDistance = distances.get(edge.destination) + edge.weight;
parent = edge.destination;
}
}
return parent;
}
private static class Edge {
int destination;
int weight;
public Edge(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
private static class NodeDistance {
int node;
int distance;
public NodeDistance(int node, int distance) {
this.node = node;
this.distance = distance;
}
}
}
public static void main(String[] args) {
Graph graph = new Graph(7);
graph.addEdge(0, 1,5);
graph.addEdge(0, 2,3);
graph.addEdge(1, 3,4);
graph.addEdge(2, 3,4);
graph.addEdge(1, 5,12);
graph.addEdge(3, 5,5);
graph.addEdge(5, 4,2);
graph.addEdge(4, 6,3);
graph.addEdge(5, 6,10);
int sourceNode = 0;
int targetNode = 6;
List<Integer> shortestPath = graph.shortestPath(sourceNode, targetNode);
System.out.println("Shortest path from node based on weight " + sourceNode + " to node " + targetNode + ": " + shortestPath);
//Shortest path based on weight from node 0 to node 6: [0, 2, 3, 5, 4, 6]
}
The time complexity of Dijkstra's Algorithm is dominated by the operations in the priority queue (heap operations) and the iteration over the neighbours of each node. For a graph with V vertices and E edges, the time complexity is O((V+E)logV) using a binary heap as the priority queue.
As we can see, BFS and Dijkstra are both graph traversal algorithms, but they serve different purposes and have different characteristics.
Dijkstra finds the shortest path based on the cumulative weight of edges, while BFS finds the shortest unweighted path, where each edge is considered equal. In our last example, using BFS, the output will be [0, 1, 5, 6].
Dijkstra is typically implemented using a priority queue to efficiently select the next node to explore based on the current cumulative weight. BFS is implemented using a regular queue, the order of exploration is based on the depth level of nodes rather than their weights.
Conclusion
There are many algorithms to solve different problems. Knowing them is essential to provide the best solution, providing better performance, and a more legible code.
References
Cracking the Coding Interview: 189 Programming Questions and Solutions