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

Google Phone Interview

🔗
echo33 2016-1-13 01:25:53 | 只看该作者
全局:
条件1很容易check

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

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

如果不知道的话要读到最后才知道,那还得回头去check一次

或者像前面说的那样最后check每个player是否都跟其他对局过。
回复

使用道具 举报

全局:
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的。
第一个就是以建一个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,当是基数时,会有一个人轮空,所以要多加一轮

如何证明一定可达呢?
回复

使用道具 举报

🔗
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轮。

补充内容 (2016-8-17 13:57):
前面的偶数个人去掉,打多了
回复

使用道具 举报

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

本版积分规则

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