h*******8
发帖数: 29 | 1 跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
鸟。
都不难，欢迎大家讨论
第一轮：聊research，最后问了一题，
write a function f(x), so that f(x) returns true with x% probability。
第二轮：Given k sorted linked list, n elements in total, merge them into one
sorted linked list。
经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
heap。
中午吃饭
第三轮：convert a binary search tree into sorted double-linked list。
implement memcpy.
第四轮：System design。
Given a location (a coordinate), return top 100 nearest places.
Follow up, given a location, return top 100 events within x months in
nearest places。follow up 其实就是多加一个时间维度。
提出的方案就是对平面坐标系做grid，每个grid里的locations放到一台机器上。搜索
的时候就是针对input的location找到候选的grids(以某个半径画个圆)，再从中通过
map-reduce找到前100个location。
可以根据grid里location的密度或者访问量决定是不是要再做partition以提高
scalability。
follow up的话就是多加一个dimension代表时间。 |
x******o
发帖数: 27 | |
z***b
发帖数: 127 | |
r*******e
发帖数: 971 | 4 第二轮不算是难题啊。估计挂在这一轮上面了。
楼主要去哪一家？？
one
follow
【在 h*******8 的大作中提到】
: 跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
: 鸟。
: 都不难，欢迎大家讨论
: 第一轮：聊research，最后问了一题，
: write a function f(x), so that f(x) returns true with x% probability。
: 第二轮：Given k sorted linked list, n elements in total, merge them into one
: sorted linked list。
: 经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
: up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
: heap。
|
j**********3
发帖数: 3211 | 5 菜鸟弱问，第一题怎么做？隐隐约约觉得我以前会啊。。。现在不会了 |
b*****i
发帖数: 76 | 6 给定概率p(0-1)，生成一个0-1的random number
[在 jobhunter123 (jobhunting) 的大作中提到：]
：菜鸟弱问，第一题怎么做？隐隐约约觉得我以前会啊。。。现在不会了 |
w****a
发帖数: 710 | |
w****a
发帖数: 710 | 8 顺便问一下，implement memcpy这题有让你优化么。或者followup下考虑overlap，再
实现个memmove？ |
h*******8
发帖数: 29 | 9 最近在版上被喷的很凶的那一家
【在 r*******e 的大作中提到】
: 第二轮不算是难题啊。估计挂在这一轮上面了。
: 楼主要去哪一家？？
:
: one
: follow
|
h*******8
发帖数: 29 | 10 overlap要考虑，优化没说，也快没时间了。
优化的话你有什么好的方案么？
【在 w****a 的大作中提到】
: 顺便问一下，implement memcpy这题有让你优化么。或者followup下考虑overlap，再
: 实现个memmove？
|
|
|
h*******8
发帖数: 29 | 11 那如何考虑partition所有的location呢？
假如随机的把所有location分不到不同机器上，岂不是要query所有的机器，是不是不
够优化？
好的partition策略就不需要query所有的machine了？
【在 z***b 的大作中提到】
: 那个系统设计的题可能按下面这个idea好些吧？
: http://www.quora.com/What-is-the-distributed-algorithm-to-deter
|
w****a
发帖数: 710 | 12 感觉最简单最适合面试的优化就是按照CPU字长为最小单位进行复制。
比如32bit的系统复制一个32bit的值比复制一个8bit的值的性能快。
按照sizeof(long)为单位copy会快一些。
当然memcpy的优化很多，这个是最简单最好实现的一个
抛砖引玉，大牛可以详细谈谈
【在 h*******8 的大作中提到】
: overlap要考虑，优化没说，也快没时间了。
: 优化的话你有什么好的方案么？
|
e*******o
发帖数: 23 | 13 求解第一题，是不是生成一个1-100的random number，小于等于x就返回true？ |
l*****a
发帖数: 14598 | 14
这个题目允许用哪个取随机数的函数啊
估计是rand()返回0/1?
one
follow
【在 h*******8 的大作中提到】
: 跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
: 鸟。
: 都不难，欢迎大家讨论
: 第一轮：聊research，最后问了一题，
: write a function f(x), so that f(x) returns true with x% probability。
: 第二轮：Given k sorted linked list, n elements in total, merge them into one
: sorted linked list。
: 经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
: up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
: heap。
|
l*****a
发帖数: 14598 | 15 好奇的是第二轮这么常见的题，你居然不知道用heap
反而拿到G的offer
one
follow
【在 h*******8 的大作中提到】
: 跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
: 鸟。
: 都不难，欢迎大家讨论
: 第一轮：聊research，最后问了一题，
: write a function f(x), so that f(x) returns true with x% probability。
: 第二轮：Given k sorted linked list, n elements in total, merge them into one
: sorted linked list。
: 经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
: up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
: heap。
|
l*****a
发帖数: 14598 | 16 肯定不会是让用rand.nextInt(100)吧
【在 e*******o 的大作中提到】
: 求解第一题，是不是生成一个1-100的random number，小于等于x就返回true？
|
P****i
发帖数: 1362 | 17 我记得以前学的这个是k-d tree
【在 z***b 的大作中提到】
: 那个系统设计的题可能按下面这个idea好些吧？
: http://www.quora.com/What-is-the-distributed-algorithm-to-deter
|
e*******o
发帖数: 23 | 18
那就是要要rand（1）一层层乘上去得到rand(100)?
【在 l*****a 的大作中提到】
: 肯定不会是让用rand.nextInt(100)吧
|
p****a
发帖数: 447 | 19 SIMD，越大越快...
【在 w****a 的大作中提到】
: 感觉最简单最适合面试的优化就是按照CPU字长为最小单位进行复制。
: 比如32bit的系统复制一个32bit的值比复制一个8bit的值的性能快。
: 按照sizeof(long)为单位copy会快一些。
: 当然memcpy的优化很多，这个是最简单最好实现的一个
: 抛砖引玉，大牛可以详细谈谈
|
w****a
发帖数: 710 | 20 SIMD面试的时候突然问还真想不起来api。。
而且一旦SIMD事情就多了。。neon呢还是sse呢？
【在 p****a 的大作中提到】
: SIMD，越大越快...
|
|
|
y*****e
发帖数: 712 | 21 求解第一题！！
以前二爷博客里有个从fair coin generate 任意probability的unfair coin
和这题有点像，但那个是给出了另外一个generate p = 0.5的function, 这个
啥function都没给，估计也不能用rand，该怎么下手？ |
p****a
发帖数: 447 | 22 要不就自己对齐对齐，不整齐的裁吧裁吧
要不就左移右移处理处理
但是我觉得这些事情编译器都能做..
到底什么快也很大程度取决于什么处理器和编译器，不好说
SIMD提一句展示下知识面得了，真要求写intrinsics就过分了吧
【在 w****a 的大作中提到】
: SIMD面试的时候突然问还真想不起来api。。
: 而且一旦SIMD事情就多了。。neon呢还是sse呢？
|
p****a
发帖数: 447 | 23 第一题没看懂啊，哪位给举个例子？
【在 y*****e 的大作中提到】
: 求解第一题！！
: 以前二爷博客里有个从fair coin generate 任意probability的unfair coin
: 和这题有点像，但那个是给出了另外一个generate p = 0.5的function, 这个
: 啥function都没给，估计也不能用rand，该怎么下手？
|
m*********p
发帖数: 112 | 24 赞
one
follow
【在 h*******8 的大作中提到】
: 跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
: 鸟。
: 都不难，欢迎大家讨论
: 第一轮：聊research，最后问了一题，
: write a function f(x), so that f(x) returns true with x% probability。
: 第二轮：Given k sorted linked list, n elements in total, merge them into one
: sorted linked list。
: 经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
: up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
: heap。
|
j**********3
发帖数: 3211 | 25 牛牛，能具体点么？我还是隐隐约约的觉得以前会。。。
我记得有个题是求从1到n的等概率
【在 b*****i 的大作中提到】
: 给定概率p(0-1)，生成一个0-1的random number
: [在 jobhunter123 (jobhunting) 的大作中提到：]
: ：菜鸟弱问，第一题怎么做？隐隐约约觉得我以前会啊。。。现在不会了
|
e***n
发帖数: 42 | 26 最后一题可以用merge k sorted list (sorted by the distance to the center
point) where k is the number of partition. 然后返回top 100, 复杂度log(k)*100
.
请教为啥要用 mapReduce? |
r*****e
发帖数: 792 | 27 同感啊
【在 l*****a 的大作中提到】
: 好奇的是第二轮这么常见的题，你居然不知道用heap
: 反而拿到G的offer
:
: one
: follow
|
n****2
发帖数: 307 | 28 本来面试就是个运气。
在F那晕了，点背，有什么办法？
到G那醒了，信手拈来，怎么着？
你以为这几家面试都像ETS那样，得保证正态分布？ |
E*H
发帖数: 1207 | 29 靠，第一题就这么tricky
x 是啥type?
Int很简单，float/double估计俺就挂了。
one
follow
【在 h*******8 的大作中提到】
: 跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
: 鸟。
: 都不难，欢迎大家讨论
: 第一轮：聊research，最后问了一题，
: write a function f(x), so that f(x) returns true with x% probability。
: 第二轮：Given k sorted linked list, n elements in total, merge them into one
: sorted linked list。
: 经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
: up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
: heap。
|
d***e
发帖数: 348 | 30 赞一个！！！！！！！！！！！！！
【在 n****2 的大作中提到】
: 本来面试就是个运气。
: 在F那晕了，点背，有什么办法？
: 到G那醒了，信手拈来，怎么着？
: 你以为这几家面试都像ETS那样，得保证正态分布？
|
