a**********0
发帖数: 422 | 1 我本来用递归方法 但是超时了 本身代码没错 就是慢 为什么慢 因为在每个递归函数
中有O（n）的操作 这样n次递归导致总体O（n平方）
如果坚持递归方法 需要返回调整好的list的尾节点的下一个节点 这个是从网友那里学
来的 其实这个过程有点tricky 为什么不简单返回 list的头节点或者尾节点 而要返
回尾节点的下一个节点呢？ 思路是这样的 尾节点经过调整已经不是原来的尾节点了
它指向的下一个已经不是原来的顺序 那为什么不返回头节点呢 ？ 头节点其实不需要
返回 每次用next找就可以了 而且每次拿到头节点也不好用 必须多次next找到尾节点
又超时了
网友的方法 我改编成了java的 后边也有返回尾节点的方法
但是很容易出错 如果面试 还是用循环而不是递归的方法 当然面试无法检查是不是超
时 所以用我最早的方法也可以吧
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* ... 阅读全帖 |
|
w***w
发帖数: 84 | 2 DP 其实就是递归。 设c(i,j)是从i-th cut 到j-th cut的线段的最小cost, 就有递归
式，c(i,j) = min_{i
不能直接递归去解，否则会指数爆炸。DP 的trick就是递归过程中记住所有见过的解，
每次递归先去查解是否已存在。或者是通常看到的递推的自底而上的填表式的解法。
至于Huffman编码，假设题目是切出要求长度的一些木块但并不限定order的话，这样你
可以把长度看成是概率 （设木板总长是1)，那么这里的cost定义就等价于平均码字长
度, 因为每一小段contribute的cost就是把它切出来需要的cut数。 |
|
t*******r
发帖数: 22634 | 3 我觉得不严格的形象表述那个属性（形象联系 XOR 和 < 号），
就是看那张彩色的 Cayley Table 的图。
bitwise-XOR 对于自然数序列的 Caley Table 实际上是基本 XOR 矩阵
0 1
1 0
逐次在不同的位 bits 上递归叠加。（上面有人提到过这个）。
（其实这个就是 bitwise-XOR 的定义）。
（另外由于这个叠加不会出现进位，所以这个叠加跟加法也是一回事）。
而比较大小的 < 号，其实也是从最高位（最高递归层）到最低位（最低递归层）
的逐次比较。
这样从那张图上递归地看：
（1）最高位比该数的最高位小的数，在长边的排列组合都会出现。
（2）最高位和该数一样的。大家统统一起剥掉最高位，然后递归到（1）。
所以不严格的概念表示，比该数小的那些数都会出现。
彩图在这里：
'^
L |
|
D**0
发帖数: 2048 | 4 ☆─────────────────────────────────────☆
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, 美东) 提到:
“夏利营”的组织者都干神马去袅？ 不能... 阅读全帖 |
|
t*******r
发帖数: 22634 | 5 我去改一下汉语。
这个语法的左递归比较简单，我可以用 C伪码 递归函数直接写。但是可能比 Yacc
更不直观，更不好理解。毕竟 Yacc 直接把语法写在字面上，C 递归把语法隐含
在递归里。。。
我们不是在讨论素数递归正则语法么？Yacc 直接把 token 写在字面上啊。 |
|
t*******r
发帖数: 22634 | 6 我现在觉得楼主的证明是错误的，原因是楼主引用的素数的递归定义。
我现在这么阐述。
=========================================================
关键问题：问题（1）：楼主引用的素数的递归定义，是不是只能存在于
formal logic 的系统里。
---------------------------------------------------------
如果问题（1）的回答是“是”。
那由于楼主所用到的古典反证法里面的“假定素数集是有限的” 这个假定无法
被符号化，从而无法被纳入 formal logic 系统，导致整个证明因为采取
相互矛盾的数学系统，不自洽，而失败。
---------------------------------------------------------
如果问题（1）的回答是“否”，那看楼主前面的帖子会发现：
（a）：楼主无法回答素数递归定义里面那个“小于a”的那个条件的必要性。
（实际上是必要的）。
（b）：更重要的是：楼主无法回答在素数递归定义里，被定义的素数（集），
和... 阅读全帖 |
|
t*******r
发帖数: 22634 | 7 楼主首贴里面的逻辑很牛逼，但伊还是引用了素数的递归定义。
现在的问题是，素数的递归定义引起混淆和争论。为了平息争论，所以想用某种
formal system 的 notation 来精确定义一下素数的递归定义。
当然，你说的对，LR grammar 的确用词不精确，LR grammar 不定义语义。
用 yacc 还是精确点。
所以也就是用 yacc 来定义一下楼主首贴证明里面所引用的“素数的递归定义”。
当然，其实不限于 yacc。任何 formal system 的 notation 方式都可以。
只不过素数的递归定义比较简单，用 yacc 就可以定义。
CFL |
|
t*******r
发帖数: 22634 | 8 素数非递归定义中，可以略去更大的自然数，是因为整除算子的存在。
而且整除算子是比素数定义先定义的。
但是另一方面，我同意你的看法，虽然这样的 formal system，对
素数有递归定义和非递归定义两种定义方式构造，用非递归定义构造的系统
的确有悖论之嫌疑。用素数的递归定义来构造系统更加合理。
当然，现在又是数学哲学问题了。我们是不是需要能够构造所有的可想象
的系统？码工的哲学是，如果构造的两个系统是等价的，其中一个系统
有悖论之嫌疑，另一个没有。那码工就直接扔掉那个有悖论嫌疑的系统，
留下那个良好的系统。背后的哲学是，我们不需要能够构造包含所有万物
的系统，我们只需要能够构造完备的能解决问题的系统。 |
|
t******n
发帖数: 2939 | 9 ☆─────────────────────────────────────☆
l63 (l63) 于 (Fri May 24 02:08:51 2013, 美东) 提到:
我不是认为命题1是真.
我是根据逻辑和公理推导出了 "如果假设成立, 则命题1为真"
看不懂别乱给人扣帽子. 你倒是给论证论证, 我怎么就 "认为命题1为真" 了?
☆─────────────────────────────────────☆
l63 (l63) 于 (Fri May 24 02:13:43 2013, 美东) 提到:
那你得指出错在哪, 是不是?
你不能说 "我已经根据假设推导出命题1为真, 所以就不考虑命题2" 是错的吧?
☆─────────────────────────────────────☆
cyw (口令) 于 (Fri May 24 02:24:23 2013, 美东) 提到:
看你id怎么隐约看见了孙维？
☆─────────────────────────────────────☆
firearasi (firearasi) 于 (Fr... 阅读全帖 |
|
t******n
发帖数: 2939 | 10 ☆─────────────────────────────────────☆
daigaku (๑۩۞۩๑) 于 (Sun May 26 04:25:00 2013, 美东) 提到:
A 素数 := 大于1，且只能被1和本身整除的自然数
/\
|
|B 素数有无穷多个（已证明）
|
\/
C 素数没有本身之外的质因数
现在我们无聊，想证明素数有无穷多个
lz的思路是：先否决B（反证假设）
然后发现在此前提下C不成立了
然后说B假设必然不成立，证毕
看出问题了吗
☆─────────────────────────────────────☆
l63 (l63) 于 (Sun May 26 04:28:50 2013, 美东) 提到:
你太笨了.
我证明C并不需要用到B, 你自己用了只能说你笨, 不要拖我下水, 谢谢!
☆─────────────────────────────────────☆
daigaku (๑۩۞۩๑) 于 (Su... 阅读全帖 |
|
b***y
发帖数: 2799 | 11 ☆─────────────────────────────────────☆
geome (珍惜生命远离bbs) 于 (Wed Mar 26 18:10:17 2008) 提到:
诸如插入，遍历等实现起来的时候到底用递归呢还是非递归。
☆─────────────────────────────────────☆
coal (煤炭) 于 (Wed Mar 26 18:11:09 2008) 提到:
都可以，recursion是可逆的
☆─────────────────────────────────────☆
geome (珍惜生命远离bbs) 于 (Wed Mar 26 18:20:01 2008) 提到:
用递归会不会太慢了呢？
☆─────────────────────────────────────☆
goodbug (好虫) 于 (Wed Mar 26 18:22:44 2008) 提到:
为啥不递归呢？现在内存这么便宜，绝大多数情况下
非递归没啥好处。
☆──────────────────────────────────── |
|
I**4
发帖数: 172 | 12 软件: 也是美国领先.不过中国的编程员的脑子绝对厉害,可惜还没有像微软那样大
规模公司.如果不看商业方面,就看软件程序的复杂和严谨程度,中国的学生绝对比美国
的厉害. 比如一些常用的数据结构的排序的递归运算，中国人很厉害，美国人觉得不行
，最多只能做一些 while loop 和 for loop, 没有掌握递归的精髓。
凭着条就知道你是文科生，
递归的精髓是什么?
很多中国programmer 连 functional language (e.g., scheme, ML) 都没听说过，更
不不要说lambda calculus；何谈理解递归的精髓 |
|
f*****n
发帖数: 224 | 13 转贴的人少转答案了。。。
附答案:
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
【答案】c
中国人会选a，西方人会选c。据说伏羲画八卦，这也只是据说，实际不可考，比较确切
的是18世纪莱布尼茨发现二进制。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
【答案】d
《指物论》是“能指”和“所指”的关系，“指”相当于“指针”，“物”相当于“对
象”。指针本身只能记录一个例如字符串的地址，通过指针可以找到这个字符串本身。
而变量a, 你可以让a = 1 ,也可以让a = 2，数组就是 [1,2,3]这种的，只是表示一个
同类的序列。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
【答案】c
四个人都不是一个时代，就是名字像，其实没关系。java跟java script 名字像但完全
没有关系。c和c++有关系。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递... 阅读全帖 |
|
t*********l
发帖数: 566 | 14 攒rp，最近遇到的面试题。。。
C++：effective c++上的东西若干；exception相关；继承和子父类指针若干. 十五分
钟左右。
算法/编程：1. 大文件随机sample，one pass. 2. sodoku solver. 3. logn解x^y,
4. DP题 5. 1Billion query里选出时间最近5分钟内最frequent的1000个，one pass
（我以前在amazon见到过这题）。6.两个排序数组找共同中值。递归和非递归解法。7.
斐波那契数列。100层楼梯下楼，可以一步也可以两步，多少种下法？递归和非递归。
8 贝叶斯后验概率。9。多少人在一起，生日可能出现重复概率大于0.5？（算法导论原
题，我只记得个答案，直接说了。。。）10. 一个数组，找最大值比较次数？同时找最
大值和最小值比较次数？找最大值和次最大值比较次数？（他问我是否知道这题，我说
是作业题。后来和师兄聊说是这他常拿来用的面试题。）
系统设计和经验：1 设计一个库，提供timer的功能。deltalist/hash，或类似linux
kernal的 timer 设计。效率 |
|
g*******y
发帖数: 1930 | 15 顺便给大家给练手的题，
用类似的方法，把Binary Tree的三种递归遍历程序改为等价的非递归stack版本
然后把 N叉树的 DFS遍历的递归程序改为等价非递归用stack版本
understand my code |
|
j**l
发帖数: 2911 | 16 递归是树遍历的平凡解法，面试时候肯定不会就让你用递归写。
非递归又数后序最麻烦，通常的解法都要用到mark，后序非递归遍历也是清华老严教材
的习题 |
|
j**l
发帖数: 2911 | 17 给出了递归和非递归的版本。
考虑如下的test case
int array[4] = {3, 4, 5, 6};
int lower = 1;
int upper = 2;
int target = 2;
对递归的版本，将返回LIMITS_REVERSED。
对非递归的版本，将返回ARRAY_UNORDERED
实际上两个版本对这个case都应该返回NOT_IN_ARRAY
PIE书把range == 0 && array[lower] != target 作为检测到NOT_IN_ARRAY并且立即返
回。而在编程珠玑中，没有LIMITS_REVERSED的错误类型，在range == 0 && array[
lower] != target的情况下并不立即返回，而是继续更改lower或upper,直到lower >
upper, 并将lower > upper作为NOT_IN_ARRAY的条件。
const int NOT_IN_ARRAY = -1;
const int ARRAY_UNORDERED = -2;
const int LIMITS_REVERSED = -3;
i |
|
t**g
发帖数: 1164 | 18 来自主题: JobHunting版 - 请教一道题 前面某位仁兄给出的
给定一棵树, 每个节点有任意个子节点, 怎样得到深度, 给出递归和非递归两种解
我知道递归算法
可是不知道如何写非递归？ |
|
j**l
发帖数: 2911 | 19 递归版本没让写，但我知道tail recursion, 编译器实际会把它优化为循环。
算阶乘和Fibonacci数列都可以用尾递归，引入一个累乘器和累加器参数。链表逆置用
递归也可以再引入一个参数来实现尾递归 |
|
p********7
发帖数: 549 | 20 最近2主要就在面这2家，本来早想投facebook，但是因为有microstrategy约我面试，
所以就把
FB 放在后面了。
M5是一个纽约的猎头找我的，当天就让我电面了他家的CTO，问了下简单的project情况
，并且发了
源代码给他看，第二日就约我onsite。
公司在Manhattan downtown，下地铁不到一个block，因为上次面了flextrade，看到
flextrade的拥挤办公室环境，以及员工颓废的精神面貌，对这家也不报很大希望。
我去的比较早，先坐那里喝咖啡，公司员工超级热心，看我一个人没人管都来问我需要
什么帮助。我
说我在等某某。这家公司的人精神面貌就不一样，除了一个中国人面色很严峻的样子，
其他人感觉都
心态都很轻松。
先是CTO跟我聊了下我的research，然后就是VP带了一个老印，估计也是高级技术人员
。先让我写
N!我写了递归，然后又让用非递归写了一次。继续问递归的确定。接着问求fib数怎么
写代码，这些
代码早练过了，所以不是问题。本来想给他show下我logN的算法，后来他没要求就不写
了。还问了
些stack里面存了哪些东西，以及顺序... 阅读全帖 |
|
p********7
发帖数: 549 | 21 等了1周，Microstrategy终于给offer了，虽然是口头的，但是待遇还不错77k
base+8kbonus+3k relocation虽然我知道我在VP面前表现过于自信，而且VP
是老印，我连他们公司干啥的都没摸清楚，但是这个老印然还不错，没灭了俺。我
准备去VA享受阳光了。
最近2主要就在面这2家，本来早想投facebook，但是因为有microstrategy约我面试，
所以就把FB 放在后面了。M5是一个纽约的猎头找我的，当天就让我电面了他家的CTO，
问了下简单的project情况，并且发了源代码给他看，第二日就约我onsite。
公司在Manhattan downtown，下地铁不到一个block，因为上次面了flextrade，
看到flextrade的拥挤办公室环境，以及员工颓废的精神面貌，对这家也不报很大希望。
我去的比较早，先坐那里喝咖啡，公司员工超级热心，看我一个人没人管都来问我需要
什么帮助。我说我在等某某。这家公司的人精神面貌就不一样，除了一个中国人面色很
严峻的样子，其他人感觉都心态都很轻松。
先是CTO跟我聊了下我的research，然后就是VP带... 阅读全帖 |
|
d*****t
发帖数: 41 | 22 对，应该在不用的时候删除短的那个vector. 但是用递归通常会用到多余的data, 这个
基本上不避
免。至于删除不需要的branch所花的时间并不比用非递归时间多，相当于非递归中把节
点从stack
里一个一个pop出来的过程。
总的来说用非递归通常会快一些，但是写起来会比较麻烦一些，我觉得是各有利弊的~
problem
the
way.
pointer
Another
found
branch,
the
branch. |
|
p*********w
发帖数: 606 | 23 本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
1. atoi
当时写的程序很不细致，没有判断正负，字符串中字符不为数字，字符串过长越界等情
况。写完后想起来了，然后口头补充了一下，面试官说知道我的意思就直接到下一道题
了。
2. 用递归
bool Equal(Node* a, Node* b){
if(a == NULL && b != NULL) || (a != NULL && b == NULL)
return false;
if(a == NULL && b == NULL) return true;
return (Equal(a->left, b->left) && Equal(a->right, b->right)) || (Equal(a-
>left, b->right) && Equal(a->right == b->left))
}
因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
度这块比较弱，在他的提示下写出来的。
然后假如左右子树需要交换的情况下，用变量保存总共要交换几次... 阅读全帖 |
|
g*********s
发帖数: 1782 | 24 本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
2. 用递归
因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
度这块比较弱，在他的提示下写出来的。
how u know tree has lgN level? the worse case could be N.
然后假如左右子树需要交换的情况下，用变量保存总共要交换几次。我用一个引用来保
存，把代码最后一行加几个if语句，在需要交换左右子树的情况下变量自增。但他似乎
不满意，给我写了两个引用，我没懂他什么意思。
why u need a variable to keep the swap? confused here.
it seems this problem has an easy version and a complicated version.
easy version not considering left/right sub-tree swapping. in this case,
you can traverse each tree twice (i... 阅读全帖 |
|
i**********e
发帖数: 1145 | 25 来自主题: JobHunting版 - 一到电面题 恩，没错。
Production code 就算有递归的形式也尽量会转成非递归的，因为栈容易溢出。
另外，速度上循环通常比递归的形式还要快。
通常的情况，递归总体来说 debug 起来还是比循环相比麻烦不少。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
d*******l
发帖数: 338 | 26 差不多就是这个意思，我对尾递归也是一知半解。其实用递归的方法很少有人会考虑栈
上的空间，这里提到尾递归是因为很多编译器会对尾递归进行优化，这样就能比较严格
的认为空间是O(1) |
|
A*****i
发帖数: 3587 | 27 螺旋矩阵的可以不用递归的，需要四个循环分别处理四个边
个人觉得能不用递归就不用，除非他们非要用递归，递归太容易出错了
bless继续加油 |
|
d********w
发帖数: 363 | 28 apple面试经历：最后被一个变态中国人给灭了，问了我一个半小时，太过分了。干脆把面
经公布出来，希望大家能有机会。
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expression tree设计，grep 电话号码
第二次onsite都是hadoop相关，join的mapreduce实现，分布式wc 列出文件行数， 见
了3个... 阅读全帖 |
|
l******o
发帖数: 144 | 29 我了个去了，这些题还真是难啊
删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expr... 阅读全帖 |
|
d********w
发帖数: 363 | 30 删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expression tree设计，gr... 阅读全帖 |
|
l******o
发帖数: 144 | 31 我了个去了，这些题还真是难啊
删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expr... 阅读全帖 |
|
n********k
发帖数: 40 | 32 来说说我自己的解法吧，呵呵，仅供参考啊。
矩阵置零的题思路是这个样子：
1.对于任何一点(x0,y0),“在x0,y0处按键”这个操作或者你不做，或者你只做一次，因为做了n次和做了n-2次效果一样
2.对于任何两点(x0,y0),(x1,y1)，“在x0,y0处按键”然后“在x1,y1处按键”和“在x1,y1处按键”然后“在x0,y0处按键”效果一样
3.由于1和2，我们可以从左上角一行一行遍历这个矩阵，用递归；我有种感觉这个问题是NPC的，虽然我没有证明，但是我觉得他妈的电话面试题能有多复杂，就写了一个暴搜。
递归这么写：
每一点
判断是否已然全零，是的话返回“成功”
判断是否已然出了矩阵范围，是的话返回“失败”
叫下一个点的递归，若成功返回“成功”
按键
叫下一个点的递归，若成功返回“成功”
按键
返回“失败” |
|
p**e
发帖数: 533 | 33 能具体说说吗？
我总觉得递归有点问题，
比如从1出发，递归2，4，5，
从3出发，递归2，5，6。
从3 出发，我们还需不需要递归2，5，如果不要的话，5－1显然是个新的节点。 |
|
R********y
发帖数: 88 | 34 我觉得递归也分情况吧。
有的递归子问题有重叠，这个肯定不行的。如果是很清楚的d&c，递归只是编译层次上
的低效率，我觉得没什么问题。大不了写完以后问一句，需不需要再写不带递归的。 |
|
f*********d
发帖数: 140 | 35 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
===============================================
Oct.19th ，东部时间1:30， 一面，印度a3
1，为什么基于比较的排序问题复杂度下界是O(nlogn)
回答出来了，他表示赞同
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)
总的来说这题做错了
3， 大数据的平方 X^2 X很长 不能用int long 之内的表示
一开始就反应时Divide and Conque， 他表示赞同， 但是我始终没有到NlogN, 只
到了N... 阅读全帖 |
|
j*****y
发帖数: 1071 | 36 一面的第三题一般是可以做到 n^(log3) 吧？
比如 算 A * A where A is n digits number
A = B * 10^(n / 2) + C
A * A = B * B * 10^n + 2 * B*C * 10(n / 2) + C * C
need to compute B * B, B * C and C * C
So we compute three items below:
(B+C) * (B+ C) = B*B + 2*B*C + C*C
B*B
C*C
from which we can get 2*B*C = (B+C) * (B + C) - B*B - C*C
let the time for A^2 is T(n)
so we have T(n) = 3 T(n/2) + O(n)
and T(n) = O(n^(log3)
这里假设两个 n digits number的求和需要 O(n)的时间
补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
=======================... 阅读全帖 |
|
l*****a
发帖数: 14598 | 37 我的体会是这种题最好定义一个结构
class Info {
int depth;
boolean balanced;
}
来记录当前子树信息，因为这种题都需要用递归从root一直到leaves.
而且求depth要递归，判断balanced还要递归，最好一次递归就把所需要的值都存下来
类似的还有那道求树中两结点间最大path那题
这是我的code,见笑了
public boolean isBalanced(TreeNode root) {
return depth(root).balanced;
}
public Info depth(TreeNode root) {
if(root==null) return new Info(true,0);
Info leftInfo=depth(root.left);
Info rightInfo=depth(root.right);
boolean bo=(Math.abs(leftInfo.depth-rightInfo.depth)<=1... 阅读全帖 |
|
t****a
发帖数: 1212 | 38 memoize:
比如给一个函数f(x,y)要进行复杂的计算，如果把它定义成memoize了的话，程序就记
住了它的返回值，下次call f(x,y)就立即返回结果。
用递归实现DP的时候很有用，因为DP的时候很多子问题是重复的
尾递归：就说背包问题用DP求解，我就不会转尾递归；以及一堆其他的问题比如换硬币
什么的；凡是涉及到在函数里多次call不同子问题，然后在它们的结果上做运算的，我
都不知道该怎么转尾递归。二爷要是有办法请教教我。
我这里说的iterate是一个“高阶函数”比如定义另一个函数f(x), 那么
iterate f(x)会产生一个序列，结果是x, f(x), f(f(x)), f(f(f(x))), ... 这东西挺
有用的。 |
|
l****i
发帖数: 2772 | 39 Update:居然收到了onsite的邀请，三面结束正好2周。很神奇。希望onsite能好运。
一面：
美国人，感觉面试官没有任何准备，没有用collabedit.
coding: BST的深度。
我：BST的深度和普通BT的深度，计算上应该是一样啊。
面试官：恩,好像是
我电话里给了递归计算BT的程序
design：设计一个电影院管理系统
我给了一个类似于MVC的design。一个room class，一个movie class，一个manager
class。
又问了一些基础问题，什么是inheritance之类的。
二面：
美国人，直接collabedit
coding：罗马数字转变为int
design：扑克牌，特别让写了shuffle的代码
面试官最后说excellent，会汇报给HR。
这时以为能拿到onsite了，结果HR说要安排三面。
三面：
印度三姐，直接collabedit。三姐强调，写coding之前，要先和她说我的算法思路。
coding：
BST的LCA，写完，三姐说“do u see the problem in your code?”我纳闷，这题都是
练过... 阅读全帖 |
|
m******l
发帖数: 4 | 40 昨天下午首次和G家进行电面，因为目前有工作， 所以心态还比较好，就是包着试一试
的态度挑战一下自己。整个过程如下：
1. 一白哥哥自报姓名，上来先问为什么选择谷歌？然后问了问简历上做过的一些项目
的细节（我还蛮奇怪的，因为听说G家都是上来就编程了啊）
2. 然后就开始问面向对象设计和设计模问题，比如如何设计 java io package,可以用
什么模式等
3. 由2引申， 问bridge pattern 和strategy pattern的区别 （一个是可以动态swap
implementation,一个只能静态）
3. 编程问题：给一个由1， 0 和 ?组成的字符串，返回所有的matching strings， “
?” 可以 match 0 and 1, 比如说：
input : 1??
output: {100, 101, 110, 111}.
input: 100100?00?
output: {1001000000,1001000001,1001001000,1001001001}
关于这个，我用了递归函数，递归call 输入字符串的 substring(1, n)，但是... 阅读全帖 |
|
J*****a
发帖数: 4262 | 41 没有特地为FB准备，不变应万变，一样复习的
1）做leetcode oj, 这是最重要的。。。即使面试没有一模一样的题目，但练完100题
之后，写代码的速度、bug的数量都会和练之前有质的不同
另外自己多总结，比如哪些有linear解，哪些是指数复杂度，哪些是DP，哪些用stack
等。
如果思考的再深入些，可以想到更多，比如可以总结出什么样的二维DP一定可以把空间
复杂度由O(n^2)降至O(n)
2）看本版面经，题目一模一样的概率不大，但是看了面经心里踏实，知道大概流程是
怎么回事，题目大概是什么类型
3）对于lc oj没有覆盖的，自己做些功课，列一些我暂时能想起来的：
3a，简单常见的算法，自己写一遍，比如快速排序，merge排序，桶排序，quick
selection等等
3b，对于常用数据结构，虽然c++或java里可以从库直接拿来用，但是自己写一遍这些
数据结构的实现能加深理解，例如hashtable, heap, threadsafeblockingqueue, BST
的插入删除等。
而且有些面试题，你还是要自己写，比如LRU cache里的双向链表什么的，写写基本的
... 阅读全帖 |
|
p**r
发帖数: 5853 | 42 他们讲的比较实战，感觉挺浅的
我作为斧头帮去听，觉得没啥帮助，都是自己做过的，
有些东西比他们做的还好，全面一些。
但是也有好处，就是把我斧头帮的名词解释搞明白了。
就好比我自己用递归用了很多年，
前些日子才知道这个叫递归。
要是之前，别人问我，你会递归吗，不会，
那尼玛这写得是啥，靠，这就是递归啊，尼玛。 |
|
b******g
发帖数: 3616 | 43 还没看过答案，我写了个递归做法，可能还有更好的解。递归的思路：
假设当前节点为r，需要先递归将r->left为根的子树upside down并返回最右叶子节点n
。然后将r->right接到n->left，将r接到n->right。由于此时新树的最右叶子节点为r
，返回r供上层递归使用。代码里的newRoot是为了返回整个树upside down后的新的根。
class Solution {
public:
TreeNode *upsideDownBinaryTree(TreeNode *root) {
TreeNode *temp, *newRoot = NULL;
temp = buildUpsideDownBT(root, newRoot);
return newRoot;
}
TreeNode *buildUpsideDownBT(TreeNode *root, TreeNode *&newRoot) {
if(!root) return root;
if(!root... 阅读全帖 |
|
j*****g
发帖数: 254 | 44 简答如下
递归时，已知[1,2,3,4,...Xn_1,] 求Xn
下个数一定是已知[1,2,3,4,...N-1,]中某个数 * 2/3/5中一个
而这个被乘数一定是最近一次被 2/3/5 乘的数递归后的下个数，否则可以证反
所以保持
a. 递归得到的[1,2,3,4,5,...]数列
b. 最近一次被 2/3/5 乘的数的序号
以便加速获得递归得到的[1,2,3,4,5,...Xn_1]数列下个数Xn
|
|
t*******r
发帖数: 22634 | 45 我觉得我现在大概明白了。
题目里的那句 “put smallest non-negative integer that does not
appear at left/below in the same column/row”，对于最小的能满足
那句话的矩阵，就是：
0 1
1 0
而上面这个矩阵，实际上就是基本 XOR 算子。
从这个矩阵开始，可以递归构建更大的满足条件的矩阵（也可以看前面彩图）。
a a + rows(a)
a + rows(a) a
而这个递归构建的过程，实际上就是从基本 XOR 算子出发，构建
bitwise-XOR 算子的过程。
因此，从这个角度看，“递归构建” vs “bitwise-XOR 算子构建”，
其实是同一个东西的两个投射。所以那个 bitwise-XOR 算子并不是
巧合。从某个角度看，bitwise-XOR 算子是自带递归的算子
（属于“自带干粮的五毛”算子哈哈）。
俺前面犯的最最主要的错误，是混淆了基本 XOR 算子，和 bitwise-XOR
算子的区别。这两者不等价。 |
|
t*******r
发帖数: 22634 | 46 其实如果把矩阵递归的表达改写成：
初始条件：
a = [ 0 ]
递归条件：
[ a , a+max(a)+1 ;
a+max(a)+1 , a ]
这样从条件开始直接 证明 / induce 角度看更直截了当是不是？
（ max(a) = rows(a) - 1 不难证明，而且这样题目里面的 min()
条件直接给出在递归表达式里面：
“put smallest non-negative integer that does not
appear at left/below in the same column/row” ）
这样是不是同时证明了 “递归生成” 和 “bitwise-XOR 算子” 生成？
我吃饱了撑的又跑一个 octave，见附件： |
|
t******l
发帖数: 10908 | 47 你这个是对的，也是可以证明的。
这个证明的主要 trick，是不要画成类似 constructive 的递归不变式，因为这个
问题本质不是从底向上的 construction 问题。要画成类似 branch & bound
的递归不变式。
具体就是每个 node 下选奇偶分支时，mark 上假设该奇偶选择保持不变到底的 sum，
然后选最大的 lower bound 的 branch，recurse down 时不断 update lower bound，
就能证明。
我昨天陷在类似 constructive 的递归不变式里，就无法 handle 证明里的
trajectory change。类似 branch & bound 的递归不变式就能绕过 trajectory
change 的问题。 |
|
b***e
发帖数: 15201 | 48 恩 我转发答案吧 不一定对阿
发信人: philofellow (大智若愚), 信区: JobHunting
标 题: Re: 微软intern面经（一些解答）
发信站: BBS 未名空间站 (Wed Jan 19 22:22:13 2011, 美东)
本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
1. atoi
当时写的程序很不细致，没有判断正负，字符串中字符不为数字，字符串过长越界等情
况。写完后想起来了，然后口头补充了一下，面试官说知道我的意思就直接到下一道题
了。
2. 用递归
bool Equal(Node* a, Node* b){
if(a == NULL && b != NULL) || (a != NULL && b == NULL)
return false;
if(a == NULL && b == NULL) return true;
return (Equal(a->left, b->left) && Equal(a->right, b->right)) || (Equal(a-
>left, b->right) && ... 阅读全帖 |
|
x*****p
发帖数: 1707 | 49 你想要递归定义，就得有终止条件。也就是你要定义第一个素数。
根据你的递归定义，要加上一条，强制规定2就是素数。否则，你如何证明没有比2小的
素数。
看来你是学计算机的，没有学数学的严谨。
那按照你的递归定义，素数是递归定义出来的，而第一个素数2是强制规定的。你要玩
算法可以，玩数学就不行了。
你要如此，我来问你，你如何定义自然数？如何定义整数？ |
|
m**x
发帖数: 8454 | 50 递归定义不是不可以啊，递归只要能追溯到源头就行。而且此定义与公认定义等价，有
什么不可以的呢。递归和循环不是一个概念。递归证明叫数学归纳法是可以的，循环的
叫循环论证是无理的。
数。
。2 |
|
