出道面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

出道面试题

出道面试题# Programming - 葵花宝典

c*s2015-10-01 07:10

1 楼

太阳双子上升位于狮子座月亮位于狮子座水星位于双子座金星位于白羊座火星位
于天秤座木星位于天蝎座土星位于天秤座天王位于射手座海王位于射手座冥王位
于天秤座北交位于巨蟹座

a*u2015-10-01 07:10

2 楼

☆─────────────────────────────────────☆
happyboar (We must continue our struggle) 于 (Sun Jul 25 16:18:22 2010, 美东) 提到:
赶跑了waichi和他的徒子徒孙。现在版上的讨论已经都是名门正派之间的切磋了，已经
没有邪派，附佛外道的容身之地。
runsun用了多少不眠之夜，在相当一段时间舍弃对妻儿的责任和自己的事业，才赢得了
艰苦卓绝的斗争。我们在景仰的同时，也要想到，谁如果想重复runsun斗waichi的经历
，想把runsun斗下去，也需要付出至少相当的代价才行。指望几句俏皮话就能三气周瑜
骂死王朗，也太不现实了。
☆─────────────────────────────────────☆
SeeU (See you) 于 (Sun Jul 25 16:58:51 2010, 美东) 提到:
runsun 满有功\劳的，语言温和点更好。
走解脱道也要修四无量心。
☆─────────────────────────────────────☆
robbin (robbin) 于 (Tue Jul 27 10:01:04 2010, 美东) 提到:

