脸 店面面经

面经如下：1. 一个二维矩阵，里面的数只有0和1，每一行如果有一个1， 那么这行之后的数都是1，然后问你对于这个二维矩阵第一个是

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

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

两道medium，但是仍然挂了，可能还是要bug free吧。

求大米，大家加油

第一题最优解法为O n

从矩阵的右上角开始判断是否为1
If 1, then move left
Else, then move down to keep test again.

除了都是0的情况，只要按照题目条件，有1存在矩阵中，最后所在的column就是最左面1所在的column.
线性扫描所以复杂度为On

hgon23 发表于 2020-3-10 13:40
[[0, 0, 0, 1],
[0, 1, 1, 1],
[0, 0, 1, 1],

对的，题目没有说都是sorted，的确这个例子应该是不可以的，当时我说是二分法，面试官就直接让我写了

hbwang 发表于 2020/03/08 01:40:08
第一题最优解法为O n

从矩阵的右上角开始判断是否为1
If 1, then move left
Else, then...

这道题最优解是你说的这个还是binary search要看输入数组的形状

请问楼主哟题号吗？感觉似曾相似。

没看明白第一个最后到底是要你在这个矩阵里用binary search找什么？第二个就是四久四吧

是要你在矩阵里找到一个第一column为1的矩阵？

如果不是sort的都是0或者1，那也只能一row一row的遍历啊

两道题都是facebook极高频题，第二题是expression add operators的简化版，电面出这两个题目，合格的candidate是要能够通过电面的

helloworld00 发表于 2020-3-8 01:08
没看明白第一个最后到底是要你在这个矩阵里用binary search找什么？第二个就是四久四吧

因为如果一行中出现1，那么这一行后面所有的数字都是1，所以可以用binary search啊。我取重中点，如果这一列中有1的话，那么我可以排除后一半了，所以可以用binary search

hbwang 发表于 2020-3-8 01:40
第一题最优解法为O n

从矩阵的右上角开始判断是否为1

对的，从右上角往左扫描，然后往下或者往右扫描，最后复杂度O(n)

楼主能透露一下题号或者再详细描述一下吗。。对于第一题的讨论真的很晕 万分感谢