给你们看个神童 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

给你们看个神童

给你们看个神童# Parenting - 为人父母

c*y2014-11-02 07:11

1 楼

小公司，有点research性质的。面了6,7个人吧，问了很多关于之前的research
projects，不具有代表性。就把记得的算法题汇报一下吧。很多也没要求写code。
1. 给定一个sorted array，如何查找所有pair，他们的和等去一个给定sum。
要求给一个不用hash table的方法
给了一个用binary search加速查找过程的方法。
2. 如何用一个1G内存sort一个10G的文件，假设硬盘空间足够大。
刚开始给了一个pair-wise sort，后经讨论improve成K-way sort。相比K-way sort，
pair-wise sort要求更多的硬盘访问次数。
后来讨论一下如果硬盘空间有限，例如只有10.5G，如何做K-way sort。
3. 给定一个有向图，如何判定是不是bipartite，只讨论的算法，没有要求写code
这里是Wiki上定义http://en.wikipedia.org/wiki/Bipartite_graph
4. 如何判定一个binary search tree
5. 给定一个array和一个sum，如何找到所有个pair和triple它们的和。不确定是不是
leetcode上的two-sum和tree-sum的原题。
two-sum
开始给了一个O(n^2)的brutal force的方法。
后要求优化到O(n log n)，给了一个基于binary search的方法（和第一题一样）。
后要求优化到O(n)，给了一个基于HashTable的方法。
后要求优化到O(1)，即对于给定任何一个sum，从constant时间返回所有pair。这里可
以preprocess。就事先用brutal force的方法，对于所有pair的和，建立一个hash
table。
three-sum
开始给了一个O(n^3)的brutal force的方法。
后要求优化到O(n^2 log n)
后要求优化到O(n^2)
思路和two-sum差不多，基本都是用hash table来加速查找。
6. 给定一组判定语句，定义一个数据结构来进行快速查找。
例如给定判定条件如下
A==5 && B==1 && Z==20
Y==20 && Z==3 && C==6
D==4 && B==2 && M==30
只讨论了算法，没有要求写code。
给了用tier来建立一个快速查找表。

h*a2014-11-02 07:11

2 楼

在kroger 买gv 算6% 吗？用america express, cash reward 算supermarket 吗？
谢谢

w*y2014-11-02 07:11

3 楼

和这位神童比，这个BBS的娃基本都输在起跑线了。是的，人家2岁就做高数了。
Tristan Pang
From Wikipedia, the free encyclopedia
Tristan Pang
Born October 18, 2001 (age 13)
East Grinstead, West Sussex, United Kingdom
Residence New Zealand
Nationality British
Other names Tristan Owain Pang
Citizenship British
Education Year 8[1] and University student[2]
Occupation Student / Founder of Tristan's Learning Hub[2]
Organization St John, Onehuga Swimming Club, Mensa, New Zealand
Association for Gifted Children
Known for Maths, Science, Logic
Home town East Grinstead and Auckland
Parents Elaine and Thomas Pang
Tristan Pang (born October 18, 2001 in West Sussex, UK), is a child prodigy[
3][4] who excelled academically from an early age. He started reading
independently and doing high school maths at the age of two. He sat the
Cambridge International Examinations IGCSE maths (Year 11 / O Level) and
earned the top grade A* scoring 97% at only nine.[5] By age eleven he top
scored with A* at the Cambridge A level exams (Year 13), delivered a
TEDxYouth talk [6] and became one of the youngest speakers in the world. He
started his university studies at the University of Auckland and created a
free online learning platform, Tristan's Learning Hub, by the age of twelve.
He has been delivering numerous speeches to schools and at conferences with
an aim to inspire young people.[5][7] 12-year-old Tristan Pang (Tristan
Owain Pang) is in Year 8 and is the head boy at Ficino School.[1] He is also
a maths student at the University of Auckland. At home, he teaches himself
in multi-levels on all subjects. He has always been fascinated by the
relationships between light and energy, and is also interested in quantum
physics and time travel, as well as how the human body and mind works. He is
planning to be a science researcher in these fields.[7]
Contents [hide]
1 Education experience speech
2 References
3 External links
3.1 Websites
3.2 Media
3.3 Speeches
3.4 Videos
Education experience speech[edit]
At the Festival of Education in March 2014 in Auckland, New Zealand, Tristan
Pang delivered a speech The Future of Education: but not as you know it.[8]
He shared his own education experience of his in-depth vertical learning
method. He also talked about technology in Learning, and also the
flexibility, trust, encouragement and support from adults. He also stressed
that mentorship, a perfect school day, a self-learning day and peer to peer
learning are all very important. And finally, he shared his educational
visions.[9]
References[edit]
^ Jump up to: a b Ficino School student Tristan Pang uses his unique talent
to inspire his peers
^ Jump up to: a b Maths whiz's website helps others to learn
Jump up ^ 10 child prodigies
Jump up ^ "Kiwi superbrain couldn’t have done it without the internet".
^ Jump up to: a b Meet the maths brain of New Zealand
Jump up ^ Tristan Pang's TED Talk
^ Jump up to: a b Quest-is-fun - the creator
Jump up ^ Quest-is-fun - Speech at the festival of education
Jump up ^ Tristan Pang at the Festival of Education

