楼主: eval
跳转到指定楼层
上一主题 下一主题
收起左侧

Google Intern 面经 20150112

全局:
gg的Host match真心拖啊拖
回复

使用道具 举报

🔗
kurtwang 2015-2-23 08:27:28 | 只看该作者
全局:
进pool11周了
回复

使用道具 举报

🔗
 楼主| eval 2015-2-23 12:32:14 | 只看该作者
全局:

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

使用道具 举报

🔗
yourway 2015-2-24 01:37:08 | 只看该作者
全局:
eval 发表于 2015-2-22 23:32
哎 。。。 还没有一个host来联系

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

使用道具 举报

🔗
will_ym 2015-2-24 03:09:43 | 只看该作者
全局:
中庸人90 发表于 2015-2-23 06:11
先统计每个char的个数,如果有count > (size+1)/2, 那就是invalid的。然后剩下的就不会了。。求问怎么做 ...

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

使用道具 举报

🔗
中庸人90 2015-2-24 04:01:41 | 只看该作者
全局:
will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串,然后再随机化。随机化的过程和普通随机化的一样,扫一遍就行。构造符合 ...

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

使用道具 举报

🔗
中庸人90 2015-2-24 04:02:26 | 只看该作者
全局:
will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串,然后再随机化。随机化的过程和普通随机化的一样,扫一遍就行。构造符合 ...

多谢!!紫薯紫薯紫薯。。
回复

使用道具 举报

🔗
yhzn 2015-2-26 03:23:51 | 只看该作者
全局:
第二题是不是可以用贪心做?
先记录每个字符出现的次数,即该字符需要被填入生成字符串的次数
然后从第一位开始填空
然后每次从剩下的字母堆中选取剩余待填入次数最多、且与前一位字符不冲突的字符填入,这样可以确保剩余可填写的不同字符种类是最多的
如果没有其他不冲突的待填写字符就报错
最多是O(26n)或O(256n)
回复

使用道具 举报

🔗
samantha_kr 2015-2-27 02:53:07 | 只看该作者
全局:
yhzn 发表于 2015-2-26 03:23
第二题是不是可以用贪心做?
先记录每个字符出现的次数,即该字符需要被填入生成字符串的次数
然后从第一 ...

感觉很对!
回复

使用道具 举报

🔗
mm豆 2015-4-6 06:24:46 | 只看该作者
全局:
will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串,然后再随机化。随机化的过程和普通随机化的一样,扫一遍就行。构造符合 ...

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表