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

google电面+onsite+加面

🔗
阿满 2016-9-16 02:19:02 | 只看该作者
全局:
楼主能说一下onsite 6 在多线程的时候该怎么做吗? 多谢!
回复

使用道具 举报

🔗
 楼主| hcheng81 2016-9-16 03:06:44 | 只看该作者
全局:
阿满 发表于 2016-9-16 02:19
楼主能说一下onsite 6 在多线程的时候该怎么做吗? 多谢!

我现在还不会做。。

他提示说应该用一个像buffer一样的东西。

求大神解惑。
回复

使用道具 举报

🔗
lingeast 2016-9-16 09:18:59 | 只看该作者
全局:
Onsite-3 是赠券收集者问题? https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
回复

使用道具 举报

🔗
pinkdatura 2016-9-16 13:58:36 | 只看该作者
全局:
请问phone第二题,就是类似merge k sorted list的样子吗
加面第一题,请问是给的2个数还是数组啊?有点没看明白题目。
谢谢啦~各种bless!!!
回复

使用道具 举报

🔗
 楼主| hcheng81 2016-9-16 22:01:19 | 只看该作者
全局:
pinkdatura 发表于 2016-9-16 13:58
请问phone第二题,就是类似merge k sorted list的样子吗
加面第一题,请问是给的2个数还是数组啊?有点没 ...

phone 第二题:

第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3
第二个裁判给的结果是:参赛者到终点顺序为:9 6 5 4
第三个裁判给的结果是:参赛者到终点顺序为:2 8 1

。。。

求最终顺序。


------------------------------------------------


加面第一题,我写的不是很清楚不好意思。。。

输入是一个数组[2, 7],输出应该是一个list的数组。

规则是这个数组里的每一个数两两相减,所得的新数append在后面

比如[2, 7] 会变成 [2, 7, 5]

[2, 7, 5] 会变成 [2, 7, 5,3]

[2,7,5,3] either变成 [2,7,5,3,1] 或者 [2,7,5,3,4]

[2,7,5,3,1] -〉[2,7,5,3,1, 6] 或者 [2,7,5,3,1, 4] -〉[2,7,5,3,1, 6, 4]  或者 [2,7,5,3,1,4,6]

[2,7,5,3,4] -〉 [2,7,5,3,4,1] -〉[2,7,5,3,4,1,6]

以此类推,到最后没有数字可以往上加了的时候停止,求所有的组合。红字为结果。

补充内容 (2016-9-16 22:02):
[2,7,5,3,1,4,6]  这个也是结果,上面忘记加红色了。

补充内容 (2016-9-16 22:13):

第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3


这个意思是,选手2在选手9 之前到达终点,选手9在选手4之前,选手4在选手3之前。
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
leonardcohen 2016-9-16 23:42:04 | 只看该作者
全局:
LZ 's information:
phone第二题:
十个人赛跑,有好几个裁判。每个裁判提供一部分人的到达终点的前后顺序。
问怎么得出完整结果。
第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3
这个意思是,选手2在选手9 之前到达终点,选手9在选手4之前,选手4在选手3之前。

My guess and solution, could LZ verify below is right or not:
Question: give you partly relative sequence to get whole sort sequence
give you 7518, 6718, 9436, 2967  to get : 294367518
Solution pseudo  code :
initial array [1,2,3,4,5,6,7,8,9]
while the relative position in [7518, 6718, 9436, 2967] is not same as the relative position in array:
swap the element in array to make sure the relative position in array is same as in [7518, 6718, 9436, 2967]

123456789 + 7518 --> 723456189 + 6718 --> 623457189 + 9436 --> 923457186 + 2967 (first round finish)--> 293456187 + 7518 (second round begin) --> 293476518 + 6718 --> 293467518 + 9436 --> 294367518 (bingo!)

It really hard.


补充内容 (2016-9-17 01:12):
This solution come out from myself is Naive.
Here is the right solution:
http://stackoverflow.com/questio ... nown-order-sequence
Google ask this in phone, OMG
回复

使用道具 举报

🔗
amszhou 2016-9-17 00:36:26 | 只看该作者
全局:
leonardcohen 发表于 2016-9-16 23:42
LZ 's information:
phone第二题:
十个人赛跑,有好几个裁判。每个裁判提供一部分人的到达终点的前后顺 ...

粗暴一点,topology sort,应该没问题
回复

使用道具 举报

🔗
domofeng 2016-9-17 11:31:01 | 只看该作者
全局:
hcheng81 发表于 2016-9-16 22:01
phone 第二题:

第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3

谢谢楼主这么详细的说明, 有个小问题

[2,7,5,3,1, 4] -> [2,7,5,3,1,4,6]

这个应该出不来吧, 因为,  [2,7,5,3,1, 4], 4和前面任意数的差都达不到6.

此外, 此题还应该注意hash去重, 否则在构造
[2,7,5,3,4]时候会有2个[2,7,5,3,4,1], 一个是从abs(4-5)来的, 一个是从abs(4-3)来的

回复

使用道具 举报

🔗
 楼主| hcheng81 2016-9-17 13:32:40 | 只看该作者
全局:
domofeng 发表于 2016-9-17 11:31
谢谢楼主这么详细的说明, 有个小问题

[2,7,5,3,1, 4] -> [2,7,5,3,1,4,6]

是两两相减

2,7,5,3,1,4 里 1和7可以变成6
回复

使用道具 举报

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

本版积分规则

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