还两周就要出10月的排期了 - 未名空间MITBBS历史存档

还两周就要出10月的排期了# EB23 - 劳工卡

q*u2012-08-23 07:08

1 楼

准备给孩子班上作万圣节cookie, 请问哪儿有卖cookie 包装纸，很小一个透明小袋子
，比较硬。谢谢。

a*y2012-08-23 07:08

2 楼

第一题，可以一步或者两步的上楼梯，一共有多少种上法
如何在stack里面实现min（）
怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

b*72012-08-23 07:08

3 楼

EB2们开始兴奋了吗？

s*n2012-08-23 07:08

4 楼

michael's
treat bags

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

: 准备给孩子班上作万圣节cookie, 请问哪儿有卖cookie 包装纸，很小一个透明小袋子
: ，比较硬。谢谢。

g*s2012-08-23 07:08

5 楼

DP
return root (assume it is a min-heap)
DP

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

A*72012-08-23 07:08

6 楼

哎呀呀，皇帝不急，急了太监

q*u2012-08-23 07:08

7 楼

treat bags 不可以包食物吧？

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

: michael's
: treat bags

i*92012-08-23 07:08

8 楼

怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
在bfs同时可以加 greedy的思路来optimization,就是算下一步所有reachable单词里跟
destination 单词的 distance,哪个最近就先走哪个

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

p*92012-08-23 07:08

9 楼

时间真快啊

s*n2012-08-23 07:08

10 楼

找food safe的呗
大部分都是的，你在棒糖包装附近找

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

: treat bags 不可以包食物吧？

a*y2012-08-23 07:08

11 楼

是单
But it is BFS, the access order are just in one level, right? I am not sure
whether this would bring much speed up. Anyway, thanks.

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

:
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
: 在bfs同时可以加 greedy的思路来optimization,就是算下一步所有reachable单词里跟
: destination 单词的 distance,哪个最近就先走哪个

k*m2012-08-23 07:08

12 楼

EB2们又等了一年

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

: 时间真快啊

q*u2012-08-23 07:08

13 楼

xiexie.

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

: 找food safe的呗
: 大部分都是的，你在棒糖包装附近找

f*w2012-08-23 07:08

14 楼

Fibonacci ?
没很明白难道用两个stack 全倒出来一遍？
heuristic, 就number of different chars 好了

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

a*n2012-08-23 07:08

15 楼

两周？没希望吧。

D*y2012-08-23 07:08

16 楼

第一个是DP
S[n]=S[n-1]+S[n-2]，就是Fibbonaci
第二个是单独弄一个stack,里面放上有史以来的min(需要extra storage)
或者改变stack里面每一个node的结构，让这个node除了放原来的data以外，还存一个min value (不需要额外内存)
第三题是做一个BFS
第二题和第三题的solution, careercup书上都有

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

b*72012-08-23 07:08

17 楼

差不多吧。 7号左右

a*e2012-08-23 07:08

18 楼

A* should work, and then there are tons of optimizations on A* (e.g., IDA*)

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

a*n2012-08-23 07:08

19 楼

9月的好像憋到了13号才出来的吧？

c*w2012-08-23 07:08

20 楼

第一题就是Fibonacci数列。比如你当前要求走到第n级楼梯的走法F(n), 那么你需要
完成知道走到n-1和n-2级的走法 F（n-1）和F（n-2）。也就是F（n） = F（n-1） +
F（n-2）。

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

p*82012-08-23 07:08

21 楼

yes. i am tired for this very tired....

i*e2012-08-23 07:08

22 楼

第二题是 wordladder 游戏的实现问题，本版有讨论过。
最基本的实现方法是用 BFS，但是level越深就越多节点。
利用一些剪枝可以进行优化
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

g*s2012-08-23 07:08

23 楼

classical. Fibonacci.
classical
bfs + greedy as someone mentioned earlier. this is actually a*.

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

C*y2012-08-23 07:08

24 楼

建一个图（或者想象有这么一个图）
起点是原来的单词
终点是目标单词
其他顶点是联通的条件是距离为一
可以用经典的greedy算法找最短路径
也可以用DP做

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

k*p2012-08-23 07:08

25 楼

电面就这么难，太变态了，好可怕啊

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

: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢

l*a2012-08-23 07:08

26 楼

这是一个很经典的问题
但是有人在面试中见到过吗？问这个也太没意思了吧

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

: 建一个图（或者想象有这么一个图）
: 起点是原来的单词
: 终点是目标单词
: 其他顶点是联通的条件是距离为一
: 可以用经典的greedy算法找最短路径
: 也可以用DP做

s*n2012-08-23 07:08

27 楼

精辟

个min value (不需要额外内存)

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

: 第一个是DP
: S[n]=S[n-1]+S[n-2]，就是Fibbonaci
: 第二个是单独弄一个stack,里面放上有史以来的min(需要extra storage)
: 或者改变stack里面每一个node的结构，让这个node除了放原来的data以外，还存一个min value (不需要额外内存)
: 第三题是做一个BFS
: 第二题和第三题的solution, careercup书上都有