s********r
发帖数: 277 | 1 估计挂了, 就贴一下
问了两道题
第一题
merge n sorted list. 我用heap做,比较容易.
第二题
题目弄了半天大概搞清楚意思, 但是没做出来. 大家出来看一下怎么做.
有一个lock, 比如说1234
假设你要解锁, 你要尝试所有的combination来解锁, 怎么把这所有的combination存在
一个sequence里面使得sequence最短.
比如说锁只能是 0 1 2 组成的数字
锁是 1
012
锁是 12
sequence 可以是
000102101112202122
代表
00 01 02 10 11 12 20 21 22
也可以是, 如果你连着读的话
0011022120
可以代表
00
01
11
10
02
22
21
12
20
我觉得是怎么压缩这些candidate key到一个string里面 |
c*******e
发帖数: 621 | |
s********l
发帖数: 998 | 3 第二题 没看明白 :( 怎么没有数字3在sequence里啊？
比如说锁只能是 0 1 2 3 组成的数字
锁是 1
012
锁是 12
sequence 可以是
000102101112202122
也可以是, 如果你连着读的话
00110220121 |
n******n
发帖数: 12088 | 4 没看懂第二题
【在 s********r 的大作中提到】
: 估计挂了, 就贴一下
: 问了两道题
: 第一题
: merge n sorted list. 我用heap做,比较容易.
: 第二题
: 题目弄了半天大概搞清楚意思, 但是没做出来. 大家出来看一下怎么做.
: 有一个lock, 比如说1234
: 假设你要解锁, 你要尝试所有的combination来解锁, 怎么把这所有的combination存在
: 一个sequence里面使得sequence最短.
: 比如说锁只能是 0 1 2 组成的数字
|
s********r
发帖数: 277 | |
s********r
发帖数: 277 | 6 我改过来了, 假设锁只能是0 1 2 组成
【在 s********l 的大作中提到】
: 第二题 没看明白 :( 怎么没有数字3在sequence里啊？
: 比如说锁只能是 0 1 2 3 组成的数字
: 锁是 1
: 012
: 锁是 12
: sequence 可以是
: 000102101112202122
: 也可以是, 如果你连着读的话
: 00110220121
|
P******r
发帖数: 1342 | |
w*****d
发帖数: 105 | |
c******n
发帖数: 4965 | 9 不明白， 第二不就是记住 123 就行了么？ 要sequence 就现generate, 这样存储最短
【在 s********r 的大作中提到】
: 估计挂了, 就贴一下
: 问了两道题
: 第一题
: merge n sorted list. 我用heap做,比较容易.
: 第二题
: 题目弄了半天大概搞清楚意思, 但是没做出来. 大家出来看一下怎么做.
: 有一个lock, 比如说1234
: 假设你要解锁, 你要尝试所有的combination来解锁, 怎么把这所有的combination存在
: 一个sequence里面使得sequence最短.
: 比如说锁只能是 0 1 2 组成的数字
|
s********r
发帖数: 277 | 10 应该就是这个，谢谢了
在 wqqafnd (wqqafnd) 的大作中提到: 】 |
|
|
s********r
发帖数: 277 | 11 应该就是这个，谢谢了
在 wqqafnd (wqqafnd) 的大作中提到: 】 |
j***y
发帖数: 1640 | |
n******n
发帖数: 12088 | 13 看起来是格雷码的变种？
【在 w*****d 的大作中提到】
: http://en.wikipedia.org/wiki/De_Bruijn_sequence
: 说实话，如果以前不知道，要现场做出这个题基本不可能。
: 我感觉你被黑了。。。
|
y****e
发帖数: 25 | |
F****n
发帖数: 3271 | 15 面试官自己搞清楚这个怎么work的了吗？
这个只适用于一些老式的会自动check不定长度输入的系统
比如PIN是4位的，如果输入12345它会check 1234 和 2345
现在都要你输入* # 之类的，早就不适用了
拿冷僻的旧技术来为难新人，Google真是奇葩
【在 s********r 的大作中提到】
: 估计挂了, 就贴一下
: 问了两道题
: 第一题
: merge n sorted list. 我用heap做,比较容易.
: 第二题
: 题目弄了半天大概搞清楚意思, 但是没做出来. 大家出来看一下怎么做.
: 有一个lock, 比如说1234
: 假设你要解锁, 你要尝试所有的combination来解锁, 怎么把这所有的combination存在
: 一个sequence里面使得sequence最短.
: 比如说锁只能是 0 1 2 组成的数字
|
G*****m
发帖数: 5395 | 16 第一题做好了 估计问题不大
第二题就是调戏一下你 不过第二题经典题啊
【在 s********r 的大作中提到】
: 估计挂了, 就贴一下
: 问了两道题
: 第一题
: merge n sorted list. 我用heap做,比较容易.
: 第二题
: 题目弄了半天大概搞清楚意思, 但是没做出来. 大家出来看一下怎么做.
: 有一个lock, 比如说1234
: 假设你要解锁, 你要尝试所有的combination来解锁, 怎么把这所有的combination存在
: 一个sequence里面使得sequence最短.
: 比如说锁只能是 0 1 2 组成的数字
|
s********r
发帖数: 277 | |
b*****n
发帖数: 618 | 18 难道你们真的认为面试官expect你必须用上面de brujin sequence的解法答出来？
不知道你们怎么想的，面试考察的仍然是基本的coding和算法，这个题目不用de
brujin就做不了了吗？
这个题目就是基本的dfs ＋ backtracking，每次试下一个可能的数是什么，不行就
backtrack，然后记录下来所有已经试过的密码是什么就行了 |
s********l
发帖数: 998 | 19 问题是这种bf解法 他能让过就行~
【在 b*****n 的大作中提到】
: 难道你们真的认为面试官expect你必须用上面de brujin sequence的解法答出来？
: 不知道你们怎么想的，面试考察的仍然是基本的coding和算法，这个题目不用de
: brujin就做不了了吗？
: 这个题目就是基本的dfs ＋ backtracking，每次试下一个可能的数是什么，不行就
: backtrack，然后记录下来所有已经试过的密码是什么就行了
|
s*****e
发帖数: 1679 | |
|
|
c********5
发帖数: 26 | |
T****U
发帖数: 3344 | 22 如果全部都遍历到，那不成了暴力解法了么？
【在 b*****n 的大作中提到】
: 难道你们真的认为面试官expect你必须用上面de brujin sequence的解法答出来？
: 不知道你们怎么想的，面试考察的仍然是基本的coding和算法，这个题目不用de
: brujin就做不了了吗？
: 这个题目就是基本的dfs ＋ backtracking，每次试下一个可能的数是什么，不行就
: backtrack，然后记录下来所有已经试过的密码是什么就行了
|
T****U
发帖数: 3344 | 23 想让你过的，即使不bf也让你过，不想让你过的，碰到bf更是有理由拒你；用bf解没太
大用
面试考数学题的都是有意刁难，或者是没事找事了
【在 s********l 的大作中提到】
: 问题是这种bf解法 他能让过就行~
|
u**l
发帖数: 35 | 24 面试官是不是烙印？
【在 w*****d 的大作中提到】
: http://en.wikipedia.org/wiki/De_Bruijn_sequence
: 说实话，如果以前不知道，要现场做出这个题基本不可能。
: 我感觉你被黑了。。。
|
b******b
发帖数: 713 | 25 I think the 2nd question is a good one, basically the questions is how to
generate the next sequence number which MAX overlap the previous one without
duplicate.
for example, let the current sequence be, i0, i1, ..., in
the best next number would be i1, i2, ...in, "?", if there is any number can
fit in the "?" which haven't been seen before, if non, then try i2, i3, ...,
in, ?1, ?2
I do think there is simple rule you can discover to easily generate the next
number, similar to next permutation sequence, I also agree it's unfair to
ask candidate to find out the rule over the phone in 5 minutes.
【在 T****U 的大作中提到】
: 想让你过的，即使不bf也让你过，不想让你过的，碰到bf更是有理由拒你；用bf解没太
: 大用
: 面试考数学题的都是有意刁难，或者是没事找事了
|
h**p
发帖数: 211 | 26 LZ，请问这个电面过了吗？
【在 s********r 的大作中提到】
: 估计挂了, 就贴一下
: 问了两道题
: 第一题
: merge n sorted list. 我用heap做,比较容易.
: 第二题
: 题目弄了半天大概搞清楚意思, 但是没做出来. 大家出来看一下怎么做.
: 有一个lock, 比如说1234
: 假设你要解锁, 你要尝试所有的combination来解锁, 怎么把这所有的combination存在
: 一个sequence里面使得sequence最短.
: 比如说锁只能是 0 1 2 组成的数字
|