赶跑？你在编故事吗？
赢？一塌糊涂的惨败还差不多。
☆─────────────────────────────────────☆
runsun (runsun) 于 (Tue Jul 27 10:30:59 2010, 美东) 提到:
waichi確實跑了，此人應該不會再上來了，也許會露個頭之類的，但絕無可能像以前一
樣。
其實我希望他上來，因為那將更加暴露他的真實面目。
waichi，還不至於這麼蠢，他也應該明白，自己大勢已去，這裡不再受他的控制了。
☆─────────────────────────────────────☆
danalake (danalake) 于 (Tue Jul 27 10:48:31 2010, 美东) 提到:
你不觉得他现在就是一个傻瓜吗?
☆─────────────────────────────────────☆
freeman08 (自由自在) 于 (Tue Jul 27 10:51:39 2010, 美东) 提到:
已经
得了
他是一贯掩耳盗铃的，我听他说话，历来想笑，
身上挂个铃铛，捂着耳朵，在客厅里跑来跑去，以为别人听不见。
肚皮舞运动，有助于喷饭消食。
周瑜
☆─────────────────────────────────────☆
Yisu (yisnotme) 于 (Tue Jul 27 11:06:08 2010, 美东) 提到:
见欢乐人当愿众生常得安乐乐供养佛
见苦恼人当愿众生获根本智灭除众苦
见无病人当愿众生入真实慧永无病恼
见疾病人当愿众生知身空寂离乖诤法
见端正人当愿众生于佛菩萨常生净信
见丑陋人当愿众生于不善事不生乐著
☆─────────────────────────────────────☆
runsun (runsun) 于 (Tue Jul 27 11:09:55 2010, 美东) 提到:
你先操心一下你自己吧。
☆─────────────────────────────────────☆
runsun (runsun) 于 (Tue Jul 27 11:11:47 2010, 美东) 提到:
那個留惑潤生的問題，你怎麼跑了？呵呵。
☆─────────────────────────────────────☆
qazxsw321 (qazxsw321) 于 (Tue Jul 27 11:54:32 2010, 美东) 提到:
我的天。。。你们学佛的人斗，比我们圈子里也不差呐。。。呵呵。
☆─────────────────────────────────────☆
advancing (摧邪显正) 于 (Tue Jul 27 14:38:43 2010, 美东) 提到:
唉，这几个都不是学佛的。waichi是GYFM。他的支持者也是。
runsun原来是跟着waichi学的，后来发现waichi是欺骗了他，所以现在糊涂着呢，对于自己是否是佛弟子，自己也不能确定。
☆─────────────────────────────────────☆
freeman08 (自由自在) 于 (Tue Jul 27 14:41:18 2010, 美东) 提到:
我基本上是为了辨别对错的。
有些明显的错，就懒得说了，happybore掩耳盗铃跑得欢，就一笑而已。
☆─────────────────────────────────────☆
robbin (robbin) 于 (Tue Jul 27 22:40:20 2010, 美东) 提到:
看样子你无常的道理没学好。：）
你猜不了他。
他的真實面目你凭啥能看见呢？
自作多情。他从来就没想控制啥。
☆─────────────────────────────────────☆
robbin (robbin) 于 (Tue Jul 27 22:43:38 2010, 美东) 提到:
happybore没咋注意。
我对runsun那些毫无进步的机械回文已经不怎莫看了。：）
☆─────────────────────────────────────☆
robbin (robbin) 于 (Tue Jul 27 22:49:07 2010, 美东) 提到:
造谣，误导。
于自己是否是佛弟子，自己也不能确定。
☆─────────────────────────────────────☆
freeman08 (自由自在) 于 (Tue Jul 27 23:24:16 2010, 美东) 提到:
我都不相信runsun能认真觉得waichi是被动走的，
除非他疯了。
happybore倒是偶尔发点乱七八糟的东西。
☆─────────────────────────────────────☆
advancing (摧邪显正) 于 (Wed Jul 28 03:30:18 2010, 美东) 提到:
这段是runsun 2008-8-29 17:10发在tj论坛上的。当时他还自认是皈依了佛教。但最近
他发贴称，对于自己是否是佛弟子，自己也不能确定。
http://webcache.googleusercontent.com/search?
“在下网名RUNSUN，曾经是QH无上师弟子，接触QH无上师创立的GY法门近十年，对于QH
无上师和QY法门团体有着很深入的了解。同时本人也是网上最大的观音法门弟子聚集地
，mitbbs.com未名空间网站wisdom版的老网友，也曾经是该版QH无上师知名弟子waichi
的忠实支持者。”
“经过将近十年对QH无上师和waichi的观察，已经完全确定这两个越南华人皆是释迦摩
尼佛预言中末法时代的邪师，乃魔王转世，惑乱佛法。已经于大半年前和家人彻底脱离
GY法门，本人正式皈依佛教，法号XX。”
☆─────────────────────────────────────☆
runsun (runsun) 于 (Wed Jul 28 03:40:38 2010, 美东) 提到:
我從來沒有這麼說過。
我是佛教弟子，是在家居士。
我一直在努力做一個符合佛陀教導的真正的佛弟子，并自認為目前做得還不錯，除了罵人
，言語強硬。但不認為這是什麽大問題。
也可以說，我自認自己正是佛弟子，也無愧於一個真正的佛弟子。對佛陀，佛法，佛的聲聞弟子，我沒有任何懷疑，并願意為正法的保留犧牲一切。
至於我是否真的是佛弟子，是否符合正法，符合佛陀教導，這不是我一個人認為就可以的。
有權利判斷的，是佛陀，是解脫者。
佛教弟子，和佛弟子，我認為是兩個不同概念。
☆─────────────────────────────────────☆
runsun (runsun) 于 (Wed Jul 28 03:46:41 2010, 美东) 提到:
再怎麼無常，太陽也不會從西面出來。
拭目以待吧。
不幸的是，我經常猜中他，很多時候，他上句說什麽，我就會知道他下句是什麽，以及
他內心暗藏著什麽。
憑的是法眼。
他想控制的多著，可惜最後失敗了。
☆─────────────────────────────────────☆
runsun (runsun) 于 (Wed Jul 28 03:49:10 2010, 美东) 提到:
waichi，完全是被動走的，很被動，甚至可以說灰頭土臉。
只不過，是要表現出主動離開的姿態的，而粉絲們，也是要信的。
☆─────────────────────────────────────☆
danalake (danalake) 于 (Wed Jul 28 04:32:45 2010, 美东) 提到:
原话:
发信人: danalake (danalake), 信区: Wisdom
标题: Re: 数学是宇宙的本质
发信站: BBS 未名空间站 (Sun Jul 18 22:21:17 2010, 美东)
这个我以前不知道,你现在自己承认了你非佛弟子.
QH
waichi
☆─────────────────────────────────────☆
bdbd (kakali) 于 (Wed Jul 28 04:38:40 2010, 美东) 提到:
回想起来，这个世界上怎么会有人常驻一个版面，职业灌水，估计不是被赶走的，是被
青海无神通走的。
☆─────────────────────────────────────☆
danalake (danalake) 于 (Wed Jul 28 04:42:43 2010, 美东) 提到:
是你撵走的吗?
别自作多情了,你一惯自我感觉良好!!!
你也不是我想得那么蠢,但是,还是比较蠢.
☆─────────────────────────────────────☆
robbin (robbin) 于 (Wed Jul 28 04:54:32 2010, 美东) 提到:
QH
waichi
我是说你这个误导：
☆─────────────────────────────────────☆
robbin (robbin) 于 (Wed Jul 28 04:57:24 2010, 美东) 提到:
你只是被自己的无力，幻想所欺骗而以。
☆─────────────────────────────────────☆
robbin (robbin) 于 (Wed Jul 28 04:58:45 2010, 美东) 提到:
freeman你小看了runsun的自我中心。
☆─────────────────────────────────────☆
advancing (摧邪显正) 于 (Wed Jul 28 05:11:12 2010, 美东) 提到:
嗯，更正一下，他的支持者除了GYFM，还有FLG，以及GYFM爱好者，FLG爱好者，etc.
☆─────────────────────────────────────☆
bdbd (kakali) 于 (Wed Jul 28 09:57:34 2010, 美东) 提到:
他自我中心碍着你什么事了？
☆─────────────────────────────────────☆
bdbd (kakali) 于 (Wed Jul 28 10:02:18 2010, 美东) 提到:
严格的说我认为虽然跑日童鞋有很多缺点，但是纵容神棍在公共版面，恐吓威胁他，并
且要打他下地狱，逼他自杀。任何支持他的人，我认为都是天良丧尽者。
☆─────────────────────────────────────☆
robbin (robbin) 于 (Wed Jul 28 10:14:55 2010, 美东) 提到:
哈哈哈。。。etc.。。。你就接着刻意误导吧。
☆─────────────────────────────────────☆
advancing (摧邪显正) 于 (Wed Jul 28 10:34:10 2010, 美东) 提到:
你其实学waichi已经很神似了。什么造谣啊，误导啊，就是不说到底怎么了。
waichi支持者显然上述群体为主流。
☆─────────────────────────────────────☆
freeman08 (自由自在) 于 (Wed Jul 28 10:50:49 2010, 美东) 提到:
可能，他先入为主的观念极强。
说去扯远的话，他可能先修高尚了，认定自己的一部分，
好像要替天行道，而不看自己的另一部分邪、弱、差的
地方。而恰恰是那些东西才是绑人在三届内的东西。
不检查为什么被绑，天天只是背书，就不用修了。
我也有问题，我应该尽量避免这些，应该跟言必信
行必果的人打交道。
☆─────────────────────────────────────☆
bdbd (kakali) 于 (Wed Jul 28 11:39:20 2010, 美东) 提到:
应该跟言必信行必果的人打交道。
言行不一。
☆─────────────────────────────────────☆
runsun (runsun) 于 (Wed Jul 28 12:46:23 2010, 美东) 提到:
算不上，我只算誘因。
我個人并不希望老歪走，最好老歪常駐。
我原來申請班副，想干的一件事就是想給waichi解封。不搞得那麼對立。
結果serawang沒批准，呵呵。
☆─────────────────────────────────────☆
runsun (runsun) 于 (Wed Jul 28 12:51:56 2010, 美东) 提到:
这个我以前不知道,你现在自己承认了你非佛弟子.

