search

bigmachine-io / mission-interview

Code and Issues for Mission: Interview Production
4 stars 1 forks source link

Islands in the sea - counterexample #2

Closed qbikez closed 6 years ago

qbikez commented 7 years ago

I believe your solution to "Islands in the see" is incorrect, here's a counterexample:

const ocean2 = [
  [1,1,0,0,0],
  [1,1,0,0,0],
  [0,0,1,0,1],
  [0,0,1,1,1]
];

There are 2 islands here, but the U-shaped one will be counted as two, because the right "leg" has no land on the left or above, but is still connected with the land below.

robconery commented 7 years ago

Is this speculation or did you run it and verify?

qbikez commented 7 years ago

I did run it and the algorithm returns 3 instead of expected 2.

robconery commented 7 years ago

Ah - cheers thanks. I confirmed as well - that was... sloppy on my part. Want to take a stab at a better solution? I'll amend the video and happy to give credit for the find/fix :).

qbikez commented 7 years ago

Sure, here's my take on this: qbikez/mission-interview.

robconery commented 7 years ago

Nice work - like the DFS approach. Do you have any test cases?

qbikez commented 7 years ago

Yep, they're in a separate project: Mission.Interview.Test/islands-in-the-sea_test.cs. Those are the two example from question description plus a third one with a "U"-shaped island.

robconery commented 7 years ago

Great! Thanks :). I'll have swing at the JS stuff later today.

robconery commented 7 years ago

Here's a redo:

https://gist.github.com/robconery/4e9d7d1cc520eae74f44bab24bca7081

I still think a greedy approach will work though I do like the idea of thinking about this as a graph. Might be a bit overkill, however, as you could do it with a simple array.

Anyway - have a look. I've tested it through a number of variations but would like a second opinion :). This one came out right:

const ocean3 = [
  [1,1,0,0,0],
  [1,1,0,0,0],
  [1,0,1,0,1],
  [1,1,1,0,1]
];

Thanks again for your help here.

qbikez commented 7 years ago

I'm still not sure if checking only the left and upper neighbours can be enough. In this example:

const ocean4 = [
    [0,0,0,1,1],
    [0,0,0,0,1],
    [0,0,0,1,1],
    [0,0,0,0,0]
  ];

getIslandCount(ocean4) returns 2.

robconery commented 7 years ago

Yeah I realized last night I biffed (again!). Went with the graph/dfs approach - think I like it much better. Updated the gist once again - it looks much more like yours. Thanks again...

qbikez commented 7 years ago

Aye!, glad I could help. I love the comments in the new version. ;-)