狗家onsite

第二题 平均数的话只能全加起来再除吧？ O(N) 然后中位数就是quick select第k/2大的元素也是O(N)
第三题 楼主BFS的思路能说下嘛？
第四题 矩阵只有0和1，走到海洋就是走到矩阵的边界么？可不可以这么做看到陆地的点就DFS下，看有没有一条全是1的路径走到边界？
第五题 是LC346吗？
祝楼主好运

cherie_0921 发表于 2016-8-26 03:55
没有特别的trick，就是要写BFS和DFS两种，然后比较tradeoff

想不出这个题怎么BSF。。

族谱有parent指针么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

haoshenxiong 发表于 2016-8-26 11:49
想不出这个题怎么BSF。。

我也觉得很奇怪，这个题抽象出来应该是找数的公共祖先，不知道怎么BFS，有一个可能性是有PARENT指针，这样可以把树节点看成一个无向图，然后BFS，看他们最先在哪里相遇

南慕伦 发表于 2016-8-26 01:25
1. BFS?
2.中位数是线性时间选择？
3. 如果只有一个查询DFS BFS都可以吧，不过感觉后序遍历是最好的…… ...

4题应该是在边界先找河流的点（1），然后BFS把所有的可以到达的河流的点都标记为可以到海洋吧