r*n2014-11-02 07:11

4 楼

祝LZ好运
最后那题也可以用hash来做吧

d*j2014-11-02 07:11

5 楼

gv是啥

u*a2014-11-02 07:11

6 楼

我看了之后特佩服这个神童，尤其是他给自己定的挑战：
Challenge #1: Lose 40 lbs by July 2015.
Challenge #2: Develop an efficient and productive daily routine.
Challenge #3: Exercise daily
那么小的孩子，减轻四十磅的体重得多有恒心才行啊！

r*h2014-11-02 07:11

7 楼

bless!
我现在觉得这种偏向于原创性research的小公司也蛮不错的

【在 c**y 的大作中提到】

: 小公司，有点research性质的。面了6,7个人吧，问了很多关于之前的research
: projects，不具有代表性。就把记得的算法题汇报一下吧。很多也没要求写code。
: 1. 给定一个sorted array，如何查找所有pair，他们的和等去一个给定sum。
: 要求给一个不用hash table的方法
: 给了一个用binary search加速查找过程的方法。
: 2. 如何用一个1G内存sort一个10G的文件，假设硬盘空间足够大。
: 刚开始给了一个pair-wise sort，后经讨论improve成K-way sort。相比K-way sort，
: pair-wise sort要求更多的硬盘访问次数。
: 后来讨论一下如果硬盘空间有限，例如只有10.5G，如何做K-way sort。
: 3. 给定一个有向图，如何判定是不是bipartite，只讨论的算法，没有要求写code

c*u2014-11-02 07:11

8 楼

Gay Video

【在 d**j 的大作中提到】

: gv是啥

s*t2014-11-02 07:11

9 楼

那他得多胖才需要减40磅重啊？！一点也不羡慕他。

h*g2014-11-02 07:11

10 楼

最后一题什么意思？

【在 r*********n 的大作中提到】

: 祝LZ好运
: 最后那题也可以用hash来做吧

h*a2014-11-02 07:11

11 楼

gv=gc=gift card

【在 c*******u 的大作中提到】

: Gay Video

C*e2014-11-02 07:11

12 楼

原来是楼主的签名档

【在 s*********t 的大作中提到】

: 那他得多胖才需要减40磅重啊？！一点也不羡慕他。

c*y2014-11-02 07:11

13 楼

多谢多谢！
如何用Hash呢？

【在 r*********n 的大作中提到】

: 祝LZ好运
: 最后那题也可以用hash来做吧

o*g2014-11-02 07:11

14 楼

kroger的子公司fred meyer用amex买食品是不算grocery的，chase就算，不知道为什么。

【在 h********a 的大作中提到】

: 在kroger 买gv 算6% 吗？用america express, cash reward 算supermarket 吗？
: 谢谢

l*f2014-11-02 07:11

15 楼

二岁是高中数学啊
高数吓了我一跳
当然两岁高中数学这个也超过我想象力了。

【在 w*********y 的大作中提到】

: 和这位神童比，这个BBS的娃基本都输在起跑线了。是的，人家2岁就做高数了。
: Tristan Pang
: From Wikipedia, the free encyclopedia
: Tristan Pang
: Born October 18, 2001 (age 13)
: East Grinstead, West Sussex, United Kingdom
: Residence New Zealand
: Nationality British
: Other names Tristan Owain Pang
: Citizenship British

