- Published on

# Google Frontend Interview Question(Topological Sorting)

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

**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.