Facebook电面

面试官是华人小美女，很nice~
题目是一个包含0和1的matrix，大概是这样[[0 1 1 1], [0 0 0

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

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

一次电面，还是太紧张了，最后很多corner case没写好。

wangyandan418 发表于 2018-12-9 06:38
哇，谢谢指点，具体怎么操作呢？

就从右上方开始找呀 如果是0的话 就往下走 说明这一行没什么好研究的了 如果是1的话 说明是potential col 就往左走咯一直走到底为0后然后再往下看 这算法很intuitive吧.. 老哥你纸上画一下就知道了

从右上开始找 复杂度可以优化到 O(row + col)

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

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

楼主，这题是不是每次对中间那一列进行线性扫描，如果发现1就然后继续在左侧的列中寻找；否则就在右侧的列中寻找；复杂度是row*log(col)

daidaixiong 发表于 2018-12-8 15:01
楼主，这题是不是每次对中间那一列进行线性扫描，如果发现1就然后继续在左侧的列中寻找；否则就在右侧的列 ...

是哈，针对每一行使用binary search，复杂度就是row*log(col)，要注意考虑某一行全零和整个matrix全零的情况

uggl233 发表于 2018-12-9 06:04
从右上开始找 复杂度可以优化到 O(row + col)

哇，谢谢指点，具体怎么操作呢？

wangyandan418 发表于 2018-12-9 06:38
哇，谢谢指点，具体怎么操作呢？

有帮助的话 加个米哈哈

uggl233 发表于 2018-12-9 14:30
就从右上方开始找呀 如果是0的话 就往下走 说明这一行没什么好研究的了 如果是1的话 说明是potential col ...

谢谢你啊!

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

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