Published on

# Google Frontend Interview Question(Topological Sorting)

## 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:

• 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.
2. 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).
3. 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.

• 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.
5. 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
for (const [x, y] of pairs) {
}

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

function isCyclic(node) {
if (!visited.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.