FB电面

原帖地址:一亩三分地

刚刚结束的FB电面~
事实证明女人的第六感太强大了,果然跟Google考了同一题~话说这两家真的很喜欢dfs和bfs的问题count number of island的变形~给了一个Bitmap class,然后找connected component需要记下每一个component size,最后return median
上来直接就是dfs了~找到每个connected component的大小,然后sort,返回median
follow up问如果map很大怎么办~dfs会导致stack上面有O(n)的function call问能不能iteratively解决~一下子没想出iterative怎么写~直接改成了bfs和queue~也可以解决stackoverflow的问题~
深入讨论了一下time complexity~求好运~希望能够有next step~~