D**********d
发帖数: 849 | 1 从本版获益非浅，献上面经并求 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 + 递归与回溯
第四个面试给两个整数串求公共元素，问不同长度又是如何，分析复杂度。
总体感觉不是很好，不能很好地表现自己。
希望借本版仙气增加一下人品，呵呵 |
p*u
发帖数: 136 | 2 第一题什么意思？
【在 D**********d 的大作中提到】
: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用
|
w*****e
发帖数: 931 | 3 第一题是说所有可能的组合都是该字符串子串的意思吗？
【在 D**********d 的大作中提到】
: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用
|
w********s
发帖数: 214 | 4 BLESS 一下楼主，毕竟是G嘛，能答成这样也不错了，希望你拿到offer。
有几个问题：
第二题是不是可以用quick select啊，也是O(n)了。
第四题有什么tricky point么？ |
m**********4
发帖数: 774 | 5 第一个这个破题这么爱问，这题没见过谁会啊。看我两年前的面经。。。。底下有人解
答怎么做，反正我是没看懂。
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**********d
发帖数: 849 | 6 可否说一下 quick select 的具体操作? n 是 dictionary 的 size?
第四题可以根据两个字符串的长短选择合适的算法. e.g. 将短的入 hash set, O(n+m)
.
【在 w********s 的大作中提到】
: BLESS 一下楼主，毕竟是G嘛，能答成这样也不错了，希望你拿到offer。
: 有几个问题：
: 第二题是不是可以用quick select啊，也是O(n)了。
: 第四题有什么tricky point么？
|
D**********d
发帖数: 849 | 7 是的，就是这个帖子里的第三题。
可能我理解不对，但是按回帖的办法也不可行,e.g.
00001111....9999 ?-> 8999 ...?
没有遇到类似的题目，也不知从什么数据结构入手。
到现在也不知道如何做。
直觉是找有向图中的 Hamilton 通路, 但一下子无从下手，
【在 m**********4 的大作中提到】
: 第一个这个破题这么爱问，这题没见过谁会啊。看我两年前的面经。。。。底下有人解
: 答怎么做，反正我是没看懂。
: http://www.mitbbs.com/article0/Quant/31263297_0.html
: 希望LZ能拿到OFFER！
|
t**********r
发帖数: 2153 | 8 我电面的第二道题就是这个。讲思路的时候还行。结果写code的时候时间不够，慌了一
下。写成了brute force. 挂了。
【在 D**********d 的大作中提到】
: 是的，就是这个帖子里的第三题。
: 可能我理解不对，但是按回帖的办法也不可行,e.g.
: 00001111....9999 ?-> 8999 ...?
: 没有遇到类似的题目，也不知从什么数据结构入手。
: 到现在也不知道如何做。
: 直觉是找有向图中的 Hamilton 通路, 但一下子无从下手，
|
D**********d
发帖数: 849 | 9 那你解决的思路是什么？
【在 t**********r 的大作中提到】
: 我电面的第二道题就是这个。讲思路的时候还行。结果写code的时候时间不够，慌了一
: 下。写成了brute force. 挂了。
|
r*******b
发帖数: 78 | 10 希望楼主能拿offer！
【在 D**********d 的大作中提到】
: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用
|
|
|
t**********r
发帖数: 2153 | 11 不知道你的要求是什么。我那个是只要最后四位是正确的就可以打开。思路是0000->
0001->0010->...
具体解释可以用图。节点是四个数字，有向边是可以一步走到。每走一步去掉节点。最
后如果还有剩，从剩余节点开始。
【在 D**********d 的大作中提到】
: 那你解决的思路是什么？
|
D**********d
发帖数: 849 | 12 他的要求是string 总长度是下界 10^4+3. 也就是图中经过每点一次且仅一次 |
n****e
发帖数: 678 | 13 用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****a
发帖数: 15 | |
n****e
发帖数: 678 | 15 网上搜了搜，发现第一题是Donald Knuth提出的问题的变形。
说不定在《The Art of Computer Programming》中可以找到答案。哈哈
网上有篇paper可以参考一下：http://people.inf.ethz.ch/zeugen/papers/zal_ipl11_perms.pdf |
p*u
发帖数: 136 | 16 0000 ~ 9999一共10000个节点，每个节点都有10条有相边连接其他节点。
猜测：直接dfs从任意节点出发找一条链即可？实际上由于图的性质，dfs不用回溯就能
找到链？所以时间复杂度是O(n)？
不知道怎么证明，猜得。
【在 t**********r 的大作中提到】
: 不知道你的要求是什么。我那个是只要最后四位是正确的就可以打开。思路是0000->
: 0001->0010->...
: 具体解释可以用图。节点是四个数字，有向边是可以一步走到。每走一步去掉节点。最
: 后如果还有剩，从剩余节点开始。
|
l*n
发帖数: 529 | 17 图的思路是对的，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****e
发帖数: 678 | 18 如果用图，从哪个点出发开始找呢？ 每一个permutation都有可能是初始的点。
【在 l*n 的大作中提到】
: 图的思路是对的，visited信息可以通过hashmap来记录，相邻节点的联系就是from节点
: 的后三个字符跟to节点的前三个字符相同。
: 但是backtracking应该肯定是要的。这图里面环很多，dfs找的时候肯定会陷到某个级
: 别的环中去，导致最后没办法跟图的剩余部分连接起来。这时候如果不backtrack的话
: ，就相当于重新开始了，那么得到的结果就肯定不是最优的。
: 4个数字的密码，最短是10^4+3，每个数都只引入一个新的数字，3是最开始初始化的起
: 点。
: 前面有人提到的面经帖中有关环的处理很是tricky，感觉不是cs的路数，cs的搞法很简
: 单，直接backtrack就是了。
|
l*n
发帖数: 529 | 19 数字是均等的，可以用任何三个数字作为起点吧？这当中可能有1111跟1234的区别，前
者不能胜任起点的话，后者肯定可以。
【在 n****e 的大作中提到】
: 如果用图，从哪个点出发开始找呢？ 每一个permutation都有可能是初始的点。
|
d****5
发帖数: 202 | 20 第一题可以用的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*****3
发帖数: 1168 | |
c*********g
发帖数: 140 | |
l*n
发帖数: 529 | 23 感觉这种题实在是太偏了，知道了不怎样，不知道也没怎样。
http://en.wikipedia.org/wiki/Lyndon_word
【在 m**********4 的大作中提到】
: 第一个这个破题这么爱问，这题没见过谁会啊。看我两年前的面经。。。。底下有人解
: 答怎么做，反正我是没看懂。
: http://www.mitbbs.com/article0/Quant/31263297_0.html
: 希望LZ能拿到OFFER！
|
n****e
发帖数: 678 | 24 请问如何证明这种解法的正确性？
【在 d****5 的大作中提到】
: 第一题可以用的pattern是
: 0000 -> 0009 -> 0099 -> 0999 -> 9999 -> 9998 -> 9989 -> ...
: 即每次找出最大的候选
|
n****e
发帖数: 678 | 25 能说说为什么第一题可以用Lyndon word解吗？
【在 l*n 的大作中提到】
: 感觉这种题实在是太偏了，知道了不怎样，不知道也没怎样。
: http://en.wikipedia.org/wiki/Lyndon_word
|
D**********d
发帖数: 849 | 26 所以对于非大牛，像我这样的，找工作运气真的很重要。
【在 l*n 的大作中提到】
: 感觉这种题实在是太偏了，知道了不怎样，不知道也没怎样。
: http://en.wikipedia.org/wiki/Lyndon_word
|
h**u
发帖数: 144 | 27 第一题问你的是不是一个头发不多的白男。
你是不是面的youtube
【在 D**********d 的大作中提到】
: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用
|
h**u
发帖数: 144 | 28 据说其实就是用set来保存已经出现过的所有组合。然后再一个个的填数字，从右边开始
【在 D**********d 的大作中提到】
: 是的，就是这个帖子里的第三题。
: 可能我理解不对，但是按回帖的办法也不可行,e.g.
: 00001111....9999 ?-> 8999 ...?
: 没有遇到类似的题目，也不知从什么数据结构入手。
: 到现在也不知道如何做。
: 直觉是找有向图中的 Hamilton 通路, 但一下子无从下手，
|
l*n
发帖数: 529 | |
l*n
发帖数: 529 | 30 你描述的就是generate Lyndon words的过程，而且还少很多重要的步骤。但是关键谁
能一眼看出就这么着串起来是解呢？
开始
【在 h**u 的大作中提到】
: 据说其实就是用set来保存已经出现过的所有组合。然后再一个个的填数字，从右边开始
|
|
|
c********e
发帖数: 186 | |
w*******e
发帖数: 395 | 32 第一题：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**********s
发帖数: 115 | |
y*********0
发帖数: 406 | 34 第三题是什么意思？怎么解的？跟leetcode中word search差不多？
【在 D**********d 的大作中提到】
: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用
|
r*******h
发帖数: 315 | 35 第一题的直观解法：从最0000开始生成数字串，依次检查组合0001, 0002，。。。每个
待检查的组合的前缀从长到短依次在数字串中查找，遇到匹配的，插入对应后缀(有可
能是空)产生新的数字串，如果到目前为止所有组合都在数字串中，继续下一个组合，
如果不是，检查下一个前缀出现的位置，如果没有，前缀长度-1，继续查，如果前缀长
度为0，把整个组合添加到数字串的末尾。这个算法对于密码只用0和1的情况是符合约
束的，还没时间写个程序验证0-9的情况。
基本思想就是假设前面k个组合已经找到一个最短的数字串，对于当前k+1组合，需要在
数字串中找到当前组合的最长前缀，然后插入剩余部分，如果新字符串可以包含之前所
有k个组合，那么继续k+2组合。
0000
00001
000010002
...
000010002...0009
0000110002...0009
... |
h******2
发帖数: 69 | |
z**q
发帖数: 577 | 37 第一题似乎答案就是理论下界: 3+10^4。
用10^3种combination作为节点建有向图，好象可以证明欧拉路径存在。
用Lyndon Word构造de Bruijin sequence弄出来的得是circular sequence吧。题目里
面有说那个code sequence是circular？
bless! |
f***h
发帖数: 22 | |
v***n
发帖数: 562 | 39 Bless
【在 D**********d 的大作中提到】
: 从本版获益非浅，献上面经并求 blessing.
: 共有四个技术面试
: 第一个面试官问题是 password generation.
: 一个四位的 password, 每位从 0-9, 求 generate 出一个最短的数字串, 使之能包括
: 所有的 possible combination.
: 这个面试回答得很糟糕，思考了半天也找不出 pattern 来。
: 最后用 brute force 方法草草了事。
: 后面三个问题比较轻松。
: 第二个问题是对无序数组找 Maximum 前n个的问题，
: 回答用 heap 解决。又问如果返回答案按原来次序，应该如何做，回答heap 里用
|
