google电面+onsite+加面

楼主能说一下onsite 6 在多线程的时候该怎么做吗？ 多谢！

阿满 发表于 2016-9-16 02:19
楼主能说一下onsite 6 在多线程的时候该怎么做吗？ 多谢！

我现在还不会做。。

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

求大神解惑。

Onsite-3 是赠券收集者问题？ https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

请问phone第二题，就是类似merge k sorted list的样子吗
加面第一题，请问是给的2个数还是数组啊？有点没看明白题目。
谢谢啦～各种bless!!!

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之前。

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

leonardcohen 发表于 2016-9-16 23:42
LZ 's information:
phone第二题：
十个人赛跑，有好几个裁判。每个裁判提供一部分人的到达终点的前后顺 ...

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

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)来的

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