一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3505|回复: 21
收起左侧

Google Phone Interview

[复制链接] |试试Instant~ |关注本帖
ninacc 发表于 2016-1-12 10:31:51 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
45分钟就面了这一道题,一开始听到Round Robin Schedule这三个词以为是亚麻OA里的题目,其实一点不一样。 题目大概是这样:给一个Game的schedule, 里面有每一个round和在这个round里面互相compete的players,比如

Round1 A-B C-D
Round2 A-D B-C.鐣欏璁哄潧-涓浜-涓夊垎鍦

这个schedule应该满足
1. 每个player每一个round只能play一次
2. 每一个player必须和其他所有对手都compete一次
3. 安排的round数应该是最少的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

返回一个boolean值,看此Game schedule是不是valid的。

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴



本帖被以下淘专辑推荐:

pawprinter 发表于 2016-8-17 13:57:27 | 显示全部楼层
william_gong 发表于 2016-8-17 13:49
如何证明一定可达呢?

偶数个人,一共 n * (n - 1) / 2场比赛,n为偶数时每轮 n / 2场,那么一共n - 1轮。如果是奇数,每轮 (n - 1) / 2场,一共n轮。
-google 1point3acres
补充内容 (2016-8-17 13:57):
前面的偶数个人去掉,打多了
回复 支持 1 反对 0

使用道具 举报

jmnjmnjmn 发表于 2016-1-12 10:44:21 | 显示全部楼层
没见过这题
回复 支持 反对

使用道具 举报

 楼主| ninacc 发表于 2016-1-12 12:11:05 | 显示全部楼层

嗯 是啊我也没见,我同学说他竟然看过这题....
回复 支持 反对

使用道具 举报

neverlandly 发表于 2016-1-12 12:23:05 | 显示全部楼层
楼主能讲一讲你做的思路吗?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-12 12:38:04 | 显示全部楼层
最少round数是不是n - 1 啊
回复 支持 反对

使用道具 举报

cnsudo 发表于 2016-1-12 15:00:03 | 显示全部楼层
哎呀好难啊好难啊,看得我头都炸了。。。
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-12 15:04:18 | 显示全部楼层
最少round 算法因该是要知道一个round 有几组可以compete吧?
回复 支持 反对

使用道具 举报

starcroce 发表于 2016-1-12 15:19:03 | 显示全部楼层
round数少于n-1直接false
建hash table,key是player1,value是set of player2
对于每个round,把a-b这样的配对放进hash table,如果某个player出现多于一次,返回false
对于最后总的schedule,判断每个player是否跟其他所有都对局过

感觉用hash table根据题目要求直接干就好了。。不知道有没有什么其他优化。。。
回复 支持 反对

使用道具 举报

ludius 发表于 2016-1-12 15:24:46 | 显示全部楼层
Hashmap 就可以吧,hashset应该也行,for loop每个round,用个boolean array检查条件1,然后把每个都放到hashset,如果已经有了就return false,for loop一下有什么缺的,return false,一直走下来的就是true吧。不难吧,还是我理解错了呢...
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2016-1-13 00:32:47 | 显示全部楼层
ludius 发表于 2016-1-12 15:24
Hashmap 就可以吧,hashset应该也行,for loop每个round,用个boolean array检查条件1,然后把每个都放到ha ...

觉得考点主要是:.1point3acres缃
. visit 1point3acres.com for more.
1. min number of rounds. 如果是n is odd, min = n, otherwise(n is even) min = n-1
2. 每轮用hashset去重, 比如A-B, A-C由于A出现了,所以invalid
3. 检查invalid的match entry比如A-A B-B. From 1point 3acres bbs
4. hashmap保存所有已经出现的比赛,保证之后不出现
回复 支持 反对

使用道具 举报

echo33 发表于 2016-1-13 01:25:53 | 显示全部楼层
条件1很容易check

条件2和3加在一起,就是楼上说的1, 以及每轮都必须有floor(n/2)对,而且每对只出现一次

但是一开始是否知道总的比赛人数?

如果不知道的话要读到最后才知道,那还得回头去check一次-google 1point3acres
.1point3acres缃
或者像前面说的那样最后check每个player是否都跟其他对局过。
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2016-1-13 09:52:37 | 显示全部楼层
echo33 发表于 2016-1-13 01:25
条件1很容易check

条件2和3加在一起,就是楼上说的1, 以及每轮都必须有floor(n/2)对,而且每对只出现一 ...

我猜应该知道n,不然如果有一个人没有比赛,那么不知道是否valid. 比如n=3个人,却只有round: B-C,你没法从round看出来
回复 支持 反对

使用道具 举报

 楼主| ninacc 发表于 2016-1-13 10:56:16 | 显示全部楼层
大家好啊,不好意思来晚了。具体实现的时候当时时间不够了,没想到怎么把三个条件组合起来设计一个刁刁的数据结构,是一个个check的。 . Waral 鍗氬鏈夋洿澶氭枃绔,
第一个就是以建一个map1,以round为key,value 是一个set, 把每个round的player加进set, 重复了return false
第二个和第一个差不多建立map2,以player为key
第三个 是比较map1和map2的size

这题做的不是很好,其实不难,但是当时有点慌,电话接起来以后就等着面two sum了,真是那义务啊,大家加油!!!
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-14 14:56:22 | 显示全部楼层
ninacc 发表于 2016-1-13 10:56
大家好啊,不好意思来晚了。具体实现的时候当时时间不够了,没想到怎么把三个条件组合起来设计一个刁刁的数 ...

LZ 能说说为什么用map1 map2 size 的比较就能知道rule3吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 07:14:15 | 显示全部楼层
starcroce 发表于 2016-1-12 15:19
round数少于n-1直接false
建hash table,key是player1,value是set of player2
对于每个round,把a-b这样 ...

怎么知道是最少的呢?
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-1-25 12:21:50 | 显示全部楼层
nothingtrouble 发表于 2016-1-13 00:32.鐣欏璁哄潧-涓浜-涓夊垎鍦
觉得考点主要是:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1. min number of rounds. 如果是n is odd, min = n, otherwise(n is even) min = n- ...

如何能证明n是基数时,min = n, 偶数时 min=n-1 ?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-6 08:56:57 | 显示全部楼层
最少round数是要自己根据是数学关系总结出来吗
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-8-17 11:02:41 | 显示全部楼层
zoufengboy 发表于 2016-1-25 12:21
如何能证明n是基数时,min = n, 偶数时 min=n-1 ?

每轮只能打一个对手,要全打过,所以是n-1,当是基数时,会有一个人轮空,所以要多加一轮
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-8-17 13:49:04 来自手机 | 显示全部楼层
pawprinter 发表于 2016-8-17 11:02
每轮只能打一个对手,要全打过,所以是n-1,当是基数时,会有一个人轮空,所以要多加一轮

如何证明一定可达呢?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 06:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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