N*D2015-10-01 07:10

3 楼

【以下文字转载自 PDA 讨论区】
发信人: pc (>>>>>mac), 信区: PDA
标题: Re: 苹果用修改过的图像告三星Tab 10.1
发信站: BBS 未名空间站 (Mon Aug 15 21:11:31 2011, 美东)
老美有时候挺深的。但凡是苹果出的都是苹果发明的，至于之前那么7,8年里出的
tablet都是塑料之类的

l*s2015-10-01 07:10

4 楼

A frog is trying to jump across a river by hopping on rocks in between the
left and right banks.
At each step, the frog can choose 3 speeds to jump to the next rocks (not
necessary neighbor), increase 1 speed, decrease 1 speed or keep the same
speed.
You are given a list of rock's positions (sorted), and need return if the
frog can jump cross the river.
The frog starts from stone position 0, and the initial speed is 0.

j*n2015-10-01 07:10

5 楼

这个盘很像习近平阿

k*r2015-10-01 07:10

6 楼

bfs?
Use a queue to record the pair of speed and position P(s,p);
At each poll to add new P(s, p + s), P(s + 1, p + s + 1), P(s - 1, p + s - 1
) if there is a rock at any of new position.
return true, if the right bank is reached; return false, if queue is empty.

c*s2015-10-01 07:10

