j*p
发帖数: 115 | 1 当时 我吭哧半天 也想到了那个两两分组的方法 后来也说可以用递归 连递归公式都说
了 f(n)=n/2 + f(n/2) 然后 不知道怎么想的 一直觉得这个得到f(n)=3n/2 :(
刚查了一下 递归公式 f(n)=n/2 + f(n/2) + 1 所以应该是 f(n)= n + log(n) - 2.
这个方法主要问题是要用n/2次swap。那个印度人后来说要minimize swap的次数。我就
很郁闷 因为已经超时了 后来他告我答案了：
不是把数分成n/2组每组两个，要把数分成2组每组n/2个。每组选最大的。比较之后，
较大的就是最大的那个数。较小的和较大的数所在的组里的其他数组成一组，再选最大
的，就得到第二大数了。一共大概3n/2次 用到了一两个额外的内存。
简单吧!:) |
|
|
S**I
发帖数: 15689 | 3 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
f********8
发帖数: 84 | 4 人好多啊。
第一题答案是用2个for loop嵌套。遍历NXN的矩阵
然后对每个节点一个递归 上下左右四个递归列阵，一旦到了四个边界就返回。
然后API里面有2个函数1是判定是不是单词2是判定是不是词头。比如appl是词头zzz不
是词头。这样就不用走完每一个点了（哦耶答上来了。）这样就是2个function一个是
forloop双雄另外一个就是递归function了。
郁闷的是在于由于没有限制你可以直接设一个变量记录每次的起始点这样就不会回到起
始点了。
树的问题是类似于linklist，就是某一个节点link错了链接到自己的某个祖先了这样查
啊查的就是死循环了。
多谢大家了！学了很多。 |
|
h****n
发帖数: 1093 | 5 你的递归结束条件不明确。。
比如这样一个矩阵
a b c d
e f g h
i j k l
m n o p
比如现在你从e开始递归，你怎么避免e->f->g->k->j->f->g->k ....这样的无法返回的
递归呢？题目之规定不能返回到起点e，没规定不能返回之间搜索到的点，如果不能返
回之间搜索到的点，那就是一个DFS而已，标记下中间的visited过的点即可 |
|
h****n
发帖数: 1093 | 6 我的递归和非递归解法，贴在下面 OJ通过 ，还有每K个reverse那个，不过那个只有递
归版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
/*
//递归做法很简单，但是要切记前面几行的顺序，别放错了
ListNode* cur = head;
if(cur==NULL) return NULL;
ListNode* n... 阅读全帖 |
|
h****n
发帖数: 1093 | 7 我的递归和非递归解法，贴在下面 OJ通过 ，还有每K个reverse那个，不过那个只有递
归版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
/*
//递归做法很简单，但是要切记前面几行的顺序，别放错了
ListNode* cur = head;
if(cur==NULL) return NULL;
ListNode* n... 阅读全帖 |
|
i*********7
发帖数: 348 | 8 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
母，但是变出来的都是valid word。
例子：head->heal->teal->tell->tall->tail
给你一个input和target，判断input能不能到达target。
说算法复杂度。
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
第三个面试官：求平方根。不能用牛顿迭代法。
第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
栈）
第五个面试官：估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？
忘了说了，这题还有一个follow up：
如果让你设计编译器的栈，你怎么设计？
第二，先写一个mergesort。
然后问你算法复杂度，但是有条件：假如你每访问一个整型数的算法复杂度为o(a)，总
的算法复杂度... 阅读全帖 |
|
w****x
发帖数: 2483 | 9 "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬 |
|
i*********7
发帖数: 348 | 10 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
母，但是变出来的都是valid word。
例子：head->heal->teal->tell->tall->tail
给你一个input和target，判断input能不能到达target。
说算法复杂度。
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
第三个面试官：求平方根。不能用牛顿迭代法。
第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
栈）
第五个面试官：估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？
忘了说了，这题还有一个follow up：
如果让你设计编译器的栈，你怎么设计？
第二，先写一个mergesort。
然后问你算法复杂度，但是有条件：假如你每访问一个整型数的算法复杂度为o(a)，总
的算法复杂度... 阅读全帖 |
|
w****x
发帖数: 2483 | 11 "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬 |
|
s**********r
发帖数: 8153 | 12 呜呜，我也是，只会递归。。。
递归那几道题目，我只会递归，等你会循环得时候，能不能告诉我一下怎么做得？ |
|
g*********e
发帖数: 14401 | 13 递归版本不太好吧 链表太长stackoverflow了。
我一般都是些iterative，能不递归的就不递归 |
|
p**e
发帖数: 533 | 14 用递归的话，最大的问题，就是计算从3出发的时候，又会对2，5，6递归，其中2和5已
经在计算从1出发的时候递归过了，所以会有重复的节点。 |
|
t**********h
发帖数: 2273 | 15 LCA？ 是二叉树吗？ 150上有原题吧，不过不是最优的，递归套递归，如果稍作改变，
可以只递归一次。不知道你给的哪种？
move on。。。更好的在后面 |
|
p********s
发帖数: 37 | 16 刚试了下，用预处理+暴力搜索可以忽悠过去
预处理：对于s1,s2的所有位置p1,p2和长度l有子串(p1,p1+l)和(p2,p2+l)，如果两个
子串包含不同的字符集则搜索时不予考虑
搜索：对于s1,s2，以及可能的字串长度l，递归搜索以下两种情况：
把s1和s2拆成l和strlen(s1)-l两段，分别递归搜索
把s1拆成l和strlen(s1)-l两段，把s2拆成strlen(s2-l)和l两段，分别递归搜索 |
|
i***e
发帖数: 452 | 17 上周二去的狗狗家onsite, 今天发信问HR update, HR说还在收集feedback, 说明天可
以给个update. 真心求bless! 希望这次可以成了， 谢谢大家！
----------------------
Update: hr今天打电话说明天hiring committee 出结果！ 还说透露点feedback： ＂
some are good, some are not consistent ", 然后说coding is good！ 看来有一些
不好的feedback 了！ 继续求bless 了！只能看人品爆发了！谢谢
--------------------------------------------------
update2： 写个面经了。。
1） int pow(int n, int m)
2) 写一个类是timer 的东西， 例如给个数值t和函数，等t时间之后call 这个函数。
（然后问有多个这些如果支持多次调用怎么办， 有哪些问题之类的）
3）给一个函数 void f(){.... return;} 然后问在return 语句的时候程序cl... 阅读全帖 |
|
i**********e
发帖数: 1145 | 18 这题可以优化用dp，通常看到递归用 i+1,j，要不然递归 i,j+1，这就是很明显的可以
转换非递归dp。
dp[i,j] = whether s3[i+j] can be formed as interleaving of substrings s1(0,i
) and s2(0,j).
eg, s1 = "hello", s1(0,1) = "h".
Then,
dp[i,j] = dp[i-1,j] && s1[i-1] == s3[i+j-1]
|| dp[i, j-1] && s2[j-1] == s3[i+j-1]
总复杂度 O(m*n). |
|
b***i
发帖数: 3043 | 19 这个基本上是对数关系，自己写过1k行的算初学者（自己写的，不是说你的项目里本来
有别人的代码，或者编译器帮你生成的），和写过2k行的熟手差一个档次，写过4k行的
基本上算是研究生毕业的高手，拿几个面试不成问题，8k可称大侠，入门工作随便挑，
16k的就是大牛了，算是做过比较重量级的应用，32k基本上大师了，做过多个重量级应
用，64k的可以算作功夫深不可测，应该是跨越多个领域的应用，比如从网页到网站到
app，128k算是沃兹尼亚克级别的可以开创一个领域了。
基本上，写过64k行代码的，那些很难的题目都遇到过。工作中没遇到过还是代码写得
不够多。比如我就用到过好几次递归,Trie。别笑，你能用到递归说明你的项目很有意
思。大部分项目连递归都用不上。还有多线程，项目中能用到过是福气，可遇而不可求。
还有一个关键是是看你用了多长时间写代码，有人从8岁开始写C语言代码，或者java，
写到20岁，每天花时间研究，没有3万也有16k，这种年轻有为的当然是面试的重点。所
以关键是你写下几万行代码的年龄，如果20-25，达到16k以上，就认为是高手。从20岁
开始学C/java,到30还没到4k,... 阅读全帖 |
|
x*****p
发帖数: 1707 | 20 很多递归算法的非递归实现，更能考察一个人的编程功底。所以面试官不般不喜欢递归
算法，过于简单太Junior level了。 |
|
|
|
p*****2
发帖数: 21240 | 23 2，分析下面递归算法的复杂度
Alg(array, size)
split -> A1, A2, A3.... O(n)
Alg(A1, size/3)
Alg(A2, size/3)
这个题目是硬伤，他push我快快快，我一紧张，递归函数没有写好， 写出来之后
说用主定理，再一紧张把 a 和 b搞反了。。。
F(n) = a * F(1/b n) + O(n)
总的来说这题做错了
这道题没看明白。上边说分析复杂度，怎么又说递归没写好？ |
|
j*****s
发帖数: 189 | 24 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
。还让我take care of myself。
整理一下心情，把onsite的面筋发出来，攒一下人品吧。
我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
叔，不过我感觉他应该是对我印象最好的一个了。
第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
作以维护这个iterator的数据结构。当然，hash table本身的操作是O(1)的，所以要求
维护这个数据结构的时间也是O(1)。压根没想过……乱七八糟说了一堆，他大概满意了
之后，开始写... 阅读全帖 |
|
j*****s
发帖数: 189 | 25 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
。还让我take care of myself。
整理一下心情，把onsite的面筋发出来，攒一下人品吧。
我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
叔，不过我感觉他应该是对我印象最好的一个了。
第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
作以维护这个iterator的数据结构。当然，hash table本身的操作是O(1)的，所以要求
维护这个数据结构的时间也是O(1)。压根没想过……乱七八糟说了一堆，他大概满意了
之后，开始写... 阅读全帖 |
|
h*******l
发帖数: 22 | 26 虽然记得不太清楚， 贡献一下面经回馈本版吧。只onsite过G和Y。其他大多电面， 而
且久远，就记不了那么清楚了。
Y 电面一个小时，只有一次电面，过了就onsite。难度和大多数电面都差不多。
Y我有两个onsite
第一个
1. 问了买卖股票（很遗憾， 没做过，不过最后还是整出线性时间的算法了，花的时间
比较多，要是leetcode上做过，会快很多），
2. LC Sequence（基础，飞快写完递归和非递归解法）；
3. hashtable实现 (基础，TA过高级数据结构)；
4. 二叉树高度，要求非递归解法
5. 数组找到第k个最大的（高频题，selection sort，平均n，最坏n平方；也可以用大
小为k的heap做，让我实现了其中一个）
6. 给一个堆，里头有无序的数，排序之，要求只用堆数据结构，最好只用两个，复杂
度最好用nlogn（我当时没有达到他的要求，看上去用了两个stack，其实用了程序自己
的stack，复杂度也没有达到n平方）
7. 单链表，有环，数据部重复， 找到环， 要求给出两种做法 （cracing google
interview上的题，两个指针... 阅读全帖 |
|
a****l
发帖数: 8211 | 27 时间上不好说，不过空间上这个解法是要用到递归的，不见得比非递归的算法更省空间
吧？理论上应该非递归的iterative算法最快最省空间，每次仅把必须换的字符换掉，
别的算法应该不可能效率更高吧？ |
|
a****l
发帖数: 8211 | 28 时间上不好说，不过空间上这个解法是要用到递归的，不见得比非递归的算法更省空间
吧？理论上应该非递归的iterative算法最快最省空间，每次仅把必须换的字符换掉，
别的算法应该不可能效率更高吧？ |
|
t****a
发帖数: 1212 | 29 偶不懂诶，玩了几天clojure的尾递归玩了个大概就算了，前面有人说不能把所有递归
转成尾递归，自己也没玩出来，后来就去搞memoize了，那个更实用些
clojure里iterate函数也很好用，做bfs一行就搞定了。也许其他FP语言也差不多 |
|
p*****2
发帖数: 21240 | 30
循环就不是尾递归了。我是看有个帖子不知道DP怎么转换成尾递归，所以我写写的。主
要是为了尾递归。数组应该没问题，你把它看成一个大functional就可以了。里边的子
函数可以访问大函数的变量。这个没问题，不改变就可以了。 |
|
h********g
发帖数: 496 | 31 g++对尾递归没有优化。尾递归和递归同时 segmentation fault
iteration的没有问题。 |
|
w****a
发帖数: 710 | 32 10分钟面经系列，这次是T家。
上次FB二面终于如期收到拒信，move on了。T家的一面希望大家bless啊。
刚开始给我一分钟时间问了我两个behavior问题，一个是我现在在做什么，一个是why
T家。
然后就开collabedit了，就写了一道题。题很简单，板上的XDJM们相信都能秒杀。
给一个多叉树和一个节点，求出这个节点所有path下来的数字的和。比如给出树和节点
4
4
/ \
2 1
\
3
答案就是413+42 = 455。
这个题倒没什么，拿到就问了他需不需要考虑big int的问题，他说不需要，int肯定够
用。那就放心写了。写完之后我怕有bug在纸上反复写各种test验证。他问我干啥，我
就说我在做“单元测试”。他就让我别在纸上画了直接在collabedit上写。我就把他给
的sample用函数流程走了一遍。。
随后就是一系列的follow up。我一开始给的解不是最优解（犯2了，啥也没想上来先用
了vector存所有路径下的数字，最后我逐个相加）。他也没说什么，因为代码本身没问
题，就是跟我说让我说出时间复杂... 阅读全帖 |
|
f****s
发帖数: 74 | 33 也就是遇到q失配的时候为什么不从q-2往前递归，而是从pi[k]往前递归呢？也就是说
从q-2往前递归，肯定也会失配。为什么呢？ |
|
n*******w
发帖数: 687 | 34 第一题可以DP
其实本质上是把set分成两部分使得两部分的差的绝对值最接近0
google MIT balanced partition
第二题是longest increasing sequence的变形
先假设w_j全为非负数
假设L[j]表示ending position在 j 的时候找到的longest increasing sequence
DP[j]表示L[j]这个sequence里边所有元素对应的w之和。
递归式为
DP[j] = max {DP[i]} + w_j
i = [0, j-1] && A[i]
返回结果 max { DP[j] } where j = [0, n-1]
如果所有w_j都等于1，那原题退化成求longest increasing sequence，因为递归式一
模一样。复杂度都是n^2
如果w_j可能为负数，那么上面的递归式里边的w_j 改成 max(0, w_j)
find
.. |
|
a*****a
发帖数: 46 | 35 题目是说用递归取代循环，如果是多种括号的话，即使递归也得用stack吧。虽然递归
自己就有stack，但是这里左右括号的处理不同，右括号的话需要pop，所以我觉得还是
得用stack。
用java写了一下，欢迎指正
private boolean isValidHelper(String s, int cur, Stack stack) {
if (cur == s.length()) return stack.isEmpty();
char c = s.charAt(cur);
switch (c) {
case '(':
case '[':
case '{':
stack.push(c);
break;
case ')':
if (stack.isEmpty() || stack.pop() != '(') return false;
break;
case ']':
if (stack.isEmpty() || stack.pop() ... 阅读全帖 |
|
s*******s
发帖数: 1031 | 36 暴力算法是 n! 时间复杂度。
我想出的是DFS一个二叉树， O(2^n)的复杂度。
将这个distance 序列按照降序排序。O(n log n)
进入递归程序:
1. suppose d1, d2, d3,...dn是降序排列的数。
d1最大，所以d1肯定是两个端点的距离。 现在要确定下一个点。
d2或者d3将会是去掉最后端点(或者最前端点)的剩余的长度。
2. 对d2,如果能在d3, d4,..., dn中找到一个di，使得 di = d1 - d2，那么d2有可能是
一个合格的子问题，在原来的序列中去掉d1, di，递归调用。如果找不到这么一个di,那
么d2不是valid choice
3. 对d3，如果能在d2, d4, ..., dn中找到dj，使得dj = d1 - d3，那么，类似于2，
对d3进行递归调用。
如果d2, d3都无法找到相应的di, dj，那么这个序列是非法的序列，返回。
stop condition:
当序列是空的时侯我们找到了一格valid结果。
Time: O(2^n） 因为是对二叉树进行DFS。
求更好的解法！ |
|
s*******s
发帖数: 1031 | 37 暴力算法是 n! 时间复杂度。
我想出的是DFS一个二叉树， O(2^n)的复杂度。
将这个distance 序列按照降序排序。O(n log n)
进入递归程序:
1. suppose d1, d2, d3,...dn是降序排列的数。
d1最大，所以d1肯定是两个端点的距离。 现在要确定下一个点。
d2或者d3将会是去掉最后端点(或者最前端点)的剩余的长度。
2. 对d2,如果能在d3, d4,..., dn中找到一个di，使得 di = d1 - d2，那么d2有可能是
一个合格的子问题，在原来的序列中去掉d1, di，递归调用。如果找不到这么一个di,那
么d2不是valid choice
3. 对d3，如果能在d2, d4, ..., dn中找到dj，使得dj = d1 - d3，那么，类似于2，
对d3进行递归调用。
如果d2, d3都无法找到相应的di, dj，那么这个序列是非法的序列，返回。
stop condition:
当序列是空的时侯我们找到了一格valid结果。
Time: O(2^n） 因为是对二叉树进行DFS。
求更好的解法！ |
|
d**e
发帖数: 6098 | 38 ☆─────────────────────────────────────☆
slimcan (道指2万4千点) 于 (Fri Jun 7 17:52:23 2013, 美东) 提到:
学生物的转行，国内的小孩英语越来越好，有闲给你题海应试。
经济不好 entry level 的工作没有增加。
学Cs的本来有点算法 os的优势架不住有码工新东方 leetcode的存在。
难啊，近日看帖有感。
需要终身学习和做open source project啊
☆─────────────────────────────────────☆
ursatong (Ursa) 于 (Fri Jun 7 17:55:22 2013, 美东) 提到:
求码工新东方是什么……
☆─────────────────────────────────────☆
huchihaisai (hu) 于 (Fri Jun 7 17:59:16 2013, 美东) 提到:
leetcode 唉
☆─────────────────────────────────────☆
jo... 阅读全帖 |
|
c******a
发帖数: 789 | 39 DP优于递归，考虑到递归calculate the same things over and over again.
也可以递归＋memorize，跟dp就一个道理了。
我要是面试官，我两种都接受。前提是你能说清楚哪个好，为啥，怎么优化。 |
|
h*****a
发帖数: 1718 | 40 现在JVM和OS应该不太可能对这种情况的递归给出类似DP cache的优化吧。否则
Fibnacci用递归来写不就行了。
不过我同意的一点是递归在解决这个具体问题上应该不差，因为现实的自然语言case基
本上不会出现指数复杂度的最坏情况。而且DP的方法增大了内存的开销，有些情况下反
而会成为问题。
我前面说过，我并不是说我给出DP的方法是最优的，我耿耿于怀的是对方对DP的“不理
解”。如果他能和我对DP的优劣做进一步的交流，我会是非常open和happy的。但似乎
从我开始写出DP的code，他就不太明白我在干什么，呵呵。 |
|
h*****a
发帖数: 1718 | 41 奇怪，你哪看出来的你说的这些东西？
我上来一边解释一边写code，一共就十几行，10分钟就完了。然后他问你这个数组干吗
的？我说我用来存中间结果，然后他再问为什么，这样都是一直在交互，我们go
through了一些例子来说明程序是怎么work的，为什么你觉得我是羞辱他？呵呵。我一
开始一直都觉得他是想让我把DP解释一下。
递归在我看来并非低等，他自己也没说你换个思路，他一直都是让我解释怎么work，后
来他还自己到白板上把我的code用例子走了一遍。他要给我任何hint说你写个递归的
code我肯定立刻就写，绝对不会说递归不好我不写。
当然，事实上最后他肯定认为我不是他愿意要的同事。但说实话，和他交流过程中我没
有不屑，也没有觉得自己牛，面试就是面试，就是交互的过程。这个过程中我make了一
些假设，比如他懂DP，结果我错了，这怎么说也是小概率事件。 |
|
c**l
发帖数: 2661 | 42 dfs 用递归 大数据不行吧
反正我用dfs大数据搞死过 后来全部用非递归
都用非递归的话
我怎么感觉用 bfs会稍微好点 尤其是 深度比宽度大的情况
此时 bfs 基本是宽度的复杂度 |
|
w*********m
发帖数: 4740 | 43 可以这么说。但是没法简单合并。第二个递归必须要try所有的segmentations，都不对
，才不对。但在第一个递归里，你还没拿到全长的string，只看见部分的string，这部
分的string的全部segmentations都不在字典里也不能说明这条路不对，因为再加一个
字母就有可能在字典里了
所以我说得用prefix tree才能在看到部分string时能决定是不是在字典里
但我写了两个递归之后，时间已经差不多了，我就讲了idea，他也没让我写prefix
tree。但我感觉99%他会给坏评价了 |
|
l*n
发帖数: 529 | 44 java的话，你可以用伪指针实现同样的设计，就是在c++用pointer的地方用一个
TreeNode[]。至于后面你问到的stack的问题，这个没有办法。inorder traversal的非
递归方法也需要stack，这样一来不用stack的话是没办法搞的，所以递归方法也不算是
有空间上的优势。非递归的好处在这里主要是显式stack是在heap分配空间的，而隐式
stack是在stack frame上，前者更不怕stack overflow，毕竟heap 比stack frame大得
多得多。 |
|
j*********6
发帖数: 407 | 45 来自主题: JobHunting版 - 请教个问题 尾递归实现和语言没关系吧？（理解不对的话求大牛指正） 不过一般情况下递归都不
是尾递归
所以就用循环之类的写吧~ |
|
a**********0
发帖数: 422 | 46 wiki上说DP是把大问题变成小问题 但我觉得这不能体现DP的特点 难道recursion不是
把大问题变小问题吗？ 我觉得差别是 DP一般从base case 到complicate case
递归反之 比如Fibonacci如果用递归 则指数复杂度 如果用循环 就是多项式 循环当然
也需要从简单到复杂而不是反之 DP相比递归就是减少了重复的计算
其实dp有点像随机过程里的马克夫过程或者martingale一样的 就是一点一点的算 |
|
L*********g
发帖数: 8 | 47 先是问了一些概念题，然后还剩30分钟：写个函数判断二叉树是完全二叉树
complete tree
例如
是：
a
/
b c
/ /
d e f g
/
h i
是：
a
/
b c
/ /
d e f g
/ /
h ij
不是：
a
/
b c
/ /
d e f g
/
h i j
不是：
a
/
b c
/
d e g
/
h i
只记得完全二叉树用在堆排序中。吭哧半天，想出了个算法能实现：只能按层遍历（看
下面的三步）。但到最后没时间了，代码没写... 阅读全帖 |
|
a*******n
发帖数: 112 | 48 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
吧。
- 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。
当然这个算法有更好的解，既然不要求顺序，而且有头尾指针，每次把父子链表接到尾
巴后面就可以了。连递归都省了。
- 算sqrt()
我提出用牛顿法，刚画完坐标系就说不让用。原话是“newton's method is for
mathematics, please use comput... 阅读全帖 |
|
e****b
发帖数: 25 | 49 你的意思是比如N是 5的话 我们要1，3这个序列吗？
我觉得是不是可以把1 到2N的完全平房数丢到一个vector 然后我们对1，2，到N的序列
做一个递归
比如N是5 那相邻最大和肯定不超过10，那就只有4和9
然后从1开始 找到3，3递归（只用大于3的序列） 然后因为3找不到6 因此就只有1，3
然后接下来就对2做
当然也可以在对3做递归时做个记录 ，所以2找完后到3时发现3已经做过就没必要再找
了 |
|
p**o
发帖数: 3409 | 50 我11楼那个方法，“后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5”，
从most significant digit开始递归，保证输出有序，
所以容易根据给定的最大值终止生成器。
此前我的思路是从个位数往高位开始左移递归：
“前n位含5 当且仅当 第n位是5 或 前n-1位含5”。
这种方法的缺陷是：结果无序，所以不方便根据给出的最大值跳出生成器。
DIGIDS_NO5 = (0,1,2,3,4,6,7,8,9)
# Generate all k-digit (1<=k<=n) numbers without digit 5
def genno5 (n):
if n == 1: yield from DIGIDS_NO5
else:
for x in genno5(n-1):
for y in DIGIDS_NO5:
yield 10 * y + x
# Generate all k-digit (1<=k<=n) numbers with digit 5
def gen5 (n):
... 阅读全帖 |
|
