[Uber - Phone ] Island Count 2


  • 0
    V

    Print the Island Count every time, a new Land infomation is added.
    Leetcode Hard Question: https://leetcode.com/problems/number-of-islands-ii/
    Expected to write a fully functional code with test cases


  • 0

    @varpar That's nuts.


  • 0

    Why would this be insane? This is simple union-find.


  • 4

    @babhishek21 It's simple iff you're able to code up union-find off the top of your head (weighted, path compressed UF, anyone?) ;) Union-find is a relatively exotic datastructure compared to most, and to ask it (disguised in a LeetCode Hard question) in a phone screen is a rather steep ramp, especially given the fact that it is the only legitimate way to solve that question leaving virtually no wiggle room for alternative solutions from the candidate.

    Then again, you seem like the person who react to a question like this by saying "Why would this be insane? This is a simple segment tree". In that case, I wish you all the best and hope that you don't phone-screen any good candidates; not because you're * so overpoweringly smart * but probably because you're detached from reality.


  • 0

    @schumpeter Haha! Fair point, I guess.

    Just a few things:

    • I don't find Union Find (more specifically DSUs) "exotic". There is a reason it is the very first thing taught in a poular algorithms course. It's not as hard as people make it out to be. The concepts behind DSUs are important stepping stones for algorithms in graph theory and interval data structures.
    • I agree that it can be hard to write by memory. But a good interviewer won't expect that you write perfect bug-free code in your first go. They won't even expect path compressions and weighted rank union. Just write the normal methods and mve from there.
    • I keeps these two signatures in mind:
    int parent[] // parent array holds the representative parent of a particular element
    // an element is its own representative if it's not representated by any one else.
    
    int findParent(int x) {  // recursively move pointer through the parents to find a representative parent
      while(x != parent[x])
        x = parent[x];
      return x;
    }
    
    void unionParents(int x, int y) { // choose one representative to be the supreme representative for both
      int px = findParent(x),
          py = findParent(y);
    
      parent[px] = py;
    }
    
    • These signatures are simple to remember. No path compressions, no weighted union, no union-by-rank, just simple deterministic union find.

    I responded as such because you labeleld the question insane(ly) difficult for a phone interview. I don't see why. As soon as you understand that it requires a union-find, you can explain your intuition to your interviewer. Sure, you lose points for not being able to write usable code. But that is not entirely what the interviewer is looking for.

    Being out of touch is only human, I get it. However assuming that just because it is a phone interview, the interviewer is not inclined to ask difficult stuff is foolishness, stat. I've heard people getting asked complex DP questions in phone interviews.

    However there are certain limits that can be expected resonably from an interviewer:

    • It can be hard to explain complex stuff in a phone interview or a video interview, which can be done much easily face to face. So I expect the interviewer to understand if I'm having a hard time explaining stuff without writing it down.
    • I also expect the interviewer to ask me to code up stuff that is reasonable to do from memory. So no, I cannot code up the KMP algorithm from memory. Yes, I can code up a simple segement tree from memory, but I'd be truly horrified if they asked me to do so in a not-face-to-face interview. [1]
    • I can explain a segment tree well, or how I'd approach problems that require interval based data structures. But I can't explain the KMP Algorithm (unless the interviewer plopped down the code themselves. Even then I'd have a hard time explaining how it works. [2]). So yes, the principle of YMMV applies.[3] Things that are easy for me might be difficult for you. But the situation is not "insane".

    [1] True story: I was asked a question involving interval trees in a video interview. I told them how it would work out the best I could. I also told them that writing the code from memory was beyond me. The interviewer told me that he wasn't expecting that anyway. He was pretty happy with my explanation.
    [2] The true essence of the "insane"(ly) complex KMP algorithm is not in the loops, but in the DFA it runs on. Its true meaning still eludes me to this day. But I guess that means I just need to put more time into understanding it.
    [3]: YMMV = Your mileage may vary.


  • 0

    @babhishek21 Thanks for your elaborate response which (in some ways) confirms some suspicions I had :) A couple of things:

    • I'm not @varpar so I can't speculate how the interview was conducted. But judging from his/her post, it seems that fully functional code was required. This may not mean that the interviewer required it to be path-compressed and weighted, but it does mean that the candidate would need to remember the signatures (and how to fill up the methods appropriately).

    • There is also a reason that this data structure is explained Chapter 21 under the Advanced Data Structures section in the CLRS book, right after van Emde Boas trees. In fact, if you take a cursory glance on the MIT OCW courses (intro, analysis) you'd be hard pressed to find where they're explained in detail. That and the fact that there are (as of this writing) just 7 problems tagged with union-find (most of which are easily solvable using general DFS/BFS as evidenced by the top voted answers). Citing the princeton class on coursera is simply strawmanning. No other class that I've seen (online MOOC or not) actually starts with this concept, although they do talk about it when get around to graph based algorithms because dynamic connectivity is a prerequisite.

    • None of this takes away from the usefulness or importance of the data structure and I haven't claimed that the implementation is absurdly complex; writing a solid concurrentHashMap with the right lock striping correctly would be far more difficult in contrast. I also believe that people never do complain about its complexity once they actually stumble upon the right material; as you astutely pointed out, if one were to spend an hour on the coursera class they would have a very good grasp of how you use it. I could just as easily point out algorithms in network routing that are fundamentally critical to how the internet works which frankly aren't covered in any introductory undergraduate classes; that doesn't mean everyone is supposed to know how they're implemented exactly. Alternatively, you could pontificate on the importance of self-balancing BSTs and claim that everyone should know the implementation details of RedBlack trees because they are stepping stones for a whole range of applications, but my personal opinion is that that stance while correct is unhelpful in the purview of a phone screen.

    The reason I said that it being asked in a phone screen is nuts (not "insane") is that the question pigeonholes the candidate into giving only 1 type of response whose implementation they're required to know off-hand. My personal preference is questions where there are a number of different alternatives so that you tease apart the candidate's expertise in a range of topics/approaches. But hey, to each his own :)


  • 0

    @schumpeter I see your line of reasoning. But comparing RB Trees and AVL trees to Union Find is comparing apples to oranges.

    And while we all have our personal preference of questions, it is wont to believe that the interviewer will pander to those. My point is this problem is not so much "nuts" as much as you are not in control of what you might be asked in any interview.


  • 1

    @babhishek21

    But comparing RB Trees and AVL trees to Union Find is comparing apples to oranges

    I agree, and it's a deliberately contrived example. While implementation complexity is a factor, I would argue that in the event the candidate hasn't seen said data-structure at all before (for whatever reason), does asking the question gauge much more than the fact that they haven't seen it? I'm sure there are tons of good programmers that haven't seen/used a segment tree and would be hard pressed to come up with one on the fly. I'm not saying that knowledge of certain datastructures is NOT a signal (it most certainly is, and indicates rigorous coursework, keen interest, programming contest experience hah), but asking questions that completely hinge on knowledge of said structures is more likely to produce binary results which depending on who you ask, may not be the best thing because congratulations, you've just verified that the candidate doesn't know it (but not much else.) Ofcourse, the line must be drawn somewhere (can't show up claiming you've never heard of a list/map/linkedlist), and that's where it gets subjective depending on the interviewer.

    My point is this problem is not so much "nuts" as much as you are not in control of what you might be asked in any interview

    You'll have a hard time finding someone who disagrees with that tautology :)


  • 0
    C
    This post is deleted!

  • 0

    To be honest, I did find Union Find (Disjoint Sets) daunting at first but watching some videos and implementing it a couple times for solving problems has made me realize that it's rather simple. On that note, here's my implementation for this problem:
    ( As I don't have a subscription I wasn't able to verify my solution on OJ. I did some testing and it seems to be working fine though. Let me know if you see any bugs. Thanks.)

    Some notes:

    • I index each row,column and store those as the keys being process in the disjoint set
    • This implementation does not treat two diagonally adjacent islands as one island. This could easily be handled by changing the 'direc' (directions) variable to check for diagonals as well.
    class Islands:
    
    	def __init__(self, m, n):
    		self.grid = [[0] * m for _ in range(n)]
    		self.m = m
    		self.n = n
    		self.ranks = {}
    		self.parents = {}
    		self.cnt = 0
    		self.direc = {(0, 1), (0, -1), (1, 0), (-1, 0)}
    
    	def addLand(self, r, c):
    		if self.valid_coord(r, c) and self.grid[r][c] == 0:
    			self.grid[r][c] = 1
    			self.make_set(r, c)
    			self.check_position(r, c)
    			return True
    		return False
    
    	def make_set(self, r, c):
    		ind = self.indexify(r, c)
    		self.ranks[ind] = 0
    		self.parents[ind] = ind
    		self.cnt += 1 # new singular island
    
    	def union(self, u, v):
    		U, V = self.find_parent(u), self.find_parent(v)
                    # This is more for a typical implementation of disjoint sets. Shouldn't happen in this problem though.
    		if U == V: return False 
    		# here on we're unioning two sets thus island count is decremented
    		self.cnt -= 1
    		if self.ranks[U] < self.ranks[V]:
    			self.ranks[V] += 1
    			self.parents[U] = V
    		else:
    			self.ranks[U] += 1
    			self.parents[V] = U
    
    	def find_parent(self, u):
    		if self.parents[u] == u: return u
    		self.parents[u] = self.find_parent(self.parents[u]) # path compression
    		return self.parents[u]
    
    	def valid_coord(self, r, c):
    		return 0 <= r < self.n and 0 <= c < self.m
    
    	def check_position(self, r, c):
    		ind = self.indexify(r, c)
    		for dr, dc in self.direc:
    			r_, c_ = r + dr, c + dc
    			if self.valid_coord(r_, c_) and self.grid[r_][c_] == 1:
    				self.union(ind, self.indexify(r_, c_))
    
    	def indexify(self, r, c):	
    		return r * self.m + c
    
    	def get_island_count(self):
    		return self.cnt
    
    if __name__ == "__main__":
    	I = Islands(3, 3) # 3x3 grid
    	I.addLand(0, 0)
    	print(I.get_island_count()) # 1
    	I.addLand(0, 1)
    	print(I.get_island_count()) # 1
    	I.addLand(1, 2)
    	print(I.get_island_count()) # 2
    	I.addLand(2, 1)
    	print(I.get_island_count()) # 3
    	I.addLand(1, 1)
    	print(I.get_island_count()) # 1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.