y****i
发帖数: 312 | |
i**********e
发帖数: 1145 | 2 我昨晚登上去玩了，与 Google Codejam 相比之下逊色不少，还有满多 bug 在里面。
UI 做的很不好，甚至有很多误导性的地方。还有很多安全性的问题没考虑好，有人已
经说过可以通过 wget 来偷偷下载数据而不启动倒时。甚至有一段时间很多人都看到一
个人飚上排名榜第一名（现在已被去除），说解了总共四道题（但其实只有三道题而已
）。
总体来说题目还好，不会很难（有 topcoder 里的人在论坛里说所有题目都不是原创）
，但下一轮估计难度会提高些。
以下是我对 Hacker Cup 的一些感想。
http://www.ihas1337code.com/2011/01/facebook-hacker-cup.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
P********l
发帖数: 452 | 3 Interesting.
The first problem is similar to one trivial interview question.
Double Squares
A double-square number is an integer X which can be expressed as the sum of
two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1
^2. Your task in this problem is, given X, determine the number of ways in
which it can be written as the sum of two squares. For example, 10 can only
be written as 3^2 + 1^2 (we don't count 1^2 + 3^2 as being different). On
the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.
Input
You should first read an integer N, the number of test cases. The next N
lines will contain N values of X.
Constraints
0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100
Output
For each value of X, you should output the number of ways to write X as the
sum of two squares. |
h****r
发帖数: 2056 | 4 So easy?
of
1
only
【在 P********l 的大作中提到】
: Interesting.
: The first problem is similar to one trivial interview question.
: Double Squares
: A double-square number is an integer X which can be expressed as the sum of
: two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1
: ^2. Your task in this problem is, given X, determine the number of ways in
: which it can be written as the sum of two squares. For example, 10 can only
: be written as 3^2 + 1^2 (we don't count 1^2 + 3^2 as being different). On
: the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.
: Input
|
P********l
发帖数: 452 | 5 3rd:
Studious Student
You've been given a list of words to study and memorize. Being a diligent
student of language and the arts, you've decided to not study them at all
and instead make up pointless games based on them. One game you've come up
with is to see how you can concatenate the words to generate the
lexicographically lowest possible string.
Input
As input for playing this game you will receive a text file containing an
integer N, the number of word sets you need to play your game against. This
will be followed by N word sets, each starting with an integer M, the number
of words in the set, followed by M words. All tokens in the input will be
separated by some whitespace and, aside from N and M, will consist entirely
of lowercase letters.
Output
Your submission should contain the lexicographically shortest strings for
each corresponding word set, one per line and in order.
Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10
See a post:
http://www.mitbbs.com/article_t/Programming/31179801.html
blaze might have a better answer. |
i**********e
发帖数: 1145 | 6 It's trivial to do a brute force search.
There are also mathematical properties that you can take advantage on.
However, assume you don't know these properties, how to write a program to
do this efficiently?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
of
1
only
【在 P********l 的大作中提到】
: Interesting.
: The first problem is similar to one trivial interview question.
: Double Squares
: A double-square number is an integer X which can be expressed as the sum of
: two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1
: ^2. Your task in this problem is, given X, determine the number of ways in
: which it can be written as the sum of two squares. For example, 10 can only
: be written as 3^2 + 1^2 (we don't count 1^2 + 3^2 as being different). On
: the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.
: Input
|
P********l
发帖数: 452 | 7 construct a hash map from 0^2, 1^2, ... floor(sqrt(n))^2.
We know if an array have two numbers sum to a given number. Now, the
question is to extend it to find all combinations rather stop at the first
pair.
【在 i**********e 的大作中提到】
: It's trivial to do a brute force search.
: There are also mathematical properties that you can take advantage on.
: However, assume you don't know these properties, how to write a program to
: do this efficiently?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: of
: 1
: only
|
i**********e
发帖数: 1145 | 8 第三题是个很好的题目，不是你想像的那么直接，如果不小心的话很容易掉入个误区。
那个 post 提供了有关那题很好的讨论。
主要就是排序，但是前提是怎么个排序法。
例如：
sd sdab sda pq
怎么把字符串连起来 to be smallest lexicographically
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
This
【在 P********l 的大作中提到】
: 3rd:
: Studious Student
: You've been given a list of words to study and memorize. Being a diligent
: student of language and the arts, you've decided to not study them at all
: and instead make up pointless games based on them. One game you've come up
: with is to see how you can concatenate the words to generate the
: lexicographically lowest possible string.
: Input
: As input for playing this game you will receive a text file containing an
: integer N, the number of word sets you need to play your game against. This
|
i**********e
发帖数: 1145 | 9 I have tried this approach.
N can go up to 2147483647,
which requires at least 2GB to store the mappings.
In my C program it fails to allocate such large amount of memory on the heap.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 P********l 的大作中提到】
: construct a hash map from 0^2, 1^2, ... floor(sqrt(n))^2.
: We know if an array have two numbers sum to a given number. Now, the
: question is to extend it to find all combinations rather stop at the first
: pair.
|
r*******y
发帖数: 1081 | 10 感觉光是排序不行阿，比如 bc < bca
但是连起来以后 bcbca > bcabc
This
【在 P********l 的大作中提到】
: 3rd:
: Studious Student
: You've been given a list of words to study and memorize. Being a diligent
: student of language and the arts, you've decided to not study them at all
: and instead make up pointless games based on them. One game you've come up
: with is to see how you can concatenate the words to generate the
: lexicographically lowest possible string.
: Input
: As input for playing this game you will receive a text file containing an
: integer N, the number of word sets you need to play your game against. This
|
|
|
P********l
发帖数: 452 | 11 how can it be?
sqrt(2147483647)=46340.95 ~ several hundreds kB.
It should be a hash set instead. It make no sense to have a hash map with
value true/false.
heap.
【在 i**********e 的大作中提到】
: I have tried this approach.
: N can go up to 2147483647,
: which requires at least 2GB to store the mappings.
: In my C program it fails to allocate such large amount of memory on the heap.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
P********l
发帖数: 452 | 12 public void test() {
int num = 2147483646;
// num = 100;
num = 2147395601;
Set hs = new HashSet((int) (Math.sqrt(num)) + 100);
for (int i = 0; i < Math.sqrt(num); i++) {
hs.add(i * i);
}
for (Integer i : hs) {
int j = num - i;
if (j < i)
continue;
if (hs.contains(j)) {
System.out.println(i + ", " + j);
}
}
}
2147395601 ==>
1, 2147395600
317694976, 1829700625 |
h**6
发帖数: 4160 | 13 看完题就点了download input，直接废掉一题。设计的也真烂，也不像google那样扣四
分钟还可以继续。 |
c******n
发帖数: 4965 | 14 isn't this the same as coins problem?
just creat your coins array os square numbers first
【在 P********l 的大作中提到】
: construct a hash map from 0^2, 1^2, ... floor(sqrt(n))^2.
: We know if an array have two numbers sum to a given number. Now, the
: question is to extend it to find all combinations rather stop at the first
: pair.
|
B********n
发帖数: 384 | 15 觉得有道理，感觉分析清楚了程序很简单。另外输入很小，用brute force也没什么问
题。M <= 9, 9! = 362880，可以作为验证。
bool StringCompare (string s1, string s2)
{
return ( (s1+s2) < (s2+s1) );
}
void PrintLeastOrder(vector words)
{
sort(words.begin(), words.end(), StringCompare);
for (int i = 0; i < words.size(); i++)
cout << words[i].c_str();
cout << "\n";
}
Output
cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy
This
【在 P********l 的大作中提到】
: 3rd:
: Studious Student
: You've been given a list of words to study and memorize. Being a diligent
: student of language and the arts, you've decided to not study them at all
: and instead make up pointless games based on them. One game you've come up
: with is to see how you can concatenate the words to generate the
: lexicographically lowest possible string.
: Input
: As input for playing this game you will receive a text file containing an
: integer N, the number of word sets you need to play your game against. This
|
c******n
发帖数: 4965 | 16 各位大牛
你们好像经常参与code jam. topsider
之类的比赛啊
你们还是学生么？
说实在这些东西在大多数it company 没什么用， 工作了的（至少我自己）很少有兴趣
去看， 倒是 design pattern. tools, tcp, apache. 等等这些domain knowledge 跟
工作直接相关，zhi直接有效，自觉看得多。
不过domain knowledge 换个工作就没用了。
【在 h**6 的大作中提到】
: 看完题就点了download input，直接废掉一题。设计的也真烂，也不像google那样扣四
: 分钟还可以继续。
|
j******8
发帖数: 191 | 17 这个主要考的是基本民工素质和，对写程序的兴趣。facebook 之类的就是要一些脑子
不太差，又特别爱干活，有一些训练的基本民工。
不是它做的好，而是其他的真的太差啦，像google，microsoft，yahoo 之类。
其实有几个有vision的牛人 executive 就行了。这个呢，只要比其他的大公司牛就行
了。
绝大部分的大公司executives，都只是起副作用的。 |
i**********e
发帖数: 1145 | 18 有关第二道题 "Peg Game",
针对 example input：
3 4 1 1 1 0
从 column 1 或者 column 2 把球掉下去而达到 goal 的机率都是一样 -- 0.5.
但是根据问题 -- "there will be no ties"...
各位大牛，可以解释下这到底是为什么吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
i**********e
发帖数: 1145 | 19 This solution works, but suffer from two problems:
1) if (j < i) continue;
can be changed to:
if (i > floor(sqrt(num))) break; // more efficient to precalculate floor
(sqrt(num)) value and store it to a variable.
2) Your total running time is O(N) (because of hs.contains(j) has a
complexity of O(sqrt(N))). However, it is no much better than a brute force.
It is only necessary for a brute force to loop from i=0 to i=sqrt(N) and j=
i to j=sqrt(N). Therefore, the brute force's method is still O(N) and
requires no additional space.
The main problem I'm asking is, if there are 1000 repeated queries, how can
you make it efficient by not recomputing the same values over and over again
? It seemed that storing precomputed values into a table is the most
efficient one. But, we don't have such great memory for expense. The real
difficulty lies in storing the computed values using as few memory as
possible.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
100);
【在 P********l 的大作中提到】
: public void test() {
: int num = 2147483646;
: // num = 100;
: num = 2147395601;
: Set hs = new HashSet((int) (Math.sqrt(num)) + 100);
: for (int i = 0; i < Math.sqrt(num); i++) {
: hs.add(i * i);
: }
: for (Integer i : hs) {
: int j = num - i;
|
i**********e
发帖数: 1145 | 20 我也是这样就废掉第一题了...
download 了 input 还要 reload 才能看到倒时，
我真是服了 FB 了！
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**6 的大作中提到】
: 看完题就点了download input，直接废掉一题。设计的也真烂，也不像google那样扣四
: 分钟还可以继续。
|
|
|
P********l
发帖数: 452 | 21 1) You assumed the hashset keeps the order of input?
2) Yes. there is room to improve. The hashset is not necessary at all.
floor
force.
j=
【在 i**********e 的大作中提到】
: This solution works, but suffer from two problems:
: 1) if (j < i) continue;
: can be changed to:
: if (i > floor(sqrt(num))) break; // more efficient to precalculate floor
: (sqrt(num)) value and store it to a variable.
: 2) Your total running time is O(N) (because of hs.contains(j) has a
: complexity of O(sqrt(N))). However, it is no much better than a brute force.
: It is only necessary for a brute force to loop from i=0 to i=sqrt(N) and j=
: i to j=sqrt(N). Therefore, the brute force's method is still O(N) and
: requires no additional space.
|
i**********e
发帖数: 1145 | 22 Okay, Yes. I assumed that the hashset keeps the order of input. If not, then
I'm wrong.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 P********l 的大作中提到】
: 1) You assumed the hashset keeps the order of input?
: 2) Yes. there is room to improve. The hashset is not necessary at all.
:
: floor
: force.
: j=
|
P********l
发帖数: 452 | 23 No. In java, the hashset does not preserve the original input order. There
is another set called linkedhashset has this property.
It is brute force but the complexity is o(sqrt(n)). Because it just scan one
through 1 to sqrt(n).
then
【在 i**********e 的大作中提到】
: Okay, Yes. I assumed that the hashset keeps the order of input. If not, then
: I'm wrong.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
P********l
发帖数: 452 | 24 Niubility! I though it should use DP.
Only one thing is odd but does not cause any different in output.
That is, "a" == "aa" == "a"+
【在 B********n 的大作中提到】
: 觉得有道理，感觉分析清楚了程序很简单。另外输入很小，用brute force也没什么问
: 题。M <= 9, 9! = 362880，可以作为验证。
: bool StringCompare (string s1, string s2)
: {
: return ( (s1+s2) < (s2+s1) );
: }
: void PrintLeastOrder(vector words)
: {
: sort(words.begin(), words.end(), StringCompare);
: for (int i = 0; i < words.size(); i++)
|
h**6
发帖数: 4160 | 25 这东西到底怎么玩的？最后上传运行结果还是代码也没有弄清楚。
我有两题都超时，结果收到邮件告诉我三题全部答对。我怀疑所有参加预选赛的全部晋级了。 |
r***u
发帖数: 241 | 26 后来改了规定，因为太多人中招了，所以把时间限制去掉了。
晋级了。
【在 h**6 的大作中提到】
: 这东西到底怎么玩的？最后上传运行结果还是代码也没有弄清楚。
: 我有两题都超时，结果收到邮件告诉我三题全部答对。我怀疑所有参加预选赛的全部晋级了。
|
h**6
发帖数: 4160 | 27 有人今天参加1A的比赛吗，facebook的系统老是出问题，实在令人失望啊。
做完前两题的时候，总是无法提交，无论点多少次submit，一直没有反应；还好成功提
交第三题，没有拿零蛋回家。 |
i**********e
发帖数: 1145 | 28 我参加了，
解完第一题之后
一直纠缠在第二道题
因为我第一个sample input的答案就不 match 他们的答案，
然后一直在检测是不是理解错误 还是代码有问题。
真是晕死了，
我的答案竟然是对的
真是他们错了，
然后他们直接把那题给取下来了
现在 subround 2 还要拖到下个星期才能举行
这样的比赛真是让我不得不服 FB
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**6 的大作中提到】
: 有人今天参加1A的比赛吗，facebook的系统老是出问题，实在令人失望啊。
: 做完前两题的时候，总是无法提交，无论点多少次submit，一直没有反应；还好成功提
: 交第三题，没有拿零蛋回家。
|
b**********n
发帖数: 399 | 29 说的容易，，你以为公司那么好管的么
【在 j******8 的大作中提到】
: 这个主要考的是基本民工素质和，对写程序的兴趣。facebook 之类的就是要一些脑子
: 不太差，又特别爱干活，有一些训练的基本民工。
: 不是它做的好，而是其他的真的太差啦，像google，microsoft，yahoo 之类。
: 其实有几个有vision的牛人 executive 就行了。这个呢，只要比其他的大公司牛就行
: 了。
: 绝大部分的大公司executives，都只是起副作用的。
|
h**6
发帖数: 4160 | 30 Round 1A的比赛重新举行了，这次题目的难度很大，我只做出了第一题，打算看看别人
的代码，研究一下后面两题如何解。 |
|
|
r***u
发帖数: 241 | 31 嗯，是挺难的，只有646人过了。第三题可以用矩阵表示然后用线性代数解方程，
http://online.redwoods.cc.ca.us/instruct/darnold/laproj/Fall200
我的线性代数是全忘光了。
还可以用暴力法求解，下面贴一个别人的答案：
You can bruteforce turning lights in the first row (2^18 = small enough).
Then you may light first row using second row. This can be done in only one
way. then use third row for lighting up second and so on. After that check
last row. If it is OK - count try this layout as an answer. Remember to
count turnings then you do them. it is easy.
【在 h**6 的大作中提到】
: Round 1A的比赛重新举行了，这次题目的难度很大，我只做出了第一题，打算看看别人
: 的代码，研究一下后面两题如何解。
|
