r****o
发帖数: 1950 | 1 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: roufoo (五经勤向窗前读), 信区: InterviewHackers
标 题: 请问一个关于递归算法的问题。
发信站: BBS 未名空间站 (Fri Apr 30 11:19:46 2010, 美东)
很多算法可以用递归实现，非常简洁，比如说二叉树的遍历。
但是通常面试的时候也会让实现一个非递归的版本。
我想问的是，非递归的版本相对于递归而言有什么优势呢？
一个方面可能是递归程序会占用系统栈资源，如果递归层次太多，会耗尽系统栈。
但是通常非递归程序也是会用一个stack，如果递归层次太多，这个非递归程序的stack
的size应该也会很大，这不也会耗系统栈资源吗？
请各位大牛指教。 |
|
z****e
发帖数: 2024 | 2 是一个基于quick sort，但是具有探查机制的算法，一旦检测到出现二次方增长倾向，
就自动改为insertion sort。
对于一个general sort算法，几乎STL 的sort已经是目前最快的。 |
|
s******y
发帖数: 172 | 3 大家好。我是EE背景，作了几年工程计算方面的软件，用C和C++。
用过一些数值计算的类库，但没搞过CS的算法。现在需要找新工作。想先把算法的基础
打扎实，再好好学学设计模式。
在版上看了看，好象CLRS的书太理论了。打算看Robert Sedgewick的Algorithms in C
或者Algorithms in C++。从学习的角度，用C的版本是否更扎实？
谢谢！ |
|
s*******n
发帖数: 1018 | 4 看了很多讨论算法的帖子，感觉大家都好牛，我怎么就想不到。需要好好恶补一下了。
所以想知道哪里能够找到比较集中的算法和数据结构的练习题。重新复习书本来不及了。大家有何建
议？
谢谢先！ |
|
h**k
发帖数: 3368 | 5 第一题的算法不对。按你这个思路，对于H[i]，你必须比较所有的H[j]和H[i]，来找到
高度为H[i]的矩形的左右边界。这样复杂度是O(n^2)。正确算法是用stack。
第二题的brute force是O(n^6)，最后利用第一题的思路，可以到O(n^2)。 |
|
m***n
发帖数: 2154 | 6 说实在的，应该不需要吧。。 而且高深算法很多人都搞不懂吧。。
常规算法知道怎么回事就行了，要用还不如搜索一下，直接套上去，呵呵
我也面试过不少人，看起来题目都会做。。其实草包的很，呵呵 |
|
r***8
发帖数: 86 | 7 两海盗在分金币，金币放在N个瓶子里， 每个瓶子放有金币，瓶子放在一排，两海盗
都知道每个瓶子放的金币数目，分的规则是这样的，每个海盗呢只也取边上的一个瓶子
，第一个，或最后一个。
请你写一算法，帮其中一海盗获得最可以多的金币，前提是两海盗可是一样的聪明啊。
给出算法复杂度，能用O（N*N）写出吗？ |
|
E********a
发帖数: 124 | 8 我主要的意思是，问算法coding题的目的，是想找头脑灵活善于思考解决问题，而且有扎实编程基础的
人，因为这样的人做项目时能很快上手，能做好项目，我也希望与这样的人共同工作讨论问题。
即便是有几年经验的人，我觉得善于思考解决问题这一点仍然是很重要的，因为他的经验很可能用不
上，就算他的职位跟经验match，他以后换组呢，以后遇到他没经历过的问题呢? 况且我们这里是
general hiring，candidate以后来什么组都还不知道，所以除非是candidate特别擅长某类
领域，in general我们希望招解决问题能力强的人，做什么都能上手。
问算法题，其实只是一个手段。虽然说，有的时候，是不太容易做出公平的评价， 对于 一个头脑灵
活的人面试的时候因为紧张或者想偏了等原因没发挥好 vs 一个因为做了充分准备和练习/做过原题而
发挥好的人。
TC2186去MS是可惜了，好歹也去个FB啥的，现在不就爽了。 |
|
i**********e
发帖数: 1145 | 9 我觉得算法固然重要，但是如果你聘请一个人完全取决于他的算法能力，那也太说不过
去了。
我觉得一个好的程序员除了需要有很好的problem solving，更重要的是他对你们公司
做的项目到底感不敢兴趣，有没有热忱。就算有幸给你聘请到，如果他天天来上班对你
们做的项目不感兴趣，那这是公司要请的人吗？
况且，一来就给面试者出DP题，我觉得作为面试题也太过了。毕竟DP题不是很多人懂，
而且要有DP的思路是需要经过不断的练习和总结才训练出来的。要知道身为面试的人会
比平时紧张，思路很容易就不清楚，然后陷入更紧张的状态。
我觉得一个好的面试题应该是有多种解法的。可以很容易想到brute force的解法，但
是也有不那么明显的方法来优化。可以先让面试者以brute force写代码（brute force
的代码不一定都很直接，也有存在很多陷阱，不容易写对的情况）。这时候面试者已经
放松一些了，才更深入地问怎么优化等等。这样我觉得能让面试者比较正常发挥自己的
水平。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
solving |
|
g***s
发帖数: 3811 | 10 算法真正的掌握是让它变成你思考的一个方法，而不是死记。
就像贪心，其实没学过算法的人很多也能直接想到贪心。
动态规划也一样，变成你的思想的时候，就算10年没做，回来还是能马上pickup。 |
|
|
w***o
发帖数: 6775 | 12 我知道算法导论。可是我时间紧，又没有系统学过这门课，需要从头看起。是不是除了
算法导论就没有别的选择了 ？btw, 我一般用c++ |
|
r*********4
发帖数: 183 | 13 小弟初到本版。。想问下各位大侠。。用什么语言学习算法最有效呢？ 看板上大家都用
C++/Java/C#,但是小弟平常做研究是用MATLAB/Python. 所以比较困惑，本来想用C++做
Research，但是老板说不要用C++，用MATLAB/Python来做。 这让我很困惑，因为看面
经，似乎大
家找工作都是用C++/Java/C#来实现算法。。那我是不是应该马上转手用C++呢？好久没
用了。。还是
本科毕业设计用了下。。。
谢谢。。 |
|
H******7
发帖数: 1728 | 14 你搞神马方向的？用MATLAB PYTHON做RESEARCH？好奇。
算法是要用C/C++来准备的。这个毫无疑问。你用MATLAB回答算法题也达不到要求啊。 |
|
z****o
发帖数: 78 | 15 的确消除一个相交可能会造成更多的相交，但是“此解错误”的结论太轻率了。
Let me prove it!
程序有穷性：
Lemma 1. 每次交换操作使得被交换的两条线的总长度减小。
交换之前 B1-R1 与 B2-R2 相交， 可以看作是四边形 B1-B2-R1-R2 的两条对角线。
交换之后 B1-R2 与 B2-R1 不交， 是这个四边形的一对边。
易知： 对角线长之和 > 任意两条边长之和。得证。
Lemma 2. 在有限次执行之后算法会终止。
由Lemma 1 可知每次交换操作使得所有边的总长度减小，而所有边的总长度一定大
于0，所以在有限次执行之后算法会终止。
程序正确性：
由 终止条件 知，终止时必不满足“存在一对相交的线”。则正确性可知。 |
|
x*****p
发帖数: 1707 | 16 zhshao的数学功底不错，是学数学的么？
不过算法功底不好，所用的证明方法，估计完全能看懂的人不多，但这个方法实际上是
证明了解的存在性，而相应算法的复杂度就相当高了。
所以我说此解错误。 |
|
g***s
发帖数: 3811 | 17 其实你的证明也是证明了用最大（小）流算法的正确性，也就是lfbenben 提到的
vehicle
pickup/deliver解法。
二分图的最大（小）匹配问题,算法复杂度其实是O（n＊m）＝O（n＾３） |
|
n********7
发帖数: 73 | 18 我觉得基本上如果是entry level的话，公司就不太期待你懂太多.Net，毕竟学校里教
这个的很少，那算法啥的就会占多数咯。反过来如果是已经有.Net的经验写在简历上，
那估计就会少问算法了 |
|
h****b
发帖数: 25 | 19 来自主题: JobHunting版 - 问个算法题 一个amazon的算法题描述如下（在以前的面经里面看到的）：
boggle游戏的问题：给定一个4*4的矩阵，每个
位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
这个题目感觉下code的话很难写的啊？ 如何用DFS或者递归的话 如何避免访问重发的
元素了或者避免Loop. 还有的话用用DFS的如何构造图呢？ 感觉DFS找一个valid word
比较容易， 找出所有的words 感觉太复杂了。大家有什么简洁的算法？。谢谢了 。。 |
|
g**e
发帖数: 6127 | 20 using young tabelau is clearer.
这个特殊的young tableau求前k个最小值以前讨论过，一直没有更好的算法，没有利用
到这个特殊young tableau的属性
求O(n)算法
m
is
里。 |
|
g***s
发帖数: 3811 | 21 个人觉得KPM算法没有必要熟到能写出来。
只要告诉面试官你知道有这个算法并且知道复杂度就可以了。然后写一个其它简单的算
法即使用O(mn)。 |
|
l*y
发帖数: 21010 | 22 你可以换一个别的算法啊
KMP在实际应用中本来就不如boyer-moore算法
人家可能只接触过后者
要。 |
|
s**********l
发帖数: 757 | 23 比如工资8万，交税3万，拿到手5万，是哪种算法算出来的？
1.先确定工资8万，再按照一定的百分比计算要扣除的tax，然后salary-tax=5万。
2.先确定net income=5万，再按照一定的百分比计算要交的tax，然后net income+tax=
8万
哪种算法正确？ |
|
c**********e
发帖数: 2007 | 24 Given two arrays, each with distinct integers, give an efficient
algorithm to find out the common elements.
显然我们可以对两个数列进行快速排序。但有更简单的算法吗？ |
|
a********m
发帖数: 15480 | 25 刚毕业的cs蔡鸟在算法上比有经验的人占了很多便宜了。。。。你有20年经验的时候会
发现考的还是学校里面学的那些算法，那时候你记得绝对比刚毕业的时候差得多。 |
|
b*******a
发帖数: 68 | 26 xyf501 (Ivan) 帖子中提到的G面试题目，请问正确的算法？xyf501 (Ivan)提到的贪吃
蛇算法能展开说说吗？谢谢了
一个吸地毯的irobot，和一个长方形的屋子，四面有墙，四个指令：
Bool moveForward（）//向前走一格，走不了的话返回false
Void Rotate（int degree）//就是左拐右拐
Bool isClean（）//当前单元格是否干净
Void clean（）
把irobot 扔在屋子任意位置，写代码让irobot清理房间，每一格都要走过（单元格没
有坐标）。 |
|
d*******l
发帖数: 338 | 27 我现在觉得面试要考察的有知识的掌握，临场应变，交流沟通能力，背景的匹配程度等
多方面，解算法题只占一小部分。像楼主说的那些问题都是边界比较多的，快速写出来
全无bug非常困难，三分数组要是在平时我一定倾向于用两次典型的qsort的partition
来做到，这样不容易出错。atoi我也不会一上来就处理溢出。
我现在觉得算法水平在所有人中达到90%就不错了，再往上提高很不容易，还不如用来
准备design或者是别的问题。临场的时候能展现出真实水平我就很满意了。 |
|
J**B
发帖数: 204 | 28 经常看到版上有牛人面试说个算法出来，还要求计算下O（）。junior level （JAVA）
的工作，那些算法必需要会的？ |
|
a**n
发帖数: 313 | 29 不是面试题, 求整数对排序算法
我有一些整数对 { (1,4), (2,7), (1,5), (5,7), (5,9), (4,7) …}
最后排序成 {(1,5), (1,4), (2,7), (4,7), (5,9), (5,7) …}，具体是先按第一个数
字排升序，如果相同则按第二个数字怕降序，有没有有效的快速的算法。
谢谢了. |
|
a*****n
发帖数: 158 | 30 倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
果好象也不对 。。。。 |
|
w**z
发帖数: 8232 | 31 不是我们想做算法。是现在面试只考算法，白板coding |
|
P**********c
发帖数: 3417 | 32 发明花了很多年的算法要求你知道也不过分啊。又没让你发明。比如
一道题受过算法训练过的人知道它大致是用DP做，然后按照DP的套路解出来
跟他发明DP有天壤之别。 |
|
f*******s
发帖数: 451 | 33 小弟只上过一学期的数据结构课，踉踉跄跄地用 Java 做的作业。想问一下什么样的水
平可以开始复习算法题了？用不用把Mark Allen Weiss 的 Data Structures and
Algorithm Analysis in Java 先做一遍？
大牛能不能指点一下练习算法题的循序渐进的教材和题目来源。谢谢。 |
|
C***U
发帖数: 2406 | 34 来自主题: JobHunting版 - 问道算法题 算法导论里有详细算法
用recursion
对任何k都可以。
n) |
|
h********e
发帖数: 1972 | 35 算法。你去做pku online的题目吧。从1000开始做起。
如果没有算法基础，那就要先从排序，查找，字符串处理，数据结构中的树，平衡树，
堆，桶 这类东西开始了解起。 然后才是分治，动态规划，贪心，图，图的DFS之类的
。 写程序避免使用任何stl，全部用自己的数据结构。 |
|
w****f
发帖数: 684 | 36 谢谢，swan。
这种算法好像对占memory较多，有无更好的算法？ |
|
c*******i
发帖数: 160 | 37 自己本科ee的, 算法书自己觉的看书自学就好了,想选点比如machine learning, data
mining的课.
但又怕别人看我研究生不是cs, 没上过算法不给面试.
大家说说? |
|
b********e
发帖数: 386 | 38 这些都是多多益善，工作中都很有用，但从面试来说不如算法根本。
对付面试,主要是两方面
1： 对算法和数据结构的掌握
2： 对一门面向对象的语言比较精通
最后就是手熟而已了 |
|
t*********7
发帖数: 255 | 39 个人经验...会做算法不等于会写代码.做产品跟做算法两码事啊... |
|
g**********y
发帖数: 14569 | 40 这种太固定的套路，不会被直接问。但是你最好知道算法的思路。大公司问到这种写程
序很长的情况，他们会让你用例子讲算法，不用写代码。
这是很经典的问题，你要见到它的变形，一点思路都没有，显然也不太好。 |
|
w********d
发帖数: 7 | 41 QQ 群号：229623621 特此诚邀您加盟
群成立之初，有超过100位同仁加盟，经过统一群名片和实名验证现优化为60位
群内有全球Top500 ACMer 三位，Google Amazon Ms 同仁数位
群刚刚成立，正在积极调整优化，力争实力稳步提升，为加群的同仁提供实实在在的帮助
另外也要诚意致歉之前因为无互动，没改群名片被请出的同仁，欢迎你们随时回来，群
的大门永远向你们敞开。
算法为王，数据结构更为王冠上最璀璨的宝石
高手优先，低手有热情有动力有悟性有恒心，任选其一同样优先
很多时候人的智力到达一定阶段，是否能实现本质的飞跃，就要看你周围的人的成色和
能量；这个群就是你身边最优秀的一群人，是每天与你相伴的自己人
实时交流，共同进步
给大家足够的动力思考新问题，尝新难问题，攻克重要问题
群号：229623621 |
|
C***U
发帖数: 2406 | 42 我说的算法对不对我不说。我的意思是他说的的不是我的算法得反例
目前都还没有正确解。他的解法（greedy DP)也不对，反例是4 4 4 9 9 9 88 88 88
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
|
r*****e
发帖数: 792 | 43 还没有考虑怎么去实现，因为不知道用什么方法更好，我其实也不知道
那个lazy的算法，DP的也还没想明白。你这个给重复数字计数的办法是说
比方有312211，你就数有两个2，两个1吗？这是不是BF的思想？
感觉上应该有什么好的算法利用起前面的结果。
另外，这个输入为n是怎么理解？1, 11, 21, 1211, 111221，这里的1211
是输入为4还是2的结果呢？ |
|
h*****3
发帖数: 1391 | 44 第二题有啥好算法啊？我能想到的就是从1开始好好算，算到n。
第一题也没啥好算法吧？就是不停的求combine（n-1,k-1)? |
|
d**e
发帖数: 6098 | 45 【 以下文字转载自 WaterWorld 讨论区 】
发信人: nudu (nudu), 信区: WaterWorld
标 题: 两年从MIT拿到PHD的罗马尼亚算法领域天才29岁去世！
发信站: BBS 未名空间站 (Sat Jun 16 12:56:36 2012, 美东)
算法界的罗马尼亚天才Mihai Pătraşcu 6月5日因脑癌去世，还不到30岁。
2007-2008 MIT Ph.D
2006-2007 MIT Master of Science
刚获2012年Presburger奖（青年理论计算科学顶级奖），在数据结构下限等基础领域有
突破贡献。信息学奥林匹克IOI界的名人，多次获得奖牌。MIT博士，师从神童教授Erik
Demaine（没读中小学12岁上大学20岁博士毕业） |
|
b******v
发帖数: 1493 | 46 【 以下文字转载自 Topcoders 俱乐部 】
发信人: bokertov (早上好), 信区: Topcoders
标 题: 找min cut的解有什么简单的算法吗？
发信站: BBS 未名空间站 (Wed Jun 20 17:36:56 2012, 美东)
书上一般先介绍怎样找max flow的解，然后说max flow和min cut的等价定理，不过好
像都没讲怎样具体怎样找min cut的解呀？有没有比较简单的算法？ |
|
z*****5
发帖数: 1871 | 47 想搭车问问面试时对算法复杂度有哪些要求。现在懂一些基本算法和数据结构，但分析
复杂度还不太会，感觉有点难以理解。如何才能较快的补习？ |
|
Y********f
发帖数: 410 | 48 O(N^2)算法：
先算出对所有i>j, i到j的区间的最大最小值，需要二维数组。这个可以O(N^2)做到
然后计算一个一维数组，其值是到该位置为止最长的无重复元素的子数组元素个数。这
个可以O(N)做到。
再利用如果一个数组没有重复元素，其最大值-最小值=元素的个数-1 算出最长的子数
组。
不知道有没有更快的算法。
。因 |
|
W******g
发帖数: 887 | 49 就是你能用来出算法题的算法，介绍几个你工作中用过的 |
|
d**e
发帖数: 6098 | 50 数据结构当然就是天天用了
不过你们平时工作上用到这么多算法，就要视乎工作是做什么了
但对大部人来说，平时都不怎么用到，其实或者不能说不需要用到，而且不自己重新写
，现成的library有太多东西可以用了。
我印象中，我曾经用到的是bst，就没有什么需要自己去implement的算法。
善用数据结构，code写得简洁明了重要得多
sorting |
|
