FB 电面 SDE intern

Job Hunting Interview
, , ,
1

输入 是2D array， 只有 0 和 1， 要求返回最左边的1 的Column index
input：
0 0 0 1
1 1 1 1
0 1 1 1
output：
0

add on： randomly return the 最左边的 1 的 position (row, column)
input：
0 0 0 1
1 1 1 1
1 1 1 1
0 1 1 1
output：
0
in multiple runs, it could return either {1, 0) or (2, 0 )

2

这是高频题了，用binary search或从右往左扫

1 Like
3

这个followup倒是第一次见到，那就意味着，有多个一样的最左的1的话，需要都找出来。可以参考random pick index的思路，用蓄水池算法做

参考 http://www.cnblogs.com/grandyang/p/5875509.html