l****o
发帖数: 135 | 1 某上市电商公司，电话面试，是个中国人面的。
上来就用中文打招呼，那个亲切啊！花半个小时问了一堆简历上的东西，然后说做个题
写个inorder traversal吧，我说recursive还是iterative。他说就写个recursive吧，
我说recursive是不是太简单了？他说那就都写吧。于是刷刷刷就写好了，给他解释了
一下recursive的代码。他说好，再做一道给定硬币面值，求给定值如6的找钱组合数。
也是常见题，给了个例子确定了一下需求，然后刷刷刷写完，他没怎么看懂，于是在
collaedit上编译通过一个测试case。
然后，第二天就来了据信说根据你phone interview的结果，我们决定找更适合的
candidate。尼玛，不带这么耍人的。实在不很理解面试官的心里。。。 |
|
x***j
发帖数: 75 | 2 海投了2个星期，刚收到第一个电面，漫长的战斗要开始了。
攒人品贴个详细的电面面经，感觉题目很简单，但交流不畅，只怪自己太嫩了。
顺便： 长期求各种马工内推！！！地点不限，不胜感激！！！
Q): find the largest number in an array, explain how?
很easy， 走一遍数组，update一下最大值。
follow up:
1) so how many times of compare do you need?
很easy n-1。
2) Is there any chance fewer times of compare?
在想，
说不用想了，没有。
3) can you find the number using divide + conquer/ recursion? write the code
不明白为什么非要recursion，
说因为优势文件很大，电脑一次只能阅读1000个数据。
于是开始写了一个1000限制的程序。
说不对，我的1000只是比如， 用类似merge的想法做。
写了出来。
4) are you OK with th... 阅读全帖 |
|
x***j
发帖数: 75 | 3 海投了2个星期，刚收到第一个电面，漫长的战斗要开始了。
攒人品贴个详细的电面面经，感觉题目很简单，但交流不畅，只怪自己太嫩了。
顺便： 长期求各种马工内推！！！地点不限，不胜感激！！！
Q): find the largest number in an array, explain how?
很easy， 走一遍数组，update一下最大值。
follow up:
1) so how many times of compare do you need?
很easy n-1。
2) Is there any chance fewer times of compare?
在想，
说不用想了，没有。
3) can you find the number using divide + conquer/ recursion? write the code
不明白为什么非要recursion，
说因为优势文件很大，电脑一次只能阅读1000个数据。
于是开始写了一个1000限制的程序。
说不对，我的1000只是比如， 用类似merge的想法做。
写了出来。
4) are you OK with th... 阅读全帖 |
|
M******9
发帖数: 10 | 4 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup都是late stage, 股票都是十万分之5-10, 感觉不好谈。LD目
前在一家大公司，说其实先去大公司几年也不错，比较稳定，貌似股票refresh也可能
不错，work/life... 阅读全帖 |
|
M******9
发帖数: 10 | 5 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup感觉不好谈。LD目前在一家大公司，说其实先去大公司几年也
不错，比较稳定，貌似股票refresh也可能不错，work/life balance比较好。我自己是
想去startup, 但... 阅读全帖 |
|
r*****n
发帖数: 35 | 6 case class TreeNode(value: Char, var left: Option[TreeNode] = None, var
right: Option[TreeNode] = None)
object TreeBuilder {
//recursive version
def recursive(input: String, start: Int): (Int, Option[TreeNode]) ={
if (start >= input.length) {
(start, None)
} else {
val cur = Some(TreeNode(input(start)))
if (start == input.length - 1) {
(start + 1, cur)
} else {
input(start + 1) match {
case '?' =>
val (loffset, l) = recursiv... 阅读全帖 |
|
a*****s
发帖数: 1121 | 7 回来查了一下没签NDA，应该没问题了。说是今天给通知，没收到说明是黄了。就是不
知道他家的打车费给不给reimburse，因为不太会用他家软件，给了100刀的coupon，要
求来的终点和回的起点时公司地址，自己设置的是公司地址，可是司机最后不知道怎么
给我稍微改了位置，结果就TMD charge了俺的信用卡。faint。
面的是体系结构engineer
还是老原则，哥没刷完题，就随便写过几道
电面是国人哥们，问的题目不难，属于leetcode的简单题一类的。记不得了。
onsite：
1. 国人哥们，典型的问了问以前以前做的什么，然后上题目，说一个未排序的整数数
组，找出所有的inversion，就是位置大但是value小的情况。例如：
9， 10， 1， 4， 100
那么应该返回4
先给了最白痴的解法，也就是n平方时间复杂度，然后主动提出可以优化，发现可能需
要排序，然后被提示说先试试merge sort，忘记了，想了一会，现自己动手写一个，没
写对，后来被提示说可以用递归，没时间了，把merge的顺序搞颠倒了，应该先二分逐
步递归，想反了。
2. 国人老板问了问behavior... 阅读全帖 |
|
发帖数: 1 | 8 Please take 60 minutes to work on this and send it back to me when you are
done. The test must be done in C++ and you must do a recursive solution.
/**
* The Fibonacci sequence is Fn = Fn-1 + Fn-2. Seed values F0=0, F1=1.
* Example: 0+1=1, 1+1=2, 1+2=3, 2+3=5, 3+5=8, ...
* Write a program that calculates the Fibonacci sequence, and then returns
all primes up to the nth prime Fibonacci number, where n is an
* option passed in on the cmd line.
* Example: In the above calculation - prime_fib 3 -> 2... 阅读全帖 |
|
t******l
发帖数: 10908 | 9 我终于明白了 logistician 的想法了，就是把我描述的 2) 给数学归纳法 recursive
back down to 1 蓝眼。
数学归纳法 recursive back down to problem-size_1 本身没有问题，但问题是把 “
外国游客的话” 也给 recursive back 回去。
矛盾在于，在这个 puzzle 里面，这个 “外国游客的话” 是看了 problem-size_n 的
结果而说的，所以是 “果”。。。但在数学归纳法里，是从 problem size (n-1) 推
出 problem size n，其背后的逻辑是 problem size (n-1) 作为 problem size n 的
“因”。。。关键是在这个 puzzle 里，只有 problem size n 是客观物理存在的，其
他的 problem size 1 to (n-1) 是数学归纳法证明过程中虚构的。
或者直观的说，外国游客是见证物理上客观存在的 problem size n 说了一句话。。。
而虚构 problem size 1 to (n-1) 那外国游客特... 阅读全帖 |
|
t*******r
发帖数: 22634 | 10 我去查了一下，发现素数这个 recursive definition 是正确的。
谢谢。
只是素数这个 recursive definition 确实不如素数非 recursive
definition 用得广泛，外加 recursive definition 的正确性
常常不是那么显而易见，俺半夜三更的就先有罪假定了一把。。。 |
|
t*******r
发帖数: 22634 | 11 “a是素数 <=> a是大于1的自然数, 且a不被任何不等于a的素数整除”
上面这个是正确的命题，但不能作为 recursive definition。因为无法 recur，
造成循环定义。
下面这个才是 recursive definition，因为这个能 recur：
“a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除”
这个是不是能 recur，对码工不太难，主要是码工写 recursive function
也是家常便饭。
那个英文版的素数 recursive definition 里面用词是 “if and only if”，
常常要那么写不容易有歧义。 |
|
t*******r
发帖数: 22634 | 12 不需要从小到大，刚才用从小到大只是说起来直观而已，并不是严格的说法。
关键的问题是在 recursive definition 里的 definition 的概念。
严格的说法，在这个 recursive definition 里，被定义的 “素数”（定义符号
左边），同时也出现在用来定义“素数”（定义符右边）。不要求从小到大，但要求
存在一个 context，在该 context 里面，定义符号右边的 “素数” 都已经被定义。
而且最终能够 recursive down，否则就是无法 recur。
recursive definition 广泛存在于计算机文法中。。。 |
|
d**********o
发帖数: 1321 | 13 第二次作业report
#+latex_class: cn-article
#+latex_header: \usepackage{CJKutf8}
#+latex_header: \begin{CJK}{UTF8}{gbsn}
#+latex_header: \lstset{language=c++,numbers=left,numberstyle=\tiny,
basicstyle=\ttfamily\small,tabsize=4,frame=none,escapeinside=``,
extendedchars=false,keywordstyle=\color{blue!70},commentstyle=\color{red!55!
green!55!blue!55!},rulesepcolor=\color{red!20!green!20!blue!20!}}
#+title: CS572 Project 2 Report
#+author: (me~~~)
#+begin_abstract
|---------------------------+------------... 阅读全帖 |
|
d**********o
发帖数: 1321 | 14 第二次作业report
#+latex_class: cn-article
#+latex_header: \usepackage{CJKutf8}
#+latex_header: \begin{CJK}{UTF8}{gbsn}
#+latex_header: \lstset{language=c++,numbers=left,numberstyle=\tiny,
basicstyle=\ttfamily\small,tabsize=4,frame=none,escapeinside=``,
extendedchars=false,keywordstyle=\color{blue!70},commentstyle=\color{red!55!
green!55!blue!55!},rulesepcolor=\color{red!20!green!20!blue!20!}}
#+title: CS572 Project 2 Report
#+author: (me~~~)
#+begin_abstract
|---------------------------+------------... 阅读全帖 |
|
Y**u
发帖数: 5466 | 15 ☆─────────────────────────────────────☆
Yisu (大头教主) 于 (Mon Nov 7 10:23:28 2011, 美东) 提到:
发信人: allanzc (品质保证), 信区: Joke
标 题: 现在的考题很强大啊
发信站: BBS 未名空间站 (Tue Nov 1 15:24:24 2011, 美东)
。。。
☆─────────────────────────────────────☆
Yisu (大头教主) 于 (Mon Nov 7 10:24:27 2011, 美东) 提到:
这个题真的很有意思。。。转过来看咱们这里有人会做不？
☆─────────────────────────────────────☆
TrueStory (不是幸福的坑不挖) 于 (Mon Nov 7 10:47:02 2011, 美东) 提到:
Per "Inception", use a spinning totem. :-) It surely will fall down, so this is not a ... 阅读全帖 |
|
w*r
发帖数: 2421 | 16 此例中只有三行，所以答案的列是4(3+1)列，结果应该是3!=6行，如果有四行，答案是
5列 4!行
如果要求是答案中abc/abc在一列里面，那么就要求有RECURSIVE CALL 做character
sequence permutation
如果知道一共输入有多少列（列数确定）可以简单的做inner join
CREATE VOLATILE TABLE t (
KEY1 VARCHAR(1),
KEY2 VARCHAR(3)
) PRIMARY INDEX(KEY1)
ON COMMIT PRESERVE ROWS;
INSERT INTO t VALUES('A','GTL');
INSERT INTO t VALUES('B','GTL');
INSERT INTO t VALUES('C','GTL');
SELECT T1.KEY1,T2.KEY1,T3.KEY1,T1.KEY2
FROM T T1
INNER JOIN
T T2
ON
T1.KEY2 = T2.KEY2 AND
T1.KEY1 <> T2.KEY1... 阅读全帖 |
|
t****n
发帖数: 10724 | 17 *******************************************************************
HR SQL难题的三种解法
*******************************************************************
摘要
本文综合描术了针对养老院人事难题的多种SQL解法。
鸣谢
Beijing
===========================================================
解法1 -- Partition 法
===========================================================
可以参考wyr解法，本解法用了lead/lag，以及ROWS UNBOUNDED PRECEDING A... 阅读全帖 |
|
P***t
发帖数: 1006 | 18 I think proof is better than arguing. So I changed tjq's program a little bit
to do a comparison:
Here is the result: with M=11, N=30, compiling with VC 6, SP5,
With optimization as Max speed,
==================
recursive
Time 1952
non-recursive
Time 1503
Count 54627300
recursive is 450 ms slower than non-recursive. But this is in when we almost
did nothing with the result (in the function "output", uncomment the return).
If I just do a sum over all data in output, the result is:
=============== |
|
i**********e
发帖数: 1145 | 19 呵呵
不好意思 漏掉了if 不能用的条件
你的解法很好啊 也同样是 recursion,但是不同的是把 run time recursion 变成
compile time recursion.
既然是 compile time recursion，你的解法只能规定于 n 是 constant 的前提上使用.
如果 n 是 variable 的话，该怎么办呢？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
H****S
发帖数: 1359 | 20 You would have to rely on trampoline to convert recursive call into tail
recursive loop. With some overhead of memory and GC, this is not the end of
the world. As a bonus, you would be able to understand more deeply about
recursion as well.
I forgot to mention, golang do you even realize recursion is a problem at
all? |
|
s**********k
发帖数: 934 | 21 发个长点的report, for 这有意义的一天。
周四临时起意决定去钓鱼，拉上了zeal, wyseu, recursive. 周6早上8点钟上船，一
开始很不顺利，先是船马达有问题，声音很响就是跑不快，觉得也就是平时一半的速度
。听lint说神奇的6号点早上有点slow,就决定先去boomer看看。然后就是一边开船一边
收拾东西，抬头一看，ft,开过了。 然后又吭哧吭哧往回开，不知道的还以为我们是从
santa cruz开过来的..到了boomer reef已经半个多小时过去了.甩了几杆，除了zeal上
了条幼齿，基本没咬口。然后决定换个位置试试,结果又悲剧了， 船怎么都拉不起来。
没办法，打电话让船老大过来救驾，又浪费了半个小时.一切的一切预示着这会是今年
钓鱼以来最悲惨的一天...
又试了几个以前的钓点还是很slow,决定开发新钓点。抬头远望，看见green house
前方无数渔船，场面十分壮观，当时就觉得是在围剿seabass. 不过开始觉得seabass和
我们没什么关系，只是过去看看是不是也能钓到cod. 新钓点飘了几回，有收获，无惊
喜。转折点是recursive... 阅读全帖 |
|
s***h
发帖数: 487 | 22 你这个理论数学系的，迭代在马工语言里是 iterative solution? 区别于
constructive solution？
马工都是直接说 stack based vs recursive function call based，没有你们数学系
这么扭扭捏捏的害羞的说法。
: 你看懂我说的东西没有啊？迭代就是用stack来做啊，不要给我倒这些高深的名
词，来
: 点简单的。
: recursive
: recursive
|
|
s***h
发帖数: 487 | 23 Recursive-function-call based graph traversal 跟 stack based graph traversal
在算法概念模型上有不少差别我想。
Recursive function call 是基于 non-overlapping subproblem 的编程概念。所谓
Preorder / inorder / postorder 就是 traverse non-overlapping subproblem 的
order。这个数学美，但有局限。
Stack 在编程概念上并不小矮挫，stack 的学名叫 LIFO ，对应的其他还有 FIFO，以
及更通用的 priority-queue (heap)。
: 不是叫iteration based traversal么？我没看哪个刷题网上用stack based来讲
，再说
: 了recursive的原理上不还是stack based么？只不过这个stack不用你费脑筋去
管理而
: 已。
|
|
g********d
发帖数: 19244 | 24 ☆─────────────────────────────────────☆
shuangseyun (shuangseyun) 于 (Tue Jun 21 15:49:00 2011, 美东) 提到:
老公坐别人的车，结果司机把车开翻了，所幸两人都没有大碍，不过老公的眼镜不见了
，脚受了伤，肿了。偏巧定了这周末出去玩的，机票和旅馆都定了，旅馆倒是可以
cancel，不知道损失的机票和重新配眼镜的钱保险公司可以cover么？那个司机只买了
liability。
谢谢！
☆─────────────────────────────────────☆
siulam (小林) 于 (Tue Jun 21 15:52:39 2011, 美东) 提到:
司机是朋友吗
☆─────────────────────────────────────☆
imrobot (robot) 于 (Tue Jun 21 15:53:05 2011, 美东) 提到:
出租？还是bus？
☆─────────────────────────────────────☆
shuan... 阅读全帖 |
|
g*******y
发帖数: 1930 | 25 The best way is to convert the recursive version to an equivalent non-
recursive version using explicit stack to simulate function call stack
you may see the original code for recursive version as a reference to understand my code |
|
l*f
发帖数: 218 | 26 我想了一下，是这样的
int recurse(int aStartIndex, int bStartIndex, int k){
if(k=1){
if(A[aStartIndex]>=B[bStartIndex])
return B[bStartIndex];
else
return A[aStartIndex];
}
else{
int aHalfK = A[aStartIndex+k/2-1];
int bHalfK = B[bSTartIndex+k/2-1];
if(aHalfK>=bHalfK)
return recurse(aStartIndex,bStartIndex+k/2,k/2);
else
return recurse(aStartIndex+k/2,bStartIndex,k/2);
}
}
O(logK) |
|
f****4
发帖数: 1359 | 27 Reverse a linked list iteratively, do it first with single pointers and then
do it again with double pointers. Now do it again recursively but not tail-
recursive, and then do it again tail-recursively. What do you do if it has a
loop?
http://cpuzz.blogspot.com/2005/07/reverse-single-linked-list-using.html
第一个问题的解，真要是面的时候给问到，脑子一下没转过弯来，肯定答不出来。。。 |
|
z*j
发帖数: 42 | 28 Amazon:
First round:
1. C++ and OO questions
2. Write a linkedlist support append at tail
3. Given a linkedlist, find duplicate elements
4. Given a linkedlist, group by different elements
Second round:
1. C++ and OO questions
2. Reservoir sampling
3. A brain teaser
4. design pattern
Onsite:
OO and C++ questions
Recursion and non-recursion version code. like reverse linkedlist, post-
order traverse a tree, permutation. (I found Amazon likes recursion a
lot. Almost each interviewer asked me about |
|
f*******r
发帖数: 1086 | 29 大家都知道有一个简单的singly linked list面试
题目就是reverse singly linked list.
在与MS欧洲电面的过程中，interviewer要我online
coding出这个函数，我因为之前都复习过，很快
写了一个recursive 版本的代码:
SLNode* head;
SLNode* Reverse(SLNode* root)
{
assert(root!=NULL);
if(root->next!=NULL)
{
Reverse(root->next);
root->next->next = root;
return(root);
}
else
head = root;
}
当时想法是代码简洁一点，但是interviewer看过后
问我如果用recursion的话，会有什么问题？经提示
才想到，recursion会使用stack memory，当链表
的节点非常多的时候会有问题，这个的确是开始写
这个函数的时候没有考虑到scales上的问题， |
|
UD
发帖数: 182 | 30 below code seems to work, and should be O(n) time and O(1) space, if you disagree, please list your argument.
The idea behind is the use and resue of sum(i,j), that's why the O(1) space.
sum(i,j)=sum of all the 1s between i and j.
sub-seq(i,j) has equal 1s and 0s when sum(i,j)*2=j-i+1, we start by setting i=0,j=A.length-1, then searching from both ends.
1. if sum(i,j)*2==j-i+1, then found it
2. else if sum(i,j)*2>j-i+1, we have more 1s then 0s, then we check A[i] and A[j]:
a. if A[i]==A[j], t... 阅读全帖 |
|
s*********l
发帖数: 103 | 31 You don't need to compare current combination with old ones.
You just make sure each combination is sorted, for example,
7 = 2 + 5 (ok)
= 4 + 3 = 2 + 2 + 3 (ok)
= 5 + 2 (not ok, 2>5)
= 2 + 3 + 2 (not ok, 2>3)
Please see my Python code at
http://fayaa.com/code/view/16593/
There are two versions, one is naive memory-less recursion, another is recursion with dynamic programming which is much faster.
A non-recursive solution would be even better. |
|
g*********s
发帖数: 1782 | 32 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
时间复杂度，如何优化。
recursion?
is_equal(root1, root1) ::= root1->dat == root2->dat &&
(is_equal(root1->left, root2.left) && is_equal(root1->right, root1-
>right || ... //swap case).
each node can at most trigger 2 swap ops. so worst case 2n? not sure if
a swap on one parent and a swap on its kid would cancel each other.
complexity exponential?
optimization: traverse the tree to calculate the size of each sub-tree.
check the sub-tree size before recursive call.
3.... 阅读全帖 |
|
s********y
发帖数: 161 | 33 刚面完，回到酒店。上帝保佑明天拿到给offer。感谢祝福。签了NDA，不过以下应该也
没有泄露亚麻的技术秘密...
网络服务组
Common questions几乎每个人都会问到, why 亚麻, why web service, your
experience/work.
Phone 1 别的组的老美
两个数组求交集。如果已经排好序了，一个数组很大，一个很小怎么办。如果数组都很
大，内存放不下，怎么办。
设计扑克牌。扑克牌shuffle算法。
两个整数，需要多少步才能把一个数的二进制表达转换到另一个数的二进制表达。 （
XOR后数1）
Phone 2 本组的印裔
设计LRU Cache, 然后讨论多线程访问Cache的问题。面完后实现Cache发代码给他。
Onsite见了7个人，每个人45分钟，连轴转。上午10点半进building, 下午4点出来
Onsite 1 很Nice的老美
讨论设计web crawler， coding BFS， 讨论多线程处理crawler等。
Onsite 2 印裔
OOD机场air traffic control system.
Onsite 3 ... 阅读全帖 |
|
b***e
发帖数: 1419 | 34 这个不用联合，就是二分法。找一个pivot, split一下：
pre_array, pivot, post_array
如果
1. pre_array.length < pivot，那么空子在前面，recursion on pre_array。
2. 否则空子在后面，recursion on post_array。
这招不能直接搞重复的情形。如果哦有重复，可以两招一起用:
2. 如果ihasleetcode_method(pre_array)找到的空子，return; otherwise,
recursion on (post_array).
这个不丢信息，而且期望为O(n). |
|
c*****t
发帖数: 13 | 35 本人CS硕士名校非牛人,一年前去了一家中型软件公司做SD,不喜欢,刚刚跳去一家小HF.面试
的过程好像西游记一样,路途遥遥,艰险不断,怪物层出不穷,自己的本领也日渐增长,2年来承蒙
版上各路豪杰照顾分享,今日也算有个结果;特此拿出小弟所见所闻共勉,纪念找工作的艰辛,愿
大家早日心想试成,取到真经!
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
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..... 阅读全帖 |
|
P**********c
发帖数: 3417 | 36 我onsite也遇到过类似情况，也是recursive程序。怎么解释对方也不信，我又不能说我准备过。我是觉得interviewer要是觉得自己recursive没有那么好，还是不要问
recursive的问题比较好。这种程序很tricky, 如果理解不是那么深入，用来判断别人
风险还是挺大的。
当然我还是觉得你这个问题不大，个人觉得G的onsite不难拿，不需要让面试官觉得一点错误没有。但是onsite真的很难，不知不觉就被据了。
又没有足够的时间。大家说这种情况怎
, |
|
s*********b
发帖数: 815 | 37 为啥扯到DP啊？regex的匹配是lexical analysis常见算法。常见算法里，要么就上
Regex -> NFA/DFA加记忆（也就是说DP最多是优化技巧），要么是Tompson's
algorithm, 要么就是recursive decent。谁说Recursion就一定慢来着？The Practice
of Programming里的mutual recursion对付面试足够了。 |
|
s*********b
发帖数: 815 | 38 为啥扯到DP啊？regex的匹配是lexical analysis常见算法。常见算法里，要么就上
Regex -> NFA/DFA加记忆（也就是说DP最多是优化技巧），要么是Tompson's
algorithm, 要么就是recursive decent。谁说Recursion就一定慢来着？The Practice
of Programming里的mutual recursion对付面试足够了。 |
|
i*******n
发帖数: 114 | 39 nvidia interview experience
location:
NVIDIA
San Thomas Expressway, Santa Clara
duration
2 hours, 1PM to 3PM
2 interviewers, each for 1 hour
------------------------------------------
cdj
xor eax, edx
sub eax, edx
问我这段代码干嘛。就是算负数的补码(Two's Complement)，正数没变化
logic puzzle,
4 fuses, each fuse burns out in 40 minutes, create a fuse that can burn
in
20 minutes. slightly flawed problem. Because when you burn the fuse from
two
ends, it is not exactly 20 minutes. (Two combustion points are
certainly
faste... 阅读全帖 |
|
v***n
发帖数: 5085 | 40 recursion是系统帮你管理栈
non-recursion实现得自己管理栈的
问题在于recursion实现的话怎么去遍历栈呢？ |
|
r****t
发帖数: 10904 | 41 来自主题: JobHunting版 - 问个SQL 不知道 recursion 是不是必要的，按前面说的 recursion 了一下，(free RDBMS里面
只有 postgres 支持，sqlite/mysql 不支持)
with recursive
relation as (ItemID, ItemName, ParentID, Level) as
(select ItemID, ItemName, ParentID, 1 as Level from Item
where ItemID = 1
union
select ichild.ItemID, ichild.ItemName, ichild.ParentID, relation.Level+1 as
Level
from Item iparent, Item ichild, relation
where iparent.ItemID = ichild.ParentID)
select * from relation; |
|
S**I
发帖数: 15689 | 42 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 01:52:31 2011, 美东) 提到:
Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
nodes in the path from root to Y - sum of nodes in the common path from root
to first common ancestor of the Nodes X and Y
☆─────────────────────────────────────☆
SecretVest (Secret Vest) 于 (Tue Jun 21 04:01:30 2011, 美东) 提到:
not hard if someone is used... 阅读全帖 |
|
w****x
发帖数: 2483 | 43
哦, 我的分类里recursion大概有30个, 和binary tree相关的题很多是recursion, 你
解释一下backtracking和recursion的区别?? |
|
z**********8
发帖数: 229 | 44 2.2 Implement an algorithm to find the nth to last element of a singly
linked list.
这题我的直觉就是两个指针然后保证两者的距离为n，跟它给出的标准解法一样。但是
他有这么一段话：
“Note: This problem screams recursion, but we’ll do it a different way
because it’s trickier. In a question like this, expect follow up questions
about the advantages of recursion vs iteration.”
实在想不出recursion的解法，可以求达人解释一下么？（如果用两个指针的话应该空
间复杂度是O（1）时间是O（n），n是链表长度。用递归可以做的更好么？advantage在
哪里呢？） |
|
p*i
发帖数: 411 | 45 这些都没关系的。
俺就遇到过这样的面试官，本来写的iterative的已经最优了，除了代码稍微多几行
人一定要找出俺的问题，说俺的代码不好看，为什么不用recursion，然后吧唧吧唧吹
recursion多好多好
后来发现此人不知道很多recursive的算法可以改造成iterative的 |
|
f*********m
发帖数: 726 | 46 Print All Combinations of a Number as a Sum of Candidate Numbers
（http://www.leetcode.com/2010/09/print-all-combinations-of-number-as-sum.html）
原文如下，稍作修改（把target 从7该为9）：
“To search for all combination, we use a backtracking algorithm. Here, we
use the above example of candidate={2,3,6,7} and target=9.
First, we start with a sum of 0. Then, we iterate over all possibilities
that can be added to sum, which yields the possible set of sum={2,3,6,7}.
Assume now that sum=2, we continue adding all poss... 阅读全帖 |
|
p*****2
发帖数: 21240 | 47
recursion其实还算简单吧？工作中不用是因为performance和不能scale的原因吧？
我刚工作本来可以用recursion来解决的，结果不让用，只能自己写个queue来解决的。
面试的时候recursion应该比BFS更简单呀。 |
|
j******2
发帖数: 362 | 48 一直以为DP就是store了之前结果的recursion。但是看到150第五版里，把18.12（最大
和的submatrix）归为DP&recursion（在9章末提到）。18.12显然没有递归，是在
iteratively利用之前的结果。所以是否DP就是recursion or iteration with stored
results?
但是18.11（最大的黑边square）里面，第二种方法把右、下的黑像素个数存储起来的
过程，跟18.12非常相似啊，iteratively using previous results，但是却没有算成
DP。
所以DP的特征究竟是什么？ |
|
r******n
发帖数: 170 | 49 跨度半年，中间的郁闷压抑各种负面情绪相信大家都懂，总之就是一句话：坚持就是胜
利！
背景非CS PhD，本来想走学术道路的，种种原因还是决定去工业界，编程基础还行，没
有系统练过。career path上来了个U turn，基本每家公司都会问原因，建议类似情况
的准备好答案，顺便提一下你理解的工业界学术界的不同，你有什么长处，挑战在哪，
你会怎么克服 blablabla，反正让人觉得你不是头脑一热，是做足准备的。
找工作初期，真正dream company不敢轻举妄动，想先涨点经验值再说。于是简历挂上
monster，linkedin, efc, 再搜一两个关键词一阵乱投，可惜专业限制，这样投出去也
不过十来个。之后倒是接了东边几个猎头的电话，都是找quant的，先上来就警告说目
前这一块有点疲软，机会不多，都倾向找有经验的，而且招聘流程比较慢。说是能帮我
投手边现有的职位，列了几家说的上号的公司，然后就石沉大海了。
三周过去了，没有任何动静，开始急了。频频上jobhunting版，找找别人报面试或者
offer的公司，发现bloomberg和epic这两个据说对非CS专业友好的公司，... 阅读全帖 |
|
l****c
发帖数: 782 | 50 我也不是很清楚，题就是这样些的。
dfs，不也需要一个visited来记录吗？那就是需要走两遍了。
我的理解是用recursion的in order遍历。要是non-recursion就需要stack了，就有节
点走了2遍；recursion的算不算1遍呢？ |
|
