Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Redundant Connection (medium)

Problem Statement

Given an undirected graph containing 1 to n nodes. The graph is represented by a 2D array of edges, where edges[i] = [a<sub>i</sub>, b<sub>i</sub>], represents an edge between a<sub>i</sub>, and b<sub>i</sub>.

Identify one edge that, if removed, will turn the graph into a tree.

A tree is a graph that is connected and has no cycles.

Assume that the graph is always reducible to a tree by removing just one edge.

If there are multiple answers, return the edge that occurs last in the input.

Examples

  1. Example 1:
    • Input:

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lee

· 2 years ago

In the pattern introduction, the complexity analysis is pretty hand-wavy in that it vaguely refers to the inverse ackerman function and offers nothing further.

Then, in this problem somehow that odd time complexity from the introduction turns into n log n. It is not obvious to me how this works. The explanation is pretty minimal.

Shashwat Kumar

Shashwat Kumar

· 2 years ago

The problem clearly states, 'If there are multiple answers, return the edge that occurs last in the input.' but the solution returns the edge immediately. If we try to instead overwrite the res array and return it after the for loop it gives memory error in C++;

Show 1 reply
Trang Luong

Trang Luong

· a year ago

Based on the knowledge in the previous post, path compression should reduce the time complexity to O(logN). However, in this solution, it's somehow get to "The find operation with path compression has an amortized time complexity of , which is almost equal to , where  is the inverse Ackermann function, which is very close to constant." It should only get to the almost constant time complexity if path compression was to be used with combination of union by rank or union by size

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class UnionFind:
    def __init__(self):
        self.rank = {}
        self.parents = {}

    def find(self, u):
        parent = self.parents.get(u, u)
        if parent == u:
            self.parents[u] = u
            return u
        self.parents[u] = self.find(parent)
        return self.parents[u]
    
    def union(self, u, v):
        par_u = self.find(u)
        par_v = self.find(v)
        if par_u == par_v:
            return 
        if self.rank.get(par_u, 1) < self.rank.get(par_v, 1):
            self.parents[par_u] = v
        elif self.rank.get(par_v, 1) < self.rank.get(par_u, 1):
            self.parents[par_v] = u
        else:
            self.parents[par_u] = v
            self.rank[par_u] = self.rank.get(par_u, 1) + 1

class Solution:
    def findRedunda
Divyanshu Varma

Divyanshu Varma

· a year ago

Turns out the test case [[1,2],[2,3],[3,1],[4,5],[5,6]] is invalid. If you see, there are two components which means there can never be an edge upon removal of which the given graph makes a tree. Grammatically, the problem states "a tree" every time, that means this test case should not be valid.