g*G2014-11-02 07:11

16 楼

没看懂最后一题，是
(... && .. && ..)
|| (... && .. && ..)
|| (... && .. && ..)
这样么？

【在 c**y 的大作中提到】

r*g2014-11-02 07:11

17 楼

这显然是胡扯。2岁做高中数学，7年后还做高中数学(那个剑桥考试). 9岁后的成绩就
不那么惊人了。

【在 w*********y 的大作中提到】

r*n2014-11-02 07:11

18 楼

我猜是这个意思：
输入是一组数int arr[26], 然后实现函数
bool fun(int arr[])
比如第一个条件 arr[0]==5&&arr[1]==1&&arr[25]==20 (A==5 && B==1 && Z==20)
如果输入的arr满足这个条件，fun就要返回true，否则false
用hash来做的话就是如果([ arr[0], arr[1], arr[25] ])的hash值如果不等于（[5,1,
20]）的hash值，就直接返回false，如果相等，就再进一步一个一个判定。如果
predicate很复杂，而且大多数输入都判定为false的情况下，这么做应该会比一个一个
判定要快些。
也不知道这个题是不是这个意思，从感觉有点奇怪。

【在 h********g 的大作中提到】

: 最后一题什么意思？

S*l2014-11-02 07:11

19 楼

可能么？高中数学都是代数和解析几何，从一岁起就不吃不喝学习来着？

e*n2014-11-02 07:11

20 楼

bless

r*g2014-11-02 07:11

21 楼

11 考得那个剑桥alevel 还是中学水平。这9年都原地踏步了。照潮水的话说，decay
的不像样了。

【在 r*g 的大作中提到】

: 这显然是胡扯。2岁做高中数学，7年后还做高中数学(那个剑桥考试). 9岁后的成绩就
: 不那么惊人了。

c*y2014-11-02 07:11

22 楼

多谢指正，应该是这个意思。
原题记不清了，应该下面两种使用方式对数据结构的要求差不多吧。
if ((... && .. && ..)
|| (... && .. && ..)
|| (... && .. && ..)) {
// do something
}
OR
if (... && .. && ..) {
...
} else if (... && .. && ..) {
...
} else if (... && .. && ..) {
...
}

【在 g**G 的大作中提到】

: 没看懂最后一题，是
: (... && .. && ..)
: || (... && .. && ..)
: || (... && .. && ..)
: 这样么？

G*T2014-11-02 07:11

23 楼

你们那里吹牛上税吗？
我们这里不。

【在 r*g 的大作中提到】

: 这显然是胡扯。2岁做高中数学，7年后还做高中数学(那个剑桥考试). 9岁后的成绩就
: 不那么惊人了。

Q*s2014-11-02 07:11

24 楼

答的还不错吧,
来offer了吗?

【在 c**y 的大作中提到】

: 多谢指正，应该是这个意思。
: 原题记不清了，应该下面两种使用方式对数据结构的要求差不多吧。
: if ((... && .. && ..)
: || (... && .. && ..)
: || (... && .. && ..)) {
: // do something
: }
: OR
: if (... && .. && ..) {
: ...

a*g2014-11-02 07:11

25 楼

我一岁就做人生的规划了，抓周时我做了重大决定以后要干什么。。。

【在 G**T 的大作中提到】

:
: 你们那里吹牛上税吗？
: 我们这里不。

c*y2014-11-02 07:11

26 楼

就是这个意思，check给定一个int arr[26]是不是满足所有给定的条件之一。

1,

【在 r*********n 的大作中提到】

: 我猜是这个意思：
: 输入是一组数int arr[26], 然后实现函数
: bool fun(int arr[])
: 比如第一个条件 arr[0]==5&&arr[1]==1&&arr[25]==20 (A==5 && B==1 && Z==20)
: 如果输入的arr满足这个条件，fun就要返回true，否则false
: 用hash来做的话就是如果([ arr[0], arr[1], arr[25] ])的hash值如果不等于（[5,1,
: 20]）的hash值，就直接返回false，如果相等，就再进一步一个一个判定。如果
: predicate很复杂，而且大多数输入都判定为false的情况下，这么做应该会比一个一个
: 判定要快些。
: 也不知道这个题是不是这个意思，从感觉有点奇怪。