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
这道题我只能通过第一组测试,第二个就通不过了,之前也提到过我的算法有漏洞就不公布了。给大家几个已经解答好的答案,方法就是判断图是否二分(这玩意我是没学过)
Problem B. Captain Hammer
这道题比较简单,纯粹的物理题。不过有些小细节需要注意,我是用Java写的这里公布一个Java版本的代码,请看题:Problem
The Hamjet is a true marvel of aircraft engineering. It is a jet airplane with a single engine
so powerful that it burns all of its fuel instantly during takeoff. The Hamjet doesn't have any
wings because who needs them when the fuselage is made of a special Wonderflonium
isotope that makes it impervious to harm.
Piloting the Hamjet is a not a job for your typical, meek-bodied superhero. That's why the
Hamjet belongs to Captain Hammer, who is himself impervious to harm. The G-forces that
the pilot endures when taking a trip in the Hamjet are legen-dary.
The Hamjet takes off at an angle of θ degrees up and a speed of V meters per second. V
is a fixed value that is determined by the awesome power of the Hamjet engine and the
capacity of its fuel tank. The destination is D meters away. Your job is to program the
Hamjet's computer to calculate θ given V and D.
Fortunately, the Hamjet's Wondeflonium hull is impervious to air friction. Even more
fortunately, the Hamjet doesn't fly too far or too high, so you can assume that the Earth is
flat, and that the acceleration due to gravity is a constant 9.8 m/s2 down.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line will
contain two positive integers -- V and D.
Output
For each test case, output one line containing "Case #x: θ", where x is the case number
(starting from 1) and θ is in degrees up from the the horizontal. If there are several
possible answers, output the smallest positive one.
An answer will be considered correct if it is within 10^-6 of the exact answer, in absolute or
relative error. See the FAQ for an explanation of what that means, and what formats of
floating-point numbers we accept.
Limits
1 ≤ T ≤ 4500;
1 ≤ V ≤ 300;
1 ≤ D ≤ 10000;
It is guaranteed that each test case will be solvable.
Sample
Input
3
98 980
98 490
299 1234
Output
Case #1: 45.0000000
Case #2: 15.0000000
Case #3: 3.8870928
题目大意:其实这道题很傻,就是说Hamjet是个飞行器制造工程师,他想知道的初速度V和最大行程D的情况下以多少角度θ才能达到这个目的。重力加速度为G = 9.8
实际上只要通过简单的物理公式马上就可以得到 θ= arcsin( D * G / (V * V) ) / 2 度
以下是我的代码:
The Hamjet is a true marvel of aircraft engineering. It is a jet airplane with a single engine
so powerful that it burns all of its fuel instantly during takeoff. The Hamjet doesn't have any
wings because who needs them when the fuselage is made of a special Wonderflonium
isotope that makes it impervious to harm.
Piloting the Hamjet is a not a job for your typical, meek-bodied superhero. That's why the
Hamjet belongs to Captain Hammer, who is himself impervious to harm. The G-forces that
the pilot endures when taking a trip in the Hamjet are legen-dary.
The Hamjet takes off at an angle of θ degrees up and a speed of V meters per second. V
is a fixed value that is determined by the awesome power of the Hamjet engine and the
capacity of its fuel tank. The destination is D meters away. Your job is to program the
Hamjet's computer to calculate θ given V and D.
Fortunately, the Hamjet's Wondeflonium hull is impervious to air friction. Even more
fortunately, the Hamjet doesn't fly too far or too high, so you can assume that the Earth is
flat, and that the acceleration due to gravity is a constant 9.8 m/s2 down.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line will
contain two positive integers -- V and D.
Output
For each test case, output one line containing "Case #x: θ", where x is the case number
(starting from 1) and θ is in degrees up from the the horizontal. If there are several
possible answers, output the smallest positive one.
An answer will be considered correct if it is within 10^-6 of the exact answer, in absolute or
relative error. See the FAQ for an explanation of what that means, and what formats of
floating-point numbers we accept.
Limits
1 ≤ T ≤ 4500;
1 ≤ V ≤ 300;
1 ≤ D ≤ 10000;
It is guaranteed that each test case will be solvable.
Sample
Input
3
98 980
98 490
299 1234
Output
Case #1: 45.0000000
Case #2: 15.0000000
Case #3: 3.8870928
题目大意:其实这道题很傻,就是说Hamjet是个飞行器制造工程师,他想知道的初速度V和最大行程D的情况下以多少角度θ才能达到这个目的。重力加速度为G = 9.8
实际上只要通过简单的物理公式马上就可以得到 θ= arcsin( D * G / (V * V) ) / 2 度
以下是我的代码:
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Captain_Hammer {
public static final double G = 9.8;
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(new FileInputStream(new File(
"B-small-attempt2.in")));
int count = Integer.parseInt(scanner.nextLine());
double[] output = new double[count];
// read data
for (int i = 0; i < count; i++) {
String str = scanner.nextLine();
String[] values = str.split(" ");
double V = Double.parseDouble(values[0]);
double D = Double.parseDouble(values[1]);
output[i] = getAngle(V, D);
}
/* output */
for (int i = 0; i < output.length; i++) {
String out = "Case #" + (i + 1) + ": ";
System.out.printf("%s%.7f\n", out, output[i]);
}
}
public static double getAngle(double V, double D) {
// return Math.asin(D / V * G / V);
double value = 90.0 * Math.asin(D / V * G / V) / Math.PI;
if (Double.isNaN(value))
value = 45.0;
return value;
}
}
不知道大家有没有注意到我在 getAngle(double V, double D) 里面判断了一下 isNaN ,这么做的原因是我在测试的过程中发现有些数据会返回NaN。后来发现原因是由于 Math.asin() 在输入大于1的情况会返回NaN。算法没错,可能是由于Java在计算过程中的精确度导致输入大于1吧,这种情况在程序里面常会出现就比如 1/3*3 会返回 0.999 一样吧。
Problem C. Moist
这道题算是里面最简单的一道题了。就直接看题吧:Problem
Moist has a hobby -- collecting figure skating trading cards. His card collection has been
growing, and it is now too large to keep in one disorganized pile. Moist needs to sort the
cards in alphabetical order, so that he can find the cards that he wants on short notice
whenever it is necessary.
The problem is -- Moist can't actually pick up the cards because they keep sliding out his
hands, and the sweat causes permanent damage. Some of the cards are rather
expensive, mind you. To facilitate the sorting, Moist has convinced Dr. Horrible to build
him a sorting robot. However, in his rather horrible style, Dr. Horrible has decided to make
the sorting robot charge Moist a fee of $1 whenever it has to move a trading card during
the sorting process.
Moist has figured out that the robot's sorting mechanism is very primitive. It scans the
deck of cards from top to bottom. Whenever it finds a card that is lexicographically
smaller than the previous card, it moves that card to its correct place in the stack above.
This operation costs $1, and the robot resumes scanning down towards the bottom of the
deck, moving cards one by one until the entire deck is sorted in lexicographical order from
top to bottom.
As wet luck would have it, Moist is almost broke, but keeping his trading cards in order is
the only remaining joy in his miserable life. He needs to know how much it would cost him
to use the robot to sort his deck of cards.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each one
starts with a line containing a single integer, N. The next N lines each contain the name of
a figure skater, in order from the top of the deck to the bottom.
Output
For each test case, output one line containing "Case #x: y", where x is the case number
(starting from 1) and y is the number of dollars it would cost Moist to use the robot to sort
his deck of trading cards.
Limits
1 ≤ T ≤ 100.
Each name will consist of only letters and the space character.
Each name will contain at most 100 characters.
No name with start or end with a space.
No name will appear more than once in the same test case.
Lexicographically, the space character comes first, then come the upper case letters,
then the lower case letters.
Small dataset
1 ≤ N ≤ 10.
Large dataset
1 ≤ N ≤ 100.
Sample
Input
2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi
Output
Case #1: 1
Case #2: 0
题目大意:Moist有个爱好就是收集溜冰交易卡,然后现在他想去给这些卡片排排序(按字母表顺序排),于是找到一个会制造排序机器的人,这个机器会从头向下找,一旦发现某个卡片序号小于之前的,就会将这个卡片放到之前一堆正确的位置,并且每做一次这种操作就计费1$,这个机器会不断地从头向下检查,直到全部有序。最后Moist希望知道,他把这堆卡片交给他排序后应该付多少钱?
我这里写的代码有点二,完全是按照他说的做法来的,还有优化的空间。不过还是贴出来吧,至少是一种可行的方案,排序的过程中用了插入排序方法。其实完全可以用自带的方法去完成,不用自己写了。以下是我的代码
Moist has a hobby -- collecting figure skating trading cards. His card collection has been
growing, and it is now too large to keep in one disorganized pile. Moist needs to sort the
cards in alphabetical order, so that he can find the cards that he wants on short notice
whenever it is necessary.
The problem is -- Moist can't actually pick up the cards because they keep sliding out his
hands, and the sweat causes permanent damage. Some of the cards are rather
expensive, mind you. To facilitate the sorting, Moist has convinced Dr. Horrible to build
him a sorting robot. However, in his rather horrible style, Dr. Horrible has decided to make
the sorting robot charge Moist a fee of $1 whenever it has to move a trading card during
the sorting process.
Moist has figured out that the robot's sorting mechanism is very primitive. It scans the
deck of cards from top to bottom. Whenever it finds a card that is lexicographically
smaller than the previous card, it moves that card to its correct place in the stack above.
This operation costs $1, and the robot resumes scanning down towards the bottom of the
deck, moving cards one by one until the entire deck is sorted in lexicographical order from
top to bottom.
As wet luck would have it, Moist is almost broke, but keeping his trading cards in order is
the only remaining joy in his miserable life. He needs to know how much it would cost him
to use the robot to sort his deck of cards.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each one
starts with a line containing a single integer, N. The next N lines each contain the name of
a figure skater, in order from the top of the deck to the bottom.
Output
For each test case, output one line containing "Case #x: y", where x is the case number
(starting from 1) and y is the number of dollars it would cost Moist to use the robot to sort
his deck of trading cards.
Limits
1 ≤ T ≤ 100.
Each name will consist of only letters and the space character.
Each name will contain at most 100 characters.
No name with start or end with a space.
No name will appear more than once in the same test case.
Lexicographically, the space character comes first, then come the upper case letters,
then the lower case letters.
Small dataset
1 ≤ N ≤ 10.
Large dataset
1 ≤ N ≤ 100.
Sample
Input
2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi
Output
Case #1: 1
Case #2: 0
题目大意:Moist有个爱好就是收集溜冰交易卡,然后现在他想去给这些卡片排排序(按字母表顺序排),于是找到一个会制造排序机器的人,这个机器会从头向下找,一旦发现某个卡片序号小于之前的,就会将这个卡片放到之前一堆正确的位置,并且每做一次这种操作就计费1$,这个机器会不断地从头向下检查,直到全部有序。最后Moist希望知道,他把这堆卡片交给他排序后应该付多少钱?
我这里写的代码有点二,完全是按照他说的做法来的,还有优化的空间。不过还是贴出来吧,至少是一种可行的方案,排序的过程中用了插入排序方法。其实完全可以用自带的方法去完成,不用自己写了。以下是我的代码
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Moist {
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(new FileInputStream(new File(
"C-small-2-attempt0.in")));
int count = Integer.parseInt(scanner.nextLine());
int[] cost = new int[count];
int index = 0;
while (scanner.hasNext()) {
int length = Integer.parseInt(scanner.nextLine());
String[] card_names = new String[length];
for (int i = 0; i < length; i++) {
card_names[i] = scanner.nextLine();
}
cost[index++] = getCost(card_names);
}
/* print cost */
for (int i = 0; i < cost.length; i++) {
String out = "Case #" + (i + 1) + ": ";
System.out.println(out + cost[i]);
}
}
private static int getCost(String[] card_names) {
// TODO Auto-generated method stub
int cost = 0;
while (true) {
boolean stop = true;
for (int i = 1; i < card_names.length; i++) {
/* the previous */
for (int j = 0; j != i; j++) {
if (card_names[i].compareTo(card_names[j]) < 0) {
stop = false;
cost++;
/* move */
String tmp = card_names[i];
for (int n = i; n != j; n--) {
card_names[n] = card_names[n - 1];
}
card_names[j] = tmp;
}
}
}
if (stop)
break;
}
// for (String str : card_names)
// System.out.println(str);
return cost;
}
}
Summary
我不是个算法高手,而且第一次做这种题的时候题都读不懂,花了很多时间才明白。感觉这一类的比赛像奥数比赛一样。而且前几名的代码风格都惊人的相似,估计都总结出一套解题流程了。