今天挂了个GS的单子， 152.66 居然filled - 未名空间MITBBS历史存档

今天挂了个GS的单子， 152.66 居然filled# Stock

e*n2010-01-23 08:01

1 楼

如今去闲不住网上做闲客早已成为流行，网上也流传许多关于闲客“知人乐教”、“赠
人玫瑰，手有余香”的若干故事。的确，闲不住网的诞生，让世界各地的民间知识贤士
有了展示自己才华的机会——可以在全世界范围贡献自己的知识，获得应得的报酬。
我在闲不住网选过很多闲客的课，自认为闲客中卧虎藏龙、强中自有强中手，现在向大
家推荐闲不住网的顶级闲客前十二强，这些闲客是各有千秋，每人手里各执一技之长，
都是各个行业中的“牛人”。
热度NO.1 闲客美国之窗
闲客美国之窗在各大网络媒体享有盛名，她是一位全能的女性，不但在美国获得了博士
和硕士学位，还是三个孩子母亲。她的声音悦耳动听，教课认真负责，而且非常有耐心
。她开设的英语课程一直是闲客学生选课的热点。她还是一个很能给人启发的老师，她
常和大家分享自己奋斗的亲身经历，帮助大家找回快乐和自信。她开设的课程有趣多样
，你总能找到可以和她交流的话题。而且大部分课程免费，收费的课程仅10元/半小时
。
热度NO.2 闲客Pro_Tutor
Pro_Tutor是闲不住上最受欢迎的英语老师，正如她的闲名一样，她是地道的
professional tutor

D*d2010-01-23 08:01

2 楼

从本版获益非浅，献上面经并求 blessing.
共有四个技术面试
第一个面试官问题是 password generation.
一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
所有的 possible combination.
这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
最后用 brute force 方法草草了事。
后面三个问题比较轻松。
第二个问题是对无序数组找 Maximum 前n个的问题，
回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用
index，他好像很满意。
第三个面试 Given a charactor board[4][4] and a dictionary, count valid words
within the board
很简单，用 trie preprocess dictionary + 递归与回溯
第四个面试给两个整数串求公共元素，问不同长度又是如何，分析复杂度。
总体感觉不是很好，不能很好地表现自己。
希望借本版仙气增加一下人品，呵呵

m*x2010-01-23 08:01

3 楼

咋办，下周一还有机会逃命吗？

p*u2010-01-23 08:01

4 楼

第一题什么意思？

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

x*i2010-01-23 08:01

5 楼

你发财了，兄弟。

w*e2010-01-23 08:01

6 楼

第一题是说所有可能的组合都是该字符串子串的意思吗？

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

m*x2010-01-23 08:01

7 楼

下周无论如何，开盘就甩卖，这大盘太吓人了

w*s2010-01-23 08:01

8 楼

BLESS 一下楼主，毕竟是G嘛，能答成这样也不错了，希望你拿到offer。
有几个问题：
第二题是不是可以用quick select啊，也是O(n)了。
第四题有什么tricky point么？

m*x2010-01-23 08:01

9 楼

今天把黑老大卖了
157.88 卖了，今天晚上不用担心了

m*42010-01-23 08:01

10 楼

第一个这个破题这么爱问，这题没见过谁会啊。看我两年前的面经。。。。底下有人解
答怎么做，反正我是没看懂。
http://www.mitbbs.com/article0/Quant/31263297_0.html
希望LZ能拿到OFFER！

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

D*d2010-01-23 08:01

11 楼

可否说一下 quick select 的具体操作? n 是 dictionary 的 size?
第四题可以根据两个字符串的长短选择合适的算法. e.g. 将短的入 hash set, O(n+m)
.

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

: BLESS 一下楼主，毕竟是G嘛，能答成这样也不错了，希望你拿到offer。
: 有几个问题：
: 第二题是不是可以用quick select啊，也是O(n)了。
: 第四题有什么tricky point么？

D*d2010-01-23 08:01

12 楼

是的，就是这个帖子里的第三题。
可能我理解不对，但是按回帖的办法也不可行,e.g.
00001111....9999 ?-> 8999 ...?
没有遇到类似的题目，也不知从什么数据结构入手。
到现在也不知道如何做。
直觉是找有向图中的 Hamilton 通路, 但一下子无从下手，

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

: 第一个这个破题这么爱问，这题没见过谁会啊。看我两年前的面经。。。。底下有人解
: 答怎么做，反正我是没看懂。
: http://www.mitbbs.com/article0/Quant/31263297_0.html
: 希望LZ能拿到OFFER！

t*r2010-01-23 08:01

13 楼

我电面的第二道题就是这个。讲思路的时候还行。结果写code的时候时间不够，慌了一
下。写成了brute force. 挂了。

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

