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 的大作中提到】
: 我申的还是software engineer new grad啊。。
| n****r
发帖数: 120 | | p*****2
发帖数: 21240 | | J*********r
发帖数: 5921 | 7 re
【在 p*****2 的大作中提到】
: 上题吧。
| p*****2
发帖数: 21240 | | p*****2
发帖数: 21240 | | e******x
发帖数: 184 | 10 是数学题呢，不用coding。。。。
【在 p*****2 的大作中提到】
: 第四题要求什么复杂度？
| | | p*****2
发帖数: 21240 | 11
靠。一间数学题就头晕。
【在 e******x 的大作中提到】
: 是数学题呢，不用coding。。。。
| e******x
发帖数: 184 | 12 第一题我当时也理解了半天，后面讨论的时候面试官也是想test case想半天想不出来
。。。。
【在 p*****2 的大作中提到】
: 多谢。不过第一题没看明白。
| M*****a
发帖数: 2054 | 13 赞
肯定能搞定好offer的，不要急，比我强太多了
range
m
each
defined
has
is
【在 e******x 的大作中提到】
: 非名校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 的大作中提到】
: 第4题真不会, 也就是想到一纬的情况区median. 最后一题考点在哪呢? 不就是重载add
: 函数??
| w****x
发帖数: 2483 | 16
牛逼个球啊, 一维情况可以这么做, 二维呢?? 不能扩展到二维啊.
【在 e******x 的大作中提到】
: 牛逼！就是先排序，奇数取中间点，偶数中间两点以及他们间任意点都可以~
: 如果它的addAll没有call add呢，这样那个count也要加n~ 可能我题没说清楚，大概是
: 这个list每次insert一次count就加一吧。。
:
: add
| q****x
发帖数: 7404 | 17 可以。确实是独立的。反证法可以证明。
【在 w****x 的大作中提到】
:
: 牛逼个球啊, 一维情况可以这么做, 二维呢?? 不能扩展到二维啊.
| w****x
发帖数: 2483 | 18
怎么扩展, 想不通, 能否详细解释一下??
【在 q****x 的大作中提到】
: 可以。确实是独立的。反证法可以证明。
| h*******s
发帖数: 8454 | 19 我的想法是求出所有x的median和所有y的median，定义他们为点c，然后找所有的点中
距离点c最近的一点就是结果
【在 w****x 的大作中提到】
:
: 怎么扩展, 想不通, 能否详细解释一下??
| e******x
发帖数: 184 | 20 min(sum(|x-xi|)+sum(|y-yi|)) = min(sum|x-xi|) + min(sum|y-yi|)
x跟y不是没关系的吗，随便取啊。。那个要求的点不需要是这n个点里面的。。。。
【在 w****x 的大作中提到】
:
: 怎么扩展, 想不通, 能否详细解释一下??
| | | w****x
发帖数: 2483 | 21
哦! 哦! 哦! 是随便取点啊!!
【在 e******x 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 不知道楼主因为什么给据了
| p*****2
发帖数: 21240 | 26
先按x排序,算出每个点距离的x分量
这句话是什么意思？
【在 n******m 的大作中提到】
: 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 的大作中提到】
: 第一题后面那两天机器不是多余的么，用第一台装两次水就是第二台的效果阿，感觉如
: 果 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 的大作中提到】
:
: 先按x排序,算出每个点距离的x分量
: 这句话是什么意思？
| w****x
发帖数: 2483 | 30
就是把所有点按x排序, 取median的x值Xm
把所有点按y排序, 取median的y值Ym
答案就是(Xm, Ym)
【在 p*****2 的大作中提到】
:
: 先按x排序,算出每个点距离的x分量
: 这句话是什么意思？
| | | p*****2
发帖数: 21240 | 31
如果要数学证明，应该怎么证明比较好？数学方面我最菜了。
【在 w****x 的大作中提到】
:
: 就是把所有点按x排序, 取median的x值Xm
: 把所有点按y排序, 取median的y值Ym
: 答案就是(Xm, Ym)
| w****x
发帖数: 2483 | 32
数学归纳法啊
【在 p*****2 的大作中提到】
:
: 如果要数学证明，应该怎么证明比较好？数学方面我最菜了。
| n******m
发帖数: 169 | 33 哦，我又看错了。。。。。。。。。。
【在 e******x 的大作中提到】
: 呃。。sry，我例子没举好，我只是想给个base case。。这些值不是给定的
: 我是用DP做的
| w****x
发帖数: 2483 | 34
这题用DP也是伪DP吧, 如果是浮点数就没法了??
【在 e******x 的大作中提到】
: 呃。。sry，我例子没举好，我只是想给个base case。。这些值不是给定的
: 我是用DP做的
| p*****2
发帖数: 21240 | 35
不懂呀。
【在 w****x 的大作中提到】
:
: 这题用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 的大作中提到】
:
: 不懂呀。
| p*****2
发帖数: 21240 | 37
,
这就是数学归纳法呀
【在 w****x 的大作中提到】
:
: 举例, 如果是编号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 的大作中提到】
: 第一题好难, 怎么做的??
| w****x
发帖数: 2483 | 40
DP怎么做的?? 真不大会这题
【在 e******x 的大作中提到】
: 为啥浮点就不行？
| | | s******o
发帖数: 2233 | 41 machine(50, 100), (100, 200), (500, 1000)
n=100, m=60 为啥是no
50*2=100不是正好么？还是我理解有问题？
range
m
【在 e******x 的大作中提到】
: 非名校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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 非名校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 的大作中提到】
: 第二题没限制的？比如不能到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 的大作中提到】
: 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 的大作中提到】
:
: 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 的大作中提到】
: 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 的大作中提到】
: 非名校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 的大作中提到】
: 牛逼！就是先排序，奇数取中间点，偶数中间两点以及他们间任意点都可以~
: 如果它的addAll没有call add呢，这样那个count也要加n~ 可能我题没说清楚，大概是
: 这个list每次insert一次count就加一吧。。
:
: add
| g***s
发帖数: 3811 | 56 (m+n)步中取n步向上走。
so, = C(m+n,n)
【在 j********x 的大作中提到】
: n*m grid这个题如果你想不到公式解我觉得不大可能中。。。
:
: range
: m
| t*********7
发帖数: 255 | 57 最后一题就是类似JAVA API里面一个变量modCount | t*********7
发帖数: 255 | 58 如果你电面题是全部要写代码,尽量BUG FREE的话...我觉得你电面题比ONSITE题要难一
点 |
|
