p*e
发帖数: 6785 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: moonlake711 (mimiinus), 信区: JobHunting
标 题: 问一道同学遇到的微软面试题：怎么向一个三岁小孩解释Recrusion?
发信站: BBS 未名空间站 (Mon Oct 20 17:16:53 2014, 美东)
这个题我想了很久，网上也找不到答案
遇到这样的题目应该怎么回答好呢 |
|
C***n
发帖数: 452 | 2 so that is it, the key is to not use if and loop, not in complexity, I think
by the way, could you post a logN algirthm in a recrusive function without
if? |
|
d****j
发帖数: 293 | 3 第一轮第二题
电面之前刚好练过这道题，但是用ArrayList 和ArrayList of ArrayList 实现的，用
recrusive 的方法，返回前k个元素的幂集合之后，再复制一边添加当前k+1元素入每个
子集合。最终返回幂集之后在打印，效率不好。但是当时想都没想就写上去了。
面完了就想起，完全可以用一个等长的int数组来标识是否取当前元素，代码如下。（
Careercup有这道题，使用一个int数i的每一位来做标识，把i从0递增到2^32-1就能打
印出所有的subsets，但最多只能实现到32个数的数组）
public static void printPowerSet(int[] set) {
int[] index = new int[set.length];
int endidx = 0;
printPowerSetSolver(set, index, endidx);
}
public static void printPowerSetSolver(int[] set, int[] index, int endidx) {
if (... 阅读全帖 |
|
d****j
发帖数: 293 | 4 第一轮第二题
电面之前刚好练过这道题，但是用ArrayList 和ArrayList of ArrayList 实现的，用
recrusive 的方法，返回前k个元素的幂集合之后，再复制一边添加当前k+1元素入每个
子集合。最终返回幂集之后在打印，效率不好。但是当时想都没想就写上去了。
面完了就想起，完全可以用一个等长的int数组来标识是否取当前元素，代码如下。（
Careercup有这道题，使用一个int数i的每一位来做标识，把i从0递增到2^32-1就能打
印出所有的subsets，但最多只能实现到32个数的数组）
public static void printPowerSet(int[] set) {
int[] index = new int[set.length];
int endidx = 0;
printPowerSetSolver(set, index, endidx);
}
public static void printPowerSetSolver(int[] set, int[] index, int endidx) {
if (... 阅读全帖 |
|
B*********e
发帖数: 9 | 5 真屈辱，心情恢复平静中。
写出来大家面他家的时候也做好思想准备吧
L公司刚上市，现在狂招人中,不知道是不是大家都cash out了。
本来要面9个人，后来只见了3个。就被人家说“I do not think we should carry on, in respectful of your time and our time”
写写吧，攒rp。大家轻拍，知道自己业务知识不强，回家读书过后再来过。
第一场本来要见host manager，后来跑来两个engineer说调换一下顺序。没有寒暄，直接问，我们问你technical的问题。
第一个给你一个FilterIterator Class（predicate p, iterator i), 写
bool hasnext() 还有bool next()
搞了半天什么是predicate，还有那个iterator i到底是哪个list上头的。但是后来这个在对方提示下写的差不多了。
第二个说给你一个很长的string list，让你分行打印。然后告诉你一行只能写L（比如
25）个字符，而且首位和末尾不能是空格，空格只能在中间，两个词中间可以空两... 阅读全帖 |
|
C***U
发帖数: 2406 | 6 假设我有一个正整数n，我要把他写成一些正整数的和。是组合问题，也就是说数字的
顺序不考虑。
有什么好的办法没有
我写了一个recrusive的，请大牛们指教一下
int count = 0;
//构造以max为最大数的 number的partition
void partitionWithMax(int number, int max) {
if(!number) {
count++;
return;
}
else {
int newMax = number > max ? max : number;
for(int i = newMax; i > 0; i--) {
partitionWithMax(number - i, i);
}
}
}
//让max从1到number都走一边
void partition(int number) {
for(int i = number; i > 0; i--) {
partitionW... 阅读全帖 |
|
|
o********n
发帖数: 193 | 8 楼上大牛们，我跑了下justtry的code，都对。我的那个明显拙劣，也对。
下面该整个recrusive版本的了。 |
|
d**e
发帖数: 6098 | 9 来自主题: JobHunting版 - 关于尾递归 我理解得比较肤浅，觉得tail recrusion应该是省空间。
不过你这个bfs是tail recursion，我错了。。 |
|
n*******w
发帖数: 687 | 10 recrusion试过，5个字母的单词都算不出来。假设字典50w单词，长度为5的单词只有几
千个。
这题我这么算的
1 先从字典里边选出长度为要找的单词的所有单词
2 建立dict，key是单词本身，value是从start到这个单词的路径长度，初始值为
integer的最大值，假设是MAX。
3 dict[start] = 0； dict[end] = MAX
4 对于dict里边每一个单词cur_word，
如果dict[cur_word] != MAX， 改变cur_word的任一个字符得到next_word，看next_
word是不是在dict里边，如果存在则更新dict[next_word] =
min( dict[next_word], 1+ dict[cur_word] )
5 如果step 4没有任何改变，退出。输出dict[end]
实际上DP，也可以看做是，建图并且Dijkstra一起做。
python写的话，不超过20行。运行时间在半分钟之内。 |
|
|
m*********1
发帖数: 204 | 12 这个题我想了很久，网上也找不到答案
遇到这样的题目应该怎么回答好呢 |
|
|
w****e
发帖数: 3827 | 14 西瓜 哈密瓜 苹果 草莓 葡萄
如果想吃西瓜的话 得把其它水果从小到大挨个都吃了。多么开心的例子 |
|
|
k*******q
发帖数: 5493 | 16 随便解释一句，然后让他PLAY OUTSIDE就结束了
不过这个RECRUSIO究竟是什么东西？ |
|
g*****g
发帖数: 34805 | 17 Youtube上有儿歌串烧，包括以下两句歌词。爸爸的爸爸是爷爷，妈妈的妈妈是外婆。
天天给小朋友放即可。 |
|
M*******a
发帖数: 1633 | 18 这个叫recursion
三岁小孩让他想象一条蛇咬住自己的尾巴然后慢慢吞进去是什么个样子 |
|
|
|
|
|
b***e
发帖数: 1419 | 23 我给你讲个故事：从前有座山，山上有座庙，庙里有个老和尚正在讲故事。讲的是什么
？"我给你讲个故事：从前有座山…" |
|
|
m*********1
发帖数: 204 | 25 这个题我想了很久，网上也找不到答案
遇到这样的题目应该怎么回答好呢 |
|
|
w****e
发帖数: 3827 | 27 西瓜 哈密瓜 苹果 草莓 葡萄
如果想吃西瓜的话 得把其它水果从小到大挨个都吃了。多么开心的例子 |
|
|
k*******q
发帖数: 5493 | 29 随便解释一句，然后让他PLAY OUTSIDE就结束了
不过这个RECRUSIO究竟是什么东西？ |
|
g*****g
发帖数: 34805 | 30 Youtube上有儿歌串烧，包括以下两句歌词。爸爸的爸爸是爷爷，妈妈的妈妈是外婆。
天天给小朋友放即可。 |
|
M*******a
发帖数: 1633 | 31 这个叫recursion
三岁小孩让他想象一条蛇咬住自己的尾巴然后慢慢吞进去是什么个样子 |
|
|
|
|
|
b***e
发帖数: 1419 | 36 我给你讲个故事：从前有座山，山上有座庙，庙里有个老和尚正在讲故事。讲的是什么
？"我给你讲个故事：从前有座山…" |
|
|
|
|
|
|
n******6
发帖数: 1829 | 42 【 以下文字转载自 JobHunting 讨论区 】
发信人: BrightSmile (BrightSmile), 信区: JobHunting
标 题: 去某刚上市公司面试被赶出来了。
发信站: BBS 未名空间站 (Thu Aug 11 17:07:23 2011, 美东)
真屈辱，心情恢复平静中。
写出来大家面他家的时候也做好思想准备吧
L公司刚上市，现在狂招人中,不知道是不是大家都cash out了。
本来要面9个人，后来只见了3个。就被人家说“I do not think we should carry on, in respectful of your time and our time”
写写吧，攒rp。大家轻拍，知道自己业务知识不强，回家读书过后再来过。
第一场本来要见host manager，后来跑来两个engineer说调换一下顺序。没有寒暄，直接问，我们问你technical的问题。
第一个给你一个FilterIterator Class（predicate p, iterator i), 写
bool hasnext() 还有bool next()
搞了半天... 阅读全帖 |
|
|
w*********a
发帖数: 9279 | 44 This is looping, not recursion |
|
|
w*********a
发帖数: 9279 | 46 recursion has exit conditions. |
|
n***d
发帖数: 8857 | 47 这么说Loop也要有退出条件，但死循环就不叫循环了吗？ |
|
w*********a
发帖数: 9279 | 48 Infinite looping is valid, but infinite recursion overflows the stack, which
is not allowed. |
|
w*********a
发帖数: 9279 | 49 This is my answer to the interview question.
I will put a candy inside a Russian nesting doll. Asking the kid to have the
candy and return the doll to me in the original shape. |
|
n***d
发帖数: 8857 | 50 infinite recursion 也是recursion，就当有bug吧
which |
|
