Google Intern 面经 20150112

gg的Host match真心拖啊拖

进pool11周了

kurtwang 发表于 2015-2-23 08:27
进pool11周了

哎 。。。 还没有一个host来联系

eval 发表于 2015-2-22 23:32
哎 。。。 还没有一个host来联系

我是1月15日电面的，也是到现在还没有host matching interview。同等待中，，，

中庸人90 发表于 2015-2-23 06:11
先统计每个char的个数，如果有count > (size+1)/2, 那就是invalid的。然后剩下的就不会了。。求问怎么做 ...

就是先构造一个符合要求的字符串，然后再随机化。随机化的过程和普通随机化的一样，扫一遍就行。构造符合要求的字符串可以对每个元素都扫一遍整个数组然后找到合适的switch， 然后处理下一个。这样的话是O(n square)。其实可以做到O(n). 统计出来每种的个数之后两两配对产生合理的字符串， 这样应该就是线性的了。

will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串，然后再随机化。随机化的过程和普通随机化的一样，扫一遍就行。构造符合 ...

我之前想的是用一个数组(size 26)保存每个字符和该字符出现的次数，求下一个字符就是对刚插入的字符以外的所有字符random select一个，然后插入，并且次数减一，如此迭代直到所有字符插入完毕。这样是O(n),但是貌似不满足randomly shuffle，因为random select 是对26种字符，而不是对所有字符。不知道这样对不对？

will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串，然后再随机化。随机化的过程和普通随机化的一样，扫一遍就行。构造符合 ...

多谢！！紫薯紫薯紫薯。。

第二题是不是可以用贪心做？
先记录每个字符出现的次数，即该字符需要被填入生成字符串的次数
然后从第一位开始填空
然后每次从剩下的字母堆中选取剩余待填入次数最多、且与前一位字符不冲突的字符填入，这样可以确保剩余可填写的不同字符种类是最多的
如果没有其他不冲突的待填写字符就报错
最多是O(26n)或O(256n)

yhzn 发表于 2015-2-26 03:23
第二题是不是可以用贪心做？
先记录每个字符出现的次数，即该字符需要被填入生成字符串的次数
然后从第一 ...

感觉很对！

will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串，然后再随机化。随机化的过程和普通随机化的一样，扫一遍就行。构造符合 ...

就是先构造一个符合要求的字符串，然后再随机化.随机化怎么保证相邻字母不等？比如， 符合要求的字符串为“abab”，怎么随机化？