Perface
昨天有幸参加了一下谷歌校园招聘的测试笔试练习题,主要是为了让我们熟悉环境的。作为一个非科班出生的人,而且从未参加过ACM竞赛的人来说还是有不少困难的,即使有不少的开发经验,尤其是对于算法的掌握还是得专门学习过才才能很熟练,好了接下来来给大家分享一下我对这次测试的心得。
Problem A. Bad Horse
第一题还确实是有一定难度的,其测试条件一的通过率只有37%左右,测试条件一能过测试条件二基本都能通过(可怜的我第一个好不容易过了,但是第二个通不过了,后来觉得自己的算法还是有点漏洞,看了别人的解析才知道,自己压根没学过这玩意)。我们来看看题目:
Problem
As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with.
Most recently, there have been far too many arguments and far too much backstabbing in
the League, so much so that Bad Horse has decided to split the league into two
departments in order to separate troublesome members. Being the Thoroughbred of Sin,
Bad Horse isn't about to spend his valuable time figuring out how to split the League
members by himself. That what he's got you -- his loyal henchman -- for.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test
case starts with a positive integer M on a line by itself -- the number of troublesome pairs
of League members. The next M lines each contain a pair of names, separated by a
single space.
Output
For each test case, output one line containing "Case #x: y", where x is the case number
(starting from 1) and y is either "Yes" or "No", depending on whether the League members
mentioned in the input can be split into two groups with neither of the groups containing a
troublesome pair.
Limits
1 ≤ T ≤ 100.
Each member name will consist of only letters and the underscore character.
Names are case-sensitive.
No pair will appear more than once in the same test case.
Each pair will contain two distinct League members.
Small dataset
1 ≤ M ≤ 10.
Large dataset
1 ≤ M ≤ 100.
Input Output
2 Case #1: Yes
1 Case #2: No
Dead_Bowie Fake_Thomas_Jefferson
3
Dead_Bowie Fake_Thomas_Jefferson
Fake_Thomas_Jefferson Fury_Leika
Fury_Leika Dead_Bowie
这题大概的意思就是:有个Bad Horse 要给他联盟里面的人分成两组,因为有些人在一起会闹矛盾,所以不能将他们分在一组里。现在的问题就是给出一系列这样的矛盾对,判断是否存在一种分组方法将他们分开,保证没有一组里会有两个人闹矛盾。(第一眼看到这题的时候读了很久们读懂,估计是没接触过这种题吧)
Problem
As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with.
Most recently, there have been far too many arguments and far too much backstabbing in
the League, so much so that Bad Horse has decided to split the league into two
departments in order to separate troublesome members. Being the Thoroughbred of Sin,
Bad Horse isn't about to spend his valuable time figuring out how to split the League
members by himself. That what he's got you -- his loyal henchman -- for.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test
case starts with a positive integer M on a line by itself -- the number of troublesome pairs
of League members. The next M lines each contain a pair of names, separated by a
single space.
Output
For each test case, output one line containing "Case #x: y", where x is the case number
(starting from 1) and y is either "Yes" or "No", depending on whether the League members
mentioned in the input can be split into two groups with neither of the groups containing a
troublesome pair.
Limits
1 ≤ T ≤ 100.
Each member name will consist of only letters and the underscore character.
Names are case-sensitive.
No pair will appear more than once in the same test case.
Each pair will contain two distinct League members.
Small dataset
1 ≤ M ≤ 10.
Large dataset
1 ≤ M ≤ 100.
Input Output
2 Case #1: Yes
1 Case #2: No
Dead_Bowie Fake_Thomas_Jefferson
3
Dead_Bowie Fake_Thomas_Jefferson
Fake_Thomas_Jefferson Fury_Leika
Fury_Leika Dead_Bowie
这题大概的意思就是:有个Bad Horse 要给他联盟里面的人分成两组,因为有些人在一起会闹矛盾,所以不能将他们分在一组里。现在的问题就是给出一系列这样的矛盾对,判断是否存在一种分组方法将他们分开,保证没有一组里会有两个人闹矛盾。(第一眼看到这题的时候读了很久们读懂,估计是没接触过这种题吧)
Answer A
这道题我只能通过第一组测试,第二个就通不过了,之前也提到过我的算法有漏洞就不公布了。给大家几个已经解答好的答案,方法就是判断图是否二分(这玩意我是没学过)