7 楼

然道哥要去搞政治？

l*s2015-10-01 07:10

8 楼

Code, Code, we are on programming discussion board.
BTW: this problem comes from Snapchat.

1
.

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

: bfs?
: Use a queue to record the pair of speed and position P(s,p);
: At each poll to add new P(s, p + s), P(s + 1, p + s + 1), P(s - 1, p + s - 1
: ) if there is a rock at any of new position.
: return true, if the right bank is reached; return false, if queue is empty.

j*n2015-10-01 07:10

9 楼

你除了两水象星座，其他都是火象风象
说明你一点都不腹黑，啥事都直接说，就是有点小聪明小诡计，哈哈
另外你喜欢追好多个女生吧，和同一个人时间长了不行
还有你是话多讲话有点喜欢夸张吧脑子很好，反应很快，口才很好，同时能做很多件事。

v*u2015-10-01 07:10

10 楼

看不懂题目。。。

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

: A frog is trying to jump across a river by hopping on rocks in between the
: left and right banks.
: At each step, the frog can choose 3 speeds to jump to the next rocks (not
: necessary neighbor), increase 1 speed, decrease 1 speed or keep the same
: speed.
: You are given a list of rock's positions (sorted), and need return if the
: frog can jump cross the river.
: The frog starts from stone position 0, and the initial speed is 0.

t*c2015-10-01 07:10

11 楼

习近平群星双子八宫，可lz十一宫头双子呀

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

: 这个盘很像习近平阿

l*s2015-10-01 07:10

12 楼

I was in a telephone and listen to all to get the problem. There wasn't text
descriptions and samples, and function input needs you define it, so I
started in this way.
I was waiting for your questions just like how the interview worked. Now I
am adding a few samples below:
1) stone list 0, 1, 3, 5, 6, 8, 12, 17 is reachable, the frog is jumping
from stone 0 with +1 speed, it goes to stone 1, then +1 it goes to stone 3,
then keep same speed to go to stone 5, and so on, after trying all
possibilities there is a way the frog can jump out of stone 17.
2) 0, 1, 2, 3, 4, 8, 9, 11 is not reachable because there is no jumping
combinations satisfy the frog jump over stone 11.

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

: 看不懂题目。。。

j*n2015-10-01 07:10

13 楼

习近平的那些宫位不准确，星座基本上准确，因为只知道出生日期地点，不知道时间，
宫位好像是被出生的具体时刻决定的，所以我不太相信宫位，如果我妈把我忍了几分钟
，那我的命运就不同了？
而且宫位好像中国才有吧？不知道是谁发明的

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

: 习近平群星双子八宫，可lz十一宫头双子呀

y*a2015-10-01 07:10

14 楼

