Earliest Time of Full Connectivity

Question

This question asks the candidate to determine the earliest time at which all entities in a dynamic graph become fully connected, considering evolving relationships over time.

Codemia · Accepted Answer

To solve the problem of determining the earliest time of full connectivity in a dynamic graph, we first need to model the relationships between entities as a graph. Each entity represents a node, and the relationships that evolve over time can be represented as edges that are added or removed. Our goal is to find the first time at which all nodes are connected.

We can use a union-find data structure to keep track of connected components in the graph. As we process the relationships over time, we can union nodes when an edge is added. The main challenge is to efficiently check when all nodes are connected. We will iterate through the time-ordered events, updating our union-find structure and checking for full connectivity.

The algorithm can be structured as follows:

1. **Sort the events** by time.
2. **Initialize a union-find structure** for the nodes.
3. **Iterate through each event**:
   - If an edge is added, perform a union operation.
   - After each union, check if the number of connected components is 1.
4. **Return the time** when all nodes are connected.

Here is a Python code snippet implementing this logic:

```python
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size
    
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]
    
    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU != rootV:
            if self.rank[rootU] > self.rank[rootV]:
                self.parent[rootV] = rootU
            elif self.rank[rootU] < self.rank[rootV]:
                self.parent[rootU] = rootV
            else:
                self.parent[rootV] = rootU
                self.rank[rootU] += 1

def earliest_full_connectivity(events):
    # Sort events by time
    events.sort(key=lambda x: x[0])
    uf = UnionFind(len(events))
    components = len(events)
    
    for time, u, v in events:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            components -= 1
            if components == 1:
                return time
    return -1  # If never fully connected
```

The time complexity of this approach is O(E log E) due to the sorting of edges, where E is the number of edges. The union-find operations are nearly constant time, specifically O(α(N)), where α is the inverse Ackermann function. The space complexity is O(N) for storing the parent and rank arrays.

Interviewers will be looking for clarity in your explanation of the problem and approach. They will assess your understanding of graph theory and algorithm optimization. Additionally, they want to see how you handle edge cases and your ability to communicate your thought process effectively.

Earliest Time of Full Connectivity

Google

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string