: 是的，就是这个帖子里的第三题。
: 可能我理解不对，但是按回帖的办法也不可行,e.g.
: 00001111....9999 ?-> 8999 ...?
: 没有遇到类似的题目，也不知从什么数据结构入手。
: 到现在也不知道如何做。
: 直觉是找有向图中的 Hamilton 通路, 但一下子无从下手，

D*d2010-01-23 08:01

14 楼

那你解决的思路是什么？

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

: 我电面的第二道题就是这个。讲思路的时候还行。结果写code的时候时间不够，慌了一
: 下。写成了brute force. 挂了。

r*b2010-01-23 08:01

15 楼

希望楼主能拿offer！

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

t*r2010-01-23 08:01

16 楼

不知道你的要求是什么。我那个是只要最后四位是正确的就可以打开。思路是0000->
0001->0010->...
具体解释可以用图。节点是四个数字，有向边是可以一步走到。每走一步去掉节点。最
后如果还有剩，从剩余节点开始。

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

: 那你解决的思路是什么？

D*d2010-01-23 08:01

17 楼

他的要求是string 总长度是下界 10^4+3. 也就是图中经过每点一次且仅一次

n*e2010-01-23 08:01

18 楼

用quick select里面的partition function
当pivot的index = k时，[0, k-1]的数为最大的k个值，复杂度是O(N). N是数组长度。
如果返回答案按原来次序，这个方法也要给每个值附加原来的index。

m)

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

: 可否说一下 quick select 的具体操作? n 是 dictionary 的 size?
: 第四题可以根据两个字符串的长短选择合适的算法. e.g. 将短的入 hash set, O(n+m)
: .

y*a2010-01-23 08:01

19 楼

谢谢分享！bless 楼主拿到offer。

n*e2010-01-23 08:01

20 楼

网上搜了搜，发现第一题是Donald Knuth提出的问题的变形。
说不定在《The Art of Computer Programming》中可以找到答案。哈哈
网上有篇paper可以参考一下：http://people.inf.ethz.ch/zeugen/papers/zal_ipl11_perms.pdf

p*u2010-01-23 08:01

21 楼

0000 ~ 9999一共10000个节点，每个节点都有10条有相边连接其他节点。
猜测：直接dfs从任意节点出发找一条链即可？实际上由于图的性质，dfs不用回溯就能
找到链？所以时间复杂度是O(n)？
不知道怎么证明，猜得。

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

: 不知道你的要求是什么。我那个是只要最后四位是正确的就可以打开。思路是0000->
: 0001->0010->...
: 具体解释可以用图。节点是四个数字，有向边是可以一步走到。每走一步去掉节点。最
: 后如果还有剩，从剩余节点开始。

l*n2010-01-23 08:01

22 楼

图的思路是对的，visited信息可以通过hashmap来记录，相邻节点的联系就是from节点
的后三个字符跟to节点的前三个字符相同。
但是backtracking应该肯定是要的。这图里面环很多，dfs找的时候肯定会陷到某个级
别的环中去，导致最后没办法跟图的剩余部分连接起来。这时候如果不backtrack的话
，就相当于重新开始了，那么得到的结果就肯定不是最优的。
4个数字的密码，最短是10^4+3，每个数都只引入一个新的数字，3是最开始初始化的起
点。
前面有人提到的面经帖中有关环的处理很是tricky，感觉不是cs的路数，cs的搞法很简
单，直接backtrack就是了。

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

: 0000 ~ 9999一共10000个节点，每个节点都有10条有相边连接其他节点。
: 猜测：直接dfs从任意节点出发找一条链即可？实际上由于图的性质，dfs不用回溯就能
: 找到链？所以时间复杂度是O(n)？
: 不知道怎么证明，猜得。

n*e2010-01-23 08:01

23 楼

如果用图，从哪个点出发开始找呢？每一个permutation都有可能是初始的点。

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

: 图的思路是对的，visited信息可以通过hashmap来记录，相邻节点的联系就是from节点
: 的后三个字符跟to节点的前三个字符相同。
: 但是backtracking应该肯定是要的。这图里面环很多，dfs找的时候肯定会陷到某个级
: 别的环中去，导致最后没办法跟图的剩余部分连接起来。这时候如果不backtrack的话
: ，就相当于重新开始了，那么得到的结果就肯定不是最优的。
: 4个数字的密码，最短是10^4+3，每个数都只引入一个新的数字，3是最开始初始化的起
: 点。
: 前面有人提到的面经帖中有关环的处理很是tricky，感觉不是cs的路数，cs的搞法很简
: 单，直接backtrack就是了。

l*n2010-01-23 08:01

24 楼

数字是均等的，可以用任何三个数字作为起点吧？这当中可能有1111跟1234的区别，前
者不能胜任起点的话，后者肯定可以。

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

: 如果用图，从哪个点出发开始找呢？每一个permutation都有可能是初始的点。

