g***j
发帖数: 1275 | 1 在HC挂了，不知道挂在哪儿
第一个，什么是bst，怎么用，怎么查，然后给一个bst，给一个数，返回离这个数最近
的数，要求写code，然后问我code有什么问题，问我coding style如何改进。我当时不
知道这个coding style指的什么，后来就是讨论哪儿有冗余code之类。谈想法，写code。
第二个，什么是多线程，给一个函数copy(char* src, char *dest), 如何设计这个函
数，是多线程safe的，谈想法，写code。
第三个，给一个无限长的整数序列，求这个整数序列的中数，要求limited memory，要
求谈想法，写code。
第四个，谈做过的project，给两个paragraph，如何判断这两个paragraph是相似的，
谈想法；给一个字符串，由多个word组成，要求求出这个连续的k以内的word组成的
word组合的次数，比如hello world all, k = 2 则返回hello 1, world 1, all1,
hello word 1, world all 1， 要求谈想法，写code
第五个，如何设计Google Search的输入时候的自动提示功能 |
w********s
发帖数: 214 | 2 安慰下LZ，毕竟G竞争太激烈了，能进ONSITE证明实力不俗，多准备下肯定能去不错的
公司的。
还有第二题LZ怎么答的呢？貌似看到很多人被问到了第三题，感觉版上的讨论很有意义
，但是如果能给出比较standard solution就好了，望哪位大牛指点一下。还有最后一
题，LZ有什么其他提示么？ |
M*********r
发帖数: 70 | 3 多谢分享面经！
第二题的话是在写之前先要获得lock吗，防止src和dest被其他线程修改。还有什么需
要注意的呢？
请问第三题怎么做的？只知道用两个heap来做，但是不满足limited memory呀。
第四题判断相似能讲下思路吗？多谢了！ |
w********s
发帖数: 214 | 4 LS能给点提示么关于第三题？两个HEAP是什么意思？ |
c*b
发帖数: 3126 | 5 第三题，对于使用limited memory找running median of stream
general的精确方法几乎是不可能的
如果允许做一些近似，就有不少思路
1，如果数据是integer，可以做binning，然后对bins进行统计
精确度取决于bin的大小
2，如果数据服从某一种分布，可以对stream做reservior sampling
samples的median就是对stream的median的一个估计
【在 M*********r 的大作中提到】
: 多谢分享面经！
: 第二题的话是在写之前先要获得lock吗，防止src和dest被其他线程修改。还有什么需
: 要注意的呢？
: 请问第三题怎么做的？只知道用两个heap来做，但是不满足limited memory呀。
: 第四题判断相似能讲下思路吗？多谢了！
|
w********s
发帖数: 214 | 6 感觉binning 的解法比较合理。那个sampling可以提一下。我想这样应该sufficient了。
其他大牛关于这个题有什么想法的也希望可以指教一下。
【在 c*b 的大作中提到】
: 第三题，对于使用limited memory找running median of stream
: general的精确方法几乎是不可能的
: 如果允许做一些近似，就有不少思路
: 1，如果数据是integer，可以做binning，然后对bins进行统计
: 精确度取决于bin的大小
: 2，如果数据服从某一种分布，可以对stream做reservior sampling
: samples的median就是对stream的median的一个估计
|
c***0
发帖数: 449 | 7 第五题是利用trie吗
[发表自未名空间手机版 - m.mitbbs.com] |
r*******n
发帖数: 3020 | 8 第二题，把dest加lock，完事后释放，应该就行了吧
【在 M*********r 的大作中提到】
: 多谢分享面经！
: 第二题的话是在写之前先要获得lock吗，防止src和dest被其他线程修改。还有什么需
: 要注意的呢？
: 请问第三题怎么做的？只知道用两个heap来做，但是不满足limited memory呀。
: 第四题判断相似能讲下思路吗？多谢了！
|
w**t
发帖数: 893 | 9
【在 c*b 的大作中提到】
: 第三题，对于使用limited memory找running median of stream
: general的精确方法几乎是不可能的
: 如果允许做一些近似，就有不少思路
: 1，如果数据是integer，可以做binning，然后对bins进行统计
: 精确度取决于bin的大小
: 2，如果数据服从某一种分布，可以对stream做reservior sampling
: samples的median就是对stream的median的一个估计
|
w**t
发帖数: 893 | 10 可不可以把超大bins方在disk上，利用类似虚存的办法更新或计算。
不过如果输入变动非常快的话，就会很多磁盘读写
【在 c*b 的大作中提到】
: 第三题，对于使用limited memory找running median of stream
: general的精确方法几乎是不可能的
: 如果允许做一些近似，就有不少思路
: 1，如果数据是integer，可以做binning，然后对bins进行统计
: 精确度取决于bin的大小
: 2，如果数据服从某一种分布，可以对stream做reservior sampling
: samples的median就是对stream的median的一个估计
|
|
|
l***i
发帖数: 1309 | 11 顶这个，好像stanford有一门课专门讲过这个问题，还有一篇paper说这个问题。
limited memory必须扔掉一些数，但是不管扔那个数，之后都可以继续给适当的数使得
扔掉的那个数是median，但是这个数已经被扔掉了。。。
【在 c*b 的大作中提到】
: 第三题，对于使用limited memory找running median of stream
: general的精确方法几乎是不可能的
: 如果允许做一些近似，就有不少思路
: 1，如果数据是integer，可以做binning，然后对bins进行统计
: 精确度取决于bin的大小
: 2，如果数据服从某一种分布，可以对stream做reservior sampling
: samples的median就是对stream的median的一个估计
|
u*****o
发帖数: 1224 | 12 我记得前不久板上讨论过一道95% bottom的数的问题 和这个median很像。那个题就是
用两个heap，但node里记录数值和frequency，所以如果知道数的range是n，就维护两
个总数为n的heap就行了。再随时更新mean。这个technique也可以用在这个题上吧。 |
n****e
发帖数: 678 | |
s********u
发帖数: 1109 | 14 想知道第二题lz是怎么做的呢？直接给整个过程加一个lock么？还是分段地lock？ |
t**********h
发帖数: 2273 | 15 帅哥，move on
来年再来
code。
【在 g***j 的大作中提到】
: 在HC挂了，不知道挂在哪儿
: 第一个，什么是bst，怎么用，怎么查，然后给一个bst，给一个数，返回离这个数最近
: 的数，要求写code，然后问我code有什么问题，问我coding style如何改进。我当时不
: 知道这个coding style指的什么，后来就是讨论哪儿有冗余code之类。谈想法，写code。
: 第二个，什么是多线程，给一个函数copy(char* src, char *dest), 如何设计这个函
: 数，是多线程safe的，谈想法，写code。
: 第三个，给一个无限长的整数序列，求这个整数序列的中数，要求limited memory，要
: 求谈想法，写code。
: 第四个，谈做过的project，给两个paragraph，如何判断这两个paragraph是相似的，
: 谈想法；给一个字符串，由多个word组成，要求求出这个连续的k以内的word组成的
|
b**********5
发帖数: 7881 | 16 看了这个面经， 只能说， 这些面经， 怎么这么简单？？！ 我去google， 人家是不
是看我大胸， 所以就想fail掉， 所以尽给我难题， 从来没看见过的题？？！！！ |
n*******1
发帖数: 145 | 17 第三题median of median可以做吧 |
