1/5 Google 面经

1/5 Google一面（A）
面试官是一位印度人，口音有点重，全程沟通有点费力。
上来直接coding。
第一题是double类型的sqrt. 我用模板写的，while退出后check left和right，被面试官指出应该返回mid。
Follow-up:你的程序如何handle input小于1的情况？复杂度？
第二题：给你一个字典，一个string，找出字典中这个string的最长subsequence，面试官一直在强调这个dict很大。我想了一下说可以iterate through all the subsequences of the string。进一步，我说我们可以先找出dict中最长word的长度 L ，然后只iterate through长度为1～L的subsequence。全程讨论，最后没有时间写代码。
轮到我提问题：你觉得我作为学生在学校应该学什么？答：好好刷算法！

1/5 Google一面（B）
面试官是一位美国人，沟通很顺畅。
上来直接coding。面试官说他准备了两道，如果我做的快的话就给我第二道，然而我最后只有时间做第一道。

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

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

轮到我提问题：我在学校里学的各种Design Pattern工作会用到吗？答：Everyday！

总的来说题很简单，但我并没答的很好求人品求大米！！

第二题应该先预处理string，因为dict特别大，做法是建一个map记录string里每个character出现的index，如果相同character有多个index就按升序排列

然后对于dict里的每个单词，按character顺序在map里查找最早可以出现的index，如果有就记录下这个index，再找下一个character，index查找可以binary search

寂寞的季节 发表于 2017-4-13 12:11
第二题应该先预处理string，因为dict特别大，做法是建一个map记录string里每个character出现的index，如果 ...

直接对每个位置每个单词都维护一个nextindex就好了，比如说nextindex[23]['a']=25这样的

spiritrhy 发表于 2017-2-3 14:33
我觉得一面的第二题面试官是想先把String的所有subseq 放到trie里，然后在用iterator遍历字典里的每一个wor ...

这样岂不是很多很多？而且面试官也强调了，这个dict会很大的

请问第一题follow up和第二题楼主能再讲讲不

第一题可以用trie存字典吗？然后找字典中以string的每个character开始的最长子串？

第一题可以用牛顿法么？
第二题用Trie做

所以楼主二分用left, right，面试官觉得看着不对吗？

我觉得一面的第二题面试官是想先把String的所有subseq 放到trie里，然后在用iterator遍历字典里的每一个word去trie里查找，更新max。

谢谢楼主分享，

可以问问楼主interval 相减的题目是什么意思？ 怎样叫interval相减？