Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Redundant Connection

.....

.....

.....

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