合法留美身份 - 未名空间MITBBS历史存档

A*r2010-06-15 07:06

1 楼

刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
base 11万多， 15% bonus
stock 160
relocation 大概6千
懒得再折腾等待了，估计就从了。。
从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础
和概念，以及本版的题目总结。。个人感觉最有用的是在本版的讨论，很多时候都让我
豁然开朗，那个时候常出现讨论的几位同学现在也大部分拿到offer了，谢谢你们了。。
不好意思，没有记录下on-site的面经，一则当时状态不好，面试前一天晚上失眠，面
完了之后整个人都晕的，二则回来之后就准备论文，等忙完了题目基本上忘得差不多了
。不过可以肯定的是，应该都不是什么难题，后来有一位同学写信问我，我才勉强想起
一道当时有点struggle的题，find sliding maximum, 感兴趣的同学可以去google一下
， optimal solution应该是 O(n)的。。
总算告一段落了，上来汇报一下，算是有始有终吧，也祝愿大家找工作顺利。。

Z*e2010-06-15 07:06

2 楼

学校的工作月底结束，(H1B倒要后年才过期，才延了一次)
EB1A 140已经批,485的EAD不知道何时能下来.
如果公司的paperwork 07/01 没有办好(可能会办O1)，那么我还是可以呆在美国吧.可
以呆好久呢?

a*n2010-06-15 07:06

3 楼

Cong～

R*n2010-06-15 07:06

4 楼

485 pennding不就是身份吗？为什么还要办其它身份？等EAD就是了，应该两三个月会
下来。

n*92010-06-15 07:06

5 楼

cong

Z*e2010-06-15 07:06

6 楼

好吧，我觉得也是，就是想验证一下

【在 R******n 的大作中提到】

: 485 pennding不就是身份吗？为什么还要办其它身份？等EAD就是了，应该两三个月会
: 下来。

c*b2010-06-15 07:06

7 楼

恭喜恭喜

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后:
。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

d*e2010-06-15 07:06

8 楼

恭喜恭喜 :)
好多钱，我眼中只有钱。。。。

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

b*n2010-06-15 07:06

9 楼

真黑呀，还没上手就要回家做月子了。

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

D*02010-06-15 07:06

10 楼

恭喜，包子，please

j*a2010-06-15 07:06

11 楼

恭喜～
请问他们问了什么design题吗？比如说，design个heap之类的？

，尽管
recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀
孕，睡不好觉挺
难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on
-site结束后才
跟导师说推荐信的事，结果就多等了将近两个星期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

h*62010-06-15 07:06

12 楼

天哪，宝宝与offer，双喜临门，楼主真牛。

A*r2010-06-15 07:06

13 楼

没有啊，我自己还想好好休息呢。。要等到明年上班。。

【在 b********n 的大作中提到】

: 真黑呀，还没上手就要回家做月子了。
:
: ，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
: 现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
: 业，导师比较忙，就on-sit
: 属于天上掉下来的机会，我从8月

L*n2010-06-15 07:06

14 楼

恭喜恭喜

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

f*l2010-06-15 07:06

15 楼

恭喜

s*t2010-06-15 07:06

16 楼

这个要赞，太不易了。

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

w*s2010-06-15 07:06

17 楼

con

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

b*n2010-06-15 07:06

18 楼

你什么时候due？大着肚子去面试的？

【在 A*********r 的大作中提到】

: 没有啊，我自己还想好好休息呢。。要等到明年上班。。

j*u2010-06-15 07:06

19 楼

赞！恭喜lz！

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

A*r2010-06-15 07:06

20 楼

印象中有两个人问了design题吧，不过不是design heap..
一个好像跟数据库有关系，我真的记不太清楚了。。

on

【在 j****a 的大作中提到】

: 恭喜～
: 请问他们问了什么design题吗？比如说，design个heap之类的？
:
: ，尽管
: recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀
: 孕，睡不好觉挺
: 难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on
: -site结束后才
: 跟导师说推荐信的事，结果就多等了将近两个星期的时间。。

A*r2010-06-15 07:06

21 楼

30周左右去面试的，反正已经很显了。。

【在 b********n 的大作中提到】

: 你什么时候due？大着肚子去面试的？

A*r2010-06-15 07:06

22 楼

你和hock的帖子，总是让我感觉受益匪浅，真的非常感谢。。
我真的不是什么牛人，可能是宝宝带来了好运气。。