a=[ 0, 1, 3, 5, 6, 8, 12, 17]
b=[0, 1, 2, 3, 4, 8, 9, 11]
def jump(pL, current_speed, current_position):
if not pL:
return [(current_speed, current_position)]
if current_position+current_speed in pL:
idx = pL.index(current_position+current_speed)
rv = jump(pL[idx+1:], current_speed, current_position+current_speed)
if rv:
return [(current_speed, current_position+current_speed)] + rv
if current_position+current_speed+1 in pL:
idx = pL.index(current_position+current_speed+1)
rv = jump(pL[idx+1:], current_speed+1, current_position+current_
speed+1)
if rv:
return [(current_speed+1, current_position+current_speed+1)] +
rv
if current_position+current_speed-1 in pL:
idx = pL.index(current_position+current_speed-1)
rv = jump(pL[idx+1:], current_speed-1, current_position+current_
speed-1)
if rv:
return [(current_speed-1, current_position+current_speed-1)] +
rv
return None
print '============',a
print jump(a, 0, 0)
print '============',b
print jump(b, 0, 0)

c*s2015-10-01 07:10

15 楼

谢谢，好像我以前都没同时追好几个女生啊，出了国貌似暧昧了好几个。不过最近喜欢
而且追一女生，不想和别人暧昧了。貌似我确实太直接了，喜欢一个人就会忍不住最后
说出来。小时候我很害羞也很活泼，现在好像皮越来越厚了。自我感觉讲话不是很夸张
。能同时做很多事是什么概念啊~~~和同一个人时间长了不行，可是我很期待天长地久
的爱情啊。最近在追一水瓶女孩，真是郁闷啊郁闷啊。。。

件事。

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

: 你除了两水象星座，其他都是火象风象
: 说明你一点都不腹黑，啥事都直接说，就是有点小聪明小诡计，哈哈
: 另外你喜欢追好多个女生吧，和同一个人时间长了不行
: 还有你是话多讲话有点喜欢夸张吧脑子很好，反应很快，口才很好，同时能做很多件事。

I*c2015-10-01 07:10

16 楼

这道题用dynamic programming来解决
做一个表格，横轴代表每个石头的位置，纵轴代表速度。速度的最大值就是最远石头的
开方。因为假设速度增加的最佳情况是1+2+3+4+5....,所以最远石头的距离就是n*(n+1
),n就是最大速度。
对于表中的任何一个值t(p,s)代表青蛙有没有可能以s的速度到达p石头的位置。
t(p,s)= t(p-s,s-1) || t(p-s),s) || t(p-s,s+1)

I*c2015-10-01 07:10

17 楼

个人认为，无论是用dfs (backtracking) 还是bfs都是穷尽的思路，其中很多重复计算
，时间复杂度是指数级。

b*S2015-10-01 07:10

18 楼

0, 1, 3, 5, 6, 8, 12, 17 is reachable
怎么从8跳到12啊,前面6->8的时候速度才是2, 2+1=3, 3+8=11啊,到不了12啊

text
,

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

: I was in a telephone and listen to all to get the problem. There wasn't text
: descriptions and samples, and function input needs you define it, so I
: started in this way.
: I was waiting for your questions just like how the interview worked. Now I
: am adding a few samples below:
: 1) stone list 0, 1, 3, 5, 6, 8, 12, 17 is reachable, the frog is jumping
: from stone 0 with +1 speed, it goes to stone 1, then +1 it goes to stone 3,
: then keep same speed to go to stone 5, and so on, after trying all
: possibilities there is a way the frog can jump out of stone 17.
: 2) 0, 1, 2, 3, 4, 8, 9, 11 is not reachable because there is no jumping

W*o2015-10-01 07:10

19 楼

没有距离信息嘛？

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

g*y2015-10-01 07:10

20 楼

from 5 to 8, skip 6.

【在 b***S 的大作中提到】

: 0, 1, 3, 5, 6, 8, 12, 17 is reachable
: 怎么从8跳到12啊,前面6->8的时候速度才是2, 2+1=3, 3+8=11啊,到不了12啊
:
: text
: ,

w*m2015-10-01 07:10

21 楼

像楼上说的，二维dp
leetcode可以收录了
应该是hard

C*n2015-10-01 07:10

22 楼