d*52010-01-23 08:01

25 楼

第一题可以用的pattern是
0000 -> 0009 -> 0099 -> 0999 -> 9999 -> 9998 -> 9989 -> ...
即每次找出最大的候选

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

p*32010-01-23 08:01

26 楼

bless

c*g2010-01-23 08:01

27 楼

Bless!!!!!!!!!

l*n2010-01-23 08:01

28 楼

感觉这种题实在是太偏了，知道了不怎样，不知道也没怎样。
http://en.wikipedia.org/wiki/Lyndon_word

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

: 第一个这个破题这么爱问，这题没见过谁会啊。看我两年前的面经。。。。底下有人解
: 答怎么做，反正我是没看懂。
: http://www.mitbbs.com/article0/Quant/31263297_0.html
: 希望LZ能拿到OFFER！

n*e2010-01-23 08:01

29 楼

请问如何证明这种解法的正确性？

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

: 第一题可以用的pattern是
: 0000 -> 0009 -> 0099 -> 0999 -> 9999 -> 9998 -> 9989 -> ...
: 即每次找出最大的候选

n*e2010-01-23 08:01

30 楼

能说说为什么第一题可以用Lyndon word解吗？

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

: 感觉这种题实在是太偏了，知道了不怎样，不知道也没怎样。
: http://en.wikipedia.org/wiki/Lyndon_word

D*d2010-01-23 08:01

31 楼

所以对于非大牛，像我这样的，找工作运气真的很重要。

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

: 感觉这种题实在是太偏了，知道了不怎样，不知道也没怎样。
: http://en.wikipedia.org/wiki/Lyndon_word

h*u2010-01-23 08:01

32 楼

第一题问你的是不是一个头发不多的白男。
你是不是面的youtube

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

h*u2010-01-23 08:01

33 楼

据说其实就是用set来保存已经出现过的所有组合。然后再一个个的填数字，从右边开始

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

: 是的，就是这个帖子里的第三题。
: 可能我理解不对，但是按回帖的办法也不可行,e.g.
: 00001111....9999 ?-> 8999 ...?
: 没有遇到类似的题目，也不知从什么数据结构入手。
: 到现在也不知道如何做。
: 直觉是找有向图中的 Hamilton 通路, 但一下子无从下手，

l*n2010-01-23 08:01

34 楼

http://en.wikipedia.org/wiki/Lyndon_word#Connection_to_de_Bruij
http://en.wikipedia.org/wiki/De_Bruijn_sequence#Uses
for proof, see "7.3 De Bruijn Sequences"
http://www.1stworks.com/ref/RuskeyCombGen.pdf

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

: 能说说为什么第一题可以用Lyndon word解吗？

l*n2010-01-23 08:01

35 楼

你描述的就是generate Lyndon words的过程，而且还少很多重要的步骤。但是关键谁
能一眼看出就这么着串起来是解呢？

开始

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

: 据说其实就是用set来保存已经出现过的所有组合。然后再一个个的填数字，从右边开始

c*e2010-01-23 08:01

36 楼

bless

w*e2010-01-23 08:01

37 楼

第一题：generate all combinations, then sort, then combine those shared
prefix.

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

f*s2010-01-23 08:01

38 楼

bless

y*02010-01-23 08:01

39 楼

第三题是什么意思？怎么解的？跟leetcode中word search差不多？

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用

r*h2010-01-23 08:01

40 楼

第一题的直观解法：从最0000开始生成数字串，依次检查组合0001, 0002，。。。每个
待检查的组合的前缀从长到短依次在数字串中查找，遇到匹配的，插入对应后缀(有可
能是空)产生新的数字串，如果到目前为止所有组合都在数字串中，继续下一个组合，
如果不是，检查下一个前缀出现的位置，如果没有，前缀长度-1，继续查，如果前缀长
度为0，把整个组合添加到数字串的末尾。这个算法对于密码只用0和1的情况是符合约
束的，还没时间写个程序验证0-9的情况。
基本思想就是假设前面k个组合已经找到一个最短的数字串，对于当前k+1组合，需要在
数字串中找到当前组合的最长前缀，然后插入剩余部分，如果新字符串可以包含之前所
有k个组合，那么继续k+2组合。
0000
00001
000010002
...
000010002...0009
0000110002...0009
...

h*22010-01-23 08:01

41 楼

bless

z*q2010-01-23 08:01

42 楼

第一题似乎答案就是理论下界: 3+10^4。
用10^3种combination作为节点建有向图，好象可以证明欧拉路径存在。
用Lyndon Word构造de Bruijin sequence弄出来的得是circular sequence吧。题目里
面有说那个code sequence是circular？
bless!

f*h2010-01-23 08:01

43 楼

bless

v*n2010-01-23 08:01

44 楼

Bless

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

: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用