Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
A

Anonymous

· 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++;

A

Anonymous

· 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
A

Anonymous

· 3 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.

Reading Progress

0%

Vote for new content