一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 1627|回复: 9
收起左侧

G家全职电面

[复制链接] |试试Instant~ |关注本帖
rhett.lhy 发表于 2015-10-31 00:36:20 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
估计是onsite太挫了,被加了两轮电面:

第一轮:给一个0,1,?组成的字符串,其中?可以背替换成0和1,输出所有combination。比如输入是"0?1"的时候,输出["001", "011"]。题很水,做完之后就开始瞎扯淡了。然后他一边自己上网搜java api document一边问我java里hashmap default constructer的default capacity是多少,load factor是多少……

第二轮:设计一个LargeString class,要求支持一下操作:
insert(pos, s): 在位置pos插入一个string s
erase(pos, len): 删除[pos, pos+len-1]位置上的所有字符
replace(pos, s): 从pos开始依次把字符替换成s,其余的不变
. Waral 鍗氬鏈夋洿澶氭枃绔,
一开始没想到最优的,就写了个bucket的算法,然后时间复杂度是O(N/B) + O(B),N是large string的长度,B是bucket size,最优的时候B = sqrt(N),整个算法复杂度是O(sqrt (N))。然后面试官问能不能稍微改一点点地方让算法的时间复杂度降到logarithmic of N。然后我问他你的意思是不是把每一个bucket看成一个相似的子问题,所以整个construction就是:
S(1) = {single character}
S(2) = {S(1), S(1)}
S(3) = {S(2), S(2)}
...
就是S(1)的size是1,S(2)是2,S(3)是4,..., S(n)是2^n 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后找pos的时候,先找出来pos \in S(k),然后计算一下pos在S(k)中的relative position (= pos'),然后这个问题就变成了在{S(k-1),S(k-1)}中locate pos'。但是这样的时间复杂度貌似是log N + log(N/2) + log(N/4) + ... = O((log N)^2),也不是O(logN)啊。不过好在后面这些扩展小哥没让我写code,就是讨论了一下。

本帖被以下淘专辑推荐:

Ziyan 发表于 2015-10-31 01:03:11 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第二轮是不是能用segment tree来做 这样时间复杂度是不是就能达到O(logN)
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-10-31 01:08:12 | 显示全部楼层
关注一亩三分地微博:
Warald
Ziyan 发表于 2015-10-31 01:03. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二轮是不是能用segment tree来做 这样时间复杂度是不是就能达到O(logN)

啊对哈,我二了……线段树确实应该是O(logN)的……

补充内容 (2015-10-31 01:11):. more info on 1point3acres.com
唉当时咋没想起来用线段树呢……T_T
回复 支持 反对

使用道具 举报

liv073 发表于 2015-10-31 02:15:28 | 显示全部楼层
lz能稍微说一下第二题的bucket方法是什么样的吗?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-31 08:47:01 | 显示全部楼层
Ziyan 发表于 2015-10-31 01:03
第二轮是不是能用segment tree来做 这样时间复杂度是不是就能达到O(logN)

请问能不能说一下,用segmentTree具体怎么做呢?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-10-31 10:09:18 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-31 08:47
请问能不能说一下,用segmentTree具体怎么做呢?

把replace当作基础操作,然后insert和erase都可以基于replace实现
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-31 10:37:07 | 显示全部楼层
rhett.lhy 发表于 2015-10-31 10:09
把replace当作基础操作,然后insert和erase都可以基于replace实现
. more info on 1point3acres.com
谢谢回复,不过就是基本的怎么用segmenttree实现这个题没搞懂,请问这道题中的segmentTreeNode这个类里都有哪些变量?除了左右两个孩子,还有一个变量时string吗?范围怎么定义呢?
回复 支持 反对

使用道具 举报

leochen4891 发表于 2015-11-4 13:54:01 | 显示全部楼层
个人理解是用segmentTree存每个bucket的起始位置,然后通过pos找到bucket的时间是O(lgn)。bucket内部操作都是O(1)的
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-4 14:30:30 | 显示全部楼层
leochen4891 发表于 2015-11-4 13:54
个人理解是用segmentTree存每个bucket的起始位置,然后通过pos找到bucket的时间是O(lgn)。bucket内部操作都 ...

我这样理解不知道对不对:
比如一个string是abcdefg的话,那么第一层root就是 val = abcdefg,start=0,end=6;
第二层就是两个bucket,一个放abcd,一个放efg。。。。一直到叶子节点每个放一个字符
然后我就不知道比如说要删掉cde这一段怎么操作这个线段树呢?root上的值用不用改变呢?
回复 支持 反对

使用道具 举报

leochen4891 发表于 2015-11-4 15:12:10 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-4 14:30
我这样理解不知道对不对:
比如一个string是abcdefg的话,那么第一层root就是 val = abcdefg,start=0,en ...

这个LargeString,意思应该就是非常大所以不适合存在一整块内存里。
SegmentTree的每个叶子节点存的不是String,而是一个指向bucket的指针,每一个bucket里存整个LargeString的一部分。然后SetmentTree的目的是找Bucket。. Waral 鍗氬鏈夋洿澶氭枃绔,
比如root是0~10000,第二层是0~5000和5001~10000,所以对应两个bucket。. more info on 1point3acres.com
我没写代码实现,大致想了一下而已
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-4-24 12:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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