这道题我在snapchat onsite的时候也遇到了，以前没见过，当时只给出了dfs的解。
现在给出dfs和dp的解，可能有bug，没做深度测试。
#include
#include
using namespace std;
//basically we can use a dfs to solve the problem
bool jumpDfs(vector & stone_pos, int pos, int speed) {
int n=stone_pos.size();
if(pos==n-1) return true;
if(!stone_pos[pos] || pos>=n || speed<1) return false;
for(int s=speed-1; s<=speed+1; ++s) {
if(jumpDfs(stone_pos,pos+s,s)) return true;
}
return false;
}
//assume init_speed >= 0
bool canJumpOverDfs(vector & stone_idx, int init_speed) {
//convert stone_idx to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
int n=stone_idx.back()+1;
vector stone_pos(n);
for(int p:stone_idx) stone_pos[p]=true;
return jumpDfs(stone_pos,0,init_speed);
}
//dfs has a lot of repeated calculations, we can use dp to avoid it
//assume init_speed >= 0
bool canJumpOverDp(vector & stone_idx, int init_speed) {
//convert stone_idx to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
int n=stone_idx.back()+1;
vector stone_pos(n);
for(int p:stone_idx) stone_pos[p]=true;
//assume every stone_position is a stone, the max speed at the end is
less than
int safe_max_speed=init_speed+n-1;
//the actual max speed could be calculated by:
//(init_speed+1) + (init_speed+2) + ... + max_speed = n;
// max_speed < safe_max_speed
//dp[p][s] means at stone position p, if there exists a case that frog
has speed s
vector> dp(n, vector(safe_max_speed+1));
if(init_speed>=1) dp[0][init_speed-1]=true;
dp[0][init_speed]=dp[0][init_speed+1]=true;
for(int p=1; pif(stone_pos[p]) {
for(int s=1; s<=safe_max_speed; ++s) {
//any dp[p][s] can be achived by the previous stone_position
p-(s-1) with speed s-1
//after the jump, increase speed by 1, then we get stone_
position p with speed s;
//also it can be achived by the previous stone_position p-s
with speed s;
//and the previous stone_position p-(s+1) with speed s+1
if(p>=s-1) dp[p][s]=dp[p-s+1][s-1];
if(p>=s) dp[p][s]=dp[p][s] || dp[p-s][s];
if(p>=s+1) dp[p][s]=dp[p][s] || dp[p-s-1][s+1];
}
}
}
//check the last stone_position, if there exists a case that frog has
any speed
for(bool b:dp[n-1]) {
if(b) return true;
}
return false;
}
int main() {
vector stone_idx={0,1,2,5,6,12};
//initial speed 5,6,7 are good to reach the end
cout << "Dfs: init speed=4, can jump over? " << canJumpOverDfs(stone_idx
,4) << endl;
cout << "Dp: init speed=4, can jump over? " << canJumpOverDp(stone_idx,
4) << endl;
cout << "Dfs: init speed=5, can jump over? " << canJumpOverDfs(stone_idx
,5) << endl;
cout << "Dp: init speed=5, can jump over? " << canJumpOverDp(stone_idx,
5) << endl;
}

k*i2015-10-01 07:10

23 楼

hop _ _ [] = True
hop speed pos poz = or [
hop speed_n pos_n $ dropWhile (<= pos_n) poz |
n elem pos_n poz ]
main = do
print $ hop 0 0 [0, 1, 3, 5, 6, 8, 12, 17] -- True
print $ hop 0 0 [0, 1, 2, 3, 4, 8, 9, 11] -- False

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

g*e2015-10-01 07:10

24 楼

dp
Use Boolean matrix dp(x, s) to denote if frog can reach rock x at step s.
O(n*s*s)

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

g*e2015-10-01 07:10

25 楼

Definitely doesn't warrant "hard"
A typical medium problem for Leetcode

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

: 像楼上说的，二维dp
: leetcode可以收录了
: 应该是hard

w*m2015-10-01 07:10

26 楼

https://leetcode.com/problems/frog-jump/

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

: Definitely doesn't warrant "hard"
: A typical medium problem for Leetcode

w*j2015-10-01 07:10

27 楼

[0, Integer.MAX_VALUE]

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

: dp
: Use Boolean matrix dp(x, s) to denote if frog can reach rock x at step s.
: O(n*s*s)