H****S
发帖数: 1359 | 1 不能改成tail recursion的话，可以上trampoline。 |
|
w*******i
发帖数: 186 | 2 我觉得递归还是很有用的，而且有时还会有一些很奇妙的用法。比如有一堆callback，
其中有sync和async的，不同callback之间还有dependency，为了保证async的callback
也能遵守dependency，目前发现利用recursion是最简单的方法。 |
|
h***o
发帖数: 539 | 3 老板会分特的。
我还是用f77吧，用比较ugly的方法bypass这个recursion的问题 |
|
G*O
发帖数: 706 | 4 【 以下文字转载自 CS 讨论区 】
发信人: GTO (正在申请Working-In-China Club), 信区: CS
标 题: 问一下primitive recursive function等于哪些其它的complexity class？
发信站: BBS 未名空间站 (Sun Dec 17 13:53:01 2006), 转信
应该是包含EXP的对吧。
但是有人问这个问题，我找不到答案。
是不是说没有其他的class与之相等？ |
|
c***z
发帖数: 6348 | 5 O(n).
Additionally, it takes a lot of time and space (stack space) to recursively
call the function.
A better way is to remember the previous F(n)'s. |
|
n******0
发帖数: 298 | 6 Recursive partitioning in the health sciences by Heping Zhang. |
|
y*****w
发帖数: 1350 | 7 就是如何写iterations。比如我需要得到如下function的运算结果：
f(x) = p*f(x-1), x>=1, p=constant
到最下面时比如x=1, 则f()有固定的distribution或者直接f(0)=constant。
如果我直接在R中输入如上f(x) = p*f(x-1)运行，R会告诉我“could not find
function f”。
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
～～～～～～～
上面是一个parameter的情况。如果我有两个parameters，比如下面这个recursive
function，应该如何表达呢？是不是必须用到matrix？
f(s,d) = p*f(s-1,d) + q*f(s,d-1), s>=0, d>=0, p=constant, q=constant, f(0,0)
=constant |
|
d*****r
发帖数: 39446 | 8 【此篇文章是由自动发信系统所张贴】
recursive 已经成为本俱乐部的正式成员, 特此通知. |
|
d*****r
发帖数: 39446 | 9 【此篇文章是由自动发信系统所张贴】
recursive 已经成为本俱乐部的正式成员, 特此通知. |
|
d*****r
发帖数: 39446 | 10 【此篇文章是由自动发信系统所张贴】
recursive 申请加入本俱乐部的请求已经通过审批, 成为本俱乐部的正式成员, 特此通知. |
|
t******n
发帖数: 2939 | 11 ☆─────────────────────────────────────☆
l63 (l63) 于 (Thu May 23 00:34:22 2013, 美东) 提到:
假设素数只有有限个, 记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
这与素数只有p_1,p_2,...,p_k矛盾.
故假设不成立.
所以素数有无穷多个.
☆─────────────────────────────────────☆
l63 (l63) 于 (Thu May 23 00:37:03 2013, 美东) 提到:
在承认素数的这个等价定义 (即 a是素数 <=> a是大于1的自然数, 且a不被任何小于a
的素数整除) 的前提下, 居然有人会认为这个证明是错的, 或者是不完备的.
我实在不能理解.
求问一下大家, 是不是有的人的脑子天生有缺陷, 根本怎么教都不会明白... 阅读全帖 |
|
b*******l
发帖数: 590 | 12 对。但是recursion本身确实要用很多的memory。这个是我刚在网上看到的：
ADVANTAGES AND DISADVANTAGES OF RECURSION
Advantages
Although at most of the times a problem can be solved without recursion, but
in some situations in programming, it is a must to use recursion. For
example, a program to display a list of all files of the system cannot be
solved without recursion.
The recursion is very flexible in data structure like stacks, queues, linked
list and quick sort.
Using recursion, the length of the program can be reduced.
D... 阅读全帖 |
|
p*****2
发帖数: 21240 | 13
Id Question Difficulty Freqency Data Structures Algorithms
1 Two Sum 2 5
array
set
sort
two pointers
2 Add Two Numbers 3 4
linked list
two pointers
math
3 Longest Substring Without Repeating Characters 3 2
string
hashtable
two pointers
4 Median of Two Sorted Arrays 5 3
array
binary search
5 Longest Palindromic Substring 4 2
string
6 ZigZag Conversion 3 1
string
7 Reverse Integer 2 3
math
8 ... 阅读全帖 |
|
p*****2
发帖数: 21240 | 14 不断看到有新人学习DP，想谈谈我的感受。
我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
没有用cache。
开始学习DP是在careercup 150那本书上。下面是一些感受。
1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出
F(n)来。当然这也是最难的。发现很多难题还是很难想到这个公式的，可能就得多练习
了，培养思路。这个定义跟careercup上的不一样的地方主要是思考的方式不同，一个
是推公式，一个是找recursion的办法。而... 阅读全帖 |
|
p*****2
发帖数: 21240 | 15 不断看到有新人学习DP，想谈谈我的感受。
我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
没有用cache。
开始学习DP是在careercup 150那本书上。下面是一些感受。
1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出
F(n)来。当然这也是最难的。发现很多难题还是很难想到这个公式的，可能就得多练习
了，培养思路。这个定义跟careercup上的不一样的地方主要是思考的方式不同，一个
是推公式，一个是找recursion的办法。而... 阅读全帖 |
|
p*****2
发帖数: 21240 | 16 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 17 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
S**I
发帖数: 15689 | 18 ☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 10:56:49 2011, 美东) 提到:
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the out... 阅读全帖 |
|
t******l
发帖数: 10908 | 19 ：那么好，(a+b)(a+b)你就把第一个(a+b)看成一个unit,看成大A
：那么 A(a+b)， 你能不能展开？
：展成 Aa + Ab之后，再把A换成（a+b)再运用一次分配律就好了
：
：这个过程，就是理解如何应用分配律展开(a+b)(a+b)的过程
：理解之后，自然可以记忆相应的口诀，以后直接用，不必次次理解式展开了
你说的这个，就是我前面说的 "recursive perform distributive"。（我就是用一生
僻词避免码这么多字。）
但这个也是我怀疑人生的一部分，我目前认为这个大部分 6 年级普通娃只能教懂（
understanding），无法真正运用 recursive operation 的概念解题（applying）。。
。例子就是大学本科的算法初级课，多少人栽在 recursive 算法里面跑不出来。。。
我另一个观点是 recursive 是类似 mathematical induction（就好比数学归纳法），
而 mathematical induction 的概念超过 6 年级普通娃的思维。
当然，我们当年初中肯定能教会，但是有可能更多的是随... 阅读全帖 |
|
t*******r
发帖数: 22634 | 20 其实我觉得你的证明思路更多倾向于 recursive-based。另外你首贴写的不太
完整，然后我看中文数学比较烂，一开始时误解了你的 recursive 思路。
欧几里德的原版不提（反正鸟语也看不懂），我看到的两个翻译（上面贴出来的），
其实一个更接近中学数学思路，另一个更接近现代集合论思路。我个人更喜欢现代
集合论思路。
如果是结果相差不大的证明思路，让我在 集合论-based vs recursive-based
里面选，我一般更倾向于选 集合论-based。主要是 recursive-based 比较
tricky，不小心会搞成循环论证。。。不过这个纯属个人 preference。
当然，码 code 另说，recursive function 写起来比 stack-based 要快，
stack/queue-based 主要是为了速度，或者有些东西 recursive 反而自找
麻烦，比如 BFS 。。。 |
|
O*******d
发帖数: 20343 | 21 说一下我怎么做的antialiase。 先把图形计算好，比最后的图像多出宽三列高三行。
图形是一个浮点数的点阵。 两个相邻的点之间的距离是一个单位。 然后用三次方程插
值。每个插值要用图形中4X4的值来计算。 在四个点组成的方格中均匀插入5X5=25个点
（单核机）或7X7=49个点（多核机），给每个插值赋予颜色，最后把一个方格中所有的
颜色平均，就是一个像素的颜色。
由于一组插值用的是同一套三次方程系数，所以写了一个class来做。 其实是一个
template。 做插值时，有两个套着的循环，分别在X方向移动和Y方向移动。 内循环是
在Y方向从上往下移动，这样每次移动一步，只需要计算最后一列的三次方程系数。下
边是我写的Cubic Interpolator. 是一个recursive template。For bicubic
interpolation, N = 2. 所有的重复计算都尽可能的避免了。 这个templete的计算
速度，在N==2时，是单独bicubic interpolation的速度的三倍。
template
class Cu... 阅读全帖 |
|
s*******y
发帖数: 105 | 22 不是很理解这里的recursion.
举例来说：
With input "hat",
1. value of i =0, out[0] = 'h', used[0]=1, recursive call (I assume i=0,
recursLev =0, is pushed on to the stack)
2. i =0 continue, i=1 out[1]='a', used[1] = 1, recursive call (i =1,
recurseLev =1 on stack)
3. i=0,1 continue, i=1 out[2] = 't', used[2] = 1, recursive call(i=2,
recurseLev=2 on stack)
4. Line 31 is executed, "hat" is printed out and it returns.
It is from here that I am confused. This is what I think happens:
5. Return to line 45, pop i fr... 阅读全帖 |
|
S**I
发帖数: 15689 | 23 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 24 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
y***n
发帖数: 6764 | 25 recursive的那个是你大大的不对，和你什么没睡好都没关系的。（1）照你这么说，
recursion的算法都不能用了？显然不对，recursion有recursion的overhead, 如果有
人问你recursion看似简单有没有缺点啦？那你那么回答是可以的。（2）和面试官
argue有什么好处？要humble知不知道？况且这上面你没道理。 |
|
g********E
发帖数: 178 | 26 EBAY的，带着打酱油的心情吐槽一下其中一个面试官--印度美眉。她长的挺漂亮的，而
且没口音，令我对她好感倍生。上来她先跟我闲聊了一会，然后开始问编程题，这就是
悲剧的开始了。
她问了一个经典的fibonacci数列问题，要求打印出前n个fibonacci数。我一想这个简
单呀，但是美眉要求用recursive写。我吭哧吭哧写了几行，发现自己水平有限， get
stuck了，尴尬了一会就说：这个用recursive不太好写，其实用iterative更efficient
,也比较好处理打印功能。美眉就让我写iterative，我喜滋滋地写了，写完美眉也认可
了，可是接着说：现在继续来写这个recursive吧。。。我就苦着脸又尴尬了一会儿，
美眉按耐不住了说其实就是你刚才写的修改一下就行了，于是我按照提示写出code,贴
在这里给大家赏鉴一下：
int foo(int n){
if(n == 0) return 0;
if(n == 1 || n == 2) {
cout<<1<<" ";
return 1;
}
int... 阅读全帖 |
|
D**0
发帖数: 2048 | 27 ☆─────────────────────────────────────☆
stevenshuang (stevenshuang) 于 提到:
这次来的夏利营的35名孩子一切都很好，一些孩子有擦伤和拉伤。
今天下午夏利营的孩子会到中国大使馆办理一些手续，之后我们会带孩子买一些生活用
品，一些孩子需要配眼镜，我家只有5人坐的小车，希望能提供车和driver的朋友跟我
们联系一下带着孩子配眼镜。
希望下午有空有时间有爱心的湾区朋友和我联系，在这里先谢谢大家了。
我的联系方式 650-257-0907
希望版主能帮忙置顶一下 谢谢
☆─────────────────────────────────────☆
ronanzj (肉男) 于 (Sun Jul 7 16:08:18 2013, 美东) 提到:
教育部不是说70名中国学生吗？
☆─────────────────────────────────────☆
pooh (小Pooh) 于 (Sun Jul 7 16:11:27 2013, 美东) 提到:
“夏利营”的组织者都干神马去袅？ 不能... 阅读全帖 |
|
P*******e
发帖数: 39399 | 28 ☆─────────────────────────────────────☆
BigBlue (#15) 于 (Fri Oct 25 04:19:02 2013, 美东) 提到:
(看到前面中雪同学为答辩辗转难眠 -- good luck again -- 和大家的回贴有感)
俩题 仨答案 有包子 别放狗 每题60秒钟为限
这是十几年前的事了 所以题目可能已经在别处出现过
或者 本版人杰地灵 波大茎深
可能就是现在当场解 你也觉得是很简单 甚至很无趣
如果是这样 就请看官跳过去罢
我写出来 只是想自己朝花夕拾一把 和给大家在周五有个愉快的分心
话说我们那个Pizza Hut Delivery的程序
一开始的第一关 是preliminary的笔试 考大学本科高年级的专业知识 比较广泛
到最后的proposal/defense 又是钻牛角尖+王婆卖瓜了 也没甚意思
但是中间的一关qualify exam的口试 就比较有弹性
当时委员长给我的信 说明除了信里指定的本领域的一个题目以外
委员会有权力问其他一些问题来考验衡量学生的思考/逻辑/... 阅读全帖 |
|
t*******r
发帖数: 22634 | 29 我后面看到那个素数的 recursive definition。
如果用素数的 recursive definition，你的比欧几里德的简单，因为
你可以直接上 recursive definition。
但是素数的 非recursive definition 更流行，如果是 非recursive
definition，应该是欧几里德的更简单明了。 |
|
t*******r
发帖数: 22634 | 30 recursive definition 和 non-recursive definition 都必须遵循
the order of definition （源于数学哲学的 causal-effect 假设）。
recursive definition 的 tricky 的部分，用现代数学语言来说，如果
被 define 的 item 是一个 set，需要存在一个 recursive context，
在该 recursive context 的时候，定义符右边的所用到的 sub-set 已经
被完整定义，从而可以用来定义定义符左边 sub-set。
这个不是时序，而是 the order of definition。
|
|
d********f
发帖数: 43471 | 31 【 以下文字转载自 JobHunting 讨论区 】
发信人: greentreeE (冬天的绿树), 信区: JobHunting
标 题: 吐槽下今天的面试(update并请教面试准备)
发信站: BBS 未名空间站 (Wed Jul 10 04:04:50 2013, 美东)
update一下，今天收到通知喊我去第二轮onsite，真是很纠结，本来这次面试都差点不
想去了，觉得自己水平太差，结果去了也果然是被打击，第一个人就问了一堆这个会不
会那个会不会，我就除了c++/data structure/oo programming其他都是不会，后来
manager又继续问，说虽然算法数据结构这些挺有用的，但是我们实际工作中考虑很多
大数据啊系统设计啊服务器之类的问题，你怎么整？而且我们都用java你也不咋会。还
问我知不知道compiler怎么work的，我当然不知道，才第一次听说lexical analysis这
个词。。
其实受点打击也无所谓，本来我已经放弃直接找工作，打算去念个CS学位了，只是正好
有个朋友说可以推荐，就抱着打酱油的心情去试一下。电话也面的不好，onsite... 阅读全帖 |
|
m*********y
发帖数: 389 | 32 Here are some questions I copied from online.. Obviously LouZhu is a lazy
ass... these questions are everywhere... :-)
SQL Interview questions
Below is a list of questions in this blog post so you can test your
knowledge without saying answers. If you would like to see questions and
answers please scrool down.
Question: What type of joins have you used?
Question: How can you combine two tables/views together? For instance one
table contains 100 rows and the other one contains 200 rows, have exac... 阅读全帖 |
|
w*r
发帖数: 2421 | 33 这个code不是MYSQL,在Teradata上测试通过，基本的语法应该和ANSI接近
解释一下解题的思路
目标：使用ID做为group by用min/max处理begin/end
第一步：要把不同行的begin/end放到同一行，这样便于比较start/end. Beijing和其
他的同学提到lag,不幸的是我这里木的用，所以用row_number()给数据按照startdate
排序做left join seq = seq+1
code:
(
SELECT T.*,
ROW_NUMBER() OVER (PARTITION BY ID ORDER BY STARTDATE) AS SEQ
FROM T
) A
LEFT OUTER JOIN
(
SELECT T.*,
ROW_NUMBER() OVER (PARTITION BY ID ORDER BY STARTDATE) AS SEQ
FROM T
) B
ON
A.ID = B.ID AND
B.SEQ = A.SEQ+1
第二步：把能够merge的行标上。注意：第一步的结果中最后一行的右边是null,所以这
里有一个la... 阅读全帖 |
|
k***g
发帖数: 75 | 34 第二个我觉得recursive没啥问题，recursive和trie也没啥矛盾，recursive的过程就
是建trie的过程，如果发现字典里没有，也就结束了。recursive相当于是DFS，也可以
用BFS。 |
|
I**********s
发帖数: 441 | 35 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
w********9
发帖数: 8613 | 36
必要。有的数可能是有重复的。排序结果可以用来避免重复计算和重复解。
还有，每次recursion是最大的数被taken out。对不少情况，这样做会让Q reduce得快
、真正要做的recursion会少一些。
改进
不是那样的。余下数的总和比S小时，recursion就没有必要做下去了，相应的那些余数
的组合也就免了（当然可能在另外的recursion里没有）。（楼主在san Francisco的版
面上把题目做了个小改动,使得更多的组合不需要做。)
这个问题本身最坏的complexity就是O(2^N)。能做的只是减小2^N前的系数。 |
|
t*****j
发帖数: 1105 | 37 这个是可行的，但是如果要打印出一棵树的所有层次来，不是要call很多次吗？对每一
个height都要call一次？那得recursive很多次啊。
第一层 recursive 0次 第二层recursive 1次， 第n层recursive n次..
哪里有queue的好啊，那个才只是一次遍历下所有节点。
heightDesired) |
|
d****j
发帖数: 293 | 38 Combination: 如果这样的话，有点大材小用了吧，一个是2^n的复杂度，另外一个是多
项式复杂度，只修改打印方程会浪费很多时间
我的想法，另外用一个数组value作参数存取被选中的数字，还是用recursive的方法，
用一个index来记录当前fill多少个数字了。
Base：如果达到了limit，直接打印value数组
Recursive: 当前需要fill的index可以选那些数字？用一个for loop实现，赋值给
value[index]一个可选的数字，然后call itself 来fill下一个位置。 由于是
combination，需要注意不能重复选以前的数字了，下一个位置永远是从之前选中的数
的后面数字里面选。所以，还需要一个参数来标注可选数字的起始点(原始数组中）。
这样的话，大概需要5个参数，2个数组，2个index，和选出数的limit。
我刚刚写了一下，这个思路code还是没问题的。注意边界条件和候选取值范围。
衍生的问题就是：Permutation
也是用类似的idea,但是比combination更简单，和powerset差不多,增加一个for lo... 阅读全帖 |
|
d****j
发帖数: 293 | 39 Combination: 如果这样的话，有点大材小用了吧，一个是2^n的复杂度，另外一个是多
项式复杂度，只修改打印方程会浪费很多时间
我的想法，另外用一个数组value作参数存取被选中的数字，还是用recursive的方法，
用一个index来记录当前fill多少个数字了。
Base：如果达到了limit，直接打印value数组
Recursive: 当前需要fill的index可以选那些数字？用一个for loop实现，赋值给
value[index]一个可选的数字，然后call itself 来fill下一个位置。 由于是
combination，需要注意不能重复选以前的数字了，下一个位置永远是从之前选中的数
的后面数字里面选。所以，还需要一个参数来标注可选数字的起始点(原始数组中）。
这样的话，大概需要5个参数，2个数组，2个index，和选出数的limit。
我刚刚写了一下，这个思路code还是没问题的。注意边界条件和候选取值范围。
衍生的问题就是：Permutation
也是用类似的idea,但是比combination更简单，和powerset差不多,增加一个for lo... 阅读全帖 |
|
l*****g
发帖数: 685 | 40 KMP是用于找出所有matches in one traveral of the string
譬如，从 abcdabcaabcbc 里找abc, 用 KMP 就可以找出 3 matches
LZ的问题是：找出match, 删除，再在结果里找match, 再删除，直到结果里无match为止
过程如下：
input: abcdabcaabcbc
find matches: [abc]d[abc]a[abc]bc
delete matches: dabc
find matches again: d[abc]
delete matches: d
no more match
output: d
这儿recursively地做了两次find-->delete；如果把KMP用于每一次recursion, 单个
recursion的复杂度是 O(n), 但多个recursion的总的复杂度还是会累加 |
|
G******i
发帖数: 5226 | 41 ☆─────────────────────────────────────☆
currant (葡萄干) 于 駡 提到:
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview...
如果以上任何概念不能熟练给出详细解答,请在往下面看之后抓紧复习1.数据结构(这个如果一
个没看懂可以按后退关窗口了)2.算法3.公司背景4.面向对象编程5.on... 阅读全帖 |
|
w***o
发帖数: 109 | 42 大牛们很忙，让我来给你解释解释。我两水平差不多，我的思路对你可能容易理解一点
。这题主要是要逼你写DP，而且是Buttomup的。我没有二爷那么牛，可以直接写
buttomup的DP，我是一步一步来的。不好意思C＋＋早忘了，java的，你凑合看吧。
先来recursive without DP。
public int numDistinct(String S, String T) {
if(T.length() == 0)
return 1;
if(S.length() < T.length())
return 0;
int ret = 0;
if(S.charAt(0) == T.charAt(0))
ret += numDistinct(S.substring(1), T.substring(1));
ret += numDistinct(S.substring(1), T);... 阅读全帖 |
|
p*****2
发帖数: 21240 | 43 来自主题: JobHunting版 - 关于尾递归
尾递归
def C(m:Int, n:Int):Int={
recursion(m, 0, None)(n)
}
def recursion(m:Int, i:Int, arr:Option[Array[Int]]):Array[Int]= i match{
case _ if i==m+1 => arr.get
case 0 => recursion(m, 1, Option(Array[Int](0)))
case _ => val ret=process(i,arr.get); recursion(m, i+1, Option(ret))
}
def process(i:Int, arr:Array[Int]):Array[Int]={
val ar=new Array[Int](i+1)
ar(0)=1
ar(i)=1
1 until i foreach(j=>ar(j)=arr... 阅读全帖 |
|
h*******0
发帖数: 270 | 44 昨天面试了bb。整个面试过程就不是很顺利磕磕碰碰的。 一路纠结，总算是面完了，
不过打算move on了。现在总结下，发一些经验教训供大家参考。
从1月9号给我发了onsite邀请后，中间历时将近一个月才把onsite搞完。 最终的
onsite还是2天前周六晚上定下来的。。 估计面她家的人太多了，recruiter都忙不过
来了。。。
一个重要的教训是，如果大家离面试地点很近，飞机只需要1个小时的话。 千万不要怕
给公司留下要求多的坏印象，就不要求提前一天去面试的城市。 我是从boston飞过去
，recruiter说你飞过来少于2个小时，不需要提前一天来住酒店。 我为了留个要求不
多的好印象，便从了。。 然后这货定了个早上7点的飞机给我。 面试前一天由于紧张
，1点多才睡着。 早上5点多喝了杯咖啡便匆匆忙忙往机场赶。 到了bloomberg公司后
大约上午9点多。 但是前台不让我上楼，因为我的面试是12点半开始。 由于肚子有些
饿，我便出去绕着BB家的大楼转了一圈。 结果发现除了一家星巴克，都是商场。。。
没办法，喝了杯咖啡吃了一小块蛋糕便继续回来等。 12点的时候，终于同意我上楼... 阅读全帖 |
|
h*******0
发帖数: 270 | 45 赞同你的观点。 但是当时我感觉不到他们想引导我写出recursive的方法。 因为我当
时想尝试写，它们不让。 就让我说说recursive和我的方法比如何。 你说我怎么答。
。 我只能说recursive费内存阿。 然后他俩才表现出不同意的。 那这时候我也没办法
了，不能人家不同意了，你也见风使舵吧。。 我在网上看到BB家有时候会故意不停的
反问你答案，来确认你是真的会。 然后当时就不知道他们是要引导我，还是要考验我
。 你说你引导我吧，就让我写下recursive的方法。 但是他们不让写啊。。。 只让我
分析我的算法复杂度。。。 |
|
i********m
发帖数: 332 | 46 从1月中旬收到onsite的邀请，直到今天才最终onsite，惨败而归，被蹂躏的体无完肤
，中间我也曾经想要反抗，但是完全不给我机会，最终我只能光荣的牺牲！希望我的牺
牲对以后去BB onsite的朋友能有帮助。
首先我想说的是，去BB onsite真心要好好复习复习C++的各种概念，像我只会Java，C+
+基本不懂的人，这次去完全就是飞蛾扑火。他家确实有钱，那栋楼估计都值不少钱，
很漂亮！ 早上10点45进去的，11点的面试。上6楼，进去后一大片的休息区，各种吃的
，喝的，不管时间，先喝一杯橙汁。玩了坐到沙发上等HR来引领我去面试办公室。途中
HR说，我们公司怎么样，漂亮吧？ 我说 very nice! 她又问我，你是第一次来纽约吧
？我心里想，老子这都是第5次来了，明显看不起我们这些农村过来的！我没有反驳她
，回了句couple of times。 然后她就不说话了，带我上楼放行李，然后就去面试的办
公室了。 里面此时已经坐了2个Engineer了。打招呼，问好，然后面试正式开始 ：
刚开始让我做了下自我介绍，然后问了问什么BB？这些都好说，随便扯！ 然后就开始
问我的proje... 阅读全帖 |
|
i********m
发帖数: 332 | 47 从1月中旬收到onsite的邀请，直到今天才最终onsite，惨败而归，被蹂躏的体无完肤
，中间我也曾经想要反抗，但是完全不给我机会，最终我只能光荣的牺牲！希望我的牺
牲对以后去BB onsite的朋友能有帮助。
首先我想说的是，去BB onsite真心要好好复习复习C++的各种概念，像我只会Java，C+
+基本不懂的人，这次去完全就是飞蛾扑火。他家确实有钱，那栋楼估计都值不少钱，
很漂亮！ 早上10点45进去的，11点的面试。上6楼，进去后一大片的休息区，各种吃的
，喝的，不管时间，先喝一杯橙汁。玩了坐到沙发上等HR来引领我去面试办公室。途中
HR说，我们公司怎么样，漂亮吧？ 我说 very nice! 她又问我，你是第一次来纽约吧
？我心里想，老子这都是第5次来了，明显看不起我们这些农村过来的！我没有反驳她
，回了句couple of times。 然后她就不说话了，带我上楼放行李，然后就去面试的办
公室了。 里面此时已经坐了2个Engineer了。打招呼，问好，然后面试正式开始 ：
刚开始让我做了下自我介绍，然后问了问什么BB？这些都好说，随便扯！ 然后就开始
问我的proje... 阅读全帖 |
|
b*******e
发帖数: 123 | 48 感觉dp和recursion都是解决recursive equation 的。如果你方便把recursive call
的输入变成有限n-维区间上的整数，就可以建dp table。不方便就用recursion +
memoization。 |
|
f******h
发帖数: 45 | 49 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
y***n
发帖数: 1594 | 50 这个Recursive还算规矩的。建议每天早上起来看3边。
还有Recursion的关键是吧Recursion的部分看作是你的小伙伴的工作，相信他，不要想
这他到底干了什么。这个题其实很经典。Standford的网上说这是"one of the neatest
recursive pointer problems ever devised" |
|
