K*******i 发帖数: 399 | 1 这题Interview Exposed上的经典老题了,不过面试官也知道太老的题就不会考了吧 |
|
w*y 发帖数: 5 | 2 一个老题:醉汉过桥
说一个醉汗初始在一条100米长的桥上的第17米位置。然后以0.5的概率随机往前
,或者往后走,每一秒走一米。问,平均需要多少秒他才能走完这座桥。
经典老题,不记得解法了。哪位帮忙解一下,或者给个连接? |
|
f******p 发帖数: 173 | 3 全是老题,设计题没答好,听语气应该是挂了
1. sorted array to bst
2. only one number appears odd times in array, find it
3. design furniture factory
答到设计题时,不知不觉就慌了,还是准备的不够。wifi中间还突然给我掉线,干 |
|
K******g 发帖数: 1870 | 4 这还是老题啊?从没有见过这两题。我已经在这里混了2个多月了。。。 |
|
n****r 发帖数: 120 | 5 【 以下文字转载自 Topcoders 俱乐部 】
发信人: nibber (nibber), 信区: Topcoders
标 题: 讨论一道老题:分离数组中的正负数
关键字: 算法 数组 O(n) 时间复杂度分析
发信站: BBS 未名空间站 (Thu Nov 8 10:45:04 2012, 美东)
负数在前,正数在后,需要保持负数之间和正数之间的顺序不变!时间复杂度要求O(n)
,空间复杂度O(1)
下面是我的代码,空间复杂度O(1)没问题,时间复杂度分析如下,
设数组中共有负数X个,分散在K个分离的连续负数的子数组段,每个子数组段的长度为
Li,1<=Li
下面算法中K个分离的负数子数组段移到最后位置需要最多进行K次swap操作,而swap的
时间复杂度是O(n),(这里n是子数段的长度),因此
一共的需要的时间是O(L1)+O(L2)+...+O(Lk) = O(X).因此整体的时间复杂度就是O(n)
这个分析妥不妥?请大牛们给指点一下,还有其他的时间O(n),空间O(1)解法没有?
public static void split(int[] ... 阅读全帖 |
|
s*****n 发帖数: 994 | 6 全是老题,设计题没答好,听语气应该是挂了
recursive
xor
1 base furniture class with all derived ones
2 production lines
3 center channel to receiver request and patch to empty production line
这个比较衰。。 |
|
R*********a 发帖数: 306 | 7 【 以下文字转载自 Stock 讨论区 】
发信人: ljiiuan2 (文刀兄), 信区: Stock
标 题: 老题重出: 你能在此图中看到什么?
发信站: BBS 未名空间站 (Thu Aug 18 19:36:59 2011, 美东)
答案:光明 |
|
z*******9 发帖数: 167 | 8 【 以下文字转载自 Quant 讨论区 】
发信人: zheda1999 (zheda1999), 信区: Quant
标 题: Re: 一道很有意思的老题: some thought
发信站: BBS 未名空间站 (Tue Aug 10 00:32:00 2010, 美东)
I think this is the first serious response I have ever seen.
==============
sly, F or G is cumulative distribution function, which is
uniform in [0,1]. seems to me nothing wrong here in shede's
expression.
============
I think your discussion is very close to my point here.
F is uniform in [0,1]. Do you know why?
If you know how to prove it, you will know t |
|
|
z*******9 发帖数: 167 | 9 【 以下文字转载自 Quant 讨论区 】
发信人: sly (伸懒腰), 信区: Quant
标 题: Re: 一道很有意思的老题: some thought
发信站: BBS 未名空间站 (Tue Aug 10 10:58:19 2010, 美东)
Thank you for your reply. I thought about it last night and worked out a
similar solution as well:
error rate=E[G(X1)*(1-F(X1))+(1-G(X1))*F(X1)], one thing to note here is
that the expectation is taken on F. then:
error rate = Integral {F(X)dF(X)}+Integral{G(X)dF(X)-2*G(X)*F(X)dF(X)}
=0.5+Integral{(G(X)*d(F(X)-F(X)^2)}
=0.5-Integral{(F(X)-F(X)^2)dG |
|
e******s 发帖数: 38 | 10 板上1年多前的老题:
老帖子在 http://www.mitbbs.com/article_t/JobHunting/31347264.html
题目: A , B 2个人商量好策略,然后一个从52张牌里面随机抽5张,看牌,考虑。。
。然后排在
桌上,摊开前4张,第5张面朝下,(前四张牌都是朝上,并且不能被转个角度来代表1或
者0.
)由第二个人判断第5张牌。 问这个策略。
如果我们假设:第5张牌不参与任何排列和组合, 我们先assume 它被A选出来之后,放
到一边。 完全靠前4张牌来猜第五张牌。 不知道有什么好的解法。 |
|
i***d 发帖数: 28 | 11 来自主题: JobHunting版 - 问一道老题 问一道老题,考古了但没有找到:
字符串有数字和字母,把数字放到字母的前面,但要保持原来的顺序。
例如: 1a2b3c==>123abc.
有没有比O(n^2)好的算法啊? 谢谢! |
|
m*****n 发帖数: 2152 | 12 昨天被问了一道老题. array={a1, a2, ..., an, b1, b2, ..., bn}变成 {a1,bn,a2,
bn-1,...,bn,a0},要求时间复杂度O(N),空间O(1).
当时根本不会,我所知道最快的算法是类似quick sort的方法,要O(NlogN), 这个O(N)怎
么做? 我记得以前有人贴过,找不到了.
还有不用random, time种子什么的, 怎么给shuffle任意一个数组,
大概就是
void shuffle(int A[]){
}
每次出来的 A 的结果不一样. |
|
g*********5 发帖数: 1 | 13 由worldquant的一道老题想到的
一个蛋糕,切成连续的n块,有m个同种豆,问如果每小块上放若干豆,并且要求相邻的2块
上豆的数目不一样,有多少种方法?
谢谢 |
|
z******8 发帖数: 844 | 14 ☆─────────────────────────────────────☆
jailbreak (biology) 于 (Wed Apr 30 09:38:34 2014, 美东) 提到:
挥挥手,终于告别了step1,一路走来,着实不易!考完试后,心里平静得出奇,成绩
本身,似乎已被抛到脑后,或许是因为复习与做题,已经让自己麻木了。今天是发榜的
日子,却突然让自己经历了从渴望迫切,到心跳加速,再到如释重负的转变。至于分数
,250+,虽然是意料之外,却也在情理之中。但这已经不重要了,重要的是,自己真
的已经告别了那段日子。
在过去的日子里,得到了前版主JennyGao和众多前辈的帮助和指点,在此一并致谢!写
下这份考经,并不代表自己对成绩有多满意,或者对自己的复习有多自信。我只是想纪
录下自己的足迹留作纪念,更希望能给后来者提供些许经验和教训,也算是回馈麦地版
曾经给过我的帮助和鼓励。
一、 材料篇
这里点评一下我用过的学习材料。其实我看过的书不太多,其他还有一些我没看过的好
书,这里就不介绍了,大家可以参考别的考经。
1) FA:全5星推荐。必读必背,必须... 阅读全帖 |
|
j*******k 发帖数: 209 | 15 四、 做题篇
1) 距考前大约8-4个月,断断续续做了UWorld offline第一遍:前期正确率大概
在60%左右,后期在70-80%之间。
2) 距考前大约4个月,用2个月时间集中完成了5套offline NBME老题。正确率如下:
NBME form 1:83.5%
NBME form 2:85%
NBME form 3:89%
NBME form 4:90%
NBME form 5:89%
3) 距考前3个月,做了UWorld offline第二遍,正确率在90%左右。
4) 之后做了online NBME form 6:600(245)。
5) 2周后做online NBME form 7: 530(228),很受打击,所谓骄兵必败,必须痛
定思痛。
6) 距考前2个月,做了一个月的kaplan qbank,挺难的,平均正确率83%。
7) 之后做了online NBME form 11:540(237),从这次开始,NBME采用了新的评
分标准。
8) 最后1个月开始做UWorld online qbank... 阅读全帖 |
|
s**********g 发帖数: 14942 | 16 实在没时间,你可以考虑高频老题+100新题
高频老题是经典题,概率肯定不低
新题是最近真人被考到的题,也有不少的概率 |
|
l****e 发帖数: 32 | 17 老题都有些啥。。。
我面的是实习,其他的都是老题,就不说了。
关于FP数的加法,就是给定32bit的unsigned int,当成FP运算,给出结果,结果也是
32bit int形势
的,不考虑溢出的情况。后来他觉得这个题好像太复杂了,改成都是positive的情况(
不考虑负数)。
这个题目其实没做好,忘记了一个重要情况,就是小数位其实省略了那个最高位的1,
比如小数部分是:
1.1011,其实实际中表示成:1011。如果算加法的话,得把这个最高位的1加上去,然
后还好考虑carry进
位的情况,同时还要考虑是不是修改指数部分。我答得很乱,不过还好,他估计也觉得
题目太难了,解释FP
数字在register里的表示就解释了好久,然后就没怎么编程。我觉得思路和表达很重要
,就是让他知道在给
定充分的解释和介绍之后你会做就行了。。。
bless大家都有好运! |
|
x****m 发帖数: 1084 | 18 请教下从能做老题到 处理新题 用了多久 下了些什么功夫? 感觉老题做多了思维有点
定势了 |
|
j**l 发帖数: 2911 | 19 具体细节忘记了,但是梯子的辐条是单向的。
也就是,原始链表的next指针保留,原始链表的random指针改为单向辐条指向对应的复制链表的节点。复制链表的random指针暂时不用,而复制链表的next指针指向的是某个原始链表的节点(因为原始链表的random指针被破坏了,改造成了单向的辐条,所以需要间接通过复制链表的next指针保留原始链表的random指针的指向信息)。接下来,先把复制链表的闲置random指指针改造到正确位置。然后考虑断开:相互辅助,有次序的从表头开始逐个恢复原始链表的random指针和复制链表的next指针。
这是一个老印想到的解法。老中发表在网上的解法,以串成两倍长度的珍珠为多,原始链表和复制链表的对应节点为珍珠串中相邻的一对珠。这道题在国内,也是招聘名题,所有人都会体会到先合后分这种思想的巧妙。 |
|
y**i 发帖数: 1112 | 20 是不是这样:
第一次复制的时候,让复制链表的每个结点的random指针=原始链表的相应结点的
random指针,然后让原始链表的相应结点的random指针=复制链表的那个结点的指针,
第二次遍历的时候就可以通过复制链表的random指针找到原始链表的random,再通过原
始的random找到复制的random应该指向的结点,但这个时候不能修改random的值啊,一
修改后面的结点就不能通过这个方法找了(如果后面的结点random指向前面的结点的话
),看来就需要临时把random的值存在数组里了?第三次遍历的时候再修改random,也
同时break了两个链表的关系。
那个两倍长的方法倒是比较好实现。
个老印想到的解法。老中发表在网上的解法,以串成两倍长度的珍珠为多,原始链表和
复制链表的对应节点为珍珠串中相邻的一对珠。这道题在国内,也是招聘名题,所有人
都会体会到先合后分这种思想的巧妙。 |
|
r****o 发帖数: 1950 | 21 能不能详细说说老中的二倍珍珠链解法啊?
老印的解法确实很巧妙。
复制链表的节点。复制链表的random指针暂时不用,而复制链表的next指针指向的是某
个原始链表的节点(因为原始链表的random指针被破坏了,改造成了单向的辐条,所以
需要间接通过复制链表的nex
始链表和复制链表的对应节点为珍珠串中相邻的一对珠。这道题在国内,也是招聘名题
,所有人都会体会到先合后分这种思想的巧妙。 |
|
t**********h 发帖数: 2273 | 22 到后期的话,重点不是新题,而是老题。按照21天搞gre的模式来说的话,到了后期,
就是重复,重复,再重复,然后诞生希望。所有每天就是过做过的几百题,达到快准狠
,bug free
一家之言
发现提升水平已经很难了。想问一下各大牛,如果只是想保持状态每天需要做几题呢?
10题够了吗?
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
t**********h 发帖数: 2273 | 23 都是老题阿,每天循环反复做,滚雪球的方式扫题,到最后每题都至少过了几十遍了。
最后基本看到题就默写出来了
你太牛了。一天几百题ya呀。
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
f*********m 发帖数: 726 | 24 从版上大牛的面经中找到的:
---------------
1)原题can Jump, 然后拓展到minJump, 我用dp + greedy从左边做, 写完code,他要
求再说说从右边忘左边如何高。 我说还是dp + greedy(这个估计是他自己背的答案)
,他想了会说, 算了,好像跟你的一样!我也不知道是不是一样就move 到下一道题了。
从右往左好像不好想吧,从左往右跳(最后跳到最右边)和从右往左跳(最后跳到最左
边)不是等假的吧?
-------------
2)一个BST tree, 现在要求在每个node, 添加一个succeesor的指针。 用递归搞定
(这个在他提示下搞出的,code 用递归就几行而已)
考虑inorder 的succeesor。用inorder traverse,大家看对不对?
void inorder(node* n, node*& prev)
{
if (!n)
return;
inorder(n->left, prev);
if (!pre)
pre->succeesor = n;
pre = n;
inord... 阅读全帖 |
|
d*******l 发帖数: 338 | 25 来自主题: JobHunting版 - 问一道老题 这题的一个特例就是那个把a1 a2 ..an b1 b2 .. bn变成a1 b1 a2 b2 .. an bn的题。
那题要求inplace不是没人给出O(n)的办法么,这题的普遍情况应该复杂的多。 |
|
N*****N 发帖数: 1605 | 26 标 题: 发挥题-如何化解尴尬局面?
发信站: BBS 未名空间站 (Fri Mar 30 20:27:17 2007)
今天忙了一天,没时间灌水,刚闲下来,给大家出个题,我也没有标准答案,就是想看看出
现这种情况,怎么答比较合适,NICEMAN给评一下吧~~~
开始:
门外~~~
媳妇在给孙子喂奶~~~~
公爹路过,叫了一声孙子,孙子看爷爷,放下口中的奶~~~~
公爹的手伸向了媳妇的乳房~~~~
儿子正巧推门而出~~~
媳妇一阵脸红~~~~~
此时次刻~~~
假如你是公爹你怎末说
假如你是儿子你怎末说
假如你是媳妇你怎末说
三者至少选取一说一段话,以化解僵局~~~~~ |
|
b******7 发帖数: 79 | 27 我刚刚面试amazon被问得,首先,这是一道老题,后悔当时看到这道题的时候没仔细研
究。以前我在版内看过这道题,但是没有人提出正确解,我也就大概想了想,没仔细想
,结果今天吃亏了。
一个分布式文件系统,7个server, 原来的文件用MD5 hash后分布到这7个server中的某
一个(比如hash%7),现在这些server快满了,就增加了7个server, 这样新文件来了可
以放到这些新的server上面。问题是,我们不能挪动原有server的文件,旧的文件仍旧
可以被访问。那么我们怎么改这个hash系统以至于新,旧文件都可以被正常read,
write。举例,如果新文件来了,我们如果还是hash%7,那么就会放到旧的server上,
但是如果放到新的上,那怎么改hash?
肯定要用hierarchical 的hash,比如,如果hash%7==1, 这些hahs被再次hash为0,1,
为0的去旧server,1的去新server,但是这个缺点是旧的已经满了,而且给你一个hash,
旧的文件属于新的还是就得server没法得到。
希望牛人指点!!!非常感谢! |
|
N*D 发帖数: 3641 | 28 正确的做法是backfill,其他解法都是hack
我刚刚面试amazon被问得,首先,这是一道老题,后悔当时看到这道题的时候没仔细研
究。以前我在版内看过这道题,但是没有人提出正确解,我也就大概想了想,没仔细想
,结果今天吃亏了。
一个分布式文件系统,7个server, 原来的文件用MD5 hash后分布到这7个server中的某
一个(比如hash%7),现在这些server快满了,就增加了7个server, 这样新文件来了可
以放到这些新的server上面。问题是,我们不能挪动原有server的文件,旧的文件仍旧
可以被访问。那么我们怎么改这个hash系统以至于新,旧文件都可以被正常read,
write。举例,如果新文件来了,我们如果还是hash%7,那么就会放到旧的server上,
但是如果放到新的上,那怎么改hash?
肯定要用hierarchical 的hash,比如,如果hash%7==1, 这些hahs被再次hash为0,1,
为0的去旧server,1的去新server,但是这个缺点是旧的已经满了,而且给你一个hash,
旧的文件属于新的还是就得server没法得 |
|
g******d 发帖数: 511 | 29 第一道应该是老题了,原题是:给定一个足够多的按字典排序的words set.learn
alphabet order.
对每个学到的rule,加入一个数据结构.例如:
a->b, e, f, z, ....
b->d, g, ...
...
z->
z 为空,即为尾.然后再将a->y中所有的Z去掉,再找空的char.数据结构的要求O(1)时间
去掉一个char,最快时间找到为空的char.
第二题也在本版见过.好像是靠hardware与sofware的协调问题, API的flexibility.
第三道没有搞百,给定string X (size sx) and Y (size sy),将Y从X的0, (sx-sy)/2,
sx-sy处开始插入? |
|
t**********h 发帖数: 2273 | 30 我擦,我是默写老题而已,不是做新题
高帅府每天几百道题也没事呀
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
s********u 发帖数: 1109 | 31 我现在做设计题,跟设计database题一样,喜欢画一个entity-relationship图,然后
每个entity有些属性。这样思路清楚很多。
不过这个题好像不是很明确,我能想到的也就是furniture弄一个factory pattern,然
后每一条production line调用一个furniture的creator来生产。然后factory作为一个
singleton class内含一个production line数组。
factory接一个订单,分配到当前空闲的production line,然后让production line去
生产?
好像没有什么真正需要实现的东西 |
|
p***o 发帖数: 3399 | 32 【 以下文字转载自 Quant 讨论区 】
发信人: latingirl (拉丁妹), 信区: Quant
标 题: 赛马题答案到底是多少,网上众说纷纭。。。
发信站: BBS 未名空间站 (Wed May 11 20:10:23 2011, 美东)
老题了,49匹马,7个轨道,不能计时,要比多少次能找到第25快的(也就是找中位数
) |
|
m*****n 发帖数: 5245 | 33 ☆─────────────────────────────────────☆
mywaistcoat (马甲) 于 (Tue Sep 25 16:05:57 2007) 提到:
刚放下电话。
Two teams
Team #1
1. Calculate intersection of 2 sorted array, this is easy;
2. Search an integer in a shifted sorted array, such as:
7 8 9 10 1 2 3 4 5 6
都是老题,我答的太快,他想了想又给了下面的题,没做出来,结果电话一放就想出来
了。
3. Character array, contains same amount of "x" and "z",eliminate all "z",
and duplicate all "x", all duplicated "x" must stay next to the original "x"
, and all other unrelated character must keep |
|
x****r 发帖数: 99 | 34 同问,,,这题我看他的解也很迷茫,感觉那个电子书里面有的复杂度是乱说的,比如
matrix里面找
max sub-matrix sum那题他的优化只做了一半只能到N^5,还有N^4和N^3的解法都没说
four
smallest).
the |
|
h**k 发帖数: 3368 | 35 老题,似乎是facebook考过的题。DP解法。
wi |
|
r********g 发帖数: 1351 | 36 我面的是实习,其他的都是老题,就不说了。
关于FP数的加法,就是给定32bit的unsigned int,当成FP运算,给出结果,结果也是
32bit int形势
的,不考虑溢出的情况。后来他觉得这个题好像太复杂了,改成都是positive的情况(
不考虑负数)。
这个题目其实没做好,忘记了一个重要情况,就是小数位其实省略了那个最高位的1,
比如小数部分是:
1.1011,其实实际中表示成:1011。如果算加法的话,得把这个最高位的1加上去,然
后还好考虑carry进
位的情况,同时还要考虑是不是修改指数部分。我答得很乱,不过还好,他估计也觉得
题目太难了,解释FP
数字在register里的表示就解释了好久,然后就没怎么编程。我觉得思路和表达很重要
,就是让他知道在给
定充分的解释和介绍之后你会做就行了。。。
bless大家都有好运! |
|
e******s 发帖数: 38 | 37 这个题不是BST, 就是一般的binary tree.
当然有别的题是BST里找。
of |
|
m**q 发帖数: 189 | 38
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),求最小值。
... 阅读全帖 |
|
m**q 发帖数: 189 | 39
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),求最小值。
... 阅读全帖 |
|
s**x 发帖数: 7506 | 40 偶很早以前考过别人这个题, 当时偶希望的答案是用 single linked list create
one circle, just go through circle , remove element until the last one. 不知
道对不对, 这道题应该在一个算法书上, 想不起来了。 |
|
|
k****n 发帖数: 369 | 42
这不就是传统数据库么。。。
数据放在一个静态数组或者list里面,用BTREE或者HASHMAP做name的index
can
老题就看经典好了,IR领域的经典题,看怎么做模糊检索
大概就是做cyclic suffix tree,或者bi/tri-gram的index什么的
但是为什么这个能match到itveabcu呢?最起码结尾应该是ou吧? |
|
m**q 发帖数: 189 | 43 题目6. 任务分配,假设有N个任务,每个任务需要W_i工作量,M个人,每人每天能做工
作量w_i,如何安排工作,使得所有工作能最快完成。这个问题其实更像一个开放性问
题,因为一个合理的贪心策略,最后的结果跟最优结是很接近的(大致上,最多只差一
天)。
是小尾羊以前提到的题目,可能是老题了,没找到答案。
求解答 |
|
H****s 发帖数: 247 | 44 这题跟直方图那题不一样吧!我理解的题目是只考虑左右两边的线段和x轴构成的水桶
,跟中间的线段没关系。(1,3),(2,2),(3,3)等效于 (1,3), (3,3)所以容积是6 |
|
|
h**k 发帖数: 3368 | 46 第二题是老题,题目是从一个不知到总长度的int stream中采集k个样本,怎么做才能
使stream中的每个int被采的概率相同? |
|
M*****e 发帖数: 568 | 47 之前帖子的一道题,没有想到特elegant的解法。主要是需要一个list存储能够蓄水的
点,而这些点选择的标准是不能小于当前点和list中的前一个点,说起来比较绕口。
不要说从左扫一个从右扫一个的解法,这种解法没办法解决中间有两个峰的情况,比如
3 1 8 1 9 1 5 => 2+7+4=13
X)Onsite 老题新酒,直方图,天上下雨,求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法,就是说:
有些地方高度随时会变,
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法,最快的返回改变高度之后的结果 |
|
|
h*******0 发帖数: 270 | 49
话说这道题我同学每次面试都必考,面了4次了,次次都有这题。。。 可惜我一次都没
遇到过。。。 |
|
g***j 发帖数: 1275 | 50 大小集合都过了,大部分一次过,请问这算快还是慢的?才开始做题,不可能每天都2
个小时,如果要做完,这要多久啊!
都是老题
1) 3 sum
2) valid parentheses;
3) merge two sorted lists;
4) implement strstr();
5) pow(x,n);
6) merge intervals; |
|