狗家onsite面经

回馈论坛，特分享上周五刚面完的狗家onsite面经。
LZ面的是博士的software engineer，总共5轮， 4轮coding＋1轮thesis。

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

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

今天收到hr说过了hiring committee了，接下来就是team match了。
最后求大米，谢谢了！！！！


补充内容 (2018-4-13 13:20):
Timeline:
2月底内推，然后3月初hr电话，约onsite。3月底onsite，一周内出结果过hc。team match花了一周左右，由于内推我的人就是我的未来老板，所以很快的。。。下周出offer。

wtcupup 发表于 2018-4-6 14:08
楼主能说下猜单词那题的思路嘛

先说可以解这个问题的算法：随便选一个单词W，然后guess它和秘密单词S的相似度，得到一个值。这里我们assume说字典的单词和秘密单词都是长度为5的（其实也不太重要啦）。然后把字典里所有的单词和W来算出它们的相似度，只有相似度和W和S的相似度（0～4，5就猜出来啦）相同的单词才有可能是S。接下来递归在筛选出来的那组单词里。

要尽量最少的次数的话，就要好好的选择这个W。因为我们不想调用太多次guess（W，S），但是我们可以算出W和其它单词的相似度。假设我们选定了某一个W，然后定义D0，D1，D2，D3，D4为和W相似度分别为0～4的单词组，那么最坏情况应该是S处在某个最大的group 里，比如说D0，如果D0的单词个数是最多的。于是乎我们可以iterate over每个单词W，求出每个单词最大的组数是多少，在这么多最大的组数里选个最小的。换句话就是求minmax。

markpen 发表于 2018-4-8 07:23
股票那题是不是用两个map，维持 prices 和 time stamps, 这样的话更新操作是O(lg n) ， 查询操作是O(1)。有 ...

就是这样。紫薯紫薯。

第五题我有一个很骚的做法，依次传入26个字符，这样你知道要你猜的单词由哪几个字母组成，然后遍历一遍字典，O(n)时间复杂度，O(1) extra space

请问lz在哪面的

blactangeri 发表于 2018-4-6 13:25
请问lz在哪面的

总部面的。

然后考虑如果matrix是sparse的情况下，如何去存储和回答query

请问lz这个怎么答比较好

然后考虑如果matrix是sparse的情况下，如何去存储和回答query

请问lz这个怎么答比较好

blactangeri 发表于 2018-4-6 13:32
然后考虑如果matrix是sparse的情况下，如何去存储和回答query

请问lz这个怎么答比较好

我面试的时候答的是用一个2维的hash table。row作为第一个维度的key，col作为第二个维度的key。这样可以只存储非零元素，但是query很慢。然后就把hash table变成了2维的balanced binary tree。用c++的语言来说就是从unordered_map 变成了map。这样子的话，query的复杂度变成了O(NZ + R log n), NZ is the number of non-zero elements in the query rectangle, R is the number of rows in the query rectangle. 本来以为还要改进的，但面试官说可以了。
后来再仔细一想， 你还可以提前把每一行的从第0列到第i 列的和给求出来，当然很多都是一样的因为很多的0， 但是只存储变化的那些sum，就是如果有一个非零元素，就存一个sum在那儿。然后每一行你可以binary search去决定这一样的和是多少。时间复杂度会降到O(R log n)。
至于有没有更好的，我还不知道，求指导。

楼主能说下猜单词那题的思路嘛

谢谢解答，你说的2维的hash table就是指Map<row, Map<col, val>>吧

blactangeri 发表于 2018-4-6 14:15
谢谢解答，你说的2维的hash table就是指Map吧

是的，就是这样。紫薯紫薯。。。。。。