e******x 发帖数: 184 | 1 非名校CS Master new grad~ 本科zju数学的
之前一心准备google,还是挂了
对machine learning,data mining比较感兴趣,不过这些组master好难进。
但自我感觉算法不错,求ms,fb大牛们的内推呢~~
把onsite的题抓上来~
1. Three coke machines. Each one has two values min & max, which means if
you get coke from this machine it will load you a random volume in the range
[min, max]. Given a cup size n and minimum soda volume m, show if it's
possible to make it from these machines.
比如三台machine(50, 100), (100, 200), (500, 1000). n=110, m=40, yes. n=90, m
=40, no. n=100, m=60, no.
2. n*m grids. How many ways from (0,0) to (n,m).
这题简单,我把递归非递归都写了一遍。
3. Given a sorted array, make a balanced binary search tree.
4. n 2D integer points. Find an point so that the total distances from each
one to this point are minimal. Distance of (x1, y1) and (x2, y2) is defined
as |x1-x2| + |y1-y2|.
这题挺郁闷的,觉得面试官不给力。。我说可以化解为一维的问题因为x,y
independent,他问了我半天为什么。
5. About Inheritance & polymiorphism. A class, like LinkedList in Java, has
two methods add & addall. Write a subclass to count how many times "add" is
called.
Be careful about how "addall" is implemented.
这题中间犯了个小错误,后面又讨论了下怎么处理多线程。 | s*******n 发帖数: 631 | | e******x 发帖数: 184 | 3 我申的还是software engineer new grad啊。。 | s*******n 发帖数: 631 | 4
哦?
我以为是machine learning之类的那个组
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我申的还是software engineer new grad啊。。
| n****r 发帖数: 120 | | p*****2 发帖数: 21240 | | J*********r 发帖数: 5921 | 7 re
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上题吧。
| p*****2 发帖数: 21240 | | p*****2 发帖数: 21240 | | e******x 发帖数: 184 | 10 是数学题呢,不用coding。。。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第四题要求什么复杂度?
| | | p*****2 发帖数: 21240 | 11
靠。一间数学题就头晕。
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是数学题呢,不用coding。。。。
| e******x 发帖数: 184 | 12 第一题我当时也理解了半天,后面讨论的时候面试官也是想test case想半天想不出来
。。。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢。不过第一题没看明白。
| M*****a 发帖数: 2054 | 13 赞
肯定能搞定好offer的,不要急,比我强太多了
range
m
each
defined
has
is
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非名校CS Master new grad~ 本科zju数学的 : 之前一心准备google,还是挂了 : 对machine learning,data mining比较感兴趣,不过这些组master好难进。 : 但自我感觉算法不错,求ms,fb大牛们的内推呢~~ : 把onsite的题抓上来~ : 1. Three coke machines. Each one has two values min & max, which means if : you get coke from this machine it will load you a random volume in the range : [min, max]. Given a cup size n and minimum soda volume m, show if it's : possible to make it from these machines. : 比如三台machine(50, 100), (100, 200), (500, 1000). n=110, m=40, yes. n=90, m
| w****x 发帖数: 2483 | 14 第4题真不会, 也就是想到一纬的情况区median. 最后一题考点在哪呢? 不就是重载add
函数?? | e******x 发帖数: 184 | 15 牛逼!就是先排序,奇数取中间点,偶数中间两点以及他们间任意点都可以~
如果它的addAll没有call add呢,这样那个count也要加n~ 可能我题没说清楚,大概是
这个list每次insert一次count就加一吧。。
add
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第4题真不会, 也就是想到一纬的情况区median. 最后一题考点在哪呢? 不就是重载add : 函数??
| w****x 发帖数: 2483 | 16
牛逼个球啊, 一维情况可以这么做, 二维呢?? 不能扩展到二维啊.
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 牛逼!就是先排序,奇数取中间点,偶数中间两点以及他们间任意点都可以~ : 如果它的addAll没有call add呢,这样那个count也要加n~ 可能我题没说清楚,大概是 : 这个list每次insert一次count就加一吧。。 : : add
| q****x 发帖数: 7404 | 17 可以。确实是独立的。反证法可以证明。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 牛逼个球啊, 一维情况可以这么做, 二维呢?? 不能扩展到二维啊.
| w****x 发帖数: 2483 | 18
怎么扩展, 想不通, 能否详细解释一下??
【在 q****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可以。确实是独立的。反证法可以证明。
| h*******s 发帖数: 8454 | 19 我的想法是求出所有x的median和所有y的median,定义他们为点c,然后找所有的点中
距离点c最近的一点就是结果
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 怎么扩展, 想不通, 能否详细解释一下??
| e******x 发帖数: 184 | 20 min(sum(|x-xi|)+sum(|y-yi|)) = min(sum|x-xi|) + min(sum|y-yi|)
x跟y不是没关系的吗,随便取啊。。那个要求的点不需要是这n个点里面的。。。。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 怎么扩展, 想不通, 能否详细解释一下??
| | | w****x 发帖数: 2483 | 21
哦! 哦! 哦! 是随便取点啊!!
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : min(sum(|x-xi|)+sum(|y-yi|)) = min(sum|x-xi|) + min(sum|y-yi|) : x跟y不是没关系的吗,随便取啊。。那个要求的点不需要是这n个点里面的。。。。
| w****x 发帖数: 2483 | 22
明白了, thanks, 第一题能解释一下吗??
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : min(sum(|x-xi|)+sum(|y-yi|)) = min(sum|x-xi|) + min(sum|y-yi|) : x跟y不是没关系的吗,随便取啊。。那个要求的点不需要是这n个点里面的。。。。
| n******m 发帖数: 169 | 23 4,
两个维度是独立的这点很重要,说明可以分开做。
但是还是需要把距离都求出来吧,因为二维的没法完全排序,也没有中间点。
先按x排序,算出每个点距离的x分量
在按y排序,每个点加上距离的y分量,
然后取最小的。复杂度是排序的复杂度 nlogn | w****x 发帖数: 2483 | | e******x 发帖数: 184 | 25 第一题讨论了很久,后面代码写完base case有问题,又讨论很久。。。。我不知道该
怎么解释,我不是举了个例子嘛。就是说我去接可乐我可以选任何一台机器,不限次数
,但要保证打的可乐不会溢出我的杯子,而且最后要大于等于m毫升比如。
那道数学题我上来就降成一维,跟他说independent把式子写给他看他还是继续问什么
,我觉得我有点被问急了,因为很简单啊,过了一会才想到可以用反证法跟他讲。
继承那题也不是很顺利,虽然后面都答出来了。。
好吧,我还没到g那个水平吧。。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不知道楼主因为什么给据了
| p*****2 发帖数: 21240 | 26
先按x排序,算出每个点距离的x分量
这句话是什么意思?
【在 n******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 4, : 两个维度是独立的这点很重要,说明可以分开做。 : 但是还是需要把距离都求出来吧,因为二维的没法完全排序,也没有中间点。 : 先按x排序,算出每个点距离的x分量 : 在按y排序,每个点加上距离的y分量, : 然后取最小的。复杂度是排序的复杂度 nlogn
| n******m 发帖数: 169 | 27 第一题后面那两天机器不是多余的么,用第一台装两次水就是第二台的效果阿,感觉如
果 cup=x, min=y, 就是判断一下 if (y>=100*((x-1)/50+1)) | e******x 发帖数: 184 | 28 呃。。sry,我例子没举好,我只是想给个base case。。这些值不是给定的
我是用DP做的
【在 n******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题后面那两天机器不是多余的么,用第一台装两次水就是第二台的效果阿,感觉如 : 果 cup=x, min=y, 就是判断一下 if (y>=100*((x-1)/50+1))
| n******m 发帖数: 169 | 29 我以为求的点需要时给定的点之一。
比如说 三个点排号之后x 分别是 x1,x2,x3
那就可以算 d1_x=其它点到第一个点的距离和的x分量=(x2-x1)+(x3-x1)
然后 d2_x 可以在 d1_x 的基础上算,类推。。。
这样可以 nlogn 算出所有距离和,然后比较出最小的
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 先按x排序,算出每个点距离的x分量 : 这句话是什么意思?
| w****x 发帖数: 2483 | 30
就是把所有点按x排序, 取median的x值Xm
把所有点按y排序, 取median的y值Ym
答案就是(Xm, Ym)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 先按x排序,算出每个点距离的x分量 : 这句话是什么意思?
| | | p*****2 发帖数: 21240 | 31
如果要数学证明,应该怎么证明比较好?数学方面我最菜了。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 就是把所有点按x排序, 取median的x值Xm : 把所有点按y排序, 取median的y值Ym : 答案就是(Xm, Ym)
| w****x 发帖数: 2483 | 32
数学归纳法啊
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 如果要数学证明,应该怎么证明比较好?数学方面我最菜了。
| n******m 发帖数: 169 | 33 哦,我又看错了。。。。。。。。。。
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃。。sry,我例子没举好,我只是想给个base case。。这些值不是给定的 : 我是用DP做的
| w****x 发帖数: 2483 | 34
这题用DP也是伪DP吧, 如果是浮点数就没法了??
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃。。sry,我例子没举好,我只是想给个base case。。这些值不是给定的 : 我是用DP做的
| p*****2 发帖数: 21240 | 35
不懂呀。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这题用DP也是伪DP吧, 如果是浮点数就没法了??
| w****x 发帖数: 2483 | 36
举例, 如果是编号1..n个点, n是奇数, 那么假设n-2个点的median点是距离和最小的,
那么对于n个点中间的n-2个点来说, 这n-2个点到median的距离和最小, 现在在这个条
件下(n-2)要证明n个点的距离和最小的也是median.
假设这n个点的range是d, 那么对于新增的左右两个端点, 所有点的额外(相对于n-2的
情况)距离和增值都是d, 那么还是median的距离和最小.
偶数同理
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不懂呀。
| p*****2 发帖数: 21240 | 37
,
这就是数学归纳法呀
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 举例, 如果是编号1..n个点, n是奇数, 那么假设n-2个点的median点是距离和最小的, : 那么对于n个点中间的n-2个点来说, 这n-2个点到median的距离和最小, 现在在这个条 : 件下(n-2)要证明n个点的距离和最小的也是median. : 假设这n个点的range是d, 那么对于新增的左右两个端点, 所有点的额外(相对于n-2的 : 情况)距离和增值都是d, 那么还是median的距离和最小. : 偶数同理
| w****x 发帖数: 2483 | | e******x 发帖数: 184 | 39 为啥浮点就不行?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题好难, 怎么做的??
| w****x 发帖数: 2483 | 40
DP怎么做的?? 真不大会这题
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为啥浮点就不行?
| | | s******o 发帖数: 2233 | 41 machine(50, 100), (100, 200), (500, 1000)
n=100, m=60 为啥是no
50*2=100不是正好么?还是我理解有问题?
range
m
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非名校CS Master new grad~ 本科zju数学的 : 之前一心准备google,还是挂了 : 对machine learning,data mining比较感兴趣,不过这些组master好难进。 : 但自我感觉算法不错,求ms,fb大牛们的内推呢~~ : 把onsite的题抓上来~ : 1. Three coke machines. Each one has two values min & max, which means if : you get coke from this machine it will load you a random volume in the range : [min, max]. Given a cup size n and minimum soda volume m, show if it's : possible to make it from these machines. : 比如三台machine(50, 100), (100, 200), (500, 1000). n=110, m=40, yes. n=90, m
| e******x 发帖数: 184 | 42 (50, 100)是说你用这台机器它会给你50-100里的任意值,你要保证任何情况下都不会
溢出恩
【在 s******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : machine(50, 100), (100, 200), (500, 1000) : n=100, m=60 为啥是no : 50*2=100不是正好么?还是我理解有问题? : : range : m
| e******x 发帖数: 184 | 43 def getCoke(min, max, m, n) :
if (n<0 or m>n) :
return False
for i in xrange(3) :
if (m<=min[i] and n>=max[i]) or getCoke(min, max, m-min[i], n-max[
i])
return True
return False
大概是这样。。求拍 | Z*****Z 发帖数: 723 | 44 我觉得这是对的。
这题就是一个完全背包问题,每个coke machine的下限是value,上限是重量,杯子的最
大容量就是包的容积。看打包之后的value总值能不能超过那个给定值。
max[
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : def getCoke(min, max, m, n) : : if (n<0 or m>n) : : return False : for i in xrange(3) : : if (m<=min[i] and n>=max[i]) or getCoke(min, max, m-min[i], n-max[ : i]) : return True : return False : 大概是这样。。求拍
| w****x 发帖数: 2483 | 45
max[
完了, 最近状态越来越差, 这题居然不会做, 哈哈 T__T
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : def getCoke(min, max, m, n) : : if (n<0 or m>n) : : return False : for i in xrange(3) : : if (m<=min[i] and n>=max[i]) or getCoke(min, max, m-min[i], n-max[ : i]) : return True : return False : 大概是这样。。求拍
| C***U 发帖数: 2406 | 46 第二题没限制的?比如不能到x轴一下?
非名校CS Master new grad~ 本科zju数学的之前一心准备google,还是挂了对machine
learning,data mining比较感兴趣,不过这些组........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非名校CS Master new grad~ 本科zju数学的 : 之前一心准备google,还是挂了 : 对machine learning,data mining比较感兴趣,不过这些组master好难进。 : 但自我感觉算法不错,求ms,fb大牛们的内推呢~~ : 把onsite的题抓上来~ : 1. Three coke machines. Each one has two values min & max, which means if : you get coke from this machine it will load you a random volume in the range : [min, max]. Given a cup size n and minimum soda volume m, show if it's : possible to make it from these machines. : 比如三台machine(50, 100), (100, 200), (500, 1000). n=110, m=40, yes. n=90, m
| e******x 发帖数: 184 | 47 当然不能往回走咯~
machine
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题没限制的?比如不能到x轴一下? : : 非名校CS Master new grad~ 本科zju数学的之前一心准备google,还是挂了对machine : learning,data mining比较感兴趣,不过这些组........ : ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
| t**********h 发帖数: 2273 | | e******x 发帖数: 184 | 49 1. An integer stored in a list, 245 -> [245]. Do increament: Increment([2, 4
, 5]) = [2, 4 6]
2. Also do an increment for a list, but this time increment means give the
next permutation of the list. Like Increment([2, 4, 5]) = [2, 5, 4]. You
need to traverse all the permutations but you can decide the order.
3. give you a string and a list, e.g. zxasbascasbsdafa & [a,b,c]. Find the
shortest substring containing all the elements in the list.
要不是之前记下来了,肯定忘了现在。。 | w****x 发帖数: 2483 | 50
4
你这里的list一定是linked list吗, 能用array吗
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. An integer stored in a list, 245 -> [245]. Do increament: Increment([2, 4 : , 5]) = [2, 4 6] : 2. Also do an increment for a list, but this time increment means give the : next permutation of the list. Like Increment([2, 4, 5]) = [2, 5, 4]. You : need to traverse all the permutations but you can decide the order. : 3. give you a string and a list, e.g. zxasbascasbsdafa & [a,b,c]. Find the : shortest substring containing all the elements in the list. : 要不是之前记下来了,肯定忘了现在。。
| | | e******x 发帖数: 184 | 51 恩可以
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 4 : 你这里的list一定是linked list吗, 能用array吗
| e******x 发帖数: 184 | 52 自己顶!
PS: FB的同学真好,还建议我改简历~~ | a***o 发帖数: 1182 | 53 这个不对吧?
比如一上来m=1, n=10000,应该也不行吧
应该 min[i]<=m<=max[i] && n>=max[i]?
max[
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : def getCoke(min, max, m, n) : : if (n<0 or m>n) : : return False : for i in xrange(3) : : if (m<=min[i] and n>=max[i]) or getCoke(min, max, m-min[i], n-max[ : i]) : return True : return False : 大概是这样。。求拍
| j********x 发帖数: 2330 | 54 n*m grid这个题如果你想不到公式解我觉得不大可能中。。。
range
m
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非名校CS Master new grad~ 本科zju数学的 : 之前一心准备google,还是挂了 : 对machine learning,data mining比较感兴趣,不过这些组master好难进。 : 但自我感觉算法不错,求ms,fb大牛们的内推呢~~ : 把onsite的题抓上来~ : 1. Three coke machines. Each one has two values min & max, which means if : you get coke from this machine it will load you a random volume in the range : [min, max]. Given a cup size n and minimum soda volume m, show if it's : possible to make it from these machines. : 比如三台machine(50, 100), (100, 200), (500, 1000). n=110, m=40, yes. n=90, m
| g***m 发帖数: 85 | 55 取中数是对的,不过不需要排序,一维是O(n),不是O(nlogn)...
【在 e******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 牛逼!就是先排序,奇数取中间点,偶数中间两点以及他们间任意点都可以~ : 如果它的addAll没有call add呢,这样那个count也要加n~ 可能我题没说清楚,大概是 : 这个list每次insert一次count就加一吧。。 : : add
| g***s 发帖数: 3811 | 56 (m+n)步中取n步向上走。
so, = C(m+n,n)
【在 j********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : n*m grid这个题如果你想不到公式解我觉得不大可能中。。。 : : range : m
| t*********7 发帖数: 255 | 57 最后一题就是类似JAVA API里面一个变量modCount | t*********7 发帖数: 255 | 58 如果你电面题是全部要写代码,尽量BUG FREE的话...我觉得你电面题比ONSITE题要难一
点 |
|