骨骼 onsite

10. 25号面的谷歌
1. 一个印度大叔，迟到了20分钟，做题前又闲聊了7分钟，然后剩下20分钟做题，就是给一个词典，然后给一个prefix，查找所有prefix下的所有词语，就是word completion填词游戏，顺利

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

？？？？）然后非得让我答，然而根本没法写代码，大叔自己都不确定该怎么写，哎，感觉要凉，

地里的各位怎么看这个情况，可以要求加面吗.....

守望者bird 发表于 2018-10-28 06:10
你有一个词典(new, to, tonight, total, today, tasd,rfe,ref,wef,hn,wfwe)，就是一个人输入几个字母(相 ...

楼主这题感觉就是LC 原题流丝尔 Auto complete

守望者bird 发表于 2018-10-28 06:49
hashmap key那个是一个方法，但是问题在于，如果range 普遍较大，空间复杂度会很高，而且每个位置都得存 ...

sorry， 我没能看懂你说的二分+优化的方法，能不能详细解释一下或者举个例子？
我有一种不同的做法：将每个range拆成两部分，比如[start, end]这个范围，拆成(start, (1, rangeid)), (end, (-1, rangeid))这两个pair，然后给所有的pair排序
排序之后从头开始扫描，到每个pair处更新目前为止有多少个range还没有结束((1, rangeid)出现过了但是(-1,rangeid)还没有出现)
那么每到一个位置我们都知道覆盖前一个位置与前面一个位置的range有哪些，同时看哪些点在当前这个subrange里面就可以了(这部分可以优化，因为给定的所有点也可以排序并从头扫描)
时间复杂度在O(nlgn)
举个例子啊(1,9) (4, 10) 拆分之后就是(1,(1,0)), (4,(1,1)), (9,(-1, 0)), (10,(-1, 1))

zhengxixiao827 发表于 2018-10-28 05:55
咦 我咋感觉面试官说不定会因为自己准备不足or迟到给lz评价打高一些 lz可以详细说说第三题嘛以及第二题的fo ...

第二题的follow up类似于，假设A告诉B一件事就是A->B， 给定一串A->B, A->C, A->D, A->E, E->D, E->F, B->F, 之类的，被告诉的人可以被重复告诉， 然后让你返回第一轮被告诉的人里面（对于这个case，第一轮被告诉的人是B, C, D, E）， 拥有最大非重复孩子数（就是A->E, E->D, 所以e,d都是a的孩子，有可能有人被重复告诉）的人
第三题给一堆range (1, 9), (2, 100), (5, 7)未排序的，再给一串点9， 19，54...返回每一个点在哪些range里面，比如说9，则返回（1，9），（2，100）.....是一个让不断优化的题目....

咦 我咋感觉面试官说不定会因为自己准备不足or迟到给lz评价打高一些 lz可以详细说说第三题嘛以及第二题的followup是啥？祝楼主拿offer！

请问一下word completion是什么呀。顺祝offer~

FML 发表于 2018-10-28 05:56
请问一下word completion是什么呀。顺祝offer~

你有一个词典(new, to, tonight, total, today, tasd,rfe,ref,wef,hn,wfwe)，就是一个人输入几个字母(相当于prefix）, 然后你要返回一堆数，然后预测用户想要哪个数，比如你输入to,然后应该返回to, tonight, total, today

没碰到一个lc的题目，和面经题目，狗家考的很灵活......

守望者bird 发表于 2018-10-28 06:07
第二题的follow up类似于，假设A告诉B一件事就是A->B， 给定一串A->B, A->C, A->D, A->E, E->D, E->F, B- ...

楼主的意思是第二题的follow up答案应该是
B C?

第三题我首先想到排序 + 二分
按照start 排序， 也按照start 二分

或者做一个 hash map key：number value： range list which hold the value.
这样对于每个查询， 可以立刻返回。

再优化可以将range overlap的 合并 成一个独立的range， 为key， value： original range list hold that range.

这样处理过的range就没有overlap了， 同样可以排序 二分查找 然后一步定位。

不知大家还有其他方法没？

0_- 发表于 2018-10-28 06:39
楼主的意思是第二题的follow up答案应该是
B C?

hashmap key那个是一个方法，但是问题在于，如果range 普遍较大，空间复杂度会很高，而且每个位置都得存有的range，当range变成（1， 10000）， （2， 10000）， （3， 10000）....时，生成这个结构就需要range * 2的复杂度，会非常大，所以采用二分法那个加优化比较好，保持一个以start排好序的list of pairs, 然后二分找到那个midpoint，在保持一个gaps的list，记录到当前这个位置出现过的最大gap, 用left.start + 当前max(gap)再做一个二分查找

最怕这种面试官了

jtzgz 发表于 2018-10-28 06:53
最怕这种面试官了

握爪，赞同啊，哎