A***o
发帖数: 358 | 1 第一个电面，感觉比想象稍微难，做题时间45-50分钟，只做了两题，剩下时间都在讨
论。
没NDA，那就积人品放出来
1. 输入一浮点数，返回浮点数开方
* 指出精度问题
* 给时间复杂度
* 实现了两个对数时间的算法
2. 一个无穷的整数流，假定数字无序没有重复，实现函数和数据结构求最近n=1百万
个数里的最大值，假定这个函数会被不断使用
* 设计了一个线性空间，对数时间的方法，写了几行伪代码，被打断，说行
* 让找更高效的数据结构，没想出来
感觉这家的管理有点混乱，其他家是hr先联系我，这个直接是招人那个组的经理，电话
的时候背景声音好大，说找不到会议室给我电话，他就坐在他的cubicle。 |
p*****2
发帖数: 21240 | 2
第二题怎么做的，是用deque吗？
【在 A***o 的大作中提到】
: 第一个电面，感觉比想象稍微难，做题时间45-50分钟，只做了两题，剩下时间都在讨
: 论。
: 没NDA，那就积人品放出来
: 1. 输入一浮点数，返回浮点数开方
: * 指出精度问题
: * 给时间复杂度
: * 实现了两个对数时间的算法
: 2. 一个无穷的整数流，假定数字无序没有重复，实现函数和数据结构求最近n=1百万
: 个数里的最大值，假定这个函数会被不断使用
: * 设计了一个线性空间，对数时间的方法，写了几行伪代码，被打断，说行
|
A***o
发帖数: 358 | 3 差不多，我用一个cyclic queue + maxheap
【在 p*****2 的大作中提到】
:
: 第二题怎么做的，是用deque吗？
|
p*****2
发帖数: 21240 | 4
如果用maxheap复杂度就高了吧？
【在 A***o 的大作中提到】
: 差不多，我用一个cyclic queue + maxheap
|
A***o
发帖数: 358 | 5 他好像没complain这个，deque怎么弄快？
【在 p*****2 的大作中提到】
:
: 如果用maxheap复杂度就高了吧？
|
p*****2
发帖数: 21240 | 6
如果碰到比当前大或者等于的数就清deque，然后加入新数
如果碰到比当前数小的话则需要保存下来
这样就是O(1)的复杂度了
【在 A***o 的大作中提到】
: 他好像没complain这个，deque怎么弄快？
|
A***o
发帖数: 358 | 7 是不是我哪里理解错了？那如果一直都是比当前max小，就一直enque，最后curPos-
maxPos>1M了，怎么O（1）update当前最大？
【在 p*****2 的大作中提到】
:
: 如果碰到比当前大或者等于的数就清deque，然后加入新数
: 如果碰到比当前数小的话则需要保存下来
: 这样就是O(1)的复杂度了
|
t*q
发帖数: 104 | 8 Amortized O(1)
有可能存很多数，如果序列是一直递减的
【在 A***o 的大作中提到】
: 是不是我哪里理解错了？那如果一直都是比当前max小，就一直enque，最后curPos-
: maxPos>1M了，怎么O（1）update当前最大？
|
m****i
发帖数: 650 | |
b***e
发帖数: 1419 | 10 Imagine there's a hanoi stack. Each time you get a new number i, it pop all
the numbers from the top that are less than i, until the top of the stack
is greater than i. Now push i in the stack. This way, any time you have
the max at the bottom of the stack. The maintenance of the stack is
amortized to be O(1) per number, because each number is in once and out once.
【在 A***o 的大作中提到】
: 是不是我哪里理解错了？那如果一直都是比当前max小，就一直enque，最后curPos-
: maxPos>1M了，怎么O（1）update当前最大？
|
|
|
r*******e
发帖数: 7583 | 11 stack不对把，求最近N个的最大值
怎么保证栈底元素是属于最近N个里的
最简单的例子是连续N+1个元素递减
all
once.
【在 b***e 的大作中提到】
: Imagine there's a hanoi stack. Each time you get a new number i, it pop all
: the numbers from the top that are less than i, until the top of the stack
: is greater than i. Now push i in the stack. This way, any time you have
: the max at the bottom of the stack. The maintenance of the stack is
: amortized to be O(1) per number, because each number is in once and out once.
|
b***e
发帖数: 1419 | 12 That's not the difficult part. When the bottom index is less than the
current head index - 1M, just remove it.
【在 r*******e 的大作中提到】
: stack不对把，求最近N个的最大值
: 怎么保证栈底元素是属于最近N个里的
: 最简单的例子是连续N+1个元素递减
:
: all
: once.
|
b****g
发帖数: 192 | 13 第二题是leetcode原题Sliding Window Maximum
http://leetcode.com/2011/01/sliding-window-maximum.html
【在 A***o 的大作中提到】
: 第一个电面，感觉比想象稍微难，做题时间45-50分钟，只做了两题，剩下时间都在讨
: 论。
: 没NDA，那就积人品放出来
: 1. 输入一浮点数，返回浮点数开方
: * 指出精度问题
: * 给时间复杂度
: * 实现了两个对数时间的算法
: 2. 一个无穷的整数流，假定数字无序没有重复，实现函数和数据结构求最近n=1百万
: 个数里的最大值，假定这个函数会被不断使用
: * 设计了一个线性空间，对数时间的方法，写了几行伪代码，被打断，说行
|
A***o
发帖数: 358 | 14 领教
all
once.
【在 b***e 的大作中提到】
: Imagine there's a hanoi stack. Each time you get a new number i, it pop all
: the numbers from the top that are less than i, until the top of the stack
: is greater than i. Now push i in the stack. This way, any time you have
: the max at the bottom of the stack. The maintenance of the stack is
: amortized to be O(1) per number, because each number is in once and out once.
|
b***e
发帖数: 1419 | 15 Seriously, groupon is not a good place to go. It's falling apart. This
problem you post here, I bet you none of the current engineers in groupon
can get it correctly. Those who can really get it are in F/G.
【在 A***o 的大作中提到】
: 领教
:
: all
: once.
|
p*****2
发帖数: 21240 | 16
大牛推荐几个好地方？
【在 b***e 的大作中提到】
: Seriously, groupon is not a good place to go. It's falling apart. This
: problem you post here, I bet you none of the current engineers in groupon
: can get it correctly. Those who can really get it are in F/G.
|
b***e
发帖数: 1419 | 17 不外乎是F/G， 再不就是赌startup.
【在 p*****2 的大作中提到】
:
: 大牛推荐几个好地方？
|
p*****2
发帖数: 21240 | 18
how about L/T?
startup貌似热门的更难进呀。
【在 b***e 的大作中提到】
: 不外乎是F/G， 再不就是赌startup.
|
d***9
发帖数: 25 | 19 请二爷介绍一下，有哪些热门的start-up啊？
【在 p*****2 的大作中提到】
:
: how about L/T?
: startup貌似热门的更难进呀。
|
c***f
发帖数: 40 | 20 请教楼主是面的哪个组呢？
【在 A***o 的大作中提到】
: 第一个电面，感觉比想象稍微难，做题时间45-50分钟，只做了两题，剩下时间都在讨
: 论。
: 没NDA，那就积人品放出来
: 1. 输入一浮点数，返回浮点数开方
: * 指出精度问题
: * 给时间复杂度
: * 实现了两个对数时间的算法
: 2. 一个无穷的整数流，假定数字无序没有重复，实现函数和数据结构求最近n=1百万
: 个数里的最大值，假定这个函数会被不断使用
: * 设计了一个线性空间，对数时间的方法，写了几行伪代码，被打断，说行
|
|
|
A***o
发帖数: 358 | 21 他没说
【在 c***f 的大作中提到】
: 请教楼主是面的哪个组呢？
|
p*****2
发帖数: 21240 | 22
貌似最火的几个
Pinterest, dropbox, square, palantir, box.net
这几天RF好像也火起来了。
【在 d***9 的大作中提到】
: 请二爷介绍一下，有哪些热门的start-up啊？
|
H****s
发帖数: 247 | 23 嗨，二爷， palantir 可以从中划掉了，跟其他几个不是一个档次的 |
b***e
发帖数: 1419 | 24 L is already fully occupied by laoyin...and there's no profit going there
anymore.
T's fine, if you like SF downtown.
【在 p*****2 的大作中提到】
:
: 貌似最火的几个
: Pinterest, dropbox, square, palantir, box.net
: 这几天RF好像也火起来了。
|
f*********m
发帖数: 726 | 25 palantir 做的东西好像意思不大。
也没太多Machine machine learning 或data方面的工作。
【在 H****s 的大作中提到】
: 嗨，二爷， palantir 可以从中划掉了，跟其他几个不是一个档次的
|