【在 h**6 的大作中提到】

: 天哪，宝宝与offer，双喜临门，楼主真牛。

k*n2010-06-15 07:06

23 楼

cong

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

w*o2010-06-15 07:06

24 楼

big cong，顺便沾点喜气

i*e2010-06-15 07:06

25 楼

恭喜了~
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

K*g2010-06-15 07:06

26 楼

再big cong+祝福一下，也顺便沾点喜气啊。。。

t*y2010-06-15 07:06

27 楼

cong!
沾点喜气

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

N*k2010-06-15 07:06

28 楼

gxgx

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

s*g2010-06-15 07:06

29 楼

cong

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

A*r2010-06-15 07:06

30 楼

呵呵，也谢谢你的网站，总结得很好。。

【在 i**********e 的大作中提到】

: 恭喜了~
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

g*s2010-06-15 07:06

31 楼

什么是find sliding maximum？我google了一下没什么发现啊。

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

A*H2010-06-15 07:06

32 楼

big cong!
btw, what is the "sliding maximum" question? Is it something like this?
http://blog.chinaunix.net/u3/105033/showart_2209043.html

m*62010-06-15 07:06

33 楼

nb!

s*12010-06-15 07:06

34 楼

楼主好幸福！沾沾喜气

A*r2010-06-15 07:06

35 楼

大概是这样说的：
给你一个unsorted数组，大小为n, 然后一个sliding window, 大小为k, 让你实时输出
这个窗口的最大数。

【在 g*********s 的大作中提到】

: 什么是find sliding maximum？我google了一下没什么发现啊。
:
: ，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
: 现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
: 业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
: 期的时间。。

w*l2010-06-15 07:06

36 楼

不工作满一年不会给那么多产假的。

【在 b********n 的大作中提到】

: 真黑呀，还没上手就要回家做月子了。
:
: ，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
: 现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
: 业，导师比较忙，就on-sit
: 属于天上掉下来的机会，我从8月

j*l2010-06-15 07:06

37 楼

维护一个大小为k的最大化堆？n*log(k)?

【在 A*********r 的大作中提到】

: 大概是这样说的：
: 给你一个unsorted数组，大小为n, 然后一个sliding window, 大小为k, 让你实时输出
: 这个窗口的最大数。

y*e2010-06-15 07:06

38 楼

恭喜恭喜～～～

，尽管
recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀
孕，睡不好觉挺
难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on
-site结束后才
跟导师说推荐信的事，结果就多等了将近两个星期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

j*l2010-06-15 07:06

39 楼

还是那个能O(1)时间输出动态变化的栈/队列的最大数的变体？
窗口滑动一格，出队列一个数，进队列一个数。

【在 A*********r 的大作中提到】

: 大概是这样说的：
: 给你一个unsorted数组，大小为n, 然后一个sliding window, 大小为k, 让你实时输出
: 这个窗口的最大数。

j*a2010-06-15 07:06

40 楼

哦哦～lz强～而且这样小孩直接带到google托儿所就好啦，很方便啊～再赞一下哈～

【在 A*********r 的大作中提到】

: 印象中有两个人问了design题吧，不过不是design heap..
: 一个好像跟数据库有关系，我真的记不太清楚了。。
:
: on

f*m2010-06-15 07:06

41 楼

恭喜楼主，请问楼主当时电话面试有没有提怀孕的事，如果不提的话，去onsite 的时
候会不会让面试官很突然？
总之楼主给了我很大的信心，我也现在在怀孕找工作。

t*j2010-06-15 07:06

42 楼

我也觉得最大堆就可以了，每次移动的时候，实际上就是删一个数，加一个数，就是2l
gk，就是O（1）.
恭喜楼主，我也要加油～

【在 j**l 的大作中提到】

: 维护一个大小为k的最大化堆？n*log(k)?

g*s2010-06-15 07:06

43 楼

能O(1)输出max必须要用堆吧？Fibonacci heap？

【在 j**l 的大作中提到】

: 还是那个能O(1)时间输出动态变化的栈/队列的最大数的变体？
: 窗口滑动一格，出队列一个数，进队列一个数。

a*92010-06-15 07:06

44 楼

cong!

b*12010-06-15 07:06

45 楼

恭喜MM~ 好多钱。。。

j*e2010-06-15 07:06

