Google Frontend Interview Question(Topological Sorting)

Problem Statement ?

Given a list of greater than pairs, return a boolean with: Whether the list of pair comparisons given are valid.

Example 1

a > b, b > c;
Input: [("a", "b"), ("b", "c")];
Output: True;

Explanation:

There are no contradictory pairs in the input list.

Example 2

a > b, c > a, b > c;
Input: [("a", "b"), ("c", "a"), ("b", "c")];
Output: False;

Explanation:

a cannot be greater than b and less than c because b is greater than c.

Provided assumptions

Each variable is a distinct UTF-8 string character. This has no bearing on how the problem is solved, and imagining just the lowercase alphabet is fine. There will not be duplicate input pairs. (duplicate pair -> [('a', 'b'), ('a', 'b')])

Topological Sorting Solution in javascript

Here's a step-by-step explanation of the approach:

Building the Adjacency List:
- We start by building an adjacency list to represent the relationships given in the pairs.
- Each variable (letter) in the pairs becomes a node in the graph, and the directed edge points from the variable that is less than the other to the one that is greater.
Topological Sorting:
- We perform a topological sort on the directed graph.
- Topological sort is a linear ordering of the vertices of a graph in such a way that for every directed edge u -> v, vertex u comes before vertex v in the ordering.
- If a cycle exists in the graph, it's impossible to construct a topological ordering, as there is a contradiction (e.g., a > b > c > a).
Detecting Cycles:
- To detect cycles, we use a modified depth-first search (DFS) algorithm.
- We maintain a set of visited nodes and a set of nodes in the recursion stack to keep track of the nodes currently being explored.
- If we encounter a node that is already in the recursion stack during DFS traversal, it means we have found a back edge, indicating the presence of a cycle.
Checking for Contradictions:
- If the graph has a cycle, it implies a contradiction in the comparisons.
- For example, if we have a cycle a > b > c > a, it means that a should be greater than b, b should be greater than c, and c should be greater than a, which is impossible.
Returning the Result:
- If no cycles are found during the topological sort, it means the given comparisons are valid, and we return true.
- If a cycle is detected, indicating a contradiction, we return false.

By using this approach, we can efficiently determine whether the given pairs of comparisons are valid or not, based on the directed graph representation and topological sorting.

function isValidComparison(pairs) {
  // Build adjacency list representing the directed graph
  const adjList = new Map();
  for (const [x, y] of pairs) {
    if (!adjList.has(x)) adjList.set(x, new Set());
    if (!adjList.has(y)) adjList.set(y, new Set());
    adjList.get(x).add(y);
  }

  // Perform topological sort
  const visited = new Set();
  const recursionStack = new Set();

  function isCyclic(node) {
    if (!visited.has(node)) {
      visited.add(node);
      recursionStack.add(node);

      if (adjList.has(node)) {
        for (const neighbor of adjList.get(node)) {
          if (!visited.has(neighbor) && isCyclic(neighbor)) {
            return true;
          } else if (recursionStack.has(neighbor)) {
            return true;
          }
        }
      }
    }
    recursionStack.delete(node);
    return false;
  }

  for (const node of adjList.keys()) {
    if (isCyclic(node)) {
      return false; // Cycle found, return false
    }
  }

  return true; // No cycle found, return true
}

// Example usage:
const input1 = [
  ["a", "b"],
  ["b", "c"],
];
console.log(isValidComparison(input1)); // Output: true

const input2 = [
  ["a", "b"],
  ["c", "a"],
  ["b", "c"],
];
console.log(isValidComparison(input2)); // Output: false

This implementation should correctly determine whether the given pairs of comparisons are valid or not. It constructs a directed graph using an adjacency list representation, then performs a topological sort while checking for cycles. If any cycle is found, it indicates a contradiction, and the function returns false. Otherwise, it returns true.

Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because we must visit each vertex and edge once during the DFS.

Space Complexity: O(V), as we need to store the vertices and the recursion stack may also go up to O(V) in the case of a long path.

Google Frontend Interview Question(Topological Sorting)