m******i
发帖数: 834 | 1 天才啊，应该直接去MIT或者CMU
江苏省常州高级中学高三（13）班学生金斌，在美国当地时间6月4日下午举行的
Topcoder Open （简称TCO）Algorithm（算法）冠军争夺战中，击败各路好手，一举夺
得世界冠军。这是继他今年一月夺得Topcoder High School（简称TCHS，即高中生比赛
）世界冠军后，一年内取得的第二个Topcoder系列赛冠军。金斌是进入现场比赛的唯一
的高中生，也是参加最终决赛的唯一一名中国选手，同时也成为了历史上第一个一年内
取得TCHS和TCO两项冠军的选手和历史上最年轻的世界冠军。
对于算法类程序设计竞赛，被全世界广泛公认的有3项大赛，分别是于1989年创办，代
表了高中生学科竞赛最高荣誉的IOI（International Olympiad in Informatics，国际
信息学奥林匹克竞赛）；由美国Topcoder公司从2001年开始举办，在个人程序设计竞赛
中最具权威的Topcoder Algorithm比赛（TCO是这项系列赛的年度总决赛）；以及于
1970年创办的，在团队程序设计竞赛中最具权威的ACM/ICPC（国 |
|
|
w*****t
发帖数: 485 | 3 Facebook面试Q&A （from: http://heliang.me/blog/）
Posted by roba on July 14, 2012 10 comments
续上篇文章，我把大家在得知此消息后普遍感兴趣的一些问题总结了一下，在此一并写
出。
说实话，其实我的眼界从来很狭窄，以前想的是，如果能在天朝帝都扎下脚跟，过上老
婆孩子热炕头的日子，对我来说已很满足。所以之前也从未对出国读书或工作有过准备
，下文所述很多内容都是我在最近的一小段时间里才接触到的，而且现在离正式入职还
早，对于fb内部的情况并没有什么了解，签证之类的麻烦事还在办理中，说不定去不成
了也是有可能的(-_-)……扯远了，总之就是说，虽然我已经尽力做到客观准确，但恐
怕难免会有错漏，请读者不吝赐教。本文仅供参考，引起什么不好的后果本人不负责任
=,=
Q: 你的学历、学校、专业、英语成绩、论文、竞赛获奖、工作经验、参与开源项目等
背景情况？一定很牛吧？
A: 真的不牛，矮丑穷，纯RP爆发而已。本科天津大学软件学院，硕士天津大学计算机
学院。高中无竞赛经历，本科阶段ACM-ICPC竞赛亚洲区域赛有几次... 阅读全帖 |
|
A*********r
发帖数: 564 | 4 topcoder上有关于LCA的算法，比较能够接受的有两个：
1）用DP作preporcessing, 用 O(nlogn) time, 然后查询再用O(logn) time
2) 转化为 restricted RMQ problem, 可以达到O(n) time, O(n) space.
（详见http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor）
不过看到了careercup上给出的一个非DP算法，recursive的，貌似算法复杂度也只有O(
n), 但是没有用多余的空间。。虽然topcoder上面的可以查询任意两个node之间的LCA,
但在实际面试题中，我们一般都是会给定两个node，这样看来careercup上的不是更好
吗？！
下面给出careercup上的算法，大家讨论一下看看。
/* Returns NULL, p, q or the nearest common ancestor of p and q, assume p
and q are in the tree |
|
S******t
发帖数: 151 | 5 TopCoder一般的算法比赛分为Div 1和Div 2.
大家可以只做Div 2的题目，三题都做
Div 1的题目就做250就行了，如果Div 1的250和500都能稳定做对的话已经是高水平了
TopCoder做题的链接是一个Java Web Start
http://community.topcoder.com/tc
打开，点左上角那个O(n)，需要注册一个用户名 |
|
|
A**d
发帖数: 13310 | 7 Then I recommend you to start with TopCoder. Don't
need to try Division 2 level 3. By the time you can
fluently deal with muti-level loops, complex boolean
statements, helper functions, and common data structures,
you can start with Leetcode. Make sure you can code
simple algorithms fluently. There are quite some real
interview questions that don't require complex algorithms
but purposely make it hard to handle parameters, loops,
and recursions,etc. You may notice TopCoder uses int array
a lot, ... 阅读全帖 |
|
|
B*********h
发帖数: 800 | 9 ☆─────────────────────────────────────☆
matII (当归) 于 (Wed Jul 26 14:38:19 2006) 提到:
Note: This problem comes from topcoder algorithm competition (SRM313 Division
1 Level 2 problem). It is intended to be solved by algorithms such as dynamic
programming, but I found it's a mutant of a typical kind of brainteasers and it can
be solved by only paper and pen. So here is the problem:
(btw, topcoder is fun! check topcoder.com if you like.) |
|
M****o
发帖数: 4860 | 10 【 以下文字转载自 JobHunting 讨论区 】
发信人: chump (chump), 信区: JobHunting
标 题: 又一牛人： 9个offer，12家公司，35场面试，从微软到谷歌，应届计算机毕业生的2012求职之路
发信站: BBS 未名空间站 (Fri Jan 11 21:59:21 2013, 美东)
转自
http://www.cnblogs.com/figure9/archive/2013/01/09/2853649.html
9个offer，12家公司，35场面试，从微软到谷歌，应届计算机毕业生的2012求职之路
1，简介
毕业答辩搞定，总算可以闲一段时间，把这段求职经历写出来，也作为之前三个半月的
求职的回顾。
首先说说我拿到的offer情况：
微软，3面->终面，搞定
百度，3面->终面，口头offer
搜狗，2面，悲剧
腾讯，1面，悲剧
布丁移动，3面，搞定
涂鸦游戏，3面，搞定
友盟，3面->CEO面，搞定
雅虎，4面->终面，搞定
微策略，2面，悲剧
人民搜索，3面->终面，搞定
人人，2面+终面+Special面，搞定
Google，7面，搞... 阅读全帖 |
|
a****n
发帖数: 1887 | 11 我用VS 2008
做项目用C#
自己写code用C++
而且装上topcoder插件， 可以在topcoder上作练习题 |
|
a********e
发帖数: 78 | 12 请问一下你说的topcoder插件指得是topcoder arena 吗？ |
|
a****n
发帖数: 1887 | 13 练习coding， 我觉得topcoder 最好， submit 直接可以测试，每个test case 都能看
到， 也可以看别人的code
judge online, 提交后只能知道是否pass， 超时什么的， 不可以看别人代码
比较而言， topcoder 对编码要求比较高， 有时间要求， judge online比较注重算法
分析。
codejam, 没做过 |
|
|
a***o
发帖数: 19 | 15 You can achieve O(n) space and O(lg(N)) time complexity if you have parent
node pointer stored in each node.
This is achieved by first building d 2 linked list to store paths from root
to each node, and then comparing the linked list to find the last common
node in both list.
You can get a better understanding on LCA problem from this TopCoder
tutorial (see link below). It gives two solutions to this problem.
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
The idea |
|
|
|
|
|
i**********e
发帖数: 1145 | 20 看了看 topcoder 的讨论，第三题似乎是用 inclusion-exclusion principle 来排除
多余的组合，看来关系还是比较棘手的。出的题目也真是太难了，说要派 300 件
tshirt 给前 300 名，结果只有 150 人答对至少一题...
这轮看来是专门针对那些专做 topcoder 的选手，看看第一题的讨论就知道，听说要用
FFT 或者 Karatsuba algorithm 来做快速乘法。看了排第一名大牛级别的代码，还真
不是一般的复杂...
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 21 我听说一般公司面试题的难度都是维持在 topcoder 的 div II 250 分的问题，也就是
topcoder 比赛最简单的题目。
我觉得最重要的是你的思路，而不是答案对了就可以了。很多时候解题要各种角度来
approach，然后分析每一个方法的优缺点，再做出总结。只有这样才能不断进步。要给
面试官的印象是头脑灵活，而不是一味的死做题，一旦问题稍微有变化就不懂怎么解了
。还有最重要的是学会冷静思考，不要冲动写代码。尽量要求第一次写代码就没有出错
，这是一般人很难做得到的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
g**********y
发帖数: 14569 | 23 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k... 阅读全帖 |
|
m**q
发帖数: 189 | 24
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
... 阅读全帖 |
|
g**********y
发帖数: 14569 | 25 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k... 阅读全帖 |
|
m**q
发帖数: 189 | 26
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
... 阅读全帖 |
|
|
r******n
发帖数: 170 | 28 一直没弄请怎么解这题，正好从topcoder tutorial上看到有相关讲解：
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
不过还是没太清楚，这个伪码里的J=1是怎么选出来的？是直接选结束时间最早的那个
事件吗？记得版上似乎有讨论过，不过没翻出来。哪位知道在哪里吗？
Let N denote the number of activities and
{I} the activity I ( 1 <= I <= N )
For each {I}, consider S[I] and F[I] its starting and finishing time
Sort the activities in the increasing order of their finishing time
- that is, for every I < J we must have F [I] <= F [J]
// A denotes the set of the activities that will be... 阅读全帖 |
|
|
|
|
|
g*****i
发帖数: 2162 | 33 来加入吧,还期待你承担起斑竹板斧的任务呢.来给我们分享点编程,比赛的心得吧. |
|
|
d******y
发帖数: 244 | 35 Last night I applied but no response. |
|
g**********y
发帖数: 14569 | 36 you are in, probably I went to sleep, approved this morning. |
|
|
k****n
发帖数: 1334 | 38 提个意见，设置成public就可以了
没有必要让人申请加入
面也不好。于是我开了个俱乐部。有兴趣讨论程序竞赛，提高编程水平的同学，欢迎加
入，大家一起提高。 |
|
g**********y
发帖数: 14569 | 39 我看时常有人各版打小广告，象写的机器人，所以没设成公开的。 |
|
k****n
发帖数: 1334 | 40 一开始人多，可以设成公开地，你也方便，人差不多了再加权限
anyway |
|
i**********e
发帖数: 1145 | 41 【 以下文字转载自 Topcoders 俱乐部 】
发信人: ihasleetcode (1337coder), 信区: Topcoders
标 题: 问个 paypal 的题目
发信站: BBS 未名空间站 (Tue Dec 6 23:37:10 2011, 美东)
这道题，想请问有没有更好的解？我的思路和解答在这里：
http://www.leetcode.com/groups/general-help/forum/topic/pay-pal
我记得本版好像有讨论过，有没有链接？谢谢
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number
of rows like this: (you may want to display this pattern in a fixed font
for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: PAHNAPLSIIGY... 阅读全帖 |
|
v***a
发帖数: 365 | 42 去TopCoder，把历年的题目做一遍，轻松应对FB的TopCoder |
|
|
s******t
发帖数: 169 | 44 PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
google的题目：
在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
另外一个问的：
直接递归法求fib（N）的复杂度是多少
还有很多杂的，各种数据结构复杂度是多少之类的。
一星期之后催HR结果被拒。悲剧。
然后急了，本来找得就比较晚，２月才开始准备，于是各种乱投简历，多数石沉大海。
本来都有点绝望了，准备好好准备一年算法搞一年竞赛明年直接申工作得了，结果拿到
了一个start up的intern。
其实... 阅读全帖 |
|
H**********y
发帖数: 7928 | 45 赞
PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
google的题目：
在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
另外一个问的：
直接递归法求fib（N）的复杂度是多少
还有很多杂的，各种数据结构复杂度是多少之类的。
一星期之后催HR结果被拒。悲剧。
然后急了，本来找得就比较晚，２月才开始准备，于是各种乱投简历，多数石沉大海。
本来都有点绝望了，准备好好准备一年算法搞一年竞赛明年直接申工作得了，结果拿到
了一个start up的intern。... 阅读全帖 |
|
|
p*****2
发帖数: 21240 | 47
当然是要去topcoder练了当然是要去topcoder练了 |
|
d**********x
发帖数: 4083 | 48 还好啊
我觉得twitter电面的风格和topcoder上某些弱500分题挺像的
topcoder可以用来练0 bug |
|
p*****2
发帖数: 21240 | 49
膜拜呀。都拿到twitter的面试了。我topcoder练过了。感觉再练下去对我面试的帮助
已经不大了。而且感觉能拿到大offer的跟topcoder的水平也没有直接的关系。 |
|
|