46 楼

牛 cs的offer package太赞了

v*n2010-06-15 07:06

47 楼

niu

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

s*h2010-06-15 07:06

48 楼

cong

s*g2010-06-15 07:06

49 楼

cong,厉害！厉害！

c*62010-06-15 07:06

50 楼

cong!

p*m2010-06-15 07:06

51 楼

congradulations!!!

G*02010-06-15 07:06

52 楼

GXGX

，尽管recruiter每周都跟我联系，说
一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训
是一定要提前准备推荐信。。我的情
况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了
将近两个星期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

k*a2010-06-15 07:06

53 楼

kaonima!

s*n2010-06-15 07:06

54 楼

不容易啊。 google不发sign bonus了嘛？

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

j*42010-06-15 07:06

55 楼

这个max in sliding window,用heap好像有问题，因为删数的时候这个数在heap里的位
置不好找。
这位大牛妹提到的O（n)方法是这样，基本就是找每段升值的最大点，加到一个vector
的尾巴上。取值从头上。

y*e2010-06-15 07:06

56 楼

cong

A*r2010-06-15 07:06

57 楼

这是解法之一，不过不是最优的，因为还是有logk.

【在 j**l 的大作中提到】

: 维护一个大小为k的最大化堆？n*log(k)?

A*r2010-06-15 07:06

58 楼

电话面试没提，不过后来通知on-site的时候提了，不过recruiter说没关系。。
面试官应该是都不知道的，可能真的关系不大吧。。

【在 f*********m 的大作中提到】

: 恭喜楼主，请问楼主当时电话面试有没有提怀孕的事，如果不提的话，去onsite 的时
: 候会不会让面试官很突然？
: 总之楼主给了我很大的信心，我也现在在怀孕找工作。

A*r2010-06-15 07:06

59 楼

我看板上汇报的都没提sign on bonus, 所以也没问recruiter为什么没有。。

【在 s*****n 的大作中提到】

: 不容易啊。 google不发sign bonus了嘛？
:
: ，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
: 现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
: 业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
: 期的时间。。

A*r2010-06-15 07:06

60 楼

嗯，其实就是需要一个数据结构，支持从头删除，从尾插入和删除，最大值永远都是在
头上。。
一个有头尾指针的单链表就可以了。。

vector

【在 j******4 的大作中提到】

: 这个max in sliding window,用heap好像有问题，因为删数的时候这个数在heap里的位
: 置不好找。
: 这位大牛妹提到的O（n)方法是这样，基本就是找每段升值的最大点，加到一个vector
: 的尾巴上。取值从头上。

g*n2010-06-15 07:06

61 楼

cong

n*p2010-06-15 07:06

62 楼

gongxi~~~~~~~~~~~~~~~~~~~

j*l2010-06-15 07:06

63 楼

空间换时间，这思路和O(1)时间取得栈元素最小值那道题的解法(用辅助栈，或者栈元
素增加一个链域)是否类似？

【在 A*********r 的大作中提到】

: 嗯，其实就是需要一个数据结构，支持从头删除，从尾插入和删除，最大值永远都是在
: 头上。。
: 一个有头尾指针的单链表就可以了。。
:
: vector

h*d2010-06-15 07:06

64 楼

太牛了，怀孕也可以这么顺利拿到offer

s*n2010-06-15 07:06

65 楼

should be the same trick.

【在 j**l 的大作中提到】

: 空间换时间，这思路和O(1)时间取得栈元素最小值那道题的解法(用辅助栈，或者栈元
: 素增加一个链域)是否类似？

m*s2010-06-15 07:06

66 楼

Cong!!!

x*32010-06-15 07:06

67 楼

gxgx

t*j2010-06-15 07:06

68 楼

有头尾指针的单链表，但是插入还是要O（k）吧？不太明白，飞牛mm能不能讲解下？

【在 A*********r 的大作中提到】

: 嗯，其实就是需要一个数据结构，支持从头删除，从尾插入和删除，最大值永远都是在
: 头上。。
: 一个有头尾指针的单链表就可以了。。
:
: vector

l*t2010-06-15 07:06

69 楼

恭喜。

l*t2010-06-15 07:06

70 楼

mm真是牛人。双喜临门！！

【在 A*********r 的大作中提到】

: 没有啊，我自己还想好好休息呢。。要等到明年上班。。

