|
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++ interview question 的document和钱能的
Ｃ++教程；如果有问题的话会google; 现在比较纠结的是概念理解的深度； 如果把网
上（例如ＷＩＫＩ）上相关问题的细节都掌握的话复习效率会很低；大家在复习是是怎
样掌握这难易程度的；另外是不是我看得书太浅了； 谢谢！
在面试时如果被问到不熟悉的问题我会发懵，手心直冒汗。听别人说如果题意不懂的
话，可以问面试官 但有时就觉的他/她像是在故意回避我的提问 让我更着急；大家
有没有相似的经历。想加入面试俱乐部的原因也就是想看看大家的经历； |
|
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了一下没什么问题就发过去了。 |
|
