📌 Company: Google
📍 Round: Phone Screen
🧠 Role: SDE-2
🗓️ Experience: 2 YOE
❌ Status: Rejected after phone screen

🧪 Question: Graph Connectivity via Value Proximity

Prompt:
Given a sorted array arr of size N, and an integer diff, construct an undirected graph where each node represents an index. Connect nodes i and j if |arr[i] - arr[j]| <= diff.

You are given a list of queries [u, v]. Return a list of booleans indicating whether there is a path between u and v.

Example:

arr = [1, 2, 3, 6]
diff = 2
queries = [[0, 2], [1, 3]]

Output: [True, False]

✅ My Approach:

• Since the array is sorted, edges only form between adjacent elements where the difference is within diff.
• I used Disjoint Set Union (Union-Find) to group connected components efficiently.
• For each query, I simply checked if both nodes belonged to the same component.

🧠 Time & Space:

• Build time: O(N)
• Query time: O(Q * α(N))
• Space: O(N)

🔧 Python Code:

def are_connected(arr, diff, queries):
    n = len(arr)
    parent = list(range(n))
    rank = [0] * n

    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    def union(u, v):
        ru, rv = find(u), find(v)
        if ru == rv:
            return
        if rank[ru] < rank[rv]:
            parent[ru] = rv
        elif rank[ru] > rank[rv]:
            parent[rv] = ru
        else:
            parent[rv] = ru
            rank[ru] += 1

    for i in range(n - 1):
        if arr[i + 1] - arr[i] <= diff:
            union(i, i + 1)

    return [find(u) == find(v) for u, v in queries]

🗒️ Final Thoughts:

Even though the round didn’t go through, it was a great experience. The problem tested key concepts in graph theory and DSU. Sharing this to help others preparing for similar interviews!

Let me know what went wrong