y*o2010-06-15 07:06

71 楼

恭喜！

r*92010-06-15 07:06

72 楼

可以说说你的背景吗？
做过intern？
名校？
phd？

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

A*r2010-06-15 07:06

73 楼

永远是从尾插入的，只要O(1)的。
如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删除一次，所以整个的复杂度是O(n)。。
这道题的trick就在这里，链表保留的不是window里面的所有数，否则的话，就达不到O(n).

【在 t*****j 的大作中提到】

: 有头尾指针的单链表，但是插入还是要O（k）吧？不太明白，飞牛mm能不能讲解下？

s*x2010-06-15 07:06

74 楼

恭喜.
BTW:sliding window 的那个题目,前面不是有人贴链接了,楼上还有没看懂的? 用线性
结构,单纯的链表或者数组肯定不行,必须用到树形结构.堆可以.问题是这里有两个值,
一个是数组的位置,要保存好更新窗口,一个是数组元素的值,这个好取最大最小.所以就
是一个优先队列了,存的元素是数组元素下标,更新的时候将下标和当前窗口边界比较,
超出的就删除;而优先级用数组元素的值来表示.同时取最大和最小,所以一共需要俩优
先队列,伪码大概是这个样子:
for i from 1 to k 窗口的大小
add i with priority v[i] into PQ1, PQ2
max[i],min[i] 分别从 PQ1, PQ2 根的优先级得到
//上面这步是初始化,当然还要考虑窗口比数组还大的特例
// PQ1, PQ2 一个是按顺序, 一个是按逆序来的, 分别得到最大最小值
for i from k+1 to n 数组长度, 1-based index
add i with priority v[i] into PQ1, PQ2
while PQ1 根的值超出窗口,就是<=i-k
删除根 // 这步很有技巧,更新队列不是一次更新一个,而是变化的数目零或者正数个
类似的 while PQ2
max[i],min[i] 分别从 PQ1, PQ2 根的优先级得到(或者取的根的值,然后检索数组)
//PQ1,PQ2里边元素时刻满足,对于值为i优先级为p的元素,有v[i]=p,v是给出来的数组.
//如果用C STL,用PriorityQueue<>,如果用Java,用TreeMap,不过java里边key是
priority这俩正好是反过来的.

t*j2010-06-15 07:06

75 楼

I see. Thanks~很tricky的方法，赞。不过这个方法是average O(1)时间，
但是对每次移动来说需要的时间variation比较大，具体看面试官要求了。

到O

【在 A*********r 的大作中提到】

: 永远是从尾插入的，只要O(1)的。
: 如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删除一次，所以整个的复杂度是O(n)。。
: 这道题的trick就在这里，链表保留的不是window里面的所有数，否则的话，就达不到O(n).

j*l2010-06-15 07:06

76 楼

是这个意思？
1) 如果新进窗口的数比当前尾部数小，直接插入尾部
2) 如果新进窗口的数比当前尾部数大，从尾部开始删除，直到遇到比当前数大或者删
空，再插入尾部
3) 如果新出窗口的数是头部的最大数，删除头部

到O

【在 A*********r 的大作中提到】

: 永远是从尾插入的，只要O(1)的。
: 如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删除一次，所以整个的复杂度是O(n)。。
: 这道题的trick就在这里，链表保留的不是window里面的所有数，否则的话，就达不到O(n).

d*e2010-06-15 07:06

77 楼

但这个删除是O(1)吗？我怎么觉得是O(k)

【在 j**l 的大作中提到】

: 是这个意思？
: 1) 如果新进窗口的数比当前尾部数小，直接插入尾部
: 2) 如果新进窗口的数比当前尾部数大，从尾部开始删除，直到遇到比当前数大或者删
: 空，再插入尾部
: 3) 如果新出窗口的数是头部的最大数，删除头部
:
: 到O

g*e2010-06-15 07:06

78 楼

我做过fb的一个类似的题，用priority heap，因为slide window size不会太大，同时
开个hashtable记录各个node在heap里的位置，这样更像heap的时候就不用平均logn了。
这道题目上lz的解法简洁很多。赞的。

到O

【在 A*********r 的大作中提到】

: 永远是从尾插入的，只要O(1)的。
: 如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删除一次，所以整个的复杂度是O(n)。。
: 这道题的trick就在这里，链表保留的不是window里面的所有数，否则的话，就达不到O(n).

