Mock Interview Questions

What is a graph in computer science?

What are the different types of graphs?

What is the difference between a graph and a tree?

What is the adjacency matrix representation of a graph?

What is the adjacency list representation of a graph?

What is a graph traversal?

What are the different types of graph traversals?

What is the time complexity of BFS and DFS?

What is the purpose of Dijkstra's algorithm?

What is the time complexity of Dijkstra's algorithm?

What is the purpose of Bellman-Ford algorithm?

What is the time complexity of Bellman-Ford algorithm?

What is the purpose of Floyd-Warshall algorithm?

What is the time complexity of Floyd-Warshall algorithm?

What is a minimum spanning tree?

What is Kruskal's algorithm?

What is the time complexity of Kruskal's algorithm?

What is Prim's algorithm?

What is the time complexity of Prim's algorithm?

Given a graph represented as an adjacency list, write a function to perform a depth-first search (DFS) traversal of the graph.

function dfs(graph, start) {
  var visited = {};
  function dfsHelper(node) {
    visited[node] = true;
    console.log(node);
    for (var neighbor in graph[node]) {
      if (!visited[neighbor]) {
        dfsHelper(neighbor);
      }
    }
  }
  dfsHelper(start);
}

Given a graph represented as an adjacency matrix, write a function to perform a breadth-first search (BFS) traversal of the graph.

function bfs(graph, start) {
  var visited = {};
  var queue = [start];
  visited[start] = true;
  while (queue.length > 0) {
    var node = queue.shift();
    console.log(node);
    for (var i = 0; i < graph.length; i++) {
      if (graph[node][i] === 1 && !visited[i]) {
        queue.push(i);
        visited[i] = true;
      }
    }
  }
}

Given a weighted graph represented as an adjacency list, write a function to find the shortest path between two vertices using Dijkstra's algorithm.

function dijkstra(graph, start, end) {
  var distances = {};
  var previous = {};
  var queue = [start];
  distances[start] = 0;
  while (queue.length > 0) {
    var node = queue.shift();
    for (var neighbor in graph[node]) {
      var distance = distances[node] + graph[node][neighbor];
      if (distance < distances[neighbor] || distances[neighbor] === undefined) {
        distances[neighbor] = distance;
        previous[neighbor] = node;
        queue.push(neighbor);
      }
    }
  }
  var path = [];
  var node = end;
  while (node !== start) {
    path.push(node);
    node = previous[node];
  }
  path.push(start);
  return path.reverse();
}

Given a weighted graph represented as an adjacency matrix, write a function to find the shortest path between two vertices using Bellman-Ford algorithm.

function bellmanFord(graph, start, end) {
  var distances = {};
  var predecessor = {};
  for (var i = 0; i < graph.length; i++) {
    distances[i] = Infinity;
  }
  distances[start] = 0;
  for (var i = 0; i < graph.length - 1; i++) {
    for (var j = 0; j < graph.length; j++) {
      for (var k = 0; k < graph.length; k++) {
        if (graph[j][k] !== 0 && distances[j] + graph[j][k] < distances[k]) {
          distances[k] = distances[j] + graph[j][k];
          predecessor[k] = j;
        }
      }
    }
  }
  var path = [];
  var node = end;
  while (node !== start) {
    path.push(node);
    node = predecessor[node];
  }
  path.push(start);
  return path.reverse();
}

Given a graph represented as an adjacency list, write a function to find the minimum spanning tree of the graph using Kruskal's algorithm.

function kruskal(graph) {
  var mst = [];
  var parent = {};
  var rank = {};
  for (var node in graph) {
    parent[node] = node;
    rank[node] = 0;
  }
  var edges = [];
  for (var node in graph) {
    for (var neighbor in graph[node]) {
      edges.push({
        node: node,
        neighbor: neighbor,
        weight: graph[node][neighbor],
      });
    }
  }
  edges.sort(function (a, b) {
    return a.weight - b.weight;
  });
  for (var i = 0; i < edges.length; i++) {
    var node = edges[i].node;
    var neighbor = edges[i].neighbor;
    var weight = edges[i].weight;
    if (find(parent, node) !== find(parent, neighbor)) {
      mst.push({ node: node, neighbor: neighbor, weight: weight });
      union(parent, rank, node, neighbor);
    }
  }
  return mst;
}
function find(parent, node) {
  if (parent[node] !== node) {
    parent[node] = find(parent, parent[node]);
  }
  return parent[node];
}
function union(parent, rank, node, neighbor) {
  var root1 = find(parent, node);
  var root2 = find(parent, neighbor);
  if (rank[root1] < rank[root2]) {
    parent[root1] = root2;
  } else if (rank[root1] > rank[root2]) {
    parent[root2] = root1;
  } else {
    parent[root2] = root1;
    rank[root1]++;
  }
}

Given a graph represented as an adjacency matrix, write a function to find the minimum spanning tree of the graph using Prim's algorithm.

function prim(graph) {
  var mst = [];
  var visited = {};
  var start = 0;
  visited[start] = true;
  while (true) {
    var minWeight = Infinity;
    var node = -1;
    var neighbor = -1;
    for (var i = 0; i < graph.length; i++) {
      if (visited[i]) {
        for (var j = 0; j < graph.length; j++) {
          if (!visited[j] && graph[i][j] !== 0 && graph[i][j] < minWeight) {
            minWeight = graph[i][j];
            node = i;
            neighbor = j;
          }
        }
      }
    }
    if (node === -1) {
      break;
    }
    mst.push({ node: node, neighbor: neighbor, weight: minWeight });
    visited[neighbor] = true;
  }
  return mst;
}