谷歌匹兹堡onsite

10月中谷歌匹兹堡面的，一共四轮，每轮45分钟，中午还带着吃顿饭。

第一轮: 给你list of string s, int k, 一个score function是对每个string返回一个int的评分, 让你返回前k高评分的list of string, 其中s里面可能有重复的.
解法：我先用了一个map，key是评分，value是list of string(对不同string同分的情况)，然后自然就排序了，但这样时间复杂度o(nlogn). 之后写了更好的一个方法是用priority_queue按评分排序, 一直保持里面有k个元素，这样时

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

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

，最后要拿最多钱
思路：关键要想到统计字母在所有word里出现频率，然后选那个字母出现频率最高的word选，o(n)时间就可以选出来，我当时想到的类似但不是o(n)时间，出来才想到o(n)解法


面试过程中各个面试官全程冰块脸，没啥feedback，感觉好难受...

最后求分...

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

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

hychin 发表于 2017-11-18 05:54
前两轮不难

第三轮，你说的是pointer == len of char list吧？

第三轮，是指的考虑的那个string word的length。然后第四轮这题的意思是只要包含字母就算，不考虑位置，然后返回的时候会告诉你位置。

hychin 发表于 2017-11-18 05:54
前两轮不难

第三轮，你说的是pointer == len of char list吧？

第三轮，是指的考虑的那个string word的length。然后第四轮这题的意思是只要包含字母就算，不考虑位置，然后返回的时候会告诉你位置。

前两轮不难

第三轮，你说的是pointer == len of char list吧？
第四轮， smart为啥返回 t_r_s?  位置不是和tries不符合吗？

hychin 发表于 2017-11-18 05:54
前两轮不难

第三轮，你说的是pointer == len of char list吧？

第三轮，是指的考虑的那个string word的length。然后第四轮这题的意思是只要包含字母就算，不考虑位置，然后返回的时候会告诉你位置。

谢谢分享，第四轮还挺有意思的，只是不太明白o(n)时间这个点，长度只有5，暴力试也是o(n)的吧，一开始10000$，所以最多可以试10次，不过你的思路应该是对的，最多试6次就可以找到答案了

hongweiz 发表于 2017-11-18 15:11
谢谢分享，第四轮还挺有意思的，只是不太明白o(n)时间这个点，长度只有5，暴力试也是o(n)的吧，一开始10000 ...

为什么最多试6次就可以找到答案了？能说详细点吗

sansi 发表于 2017-11-18 16:47
为什么最多试6次就可以找到答案了？能说详细点吗

后来仔细想了一下，6次是理想情况，最坏要比6次多很多。

第四轮这个能猜得words是给定的并且存在array里的吧，既然不能随便猜，和字母频率有什么关系？
如果可以随便猜得话，26个字母6次试完一定出结果，那就是O(1)了。那这题就没意义了。

前两天去bakery square玩了一圈，突然好想申请……