l*e2010-06-15 07:06

79 楼

这题的正确解法是用circular buffer

【在 j**l 的大作中提到】

: 是这个意思？
: 1) 如果新进窗口的数比当前尾部数小，直接插入尾部
: 2) 如果新进窗口的数比当前尾部数大，从尾部开始删除，直到遇到比当前数大或者删
: 空，再插入尾部
: 3) 如果新出窗口的数是头部的最大数，删除头部
:
: 到O

j*l2010-06-15 07:06

80 楼

是指从每个数入链表一次，出链表一次的角度看？

【在 d**e 的大作中提到】

: 但这个删除是O(1)吗？我怎么觉得是O(k)

l*e2010-06-15 07:06

81 楼

是，每个数最多进窗一次出窗一次

【在 j**l 的大作中提到】

: 是指从每个数入链表一次，出链表一次的角度看？

j*l2010-06-15 07:06

82 楼

应该是：
如果要插入的数比当前尾部数大？

到O

【在 A*********r 的大作中提到】

: 永远是从尾插入的，只要O(1)的。
: 如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删除一次，所以整个的复杂度是O(n)。。
: 这道题的trick就在这里，链表保留的不是window里面的所有数，否则的话，就达不到O(n).

A*r2010-06-15 07:06

83 楼

你的理解是对的。。

【在 j**l 的大作中提到】

: 是这个意思？
: 1) 如果新进窗口的数比当前尾部数小，直接插入尾部
: 2) 如果新进窗口的数比当前尾部数大，从尾部开始删除，直到遇到比当前数大或者删
: 空，再插入尾部
: 3) 如果新出窗口的数是头部的最大数，删除头部
:
: 到O

j*l2010-06-15 07:06

84 楼

这是下面这道题的特例吧？
请实现一个队列，要求enqueue, dequeue和GetMax都是O(1)时间。
只是随着窗口的滑动，队列每次删除一个元素，插入一个元素，始终维持长度k不变
由于队列可以用两个栈实现，又可归约为下面一道名题
请实现一个栈，要求push, pop和GetMin都是O(1)时间。

到O

【在 A*********r 的大作中提到】

: 永远是从尾插入的，只要O(1)的。
: 如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删除一次，所以整个的复杂度是O(n)。。
: 这道题的trick就在这里，链表保留的不是window里面的所有数，否则的话，就达不到O(n).

A*r2010-06-15 07:06

85 楼

嗯，写错了，已经改了。。

【在 j**l 的大作中提到】

: 应该是：
: 如果要插入的数比当前尾部数大？
:
: 到O

A*r2010-06-15 07:06

86 楼

非名校cs fresh phd. intern once

【在 r********9 的大作中提到】

: 可以说说你的背景吗？
: 做过intern？
: 名校？
: phd？
:
: ，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
: 现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
: 业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
: 期的时间。。

g*e2010-06-15 07:06

87 楼

我说的那题目跟这个基本就是一样了。但是没告诉我期望（最优）的复杂度是多少。老
兄只用两个stack可以实现getmin/max是o（1）。指教一下，多谢了

【在 j**l 的大作中提到】

: 这是下面这道题的特例吧？
: 请实现一个队列，要求enqueue, dequeue和GetMax都是O(1)时间。
: 只是随着窗口的滑动，队列每次删除一个元素，插入一个元素，始终维持长度k不变
: 由于队列可以用两个栈实现，又可归约为下面一道名题
: 请实现一个栈，要求push, pop和GetMin都是O(1)时间。
:
: 到O

d*e2010-06-15 07:06

88 楼

如果这样……
我昨天也面了一道类似的，unsorted array,输出第k大的数.

【在 j**l 的大作中提到】

: 是指从每个数入链表一次，出链表一次的角度看？

j*l2010-06-15 07:06

89 楼

不管是原始名题O(1)求栈最小(或最大)
还是变体题O(1)求队列最小(或最大)
还是这道滑动窗口题，
思路都是空间换时间，核心都是用空间维持一个序列，因为最大的可能会被删除，原来
小的会变为最大。可以用辅助栈，可以给元素增加链域，也可以这道题那样单独用一个
链表(其实也是一个辅助队列，一个特殊的双端操作的队列)
所谓O(1)都是amortized分析，也就是看每个元素出入辅助空间的次数
单次操作当然有可能是O(k)的

