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

Google 电面

全局:

2018(4-6月) 码农类General 硕士 全职@google - Other - 技术电面  | | Other | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
题目我之前没见到过,希望大家一起讨论一下最优解法。
您好!
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies


请大家来讨论一下。


补充内容 (2018-6-13 09:24):
好几个同学说看不到,那我把分数降一降吧
您好!
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies


补充内容 (2018-6-13 09:25):
[/hide=120]我当时做的是n^2的,结果是加面了,所以我想和大家讨论一下,看是否有nlogn的做法[/hide]

补充内容 (2018-6-17 07:11):
根据目前大家的讨论,应该是没法nlogn内完成的,不过如果有觉得可行的具体解法欢迎写出来讨论

补充内容 (2018-6-17 07:13):
再补充一下,上面说的没法nlogn完成是指的没有办法用常见的算法在面试时间内完成, magicsets 同学给出了一篇论文,使用了比较复杂的算法能够在nlogn时间内完成,感兴趣的同学可以下载来看看。

评分

参与人数 4大米 +8 收起 理由
Anakin09 + 1 给你点个赞!
happyrabbit + 3 给你点个赞!
dnullptr + 3 给你点个赞!
chillin1017 + 1 很有用的信息!

查看全部评分


上一篇:vm凉凉电面
下一篇:BB昂赛跪经
推荐
aiyawocao 2018-6-14 12:24:39 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

推荐
magicsets 2018-6-14 14:10:11 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

推荐
 楼主| yangdaxian 2018-6-16 12:19:17 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
chillin1017 2018-6-13 06:42:43 | 只看该作者
全局:
利口把伞溜是矩阵重叠

堵路我只能想出O(n^2)的还不好实现,碰到这种映射的就不会......

求大神指教

感谢分享!

补充内容 (2018-6-13 08:08):
将矩阵按y排序 沿着y轴从下往上扫 前一个矩阵如果和后一个矩阵overlap就save后一个矩阵 再往上找 想了很久 我只能想到O(n^2)的 哎
回复

使用道具 举报

无效楼层,该帖已经被删除
无效楼层,该帖已经被删除
无效楼层,该帖已经被删除
🔗
hyforever 2018-6-13 08:37:16 | 只看该作者
全局:
是不是相当于合并多个y值区间,然后判断0-1这个区间在不在合并的区间内?  时间nlogn行么?
回复

使用道具 举报

🔗
devilnut 2018-6-13 08:49:48 | 只看该作者
全局:
堵路的如果没理解错 可以union find找所有连通集团 然后看连通集团y轴的跨度是否cover了0到1 这样每个矩形过一遍就可以了
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
devilnut 2018-6-13 09:02:53 | 只看该作者
全局:
devilnut 发表于 2018-6-13 08:49
堵路的如果没理解错 可以union find找所有连通集团 然后看连通集团y轴的跨度是否cover了0到1 这样每个矩形 ...

不好意思 请无视……
回复

使用道具 举报

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

本版积分规则

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