Island count

June 30, 2018

Introduction

It is my 4:00 PM mock interview. I had to work on the algorithm called Island count. After I explained the algorithm to the peer, peer asked me if I like to continue to write the code for the solution, or I like to discuss with the extended algorithm. I chose to discuss the extended algorithm.

Extended algorithms 

I was asked to work on the extended algorithm. Here is the transcript for our discussion. I need to write code for those two extended algorithms.

Follow up No. 1

	Follow-up 1:
	Let's say the dataset is very large.
	The input data is now a list of coordinates for any piece of land.
	No guarantee on order of coordinates given to you. (random order)
	(1000, 23)
	(0, 1)
	(0, 3)(3948, 1837)
	Julia's analysis:
	size k -> preprocessing size k -> order by sort by row, second col (added after mock interview, I did say that
	it is not necessary)
	put all cordination into dictionary to loop up O(1) <-
	key = row + ';' + col -> 1 -> value 1's dictionary -> O(1)
	visited one -> look up hashset O(1)
	1st loop: insert all into land_dictionary
	2nd loop: lookup neighbors in land_dcitionary and mark in visisted dictionary
	returning number of island at the very end

view raw island count follow up No 1 hosted with ❤ by GitHub

Follow up No. 2

	Follow-up 2:
	We have the same conditions as above.
	0123
	0 0bec
	1 000d
	2 a000
	Stream:
	a: (2, 0)
	b: (0, 1)
	c: (0, 3)
	d: (1, 3)
	e: (0, 2)
	0bec
	000d
	a000
	Return:
	a, b, c, d, e
	1, 2, 3, 3, 2
	Result:
	[1, 2, 2, 3]
	Julia's explanation:
	1. find island, assign id,using global id startin from 1 , increment one at time
	2. still want to go over the steam one by one, mark element, create -> save steamid, id -> dictionary
	The peer patiently to explain to me that the island will go down from 3 islands to 2 islands. When line 14 e:(0, 2) is added
	to the island, two islands are connected so island 2 and island 3 will become one island instead.
	I told the peer that it should be a union join algorithm. And the peer asked me to explain the union join algorithm in my own words.
	I did explain the algorithm to the peer.
	3. go over stream, look up dictionary, try to find island

view raw Island count follow up No. 2 hosted with ❤ by GitHub

Feedback

It is also a good idea to work on the feedback from the peer.

My feedback to the peer

Here is my feedback.