【在 g*****e 的大作中提到】

: 我说的那题目跟这个基本就是一样了。但是没告诉我期望（最优）的复杂度是多少。老
: 兄只用两个stack可以实现getmin/max是o（1）。指教一下，多谢了

a*12010-06-15 07:06

90 楼

cong!粗略算算第一年都有20万了。。。。。。请问股票是不是每年都给这么多的?

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

g*e2010-06-15 07:06

91 楼

了解。那跟我给的算法思路是一样的。多谢

【在 j**l 的大作中提到】

: 不管是原始名题O(1)求栈最小(或最大)
: 还是变体题O(1)求队列最小(或最大)
: 还是这道滑动窗口题，
: 思路都是空间换时间，核心都是用空间维持一个序列，因为最大的可能会被删除，原来
: 小的会变为最大。可以用辅助栈，可以给元素增加链域，也可以这道题那样单独用一个
: 链表(其实也是一个辅助队列，一个特殊的双端操作的队列)
: 所谓O(1)都是amortized分析，也就是看每个元素出入辅助空间的次数
: 单次操作当然有可能是O(k)的

q*e2010-06-15 07:06

92 楼

这个应该是option吧。。。

【在 a*******1 的大作中提到】

: cong!粗略算算第一年都有20万了。。。。。。请问股票是不是每年都给这么多的?

s*n2010-06-15 07:06

93 楼

我的方法：
数据结构：滑动window array, size_t k as circular buffer.
int max, int maxindex,
int secondaftermax, int second index,
// prepossing:
compute max, maxindex
for all data after max in windows
compute secondafteramx, get the index.
if maxindex is the last one,
secondaftermax is -1, secondinex is -1;
void EnWindow(int x)
{
enqueue(x);
if (x >= max)
update max, maxindex;
if ( x < max && x >= secondaftermax)
update secondaftermax, secondindex;
}
void Dewindow()
{
if (maxindex is the dequeued one)
{
max = secondaftermax;
maxindex = secondindex;
secondaftermax = -1;
secondindex = -1;
}

dequeue ()
}

【在 j**l 的大作中提到】

: 不管是原始名题O(1)求栈最小(或最大)
: 还是变体题O(1)求队列最小(或最大)
: 还是这道滑动窗口题，
: 思路都是空间换时间，核心都是用空间维持一个序列，因为最大的可能会被删除，原来
: 小的会变为最大。可以用辅助栈，可以给元素增加链域，也可以这道题那样单独用一个
: 链表(其实也是一个辅助队列，一个特殊的双端操作的队列)
: 所谓O(1)都是amortized分析，也就是看每个元素出入辅助空间的次数
: 单次操作当然有可能是O(k)的

s*n2010-06-15 07:06

94 楼

Treemap不是red-black tree吗？怎么实现max-queue?

【在 s*x 的大作中提到】

: 恭喜.
: BTW:sliding window 的那个题目,前面不是有人贴链接了,楼上还有没看懂的? 用线性
: 结构,单纯的链表或者数组肯定不行,必须用到树形结构.堆可以.问题是这里有两个值,
: 一个是数组的位置,要保存好更新窗口,一个是数组元素的值,这个好取最大最小.所以就
: 是一个优先队列了,存的元素是数组元素下标,更新的时候将下标和当前窗口边界比较,
: 超出的就删除;而优先级用数组元素的值来表示.同时取最大和最小,所以一共需要俩优
: 先队列,伪码大概是这个样子:
: for i from 1 to k 窗口的大小
: add i with priority v[i] into PQ1, PQ2
: max[i],min[i] 分别从 PQ1, PQ2 根的优先级得到

a*r2010-06-15 07:06

95 楼

cong！！

G*32010-06-15 07:06

96 楼

Con

x*y2010-06-15 07:06

97 楼

我遇到过一个类似问题, 不过是滑动每一步找MEDIAN, 而不是MIN/MAX. 也要求O(N),
怎么做?

【在 j**l 的大作中提到】

: 不管是原始名题O(1)求栈最小(或最大)
: 还是变体题O(1)求队列最小(或最大)
: 还是这道滑动窗口题，
: 思路都是空间换时间，核心都是用空间维持一个序列，因为最大的可能会被删除，原来
: 小的会变为最大。可以用辅助栈，可以给元素增加链域，也可以这道题那样单独用一个
: 链表(其实也是一个辅助队列，一个特殊的双端操作的队列)
: 所谓O(1)都是amortized分析，也就是看每个元素出入辅助空间的次数
: 单次操作当然有可能是O(k)的

