Grokking Amazon Coding Interview
Vote

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
Cristian

Cristian

· 7 months ago

Is the union find solution wrong? Also, is the test results validator wrong?

Try this test case

[[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,1,0,1]]

1 -> 4 -> 2 -> 3

Shouldn't it be 1 province?

Show 1 reply
C

c.avina05

· 2 years ago

It's silly to hop into Union-Find at this level if you haven't been exposed to it.

Here is a simple DFS solution.

class Solution:
    def findProvinces(self, isConnected):
	    def dfs(node):
	      visited[node] = True
	      for neighbor in range(n):
		      if isConnected[node][neighbor] == 1 and not visited[neighbor]:
						dfs(neighbor)

			provinces = 0
			n = len(isConnected)
			visited = [False]*n
			for i in range(n):
				if not visited[i]:
					dfs(i)
					provinces += 1
		return provinces
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class UnionFind:
    def __init__(self):
        self.parents = {}
        self.rank = {}
        
    def find(self, u):
        parent = self.parents.get(u, u)
        if parent == u:
            self.parents[u] = u
            return self.parents[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, 0) < self.rank.get(par_v, 0):
            self.parents[par_u] = par_v
        elif self.rank.get(par_v, 0) < self.rank.get(par_u, 0):
            self.parents[par_v] = par_u
        else:
            self.rank[par_u] = self.rank.get(par_u, 0) + 1
            self.parents[par_u] = par_v

class
Show 1 reply
L

Lee

· 3 years ago

The python solution uses path compression, but not union by rank. As a result, the complexity explanation is not clear. It says adding path compression and and union by rank get's it down to near n^2. So it's not clear what the complexity of the solution is (n^2, n^3, or something else), or if the solution could be improved by adding a union optimization. The ambiguity is confusing.

Show 1 reply

Reading Progress

0%

Vote for new content