一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
123
返回列表 发新帖
楼主: 匿名
收起左侧

狗家vo以及统计timeline

[复制链接] |试试Instant~ |美国面经, 面试经验, google, 码农类general
我的人缘0
jessica007 2020-5-8 01:31:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
楼主,恭喜拿到offer。 我想问一下,第二题的follow up,是给四组interval, 每组的interval是没有overlap的。然后给你一个interval,问你是不是可以插入到其中某一个组里,保证没有interval? 没太明白,压缩四组interval是什么意思,压缩了之后可以找到四个interval都overlap的interval,但是具体到每一个interval,不是还需要一组组的去二分查找吗?a [1,3] b [2,4] c [2,4] d [2,4] 比如这种情况,虽然压缩了之后【2,3】肯定是不能往里加的。但是如果给【4,5】的话,不是还需要每个组都要比一遍吗?谢谢楼主。已经加米!!
回复 微信

使用道具 举报

我的人缘0
Jimmy123 2020-5-11 07:23:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (84)
 
 
1% (1)    👎
请问楼主能不能再详细描述一下第一个follow up union find 具体是怎么操作? 还没看明白要怎么进行Union。能否举个例子。谢谢
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (97)
 
 
3% (4)    👎
請問一下第四題 既然是unsorted的 就不能用 Binary Search 那要怎樣才能小於O(n) 呢? 我也是用Python沒想到啥好方法
回复

使用道具 举报

地里的匿名用户
地里的匿名用户  发表于 2020-5-12 07:20:50
本楼: 👍   0% (0)
 
 
0% (0)   👎
jessica007 发表于 2020-5-8 01:31
楼主,恭喜拿到offer。 我想问一下,第二题的follow up,是给四组interval, 每组的interval是没有overlap ...

只要有任意一个不重合的就可以,所以压缩之后为[2,3], [4,5]只需要跟[2,3]比就好了

回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   82% (268)
 
 
17% (56)    👎
黑人不是牙膏 发表于 2020-5-2 04:20
请问楼主第四题list是sorted么?有其他限制条件么?没有的话岂不是就直接traverse么。。。2333

第五题没 ...

第四题start end是index啊。。这个是segment tree最简单的应用之一。。
感觉问这个题不厚道啊。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (363)
 
 
5% (20)    👎
Diamond_dogs 发表于 2020-5-19 07:51
第四题start end是index啊。。这个是segment tree最简单的应用之一。。
感觉问这个题不厚道啊。

我segment tree刷题一直跳过的。。。不是传言几乎不会考么 哭了。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   82% (268)
 
 
17% (56)    👎
黑人不是牙膏 发表于 2020-5-19 07:54
我segment tree刷题一直跳过的。。。不是传言几乎不会考么 哭了。

按理说是不会特意考。但是很多恶心题能用segment tree的时候,讨巧用一下肯定没问题,比如贴海报,或者天际线。感觉实现起来要写很多代码,如果作为follow up的话,应该讲一下用的思路就好。我是手残30分钟肯定写不完。

这个题,感觉不用线段树暂时没想到好方法。毕竟区间查询是线段树最典型的应用了。

评分

参与人数 1大米 +2 收起 理由
黑人不是牙膏 + 2 很有用的信息!

查看全部评分

去Fiverr找HR修改简历

去Fiverr找HR修改简历!
            
回复

使用道具 举报

地里的匿名用户
地里的匿名用户  发表于 4 天前
本楼: 👍   0% (0)
 
 
0% (0)   👎
本帖最后由 匿名 于 2020-5-22 04:59 编辑
匿名者 发表于 2020-5-12 07:20
只要有任意一个不重合的就可以,所以压缩之后为[2,3], [4,5]只需要跟[2,3]比就好了

楼主 Q2 followup 还是有一些问题, 是只要有一个list能插进去就行还是4个都能插入才行呢?比如,你之前的例子
[1,3]
[2,4]
[2,4]
[2,4]
给interval [4,5] 结果是true 还是false 呀?

(如果是要求四个组都能插进去的话 岂不是就是将四个组的interval 全merge就好?)
按照你压缩组找四个组overlapping区间的办法,比如:
[1,4]
[1,2]
[2,3]
[1,4]
压缩后没有公共区间。如果想插入[1,4],那岂不是return true了?而正确答案是false呀
望解答!


回复

使用道具 举报

我的人缘0
jtzgz 前天 09:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   79% (377)
 
 
20% (100)    👎
第一题,第四题,求leetcode的题号。谢谢。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-5-26 14:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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