COMPANY: Google Cloud
POSITION OFFERED: Software Engineer- III (L4)
CURRENT ROLE: Senior Frontend Engineer at MNC
TOTAL EXPERIENCE: Over 3.5 Years
MODE: Virtual Interview (Google Meet) & (Google Docs)
RECRUITER REACHED: On LinkedIn
DID MOCK INTERVIEW HAPPEN?: Yes
TIME GIVEN TO PREPARE: 25 days

TIME FOR INTERVIEW: Exactly 45 minutes (This included quick introduction as well as feedback.)

Question:
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')])

CODE I Provided:
Python solution:

def canFinish(pairs):
    from collections import defaultdict

    # Create a graph from pairs
    graph = defaultdict(list)
    for x, y in pairs:
        graph[x].append(y)

    # A recursive function to check for cycles
    def is_cyclic(v, visited, recStack):
        visited[v] = True
        recStack[v] = True

        # Recur for all the vertices adjacent to this vertex
        for neighbour in graph[v]:
            if not visited[neighbour]:
                if is_cyclic(neighbour, visited, recStack):
                    return True
            elif recStack[neighbour]:  # If the node is in the recursion stack, there is a cycle.
                return True

        recStack[v] = False  # Pop v from recursion stack before function ends
        return False

    visited = defaultdict(bool)
    recStack = defaultdict(bool)

    # Call the recursive helper function to detect cycle in different DFS trees
    for node in graph:
        if not visited[node]:
            if is_cyclic(node, visited, recStack):
                return False

    return True

# Example usage:
print(canFinish([('a', 'b'), ('b', 'c')]))  # Output: True
print(canFinish([('a', 'b'), ('c', 'a'), ('b', 'c')]))  # Output: False

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.

Explanation:
To solve this problem, we can use graph theory. We'll consider each unique character as a vertex in a graph, and a "greater than" pair as a directed edge from one vertex to another. Our goal is to check if the graph contains any cycles because a cycle would imply a contradiction (e.g., a > b > c > a is a cycle and a contradiction).

Here's the step-by-step approach:

1. Graph Construction: Create a directed graph from the list of "greater than" pairs.
2. Cycle Detection: Use Depth-First Search (DFS) to detect cycles in the graph.

Few Questions asked by Interviewer that I remember:

1. Why finding a cycle is crucial here?
2. Give example of a cycle.
3. Why did you use "recStack"? what is that? (recStack is nothing but short for recursion stack to keep track of nodes of current path)
4. Why you used recursion?
5. Can you check for indentation error? (I had couple of them initially)
   NOTE:
   This is for the Leetcode community to help you how real google Interview is also this was my first time interviewing with Google for Frontend Engineer.
   My Preparation was less since I already have a full time job working as a Senior Frontend Eng.
   The interview didn't went to well as I expected it to be.
   Cheers & All the best!