|
t**n 发帖数: 272 | 2 第二题是resevoir sampling? 第一批10个数字进数组,第二批10个以1/2概率替换数组,
第三批1/3概率... 但是这样连续10个的命运就联系在一起了,不知道是否符合题意
第一题难道要计算数组的和和平方和? |
|
d********e 发帖数: 132 | 3 请问第三道题是什么意思?没明白题意。
two
equal
again
so |
|
b******v 发帖数: 1493 | 4 来自主题: JobHunting版 - 一道面试题 假设第一个被选数字前有a个数字,最后一个被选数字后有b个数字
则这a+b个数字可以看成是被浪费掉了
中间这X个数字一起形成了X-1个间隔,依照题意,每个间隔至少包含一个数字(不含两
端)
我们的任务是把N-(a+b)-X个数字放进这X-1个间隔里去,使得每个间隔至少包含一个数字
这可以归结为把n个不可分辨的球放入k个容器,使得每个容器至少一个元素的问题
这样的问题的解是C(n-k+k-1,k-1) = C(n-1,k-1)
从而我们的任务有C(N-X-(a+b)-1, X-2)种选择
接下来,设a+b=k, 那么k的取值范围是多少呢?k最小可以是0,最大必须使得
N-(a+b)-X >= X-1,从而k <= N+1-2*X
对于每个这样的k,(a,b)组合有(k+1)种取法(a可以是0,1,2,...,k)
从而问题的答案是\sum_{k=0,N+1-2*X} (k+1)*C(N-X-k-1, X-2)
当然,上面假设了X>=2,否则组合数没有意义
如果X=1,则易得答案是N
可以用X=2来验证上述公式对不对:
当X=2时,易得答案是C(N,2)-(N-1) = (N-1)(N-2) |
|
|
f*********5 发帖数: 576 | 6 举个例子吧,让别人能够更清楚的了解题意
谢谢!
fin
the |
|
y*c 发帖数: 904 | 7 明确题意+提供思路,假设第一次探测x
则如果x就complain的总天数 x + \sum_{i=x+1}^{i=99}
如果没有complain, 下一次探测总天数 x' + \sum_{i=x'+1}^{i=x-1}
如此下去得到x序列。
很明显,x 应该是比较接近100的一个数,x'是小于x的一个数。原则是希望每一轮总天
数接近。由于第二个“鸡蛋”的测试带来的是平方项,所以第一个鸡蛋测试的gap肯定
不是线性递减的。具体怎么算我还没什么办法。 |
|
f*********5 发帖数: 576 | 8 不对
如果是 a[index]==index && a[index +/- 1]=index
就不满足题意了, |
|
f*********g 发帖数: 207 | 9 FSD entry职位,刚收到据信。记录一下面经。
phone interview: 一老美,一老印,都很nice。
1.how to reverse a linked list?
我回答recursive function. 对方追问如果linked list很大,有什么问题,经他提示
,是指会使stack size变得很大。
2.how to find a circular in a linked list?(fast/slow pointer or hashing
address)
3.give bill to somebody in a month, in day n the people have n dollors, how
to minimize the # of bills
费了挺大劲才搞清题意,应该是第一天1块,第二天给两块,找回一块,第三天再给找
回来的一块,然后四块,八块等等,保证底n天,对方手里有n块
100! how many zeros?
Why bb?
onsite:
先是两junior developer,一亚裔一可能是印度,都很年轻。
一上来听说用过l |
|
j**l 发帖数: 2911 | 10 how to reverse a linked list?
我回答recursive function. 对方追问如果linked list很大,有什么问题,经他提示
,是指会使stack size变得很大。
可以用尾递归,不会栈溢出。
give bill to somebody in a month, in day n the people have n dollors, how
to minimize the # of bills
费了挺大劲才搞清题意,应该是第一天1块,第二天给两块,找回一块,第三天再给找
回来的一块,然后四块,八块等等,保证底n天,对方手里有n块
以前一个益智故事是财主给长工七天的工钱,有一个七节的金链条,断成七部分每天给
一部分没有必要,只需要断成1, 2, 4三部分。
第一天给1,第二天给2取回1,第三天给1,第四天给4取回1和2,第五天给1,第六天给
2取回1, 第七天给1
利用了等比数列的性质,也有递归的特点。 |
|
h**6 发帖数: 4160 | 11 to Done:
你没有理解题意,只能从两端开始取,也就是第一轮只能取4或9,不能取10。
to zysxqn:
双方各取一次确实是四种取法,不过并不是在这四种情况中找最优,而是每两种情况
找出最差再找最优。因为对手的最优,是我方的最差。 |
|
b***k 发帖数: 2673 | 12 最坏测4次还不可以吗?
4次都不行,那剩下当然就是好的电池了。
呵呵,也许我题意理解的不准确。 |
|
y*********e 发帖数: 518 | 13 碰巧今天在做这个题目。说下我对这个题目的理解。
问题的输入是一个DNA(可以认为是一个字符串)。这个DNA上有一系列基因,每一个基
因有起始点,结束点,以及权重值。要求在这个DNA串里面,找出不重叠的所有基因,使
得它们的权重值总和最大。
举个例子:
DNA(长度是45):AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
5个基因(起点,终点,权重):
E0: 1 10 11
E1: 14 19 5
E2: 18 36 13
E3: 26 31 5
E4: 35 40 5
E0没有与任何其他基因相交。E2与E1,E3,E4相交。E1,E3,E4并不互相重叠。依题意,
符合条件的基因组合是E0,E1,E3,E4,权重总和是26,是最大的可能组合。
题目的链接在这里:http://www.facebook.com/careers/puzzles.php?puzzle_id=15
值得注意的是,DNA的具体值并不重要,只需要它的长度就可以了。
我最开始用Dynamic Program |
|
y******5 发帖数: 43 | 14 看来我对题意理解有误。我以为一个人只能给他的债主写check,也就是说,在有向图
中我们只能减少
某个点的已有出度边。
如果e可以代替b向"b的而非e的"的债主还钱,感觉总是有解啊,这题目还要我们判断什
么?能说说你的
理解么? |
|
y*********e 发帖数: 518 | 15 根据题意,该矩阵满足如下条件:
每一行按升序排列, 每一列也按升序排列。
00 02 03 04 05 06
01 04 07 11 15 16
02 05 08 12 19 20
03 06 09 16 22 23
10 13 14 17 24 25
18 21 23 26 30 31
设N是矩阵的长度。比如如上的矩阵N=6
用divide-and-conquer的思路,找8。
第一步:
binary search第六列,找到首个小于8的行。是为第一行。
binary search第一列,找到首个大于8的行。是为第五行。
把第一行,第五行和第六行丢弃掉。
00 02 03 04 05 06 |
|
g***s 发帖数: 3811 | 16 sum(i)表示到第i个元素的和。O(n)可以做。
用二分对i来找到一个位置p,使得sum(p)可以满足题意,但sum(p-1)不能。 O(nlogn)
例如 2,2,2,2,2,5,5,5,1,1,1,1,1 k=3
那么这个p=5 sum(5)=10,sum(4)=8不行
然后对 sum(p-1) -> sum(p)进行二分。可以知道,sum(p)-sum(p-1)的值就是a[p],
小于等
于max(a[])
所以,负责度是O(nlogn + n log max(a[])
对于DP,因为
dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
所以是 O(NKLogN)
另外,空间复杂度可以用O(n)因为任何dp函数,k都只和dp[k-1]相关。所以,用两个长
度为n
的array就可以了。(另外还要一个sum(i)的数组,那么空间是3×n) |
|
d*****e 发帖数: 29 | 17 sum(i)表示到第i个元素的和。O(n)可以做。
nlogn)
────────
可以解释一下什么是满足题意吗?是说sum(p) = maximum吗?如果大数字都在队尾,p
可能不存在。
Number array: 1, 1, 10 k=2
p = ? |
|
z****n 发帖数: 1379 | 18 刚刚从了google的offer,base 116k,bonus 15%, stock unit 160, relocation
7500。由于签了保密协议,具体的面试题就不详细透漏了,都是很基本的算法题,
先说算法,再coding,没有长老级别的难题,也没问什么其他东西,就是算法。听
说最近google招人很多,大家好好准备算法,现在进google真的没有以前想象的那
么难了。
开始找工作以来就在这个版上取经,收益良多,所以也想分享一下自己找工作的经
验,回馈版面。
我是fresh cs phd,学校排名50左右,找工作开始就将目标定在硅谷,因为喜欢那
里的天气和中餐,初期也会投些其他地方的大公司,积累积累面试经验。一共拿到
了A,O,BB,G,M五家大公司的onsite,也许是被人看出来了只想去硅谷,A和BB的
onsite都挂了 ^_^ 拿到了O和G的,M由于时间太晚决定从了G就没去。另外还有些其
他中小公司的电面,感觉中小公司的电面太注重实际经验和语言细节,对我这种fr
esh学生来说,反而不如大公司的电面好通过。
下面说些我复习准备时的经验,版面上各种复习资料经验已经非常多,... 阅读全帖 |
|
o**s 发帖数: 65 | 19 code: multiplication algorithm for a long long integer,(you can not store
the integer with int or even long, unsinged long)
找到一些解法,把结果储存在string里,但是不太明白题意是这样吗? |
|
s*******t 发帖数: 248 | 20 感觉题意不是这个意思吧! 都是正数的话,你的那个就是所有加和了。
array |
|
r*****n 发帖数: 20 | 21 恩 make sense
题意理解有误
这个题有比O(n^2)好的算法么?
写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
return:
stekelenburg,hohohohohoho
代码如下
int myfunc(string a, string b){
return a.size()>b.size();
}
void foo(vector arr){
if(!arr.size())
return;
//step 1. sort w.r.t. lentgh of each word O(nlogn)
sort(arr.begin(), arr.end(), myfunc);
//step 2. compute signature for each word
vector sig;
for(long i=0; i阅读全帖 |
|
D*******i 发帖数: 16 | 22 排序不会改变原来数值的index么?
结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
如果空间复杂度为O(1)的话,怎么保存原来的i,j和k啊?
是我没有理解题意么。。。。 |
|
D*******i 发帖数: 16 | 23 排序不会改变原来数值的index么?
结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
如果空间复杂度为O(1)的话,怎么保存原来的i,j和k啊?
是我没有理解题意么。。。。 |
|
l********y 发帖数: 1327 | 24 主要是题意不太理解,创建一个linkedlist把每层的节点放进去?还是每个节点多出一
个next pointer,然后把这个next pointer指向同层的右边节点?前一种只要push_
back操作,后一种就不知道怎么做了 |
|
s*******t 发帖数: 248 | 25 cong!
能详细说下13,14题的题意吗?没太明白,13是给一个算式来算结果? 14题序列化的
要求是什么?
关于24题,能否说说你的答案,对这类题最没有把握。
谢谢!
考。 |
|
g*********s 发帖数: 1782 | 26 题意不清。什么叫”get any line in equal probablity“? |
|
i***d 发帖数: 28 | 27 关于C++的概念我主要是看一个叫c++ interview question 的document和钱能的
C++教程;如果有问题的话会google; 现在比较纠结的是概念理解的深度; 如果把网
上(例如WIKI)上相关问题的细节都掌握的话复习效率会很低;大家在复习是是怎
样掌握这难易程度的;另外是不是我看得书太浅了; 谢谢!
在面试时如果被问到不熟悉的问题我会发懵,手心直冒汗。听别人说如果题意不懂的
话,可以问面试官 但有时就觉的他/她像是在故意回避我的提问 让我更着急;大家
有没有相似的经历。想加入面试俱乐部的原因也就是想看看大家的经历; |
|
w********p 发帖数: 948 | 28 我这么觉得这道题歧义很大啊
100个箱子,每个箱子的容量? 是不是都要放满? 苹果、梨、橘子是不是假设一样大?
总共苹果, 总共梨、总共橘子 总共苹果梨橘子各是多少?还是完全不限?
本题是问可不可以 “总能挑出51个箱子,使这51个箱子里的苹果、梨、橘子分别都不
少于其他49个箱子里的苹果、梨、橘
子?”的算法,还是问机率问题?
总之对我来说题意不明白。 |
|
y***m 发帖数: 7027 | 29 既然是排好序的,decoding直接把字母排序还原回去不行么?不知题意是否理解有误... |
|
r******e 发帖数: 80 | 30 A Rubik's Cube has owl heads on it, which can be misoriented. How many (
times) MORE combinations are there of this cube vs. one that has blank
stickers?
看不懂题意。 请高人解惑。 |
|
|
Y**B 发帖数: 144 | 32 如果第一题按照原题意,1000个元素有一个是重复的,那么你们的加加减减的方法根本
不好使。面试管的答案才是他的题目的正解。
注意审题!! |
|
W**********r 发帖数: 8927 | 33 从题意可以看出来,没有这么一个现成的树,那你有必要和怎么建这个树?每个可能有很多Children,还必须是双向链接,否则要遍历寻找,要费多少空间呢? |
|
y***m 发帖数: 7027 | 34 ms题意只要求最接近V没要求邮票张数也最少吧? how about this?
邮票数组a,邮票张数数组c
看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模,一旦找到模为0退出循环
如果要求最少张数就把金额排序再递归
V = 358;
array a[]={0,2,3,5....n}; //邮票金额
array c[]={0,55,13,5,...n}; //邮票张数
array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数
array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数
calc(V, 1); //算出 pick 数组
int minMod=1000000000000;
function calc(V,j){
int i = V/a[j] > c[j] ? c[j]:V/a[j];
for(;i>-1;i--){
if(i>c[j])
continued;//大于预定的邮票张数继续-1
int imod = V... 阅读全帖 |
|
n******n 发帖数: 49 | 35 能不能详细讲讲第二题的题意?n-dimensional为什么是正方形? |
|
g**********y 发帖数: 14569 | 36 第二个是说让N个皇后不能互相攻击。最著名的是N=8, 8皇后问题,共有92种解法。
第三个题意不清楚:是要找字符串里最长的回文子串?还是要添加字符把它变成一个回
文串? |
|
d*******l 发帖数: 338 | 37 看了回复终于明白题意了,大概意思就是A掷到6就赢,B掷到1就赢,A先B后,两人轮流
,不死不休。。。其实可以抽象为两个人每轮都有1/6概率获胜,问先掷和后掷赢得概
率分别是多少。
其实还是比较简单的,设A赢得概率P(A)
P(A) = 1/6(第一轮掷到6)+ 5/6 * (1 - P(A))
P(A) = 6/11 |
|
g**e 发帖数: 6127 | 38 是不是我题意没理解清楚, 比如下面的数组 1 2 3 4 5, pipe放在3,
total cost = 1*3 + 2*2 + 3*1 + 4*2 + 5*3 = 33
是不是这样? |
|
g**e 发帖数: 6127 | 39 可是题目是“pipe给当前cage的cost 是 这个cage动物的用水量,给其他cage的动物供
水的cost是 (distance to that cage)*那个cage动物的用水量”
按照你这么算,pipe位置没有cost,不符合题意啊 |
|
d*******l 发帖数: 338 | 40 刚开始我也想错了。。那这个题意有点不和谐了,不过一个pipe还是应该能O(n)的。两
个pipe的情况,我现在想到一个可能的办法。假设pipe1,pipe2的位置是i,j。
开始的时候i=1,然后找到相应的最优的j,这个是O(n)的。
然后i递增,j也递增。这里的假设是,随着pipe1向右推移,pipe2的最优位置是不会回
退的。如果假设是正确的,那似乎可以在i,j都走完一遍之后就出结果。O(n) |
|
g**e 发帖数: 6127 | 41 1 1 怎么不是先拿必败?第一个人只能拿一根,第二个人就赢了
是不是我理解错了第二题意? |
|
P**********c 发帖数: 3417 | 42 你没理解对题意吧。
0000对应的解肯定是1234
如果是1324,那就是0100
排序 |
|
a***u 发帖数: 383 | 43 不确定自己是否理解题意。对这个程序有点疑问,如果给的数组中第一个数是最大的,
那么程序的返回值total是0? |
|
a***u 发帖数: 383 | 44 不确定自己是否理解题意。对这个程序有点疑问,如果给的数组中第一个数是最大的,
那么程序的返回值total是0? |
|
N*******7 发帖数: 14 | 45 第二题题意不太理解,是说已知一种一一映射,求逆关系么? |
|
g**********y 发帖数: 14569 | 46 1不清楚题意,要求排序的话,先排序再转换?
2, 5都是Trie的应用
2. L[i] = longest length of substring can split into words, starting from
position i (0<=i
for i = N-1 -> 0 {
L[i] = max(L[i+word.length] + word.length, for all valid word starting at
i)
}
return max(L[])
5. DFS
3好象需要问很多问题,才能开始解,这个描述太泛了。
4可以用二分,我以前贴过code。可能有更好的解法,搬板凳坐等。 |
|
P**********c 发帖数: 3417 | 47 1的题意不是说要排序,是说通过某种转换,转换之后的string假设要排序的话,排出来的顺序应该跟原来数字排出来的顺序一样。这个转换可以是任意的转换,不是简单的把数转成string即可。因为那样的话假如排序,就不一样了。比如string排序,123应该排在32的前面。但是数字排序,123应该排在32后面,所以要求的转换,要转成string之后,123对应的string还能排在32的后面。
5. DFS可以吗?单词里面可能某个字母会重复出现的,不是visit一次就够了。
at |
|
P**********c 发帖数: 3417 | 48 我的意思是,题目是让打出所有的通过按号码可生成的valid的words, 你给的这个函数,str这个input怎么产生?是要把所有可能的情况都遍历一遍吗?
另外,题意更清楚一些,这个是找那种简化号码,就是比如1-800-352-JUNK. 所以一个数字可以当作3个字母,但是不出现按两次按三次不同的情况
hard |
|
x****1 发帖数: 118 | 49 Google onsite归来,回馈本版,贡献一点面经和体会。记题的能力不是太好,就捡记
得住的说吧。废话不说,直接上题:
Phone screen:
先问了10道左右的小题,都是概念性的。
包括OOP,hashtable,BST,big O问题, 多线程,都是基本知识,没有什么tricky的地方。
有一道程序改错题,程序大概是替换一个字符串里面的pattern,不知道是谁写的,不是很
organized,估计是其他面试的同学的程序,我看了半天虽然觉的code写得很别扭,但也没找出什
么大错,面试官看我卡住了,就说我们继续吧。好在后来的题都答得比较顺利。
接下来又问了问现在做的项目,根据我的项目问了些问题,如server端如何实现session,项目中
有没有多线程,怎么实现。
最后还有5分钟结束的时候,给留了两道coding题,让我明早之前发给他。
一个就是binary search,不用多说了。
另外一个就是如何查找rotated sorted array (这也是很常见的题,因为面试官讲的是
cyclic,所以一开始我理解成{123456456},后来email问了才明白题意)... 阅读全帖 |
|
l****s 发帖数: 165 | 50 Google jobs:
http://jobguiding.com/it-jobs/it-companies/google.html
的说吧。废话不说,直接上题:
的地方。有一道程序改错题,程序大概是替换一个字符串里面的pattern,不知道是谁
写的,不是很organized,估计是其他面试的同学的程序,我看了半天虽然觉的code写
得很别扭,但也没找出什么大错,面试官看我卡住了,就说我们继续吧。好在后来的题
都答得比较顺利。
session,项目中有没有多线程,怎么实现。
是cyclic,所以一开始我理解成{123456456},后来email问了才明白题意)。
的地方。因为是常见题,很快完成,run了一下没什么问题就发过去了。 |
|