s*n2010-06-15 07:06

98 楼

if o(n). simply keep a sort array, then dewindow, remove one left a blank
position, then when enwindow, insert the one and rearrange like insert sort.

【在 x**y 的大作中提到】

: 我遇到过一个类似问题, 不过是滑动每一步找MEDIAN, 而不是MIN/MAX. 也要求O(N),
: 怎么做?

l*42010-06-15 07:06

99 楼

好多钱啦，楼主，恭喜恭喜。

s*x2010-06-15 07:06

100 楼

存俩sorted list, 一个按index排, 一个按value排, 都用双链接结构, 前面的有后面
的索引.滑动的时候都可以直接找到删掉,O(1),但是插入第二个要二份检索需要O(log k
),大概应该是O(N logk),不考虑k就是O(N)的了.

【在 x**y 的大作中提到】

: 我遇到过一个类似问题, 不过是滑动每一步找MEDIAN, 而不是MIN/MAX. 也要求O(N),
: 怎么做?

r*w2010-06-15 07:06

101 楼

股票还是option？这个差好远
如果是160股股票的话，那值10万刀了
如果是option on 160 shares，那估计只有1万左右

【在 q*****e 的大作中提到】

: 这个应该是option吧。。。

b*u2010-06-15 07:06

102 楼

wk, google这么多钱啊？stock+relocation都有6, 7万了吧？

，尽管
recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀
孕，睡不好觉挺
难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on
-site结束后才
跟导师说推荐信的事，结果就多等了将近两个星期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

b*n2010-06-15 07:06

103 楼

不懂别胡说。

on

【在 b***u 的大作中提到】

: wk, google这么多钱啊？stock+relocation都有6, 7万了吧？
:
: ，尽管
: recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀
: 孕，睡不好觉挺
: 难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on
: -site结束后才
: 跟导师说推荐信的事，结果就多等了将近两个星期的时间。。

l*x2010-06-15 07:06

104 楼

牛，恭喜恭喜

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

j*l2010-06-15 07:06

105 楼

这是采用有序链表来实现优先队列的思想吧，优先级最高的就是首结点。优先队列当然
也可以用其他底层数据结构来实现，比如说heap。
只不过插入一个元素的时候可能伴随一系列的删除操作，一般的优先队列插入的时候不
删除。
不过，这是一个从头删除，从尾插入和删除的双端队列, 用单链表怎么实现从尾部向前
删除元素呢？是否要用双链表才行？

e*62010-06-15 07:06

106 楼

恭喜呀~~ Google offer好羡慕噢~~~

f*u2010-06-15 07:06

107 楼

gxgx
lz的学校是top多少的阿

C*s2010-06-15 07:06

108 楼

好有银子
真不平啊为啥博后这么少的钱
都是fresh phd
555

t*a2010-06-15 07:06

109 楼

cong !~

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-sit
属于天上掉下来的机会，我从8月

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础

h*s2010-06-15 07:06

110 楼

Cong! 沾沾运气！

，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是
现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕
业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星
期的时间。。

【在 A*********r 的大作中提到】

: 刚刚从recruiter那里得到口头offer, 一般的fresh cs phd的 package
: base 11万多， 15% bonus
: stock 160
: relocation 大概6千
: 懒得再折腾等待了，估计就从了。。
: 从on-site到现在，差不多等了一个月，刚开始两周不着急，后来却觉得有点煎熬了，尽管recruiter每周都跟我联系，说一下近况，但是等待的滋味真的不好受，尤其是现在怀孕，睡不好觉挺难受的。。教训是一定要提前准备推荐信。。我的情况是准备毕业，导师比较忙，就on-site结束后才跟导师说推荐信的事，结果就多等了将近两个星期的时间。。
: 我个人的经历没有什么普遍意义，这个google的面试属于天上掉下来的机会，我从8月
: 份收到recruiter的电话，到9月初准备电话面试，到10月初准备on-site, 前后复习的
: 时间有限，主要就是在本版混了差不多两个月，电面的时候看了interview exposed
: and careercup 150, 准备onsite时，以careercup 4th为范本大概过了一遍所有的基础