楼主: 谁的时延
跳转到指定楼层
上一主题 下一主题
收起左侧

Google onsite 面经

🔗
pyemma 2015-11-18 03:50:07 | 只看该作者
全局:
oneshot 发表于 2015-11-17 08:21
感谢楼主分享,第一道题,一个string里面有一个词放不下放到下一行,意思是这个词放到下一行吧?楼主当时是 ...

这到题如果想高效的写的话需要找到循环节
回复

使用道具 举报

🔗
面假空虚 2015-11-18 11:18:42 | 只看该作者
全局:
pyemma 发表于 2015-11-18 03:48
即使多于也不影响,留出预留空间放置意外

哪有你这样说的,多余了就是无意义地增加了计算量啊。
回复

使用道具 举报

🔗
宝贝忆彼岸 2015-11-18 11:36:18 | 只看该作者
全局:
bless LZ!请问第四轮O(N)解法是什么呀?
回复

使用道具 举报

🔗
pyemma 2015-11-20 16:41:41 | 只看该作者
全局:
面假空虚 发表于 2015-11-17 19:18
哪有你这样说的,多余了就是无意义地增加了计算量啊。

主要是有时候做除法down cut的时候可能会出个意外啥的
回复

使用道具 举报

🔗
curry97 2015-11-20 18:49:29 | 只看该作者
全局:
小小平民 发表于 2015-11-11 14:46
第四轮:map + linkedList 的解法是怎么做的啊?还是不太明白。
我的疑问是 map 的插入操作不是logN复杂 ...

可以用unordered_map吗?
回复

使用道具 举报

🔗
snail_914 2015-11-26 05:50:36 | 只看该作者
全局:
不知道楼主现在有结果了吗 保佑
关于第四轮, 不明白为什么不直接用HashSet 加双指针, 一个fast pointer正常遍历array, 一个slow来收缩array, slow标记过的部分都是没有重复的。 举个栗子, [2 3 3 4 3],
fast [2 ]
slow[2 ]
set(2)

fast [2 3]
slow[2 3]
set(2 3)

fast [2 3 3]
slow[2 3]
set(2 3)

fast [2 3 3 4]
slow[2 3 4]
set(2 3 4)

fast [2 3 3 4 3]
slow[2 3 4]
set(2 3 4)

回复

使用道具 举报

🔗
snail_914 2015-11-26 06:17:56 | 只看该作者
全局:
谁的时延 发表于 2015-11-10 10:04
第三题:
~  ~   ~   ~   ~   ~  ~
~  1   2   2   3  (5) *

请问楼主能够在解释清楚一点第三题吗? 每一个点前进路径会有什么限制呢?  
第五题应该是字符串重排, 要求相同字符的间距>k的变种题. 使用Heap可以快速解决。 大概是HashMap统计词频, Entry<Character, Integer> 作为item 放进Max Heap, 以Integer重复数量作为排序因子。 然后每次从Heap取出k个元素append到StringBuffer, Integer分别-1之后再放回Heap. 再取出K个entry重复就好了
回复

使用道具 举报

🔗
returning 2015-11-29 03:53:18 | 只看该作者
全局:
snail_914 发表于 2015-11-26 06:17
请问楼主能够在解释清楚一点第三题吗? 每一个点前进路径会有什么限制呢?  
第五题应该是字符串重排,  ...

第四题,为何需要双指针?如果可以用hashtable的话,那么直接从左到右遍历,如果当前的数重复出现,那么跳过,如果是第一次出现,那么把它向左移动就行了,每移动一次,更新一下index。

第五题,我看不懂你说的Heap取出k个元素append到stringbuffer,如果直接取k个最大的,那么如果保证这新的k个和前面的自身间隔大于k?我觉得还是用bst维护好一些,bst按照出现频率维护,频率大的在后面。另外一个hashtable维护前面k个已经出现的数,想要继续插入,就是在bst里面找出现频率最大的数,并且这个数没有在前面k个里面出现,找到之后,更新hasthtable,更新bst。用bst好处是,每次查找新插入的string,不需要真正取出string,只需要在bst里面从后向前走就行了。
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
bobzhang2004 2015-12-1 10:56:08 | 只看该作者
全局:
returning 发表于 2015-11-29 03:53
第四题,为何需要双指针?如果可以用hashtable的话,那么直接从左到右遍历,如果当前的数重复出现,那么 ...

第四题hashset就行了
回复

使用道具 举报

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

本版积分规则

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