楼主: alucardzhou
跳转到指定楼层
上一主题 下一主题
收起左侧

Jet 电面(Karat 外包面试)

🔗
genius1wjc 2016-9-13 05:20:54 | 只看该作者
全局:
alucardzhou 发表于 2016-9-10 04:01
我是用的binary search。index = n x m。转坐标就是 matrix

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

使用道具 举报

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

使用道具 举报

🔗
 楼主| alucardzhou 2016-9-13 08:43:40 | 只看该作者
全局:
glaciersilent 发表于 2016-9-12 17:17
对follow-up, 如果不要求保持原来的矩阵不变的话,还可以在遍历的时候,每遇到一个0,在找长、宽、顶点的过 ...

这个想法不错。
回复

使用道具 举报

🔗
 楼主| alucardzhou 2016-9-13 08:53:17 | 只看该作者
全局:
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),但还是稍微快点。
回复

使用道具 举报

🔗
genius1wjc 2016-9-13 09:00:39 | 只看该作者
全局:
alucardzhou 发表于 2016-9-13 08:53
仔细一想,貌似我的描述有欠缺啊。
那个面试官还点头说对。
我去...

嗯啊,这样我就大概想明白了,确实这样会快一些!谢谢楼主解答!
回复

使用道具 举报

🔗
gretchency 2016-9-15 21:53:57 | 只看该作者
全局:
小白想问一下如果是1 怎么向两边同时二分呢, 我理解的二分是可以去掉一半? 谢谢啦!
回复

使用道具 举报

🔗
 楼主| alucardzhou 2016-9-15 22:08:06 | 只看该作者
全局:
gretchency 发表于 2016-9-15 08:53
小白想问一下如果是1 怎么向两边同时二分呢, 我理解的二分是可以去掉一半? 谢谢啦!

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

使用道具 举报

🔗
haiweiosu 2016-9-28 06:12:30 | 只看该作者
全局:
楼主, 我刚刚收到Jet.com的Karat面试。 你感觉他们面试难度怎么样?
回复

使用道具 举报

🔗
 楼主| alucardzhou 2016-9-28 09:23:04 | 只看该作者
全局:
haiweiosu 发表于 2016-9-27 17:12
楼主, 我刚刚收到Jet.com的Karat面试。 你感觉他们面试难度怎么样?

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

使用道具 举报

🔗
haiweiosu 2016-9-28 10:58:50 | 只看该作者
全局:
alucardzhou 发表于 2016-9-27 20:23
难度算中等吧。一定要注意时间,他们卡时间的,时间一到绝对不让你写了。然后不怎么给hint。他们的目标是 ...

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表