Jet 电面（Karat 外包面试）

alucardzhou 发表于 2016-9-10 04:01
我是用的binary search。index = n x m。转坐标就是 matrix

想问一下楼主，binary search具体的做法是什么？如果`index = 0`和`index = n *m - 1`都是1的话，我们该如何divide这个matrix呢？

对follow-up, 如果不要求保持原来的矩阵不变的话，还可以在遍历的时候，每遇到一个0，在找长、宽、顶点的过程中把所有的0都变成2，然后接着遍历，这样就可以避免判断之后遇到的0是不是属于前面哪一个长方形，这样不增加复杂度和额外的空间。

glaciersilent 发表于 2016-9-12 17:17
对follow-up, 如果不要求保持原来的矩阵不变的话，还可以在遍历的时候，每遇到一个0，在找长、宽、顶点的过 ...

这个想法不错。

genius1wjc 发表于 2016-9-12 16:20
想问一下楼主，binary search具体的做法是什么？如果`index = 0`和`index = n *m - 1`都是1的话，我们该 ...

仔细一想，貌似我的描述有欠缺啊。
那个面试官还点头说对。
我去...

我的想法有点像，rotated sorted array with repeated element那题的二分法吧
每次都找中点看是不是0，如果不是就还是要在左右两部分接着找。目的只是找到这个0矩阵的任一点。
虽然最坏情况是O（n），但还是稍微快点。

alucardzhou 发表于 2016-9-13 08:53
仔细一想，貌似我的描述有欠缺啊。
那个面试官还点头说对。
我去...

嗯啊，这样我就大概想明白了，确实这样会快一些！谢谢楼主解答！

小白想问一下如果是1 怎么向两边同时二分呢， 我理解的二分是可以去掉一半？ 谢谢啦！

gretchency 发表于 2016-9-15 08:53
小白想问一下如果是1 怎么向两边同时二分呢， 我理解的二分是可以去掉一半？ 谢谢啦！

找到第一个点确实最坏是O（n），只是期望可以在logN。
另外找到第一个点后向上下左右找边界可以用binary search稍微优化一点。

楼主， 我刚刚收到Jet.com的Karat面试。 你感觉他们面试难度怎么样？

haiweiosu 发表于 2016-9-27 17:12
楼主， 我刚刚收到Jet.com的Karat面试。 你感觉他们面试难度怎么样？

难度算中等吧。一定要注意时间，他们卡时间的，时间一到绝对不让你写了。然后不怎么给hint。他们的目标是对每一个考生公平。所以感觉有点特别。

alucardzhou 发表于 2016-9-27 20:23
难度算中等吧。一定要注意时间，他们卡时间的，时间一到绝对不让你写了。然后不怎么给hint。他们的目标是 ...

非常感谢楼主回复！ 你知道Jet电面其他题目吗？ 地里面貌似就你po了。。。没有其他任何资源。。。