经验

发信人: SigmaPhi (SigmaPhi), 信区: JobHunting
标  题: Google Offer
发信站: BBS 未名空间站 (Thu Oct 23 20:45:02 2014, 美东)

Fresh Master, 100k base + 15% bonus + 250 GSU + 15k sign-on + relocation.

藤校物理PhD quit. 科研两年一直用matlab做计算。 去年10月开始自学了Java, 然后
修了一门algorithm。今年春季，去跟CS一个老板搞了一学期Big Data 的research。

暑假开始刷Cracking Code 大概三遍。 然后Leetcode刷了4遍。第一遍还处在熟悉Java
语法状态，往往一道题要想上好久，这一遍用了一个月。第二遍就把每一道题就总结
了一下，并在blog上写了结题报告。我觉得这个过程对于我们non-native-speaker来讲
很好。第三遍开始想一题多解，开始离开complier，用vim刷题。第四遍注意了bug
free 和coding style，用白板或者白纸刷题。

8月开始找工作，期间面了好多公司，包括Akamai, Goldman, JP Morgan, Jane Street
, Two Sigma, Indeed, Salesforce, Amazon, Google, 还有一些小公司。面过Quant,
Data Scientist，SDE. 有些进了第二轮，有些进了onsite, 不过最后都挂了。最后就
剩下一个LA的小公司和Google.

能拿到Google的offer一方面是运气好，Google 面我的都是算法，完全没有system
design. 另一方面，我一开始就瞄准Google， 看了他们家好多面经。Cracking Code
网站上的面经我大概看了一半，mitbbs上跟google 有关的面经我基本都看了一遍。最
后面试的那天我本来抱着打酱油的心态去的，没想到运气好，都是我见过的题。由于签
了NDA，我就不说题了，题都在板上能找到。

一点感想：

A. 我觉得面Google光刷Leetcode是不够的，还是应该多看看他家近期的面经。以我有
限的经历来看，我onsite 的题都是最近面经离出现的题。

B. 有限样本表明，物理quit+自学Java+一学期project+刷题 是可以进Google的。广大
转行的同志们加油！

C. 前段时间看见板上吵CS， Physics 谁难。 我觉得都挺难的。。。现在也就会个算
法，还要补各种基础课程，以后的路还长着呢。。。

基本上就是这样了。

FB的intern和准备的经历

发信人: GuojiaAgain (GuojiaAgain), 信区: JobHunting
标  题: FB的intern和准备的经历
发信站: BBS 未名空间站 (Wed Apr  2 03:56:48 2014, 美东)

今天中午刚收到f家的intern offer， 超级开心。在这个版块看了很多也收获很多。
onsite前天晚上面就就对自己说，过了一定发个帖跟需要的人分享下自己的经历。论坛
上帖
子看了很多，很多拿了FLAG之类公司的人都说自己不是大牛啦，没准备多久啦。 LZ 觉
得都太假了。 所以希望LZ的帖子能真正的对之后同学的人有些启发。也给LZ攒攒RP啦。

首先说下背景。本科西安一个万年211的高校的telecommunication，EE很强（西安的同
学应该猜到了是哪个了）。本科没做过research。春季入学了LA一个中国学生超级多的
学校， 专业CS， Master。没有任何实习经历或者research 经历。因为LZ完全不知道
从哪下手于是就作罢了。 科目修了OS，Alg，DB， ML， Software Architecture，AI
。GPA3.79

1月份下旬开始投的简历，因为有大牛的帮助，有5个refer。结果LinkedIn 和twitter
refer直接被拒，Yahoo 一直没合适的岗位。自己也投了将近10家大公司和4家小公司，
都没有消息（可以看出LZ背景确实不行）。 最后只收到了G 和 F的电面。最后G家进了
waiting pool，F 家一轮oniste 拿到offer。

准备资料：
leetcode + cc150(cracking coding interview) + Coursera 的 Algorithms, Part
I. LZ其实1月5号左右才开始正
儿八经准备面试，之前只是上过学校的算法课。不过简历是寒假就准备了的。

准备顺序：
1. cc150 基础部分（不包括 programming language， memory limit 和 OOD）。 筑
基过程，非常重要。

2. leetcode 老80 道题。 LZ一开始以为leetcode就是 leetcode.com 不知道有oj 这
么个东西，不过 老80道题有些题目真的非常经典，建议有空可以看看。

3. leetcode oj，一共150道题，LZ是每一题都是自己独立做的，除了 string pattern
类的题目，有一些是抄的。 但是这是绝对的错误，尤其是你去FB的话，string 类的
题极其容易被考的，不信可以翻mitbbs记录。这也是最痛苦的过程。LZ建议不要干别的
事这个时间，集中画2周到3周一题题突破。不要拖太长时间，因为你会发现时间越长越
没动力。

4.CC150 最后两章。LZ是在G 家第一轮面试前发现的这两章，当时吓出了一身冷汗。因
为之前室友问过LZ自己面试遇到的难题都在这里面发现了，甚至一些比较偏门的也能在
这发现。强烈建议练习，背诵！

5. CC150 全书，这段时间也是LZ最迷茫的时候，因为不知道该做什么了。最后决定还
是继续筑基。于是开始重做CC150.

6. leetcode 130道题。如果你之前都是自己做的话，你会发现这个阶段你提高的非常
明显。LZ 没写一道题都会发现 coding 风格比之前的更加简洁，并且做得更快，130题
只用了一周多一点点就全部跑过了。

7. Coursera 的Algorithms, Part I， Princeton Univ. 很多人都觉得 leetcode 刷
通了就能进FLAG。 但是LZ觉得，不管是intern 还是 fulltime， leetcode对付 电面
完全够了，但是onsite 就比较悬了，必须要从算法根本重新复习。所以LZ F家onsite
之前花了2天看了公开课的所有视频，有些章节甚至看了两遍。LZ承认，自己onsite没
用到，但是跟LZ一起onsite的一个CMU的哥们问到了 sparse vector multiplication，
公开课的原题啊！

基本上顺序就是这些，其实每次电面前三天LZ都会用google doc 敲一遍 CC150最后两
章的重点题，因为实在是太经典了。之前的章节也会自己带着做一些。

准备建议：
1。 数据结构必须精通，甚至要回搭建自己简单的数据结构 比如hashmap， linklist
之类的。
2. CC150 是神书，最神奇的是最后两章，
3. 不要浮躁的刷题，有时间多看一些算法课的视频，有些思想没准哪天你就会用到了。
4. leetcode要练精，第一遍做的时候可以尝试多一些，第二次要尽量做到bug free，
代码一次成型，这点非常重要。
5. leetcode上一些复杂的DP其实考得很少，因为45分钟你很难做出来，（面试官当然
会假设你没做过）而且面试官也不一定能确定你做的是对的。真正重要的就是一些
string 类型的小题目。很简单，但是容易错，非常考验代码风格。
6。 做题的时候就要保证代码规范，虽然只有F家注重这些，但是好的代码规范据说会
加分哦。
7. 只用写字板写代码，onsite 前可以找白板练练。
8. coding 要老老实实地练，不管java 还是C++ ，leetcode总有人能跑过的，LZ自己
就是Java 151/151. 所以，少抱怨些，多静下心来做做题。（如果你有跑不过的，可以
给LZ留言，LZ可以把自己代码发给你参考下）。

面经：
都是一些极其基础的leetcode。只有一个Google二面时候 brain teaser， 面试官很
聪明得给了LZ一段代码，LZ觉得很眼熟，想起来时 CC150 brain teaser 最后一题。于
是一边聊天拖时间一边翻开书看了下，给了他答案。面试官最后非常满意。

其他：
其实LZ面试挺坎坷的，Google电面第一轮是LZ张那么大的第一轮面试，及其紧张。LZ英
语也是半个结巴，所以感觉非常不好。最后一道题竟然还被告知bug。但是LZ 一直找不
到，问他他也说你可以自己找。LZ最后用eclipse测出来没问题就发邮件个面试官解释
了了下自己的思路。竟然最后两轮过了之后面试官主动打电话说不要意思，面试时候看
错了 你的代码是bug free的。 不由的佩服老美native的心胸。 相比下F家第一轮的烙
印就差点把LZ坑死， two sum不给用 夹边的那个算法。LZ给了个hashmap的 被告知有
bug，还给了LZ个test让肉眼debug。真是拼了老命都没找到啊，结束后用eclipse test
， 完美跑过了他给的2个test。当时就惊呆了。。。 不过确实有个小bug，但是跟他给
的test完全没关系。LZ面试的时间就这么被耗尽了。不知道是不是被这个烙印给故意坑
了。不过幸好是refer的，所以recruiter给了第二轮面试，leetcode原题，表现良好，
就直接给了onsite。

所以大家还是保佑别遇到极品阿三吧。不过LZ Google 第二轮遇到的阿三哥还是蛮nice
的， LZ面的不错，爽快的给LZ过了， 还弥补一面悲剧的表现。所以什么地方都有好人
，也有坏人，大家不必一概而论。不过经过被F家一面烙印坑了之后，LZ还是决定，以
后如果当面试官的话，遇到不靠谱的阿三直接难题秒他。

LZ现在也有些不知所措，不知道intern 要做什么，自己能干什么。不过以前一个师兄
有句话对LZ帮助很大，最后送给大家：”当你迷茫的时候或者不知所措的时候，就老老
实实把手边的事情做好就行了，所有事情都会慢慢变好的”。



--

※ 修改:·GuojiaAgain 於 Apr  3 13:24:16 2014 修改本文·[FROM: 206.]

fb interview question

给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个value
，面试官要求 O(1) space和 O(log N) time的解法。







 Answer:

Node greater=null;
Node cur=root;
while(cur!=null) {
   if(cur.val<=target) { cur=cur.right; }
   else { greater=cur; cur=cur.left; }
}
if (greater==null) // no result
else return greater.val;

Good面经-good

发信人: xiaolongnv84 (一见若彤误终身), 信区: JobHunting
标  题: F, A, MS, QM, RF的OFFER和经历 -- Final update
发信站: BBS 未名空间站 (Fri Nov  1 14:55:43 2013, 美东)

昨天收到FB的电话，我的OFFER已经批下来了，这也意味着我的JOB HUNTING结束了，下
面是我这两个月来申请结果汇总：
Applications (7): Facebook, Google, Microsoft, Square, Twitter, Rocket Fuel,
Amazon
Offers (5): Facebook (accepted), Microsoft, Amazon, Rocket Fuel, Qualcomm (
return offer)
Rejections (3): Square, Twitter, Google

OFFER细节就不报了，上次看有人报MS的OFFER细节，结果引发口争，有人将其定性为
SHOW OFF。。。

在版上受益良多，我会陆续呈上各家公司的面试经历和面试题（FB的面试题除外），当
务之急是给LEETCODE捐点钱。

非大牛，版上互赞大牛的风气不可取。有二爷，半海和一帮真牛在这镇着，谁敢放肆！

============
个人背景
============
既然已经被不少朋友认出来了，就提供下背景信息吧。
我是2009入学的PHD＠ECE，今年11月刚毕业，研究方向是Wireless Sensor Networks和
Distributed Systems Design。在过去的四个暑假里，完成三个实习，每个大概14星期
。第二个暑假我没有实习，跑去加拿大和意大利游玩了。

更多信息，比如个人主页，可以站内信。

============
如何准备
============
1. 书籍：
B1. Introduction to Algorithms
B2. Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne
B3. Cracking the Coding Interview
B4. Programming Pearls
毫无疑问，B1是最重要的，其中的基本和中级算法章节我至少读了4遍，高级算法部分
间断地读了2遍。版上很多人非常推崇B3和LEETCODE （我后面会讲），却忽略了这本葵
花宝典。读这本书时，重点不是解上面的题或是背算法，最重要的是理解掌握各个算法
背后的设计思想。面试中遇到原题是你运气，大部分时候是没这种运气的。但是绝大部
分面试题的解题思想非常类似，无非是从各种排序算法，BST算法和基本图论算法中变
化的而来。微软的面试题4.1我从来没见过，好像这个版上也没讨论过，我也是现场灵
光一闪，发现其本质就是QUICKSORT算法，然后给出了最优答案。

B2与B1类似，都是大部头的书，确实需要点勇气的耐心去读。这本书中讨论了很多更为
实用的算法，更适合去解面试题。如果你有时间的话，一定要读一下，网上可以找到
PDF版本。B3可以看下，主要是看解题思路，上面的代码质量很一般。我是在刷完
LEETCODE几遍后，随手翻的。因为我已经把LEETCODE上的题刷得很熟了，所以这本书我
看得很快。B4感觉是个鸡肋，以前版上很多少推荐过，所以我也就看了看，发现这本书
实在是非常非常基础。如果你已经把B1看过两遍了，这本书就没必要了。

题外话，我从来不相信只靠刷题就能拿到FLGT的OFFER。这些顶级公司对个人能力的考
查还是很全面的，有时即便你全部答对了题，也不一定能拿到OFFER。况且现在不少面
试官已经知道LEETCODE这类的刷题网站（他们当中有些人以前就是这么刷进去的），他
们也会尽量避免出原题。当然，如果哪位国人哥哥想放水，出个原题让你水过，也是有
可能的。

话说我面试最怕国人，其次是日本人和韩国人。阿三就不用提了，我已经将他们划为抱
团阴狠的鼠类。

2. 在线资源
MITBBS
LEETCODE
TOPCODER
CAREERCUP
找工作的前一个月，我就开始MITBBS考古，看了不少题。后来在面试期间，基本上每天
早晨都会上来把前一天的所有关于面试的帖子看一遍。从开始感叹各位神人的答案，到
后来我也开始提供答案了。在我看来，LEETCODE是最好的在线训练网站。刷LEETCODE的
目的不是解上面的题，而是通过训练来熟练掌握B1中的算法设计思想，因为LEETCODE上
不少题的解题思想非常类似，还都是那些基本算法的变种。LEETCODE每道题我认真
地写了两遍，都是自己努力想答案，如果实在不行，才去看别人的解法。因为大部分题
是自己做出来的，所以印象非常深刻。到后来，我两三天就能快速地过一遍；随机挑个
题，我很快就能写出来。

TOPCODER上有非常好的TUTORIAL，讲得深入简出，非常值得认真读一下。我以前就一直
没太明白KMP算法，看过上面的TUTORIAL后，一切都明朗了，LEETCODE上的STRSTR那题
我也是用KMP算法解的。在面试RF时，一个阿三一上来就考这个STRSTR题，而且还很卑
鄙地把那个最基本的逐个比较的算法说出来了，意思是说你不能用这个基本算法解了，
然后那个SB一脸欠揍的得意表情。我当时就是现场用25分钟左右时间写了KMP算法，那
个SB又变成一脸失望的表情。面完那轮后，我后面心态就非常随意了，因为已经决定不
去这家充斥着阿三的公司了。

当我已经把LEETCODE做得非常熟了后，我就开始随机做TOPCODER上DIV1和DIV2的题了。
DIV3的题就不用看了，太难，不适合面试。在面每家公司前两天，我会去CAREERCUP把
这家公司前4页的题都看一下。只是看看，过过脑子既可，没有去写代码。

3. Design
总结贴：
http://blog.csdn.net/sigh1988/article/details/9790337

其它资源：
http://www.mitbbs.com/article_t/JobHunting/32498535.html
https://www.facebook.com/note.php?note_id=365915113919
https://www.facebook.com/video/video.php?v=432864835468
https://www.facebook.com/photo.php?v=572283147938&set=vb.9445547199&type=3&
permPage=1
http://vimeo.com/11280885

必看论文：
Google: Google File System, MapReduce, BigTable
Facebook: Cassandra
Amazon: Dynamo

其实读懂这5篇论文后，很多系统设计题就应该大概明白怎么做了，因为很多重要的设
计思想都在这些论文中。

============
Facebook
============
下面更新FB的面试经历吧，因为已经从了，所以不想说具体题目，只说我这个非典型经
历吧。
第一次和FB打交道是在今年２月份，当时我突然想在毕业前再去实习一次，于是网投了
FB的实习，没有找人REFER。一个月后收到HR的通知，安排面试。他家效率非常之高，
一周之内就搞定了两轮电面，进入PROJECT MATCH。可惜时间太晚了，没有MATCH上。

我今年９月向我老板确认我可以４年半毕业，于是开始申请工作。我直接发信给我上次
的那个HR，说我想申请正式职位，看她能不能安排下电面。她非常爽快地说，我们不用
浪费大家的时间了，电面就不用了，你直接来ONSITE吧。于是安排两周后电面。ONSITE
一共四轮，第一轮是PHD JEDI，主要是让我在白板上讲解的我DISSERTATION，最后问了
个无限数据处理的问题。第二轮和第三轮是CODING NINJA，每轮两个题目，可以有点小
BUG，但要能自己发现。最后一轮是DESIGN，主要是讨论设计思想，根据面试官提出的
种种问题进行改进。

一周后收到OFFER，可惜在那周的星期三我已经ACCEPT了微软的OFFER。话说微软很不自
信，三天两头催我做决定，最后说在周三之前必须做决定，大概是因为他们知道我还在
面FB吧。比较了两个OFFER，发现在考虑税收和LIVING COST下，FB的只多个两三W，我
不想为了这么点钱伤人品，于是发信给FB，说已经接了MS的OFFER，非常不好意思。不
过我明年会跳槽过来的。

然后FB的HR没理我，我想她们很少见过有为了MS的OFFER，拒掉FB的OFFER的傻B吧，还
是在FB给的钱多的情况下。三天后，突然接到HR的邮件，说面试我的几个人都强烈推荐
我，他们想再给我加一轮DESIGN面试，来决定是否要给我加工资。我一想还有这种好事
，于是就同意了，当天下午就SKYPE面试了。几天后收到新的OFFER，说如果我愿意拒掉
MS的，他们会把我的PACKAGE提高１２％。话说他们这么没有节操的硬抢，我也就没有
节操的同意了。。。

这个故事可以打消很多的关于反悔OFFER的顾虑。上次还有人担心拒人别家，从了FB的
话，FB知道后会收回OFFER。其实FB还是很喜欢抢人的，只要你有货。

============
Twitter
============
话说我和T家非常没有缘分。今年2月申请实习时，让我朋友REFER，结果他家HR连电面
都没有给，就把我给拒了。今年我换了另一个朋友REFER我，电面是拿到了，第一面就
挂了。电面先是一个LEETCODE原题，Palindrome Partitioning II ，我给了O(n^2)的
解法。然后是问LINUX里面BASH SHELL是如何实现的，运行一个命令时，系统有哪些步
骤，系统STACK是如何转换的。我对LINUX底层的东西不熟悉，第二部分答得不好，磕磕
碰碰的，然后就没有然后了。

============
Square
============
这家我是网投的，两天后拿到面试。电面有两轮，间隔两天：
1. 经典的小偷问题：一排房子，每个房子里有一定价值的东西，小偷不能偷相邻的两
个房间。即如果小偷光临了房间i, 那么就不能再偷房间i - 1和房间i + 1。要求返回
小偷能偷到东西的总价值的最大值。这是个经典DP问题，版上讨论过。
Sol: Suppose v[i] = the value of house i, and totally we have n houses.
f[0] = v[0], f[1] = v[1], f[i] = max{f[i - 1], f[i - 2] + v[i]} for i >= 2

A modified version of this problem is that all houses form a circle, whose
solution is very similar. We need to run DP twice.
1st: f[0] = v[0], f[1] = 0, f[i] = max{f[i - 1], f[i - 2] + v[i]} for i = 2,
3, ..., n - 2 ==> ans1 = f[n - 2]
2nd: f[0] = 0, f[1] = v[1], f[i] = max{f[i - 1], f[i - 2] + v[i]} for i = 2,
3, ..., n - 1 ==> ans2 = f[n - 1]
return max{ans1, ans2}

Sample code: https://gist.github.com/krisys/4089748
More explanation (Bad Neighbors): http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=tccc04_online_rd_4

2. 扑克牌问题：给一副扑克牌排序，先是按花色，同一花色按数字排序。主要是扑克
牌这个CLASS应该如何设计，如何表示花色和面值。我给出了他想要的JAVA enum表示法
，但我以前在JAVA中很少用enum，导致里面有些方法都忘记了。
FOLLOW-UP：现在你有一手牌，你要计算其分值，规则如下：如果两张牌相同，或这两
张牌的面值和为15，则计2分。ACE可以是1或者11.

这家公司对代码简洁度有着变态的要求，凡是能一行写出来的东西，绝不会让你写两行
代码，哪怕两行代码的版本更容易理解和维护。写完代码后，其余的时间全是在按他们
的要求简化压缩代码。最后代码的行数是减少了不少，可是可读性也是一样。第二面挂
掉，我觉得主要是用enum的时候，明显不熟。

============
Google
============
与FB类似，我在今年3月申请实习的时候，也过了前面两轮电面，进入HOST MATCH，最
后也没MATCH上，于是他们直接让我去ONSITE。我当时还没准备好正式找工作，就把
ONSITE推到了10月，也就是在FB面试的后面几天。面试一共四轮，全是CODING，只有一
个人稍微问了下我的研究内容，这点就明显没有FB给我的感觉好。

第一轮是个香港帅哥，人很好，这轮是我表现最好的一轮。题目如下：
1.1. Tokenize a string to words. Ignore any space and punctuator

1.2. Design an distributed file system to store files of TB size
Follow-up: How to find and store the top-k most frequent keywords among
documents stored on all Google servers

第二轮是个阿三，感觉很吊的样子，一副大爷样地坐在那里，让我很不爽。他就问了很
简单的一道题，然后就是不停地问我如何改进。
2. Given a list of words, find two strings S & T such that:
    a. S & T have no common character
    b. S.length() * T.length() is maximized
Follow up: how to optimize and speed up your algorithm

第三轮如下：

3.1 Design an interface that can convert both a sorted linked list and a
sorted array into a balanced binary search tree. Implement it in both bottom
-up and top-down approaches

3.2. (Leetcode 原题) Given a matrix of size m * n, matrix[i][j] stores the
number of carrots in cell (i, j). Now a rabbit starts from the left upper
corner and wants to reach the right below corner. It can only move either to
the right or below. Compute the maximum number of carrots that it can
collect along the way, and output that path.
Follow up: how many different ways are there?

第四轮就是个悲剧，一个更年期日本女人，英文听得让我想死。进来后没有任何问候，
连自我介绍都没有，坐下来就板着个脸开始问。整个过程中就是我在说，她没有任何回
应或是表情，我还不如去她们日本买个漂亮的充气娃娃来对着面试呢。这轮我从一开始
就很紧张，发挥得也不好，到最后快结束时才写出代码。这题其实想明白了，算法极简
单。只是我当时不知道怎地，居然卡在这上面了。
4. Given a byte array, which is an encoding of characters. Here is the rule:
    a. If the first bit of a byte is 0, that byte stands for a one-byte
character
    b. If the first bit of a byte is 1, that byte and its following byte
together stand for a two-byte character
Now implement a function to decide if the last character is a one-byte
character or a two-byte character
Constraint: You must scan the byte array from the end to the start.
Otherwise it will be very trivial.

============
Microsoft
============
一共五轮，过程没什么好讲的，标准流程，直接上题吧：

1.1. What are the two ways to implement hash tables? How to add, delete, and
lookup an key? How to deal with collision?

1.2. Given an integer, return the next prime number bigger than it.
Follow-up: If this function will be called frequently, how to optimize the
performance?

2.1. What's a full outer join in database? Implement a full outer join given
two tables.
Follow-up: If two tables are very big (i.e., no enough RAM to load them),
how to deal with it?

2.2. Given random() that can return 0 or 1 uniformly, implement random_new()
that can return 0 with 90%, and 1 with 10%.

3.1. Given an image represented by byte[][] image, return its mirror image.

3.2. Design a distributed LRU

4.1. Given an array [a1, a2, ..., an, b1, b2, ..., bn], transform it to [a1,
b1, a2, b2, ..., an, bn].
Requirement: time complexity O(nlogn), space complexity O(logn)
Sol: the base idea is to use quicksort techniques. Suppose the current array
is A, whose size is 2k.
1. Divide A into four segments: A = [A1 A2 B1 B2], where A1.size = B1.size =
k / 2, B1.size = B2.size = k - k / 2;
2. Swap A2 and B1, and we get A = [A1 B1 A2 B2]. In this step, we actually
need to rotate [A2 B1] to the right by k - k / 2 items. This can be done by
reversing [A2 B1] first, and then reversing [A2] and [B1] respectively.
3. Recursive on [A1 B1] and [A2 B2] respectively.

Example: A = [1 2 3 4 5 6 7 8 9 10]
A1 = [1 2], A2 = [3 4 5], B1 = [6 7], B2 = [8 9 10]
After 2nd step, A = [1 2 | 6 7 | 3 4 5| 8 9 10]
For the 3rd step, process [1 2 6 7] and [3 4 5 8 9 10] repectively

4.2. Design: suppose you have a cluster, and each machine in this cluster
has a large number of numbers. How can you find out the median of all the
numbers on all the machines.

5. Design: How to design a crawler?


============
Amazon
============
题目比较简单，感觉他家标准降低好多好多。。。

1. Given a string, find the longest palindromic substring

2. Given a binary tree, find the length of the longest path in the tree. A
path can start and end anywhere in the tree (i.e., not necessary from the
root to a leaf).

3. Given a large number of integers, return the largest K numbers. How to
process them using MapReduce?

4. Implement a priority queue: enQueue, getFront, deQueue

5. Given a set of points on a plane, and a list of circles centered at the
original point, find the ring containing the most number of points.

6. Design: You have a HTML page, which contains many strings describing
potions in a CSS file, how can to compress these strings to reduce the size
of the HTML page.
Follow-up: Users complain that your website becomes slow recently, how can
you find out the problems, and how to fix them?

7. Java OO concepts, dissertation and behavior questions from CC150.


--

※ 修改:·xiaolongnv84 於 Dec 12 18:13:52 2013 修改本文·[FROM: 108.]

Go Tigers!: Sort Colors [Leetcode]

Go Tigers!: Sort Colors [Leetcode]: Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in th...

Rotate Image

    //method 1
void rotate(vector<vector<int> > &matrix) {
        int nn=matrix.size();
        for(int layer=0;layer<nn/2;layer++){
            for(int j=layer;j<nn-layer-1;j++){
                int row=layer;int col=j;
                int tmp=matrix[row][col];
                for(int k=0;k<3;k++){
                    matrix[row][col]=matrix[nn-1-col][row];
                    int tt=row;
                    row=nn-1-col;
                    col=tt;
                }
                matrix[row][col]=tmp;
            }
        }
    }

//another flavor of method 1
void rotate(vector<vector<int> > &matrix) {
        int n=matrix.size();
        for(int layer=0;layer<n/2;layer++){
            for(int j=layer;j<n-layer-1;j++){
                int tmp=matrix[layer][j];
                //note that:1. the right side of the equation is the left side of the next equation
                //2. each of the equation has the form: matrix[a][b]=matrix[n-1-b][a];
                matrix[layer][j]=matrix[n-1-j][layer];
                matrix[n-1-j][layer]=matrix[n-1-layer][n-1-j];
                matrix[n-1-layer][n-1-j]=matrix[j][n-1-layer];

                matrix[j][n-1-layer]=tmp;
            }
        }
}

//method 2,from anniekim

123 -> 147 ->  741

456      258      852

789      369      963

    void rotate(vector<vector<int> > &matrix) {
        int N = matrix.size();
        for (int i = 0; i < N; ++i)
            for (int j = i+1; j < N; ++j)
                swap(matrix[i][j], matrix[j][i]);
        for (int j = 0; j < N/2; ++j)
            for (int i = 0; i < N; ++i)
                swap(matrix[i][j], matrix[i][N-j-1]);
    }

Spiral Matrix II

 //similar to Spiral Matrix
    vector<vector<int> > generateMatrix(int n) {
        vector<vector<int>> matrix(n,vector<int>(n,0));
       
        int row=n,col=n;

        int rowStart=0,colStart=0;
        int v=1;
        while(row>0&&col>0)
        {
           
            for(int k=colStart;k<colStart+col;k++)
                matrix[rowStart][k]=v++;
            if(row>2)   
                for(int k=rowStart+1;k<rowStart+row-1;k++)
                    matrix[k][colStart+col-1]=v++;
            if(row>1)       
              for(int k=colStart+col-1;k>=colStart;k--)
                  matrix[rowStart+row-1][k]=v++;
            if(row>2&&col>1)    
                for(int k=rowStart+row-2;k>=rowStart+1;k--)
                    matrix[k][colStart]=v++;
            row-=2;col-=2;
            rowStart++; colStart++;
        }
        return matrix;
    }

Spiral Matrix

//first one, do it in a natural way

    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ret;
       
        int row=matrix.size();
        if(row==0)
            return ret;
        int col=matrix[0].size();

        int rowStart=0,colStart=0;
        while(row>0&&col>0)
        {
           
            for(int k=colStart;k<colStart+col;k++)
                ret.push_back(matrix[rowStart][k]);
            if(row>2)   
                for(int k=rowStart+1;k<rowStart+row-1;k++)
                    ret.push_back(matrix[k][colStart+col-1]);
            if(row>1)       
              for(int k=colStart+col-1;k>=colStart;k--)
                  ret.push_back(matrix[rowStart+row-1][k]);
            if(row>2&&col>1)    
                for(int k=rowStart+row-2;k>=rowStart+1;k--)
                    ret.push_back(matrix[k][colStart]);
            row-=2;col-=2;
            rowStart++; colStart++;
        }
        return ret;
    }

generate a tournament schedule

In a tournament with N teams, where in one team can play only one match per day, develop an algo which schedules the matches in the tournament.

Each team shall play with the other team once.

N need to be power of 2.

 This is a popular interview problem that has been asked by MS, Google, Bloomberg.

//idea from careercup
void tourna(vector<int>& myinput,vector<vector<int>>&ret){
    int n=myinput.size();
//i is the size of group. a member  inside one group do play with that of the neighbor group.
    for(int i=1;i<=n/2;i<<=1){
        for(int j=0;j<i;j++){//j is the alignment number
            vector<int> com;
            for(int start=0;start<n;start+=2*i){//everytime process two neighbor groups
                int rstart=start+i;
                for (int k=0;k<i;k++)//pair players in the two neighbor groups
                {
                    com.push_back(myinput[start+k]);
                    com.push_back(myinput[rstart+(j+k)%i]);
                }
              
            }
            ret.push_back(com);
        }
    }
}

//idea from stackoverflow



for example: A....H

If you start with this setup (teams in the upper row playing against the corresponding lower team):

A B C D
H G F E

you set one team as fixed (e.g., A) and rotate the rest (e.g., clockwise):

A H B C     A G H B     A F G H     A E F G    A D E F    A C D E  
G F E D     F E D C     E D C B     D C B H    C B H G    B H G F

Voilà, 7 rounds, and every team plays each other team.

void tourna2(vector<int>& myinput,vector<vector<int>>&ret){
    int n=myinput.size();
    for (int i=0;i<n-1;i++){//i is the alignment number
        vector<int> com;
        com.push_back(myinput[0]);
        com.push_back(myinput[1+(n-2+i)%(n-1)]);
        int step=0;
        while(step<(n-2)/2){
            int left=1+(i+step)%(n-1);
            int right=1+(n-3+i-step)%(n-1);
            com.push_back(myinput[left]);
            com.push_back(myinput[right]);
            step++;

        }
        ret.push_back(com);
    }
}

Go Tigers!: Max Points on a Line [Leetcode]

Go Tigers!: Max Points on a Line [Leetcode]: Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Solution: the key point here is how t...

Go Tigers!: Trie Implementation in C++ [GeeksforGeeks]

Go Tigers!: Trie Implementation in C++ [GeeksforGeeks]: Check here for node insertion and searching, and here for node removal. In addition, I used postorder traversal to delete the entire tree....

Best Time to Buy and Sell Stock III & IV

//from codeganker.
使用动态规划来完成，事实上可以解决非常通用的情况，也就是最多进行k次交易的情况。
这里我们先解释最多可以进行k次交易的算法，然后最多进行两次我们只需要把k取成2即可。我们还是使用“局部最优和全局最优解法”。
我们维护两种量，一个 是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易 在当天卖出的最好的利润是多少（local[i][j]）。下面我们来看递推式，全局的比较简单，如果第i天有卖出，那么global[i][j]=local[i][j]；如果第i天没有卖出，那么global[i][j]=global[i-1][j]。
综合以上两种情况，global[i][j]=max(local[i][j],global[i-1][j]).     （*）

 local[i][j]的划分标准是根据它的最后一次交易的买入时间t。（ diff = prices[i] - prices[i - 1]. ）
1)如果t<i-1,那么local[i][j]= local[i-1][j]+diff（这种情况有些难想到，但可以通过cut-and-paste 反证法来证明。在这种情况下，把 local[i-1][j]的最后一次交易的卖出时间从第i-1天延迟到第i天，就得到了local[i][j]的最后一次交易的  c。）
2)如果t=i-1，那么local[i][j]=global[i-1][j-1]+diff
3)如果t=i, 那么local[i][j]=global[i-1][j-1]+0
 综合以上三种情况，local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)

/*
第三种情况似也可不用考虑。因为如果不断删除这种当天进行了一次先买入后卖出的无意义操作，
a）最后还剩下唯一一个卖出操作，则它必定等价于1)或2）中的一种情况。
b）最后没有操作剩下，则相当于当天没有任何操作。但是，这种情况不会影响global[i][j]的值（global[i][j]取global[i-1][j]就可以了）。而最后我们是根据global的值来得出最大利润的。所以，情形3）不考虑时，可能影响local[i][j]的值，但不会影响最后我们要的结果。情形3）不考虑时，相当于禁止出现当天进行先买入后卖出的无意义操作。此时，回到开头我们对local[i][j]的定义可以更严格一些：
local[i][j]：当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出，并且这种交易不是先买入后卖出的无意义情况的，最好的利润。
(其实也可以从题目一开始就声明不允许存在这样的交易，因为这样的交易没有任何意义，白白浪费了一次交易机会。这样对local的定义，就不需要特别说明了。)
*/

上面的算法中对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n*k)，如果是最多进行两次交易，那么复杂度还是O(n)。空间上只需要维护当天数据就可以，所以是O(k)，当k=2，则是O(1)。代码如下：

    int maxProfit(vector<int> &prices) {
        if(prices.size()==0)
            return 0;
        int local[3]={0};
        int global[3]={0};
        for(int i=1;i<prices.size();i++){
            int diff=prices[i]-prices[i-1];
            for(int j=2;j>=1;j--){
                local[j]=max(local[j]+diff,global[j-1]+max(diff,0));
                global[j]=max(local[j],global[j]);
            }
        }
        return global[2];
    }



楼主你背后的得到这个思路的思维过程是怎样的能分享一下吗？

Code_Ganker回复 ： 这个感觉就是凭灵感了，解决时尽量尝试多种角度，这有点像以前做辅助线，

其实也没什么通法，就是试试看哈~

Bin Mu2014年10月25日 上午6:34

代码中的for循环，为什么j是从2到1，而不是从1到2呢？j是交易次数，按道理应该从小到大来求啊。

删除

Bin Mu2014年10月25日 上午6:57

j是从2到1，大概想明白了。因为如果j从1到2，在计算j=2之前，前一天的值已经被覆盖掉了，这样无法使用一维dp了。

删除

Huan Lin2014年10月25日 上午11:13

对，这个是动态规划要省空间常用的技巧哈~ 就是看数据是要旧的还是新的，这里是要旧的，所以要从大到小~

扩展：下面的代码同时打印出最大利润时的交易操作。现在有一个缺点是只能打印一种可能。如下例子就有两种操作序列都能实现最大利润：

Input: k = 2, prices = [4, 4, 6, 1, 1, 4, 2 ,5]
max profit: 6
Explanation: 

1)Buy at 4 and sell at 6. Then buy at 1 and sell at 5. Your profit is 2 + 4 = 6.

2)Buy at 1 and sell at 4. Then buy at 2 and sell at 5. Your profit is 3 + 3 = 6.

思路： prelocal[i][j] 保存了local[i][j]的最后一次交易的买入时间（最后一次交易的卖出时间，
根据local的定义即为i）

int maxProfit(vector<int> &prices,int k) { int n =prices.size(); if(prices.size()==0) return 0; //int local[3]={0}; //int global[3]={0}; vector<vector<int> > local(n,vector<int>(k+1,0)); vector<vector<int> > prelocal(n,vector<int>(k+1,0)); vector<vector<int> > global(n,vector<int>(k+1,0)); for(int i=1;i<prices.size();i++){ int diff=prices[i]-prices[i-1]; for(int j=k;j>=1;j--){ local[i][j]=max(local[i-1][j]+diff,global[i-1][j-1]+max(diff,0)); if(local[i][j]==local[i-1][j]+diff) prelocal[i][j]=prelocal[i-1][j]; if(local[i][j]==global[i-1][j-1]+diff) prelocal[i][j]=i-1; if(local[i][j]==global[i-1][j-1]+0) prelocal[i][j]=i; global[i][j]=max(local[i][j],global[i-1][j]); } } int p=n-1,q=k; while(global[p][q]>0){ if(global[p][q]==global[p-1][q]) p--; else{ cout<<p+1<<endl;//when output let day index start from 1 cout<<prelocal[p][q]+1<<endl; int temp=global[p][q]; int temp2=prices[p]; p=prelocal[p][q]; q--; if(global[p][q]!=temp-(temp2-prices[p])) cout<<"wrong!"<<endl; } } return global[n-1][k]; }

经过一番努力，现在的代码可以打印全部可能的操作序列了：

#include <iostream> #include <vector> #include <set> #include <cstdlib> #include <ctime> using namespace::std; void printActions( vector<vector<int> >&global,int p,int q, vector<vector<int> >&local, vector<vector<set<int> > >&prelocal,vector<int>&actions,vector<vector<int> >&collect); /*综合以上两种情况，global[i][j]=max(local[i][j],global[i-1][j]). local[i][j]的划分标准是根据它的最后一次交易的买入时间t。 如果t<i-1,那么local[i][j]= local[i-1][j]+diff 如果t=i-1，那么local[i][j]=global[i-1][j-1]+diff 如果t=i, 那么local[i][j]=global[i-1][j-1]+0 综合以上三种情况，local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)*/ int maxProfit(vector<int> &prices,int k) { int n =prices.size(); if(prices.size()==0) return 0; //int local[3]={0}; //int global[3]={0}; vector<vector<int> > local(n,vector<int>(k+1,0)); vector<vector<set<int> > > prelocal(n,vector<set<int> >(k+1,set<int>())); //for(int i=0;i<k+1;i++) // prelocal[0][i].push_back(0); vector<vector<int> > global(n,vector<int>(k+1,0)); for(int i=1;i<prices.size();i++){ int diff=prices[i]-prices[i-1]; for(int j=k;j>=1;j--){ local[i][j]=max(local[i-1][j]+diff,global[i-1][j-1]+max(diff,0)); if(local[i][j]==local[i-1][j]+diff) prelocal[i][j]=prelocal[i-1][j]; if(local[i][j]==global[i-1][j-1]+diff) prelocal[i][j].insert(i-1); if(local[i][j]==global[i-1][j-1]+0) prelocal[i][j].insert(i); global[i][j]=max(local[i][j],global[i-1][j]); } } /*debug info for(int i=0;i<prelocal.size();i++){ for(int j=0;j<prelocal[i].size();j++){ cout<<i<<" "<<j<<": "; for(set<int>::iterator it=prelocal[i][j].begin();it!=prelocal[i][j].end();it++) cout<<*it<<" "; cout<<endl; } } */ vector<int> actions; vector<vector<int> > collect; printActions(global,n-1,k,local,prelocal,actions,collect); for(int i=0;i<collect.size();i++){ for(int j=0;j<collect[i].size();j++) cout<<collect[i][collect[i].size()-1-j]<<" "; cout<<endl; } return global[n-1][k]; } void printActions( vector<vector<int> >&global,int p,int q, vector<vector<int> >&local, vector<vector<set<int> > >&prelocal,vector<int>&actions,vector<vector<int> >&collect){ if(global[p][q]==0) { collect.push_back(actions); return;} if(global[p][q]==global[p-1][q]) printActions(global,p-1,q,local,prelocal,actions,collect);//should not use return here, //because global[p][q]==local[p][q] may also be true; if(global[p][q]==local[p][q]) { for(set<int>::iterator it=prelocal[p][q].begin();it!=prelocal[p][q].end();it++){ actions.push_back(p+1);//when output, let day index start from 1 actions.push_back(*it+1); //p=prelocal[p][q][i]; //q--; printActions(global,*it,q-1,local,prelocal,actions,collect); actions.pop_back(); actions.pop_back(); } } } int main() { std::cout << "Hello World!\n"; vector<int> vect{4, 4, 6, 1, 1, 4, 2 ,5}; int aa=maxProfit(vect,2); cout<<"max: "<<aa<<endl; /* //test code vector<int> vect2; srand((unsigned)time(0)); for(int i=0;i<11;i++) vect2.push_back(rand()%100); vect2.push_back(vect2.back()); for(int i=0;i<vect2.size();i++) cout<<vect2[i]<<" "; cout<<endl; cout<<"actions: "<<endl; int aa=maxProfit(vect2,3); cout<<"max: "<<aa<<endl; */ }

下面的代码删除了产生的没意义操作的情况（当天先买入后卖出），同时确保每天只能进行一个操作

void printActions( vector<vector<int> >&global,int p,int q, vector<vector<int> >&local, vector<vector<set<int> > >&prelocal,vector<int>&actions,vector<vector<int> >&collect); int maxProfit(vector<int> &prices,int k) { int n =prices.size(); if(prices.size()==0) return 0; vector<vector<int> > local(n,vector<int>(k+1,0)); vector<vector<set<int> > > prelocal(n,vector<set<int> >(k+1,set<int>())); vector<vector<int> > global(n,vector<int>(k+1,0)); for(int i=1;i<prices.size();i++){ int diff=prices[i]-prices[i-1]; for(int j=k;j>=1;j--){ local[i][j]=max(local[i-1][j]+diff,global[i-1][j-1]+max(diff,0)); if(local[i][j]==local[i-1][j]+diff) prelocal[i][j]=prelocal[i-1][j]; if(local[i][j]==global[i-1][j-1]+diff) prelocal[i][j].insert(i-1); if(local[i][j]==global[i-1][j-1]+0) prelocal[i][j].insert(i); global[i][j]=max(local[i][j],global[i-1][j]); } } vector<int> actions; vector<vector<int> > collect; printActions(global,n-1,k,local,prelocal,actions,collect); cout<<"actions:"<<endl; for(int i=0;i<collect.size();i++){ for(int j=0;j<collect[i].size();j++) cout<<collect[i][collect[i].size()-1-j]<<" "; cout<<endl; } return global[n-1][k]; } void printActions( vector<vector<int> >&global,int p,int q, vector<vector<int> >&local, vector<vector<set<int> > >&prelocal,vector<int>&actions,vector<vector<int> >&collect){ if(global[p][q]==0) { collect.push_back(actions); return;} if(global[p][q]==global[p-1][q]) printActions(global,p-1,q,local,prelocal,actions,collect);//should not use return here, //because global[p][q]==local[p][q] may also be true; if(global[p][q]==local[p][q]) { for(set<int>::iterator it=prelocal[p][q].begin();it!=prelocal[p][q].end();it++){ if(*it==p) continue; /* if(global[*it][q-1]!=0 && ( global[*it][q-1]==local[*it][q-1]) ) //本来想用这个条件来杜绝当天先卖出后买入的情况生成。但是存在当天 （1）有卖出
操作（2）没有卖出操作，都能产生global的最大值。而当（2）也能获得最大值，说明（1）的卖出
操作，只是先买入后卖出的无意义情况。故当使用这种条件来排除这天，就漏掉了（2）的情况了。 { continue; } */ if(actions.size()>0&&p+1==actions.back()) continue; actions.push_back(p+1);//when output, let day index start from 1 actions.push_back(*it+1); printActions(global,*it,q-1,local,prelocal,actions,collect); actions.pop_back(); actions.pop_back(); } } }

Simplify Path

[解题思路]
利用栈的特性，如果substring element
1. 等于“/”，跳过，直接开始寻找下一个element
2. 等于“.”，什么都不需要干，直接开始寻找下一个element
3. 等于“..”，弹出栈顶元素，寻找下一个element
4. 等于其他，插入当前elemnt为新的栈顶，寻找下一个element

最后，再根据栈的内容，重新拼path。这样可以避免处理连续多个“/”的问题。

1:       string simplifyPath(string path) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            vector<string> stack;   
5:            assert(path[0]=='/');   
6:            int i=0;   
7:            while(i< path.size())   
8:            {   
9:                 while(path[i] =='/' && i< path.size()) i++; //skip the begining '////'  
10:                 if(i == path.size())   
11:                      break;   
12:                 int start = i;   
13:                 while(path[i]!='/' && i< path.size()) i++; //decide the end boundary  
14:                 int end = i-1;   
15:                 string element = path.substr(start, end-start+1);   
16:                 if(element == "..")   
17:                 {   
18:                      if(stack.size() >0)   
19:                      stack.pop_back();   
20:                 }   
21:                 else if(element!=".")   
22:                 stack.push_back(element);      
23:            }   
24:            if(stack.size() ==0) return "/";   
25:            string simpPath;   
26:            for(int i =0; i<stack.size(); i++)   
27:            simpPath += "/" + stack[i];   
28:            return simpPath;   
29:       }  

Best Time to Buy and Sell Stock II

sum all the differences that are greater than 0.

    int maxProfit(vector<int> &prices) {
        int profit=0;
        for(int i=1;i<prices.size();i++){
            profit+=max(0,prices[i]-prices[i-1]);
        }
        return profit;
    }

Best Time to Buy and Sell Stock

//Solution: For each element, calculate the max difference with the former elements.
    int maxProfit(vector<int> &prices) {
       if (prices.size() == 0)
            return 0;
        int maxv=0;
        int low=prices[0];
        for(int i=1;i<prices.size();i++)
        {
            low=min(low,prices[i]);
            maxv=max(maxv,prices[i]-low);
        }
        return maxv;
    }

Sort Colors

 from geeksforgeeks
The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-1] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi–
       
    

     void sortColors(int A[], int n) {
        int lo=0,mid=0,hi=n-1;
        while(mid<=hi){
            switch(A[mid]){
                case 0:swap(A[lo++],A[mid++]); break;
                case 1:mid++; break;
                case 2:swap(A[mid],A[hi--]);
            }
        }
    }

Search Insert Position

 binary search

    int searchInsert(int A[], int n, int target) {
       
        int low=0,high=n-1;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(A[mid]<target)
                low=mid+1;
            else if(A[mid]>target)
                high=mid-1;
            else
                return mid;
        }
        return low;
    }

Subsets II

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int> &S) {
        vector<vector<int> > res(1, vector<int>());
        sort(S.begin(), S.end());
        vector<int> set;
        int N = S.size();
        for (int l = 1; l <= N; ++l)
            subsetsWithDupRe(S, l, 0, set, res);
        return res;
    }
//this function generates all the subsets of length L to be stored in set.
    void subsetsWithDupRe(vector<int> &S, int L, int start, vector<int> &set, vector<vector<int>> &res)
    {
        int N = S.size(), M = set.size();
        if (M == L) {
            res.push_back(set);
            return;
        }
        for (int i = start; i <= N - (L - M); ++i) {
            if (i > start && S[i] == S[i-1]) continue;
            set.push_back(S[i]);
            subsetsWithDupRe(S, L, i + 1, set, res);
            set.pop_back();
        }
    }
};

Code Ganker: Subsets II -- LeetCode

Code Ganker: Subsets II -- LeetCode: 原题链接: http://oj.leetcode.com/problems/subsets-ii/ 这道题跟 Subsets 一样是经典的 NP问题 --求子集。比 Subsets 稍微复杂一些的是这里的集合中可能出现重复元素，因此我们在求子集的时候要避免出现重复的子集。在 S...

Code Ganker: Subsets -- LeetCode

Code Ganker: Subsets -- LeetCode: 原题链接: http://oj.leetcode.com/problems/subsets/ 求子集问题是经典的 NP问题 ，复杂度上我们就无法强求了哈，肯定是非多项式量级的。一般来说这个问题有两种解法：递归和非递归。 我们先来说说递归解法，主要递推关系就是假设函数返回递归...

Subsets

Three methods are provided.


//first, use recursive definition of subset 
//iterative version
vector<vector<int> > subsets(vector<int> &S) {
    sort(S.begin(),S.end());
    vector<vector<int> >  ret(1);
    for(int i=0;i<S.size();i++)
    {
        int n=ret.size();
        for(int j=0;j<n;j++){
            ret.push_back(ret[j]);
            ret.back().push_back(S[i]);
        }
    }
    return ret;
}

//recursive version
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>>ret;
        sort(S.begin(),S.end());
        subsetsRe(S,S.size(),ret);
        return ret;
       
    }
//subsetsRe computes the subsets of S[0...num-1] 
    void subsetsRe(vector<int> &S, int num,vector<vector<int>>&ret){
        if(num==0){
            ret.push_back(vector<int>());
            return;
        }
        subsetsRe(S,num-1,ret);
        int n=ret.size();
        for(int i=0;i<n;i++){
            ret.push_back(ret[i]);
            ret.back().push_back(S[num-1]);
        }
    }
};

//another kind of recursion
vector<vector<int> > subsets(vector<int> &S) {
    vector<vector<int> > res(1, vector<int>());//same as vector<vector<int> > res(1);
    sort(S.begin(), S.end());
    vector<int> set;
    int N = S.size();
    for (int l = 1; l <= N; ++l)
        subsetsRe(S, l, 0, set, res);
    return res;
}
//subsetsRe generates all the subsets of length L to be stored in res
void subsetsRe(vector<int> &S, int L, int start, vector<int> &set, vector<vector<int> > &res)
{
    int N = S.size(), M = set.size();
    if (M == L) {
        res.push_back(set);
        return;
    }
    for (int i = start; i <= N - (L - M); ++i) {
        set.push_back(S[i]);
        subsetsRe(S, L, i + 1, set, res);
        set.pop_back();
    }
}



//third one, bit maniputation
vector<vector<int> > subsets(vector<int> &S) {
    sort(S.begin(),S.end());
    vector<vector<int> >  ret;
    int n=S.size();
    for(int i=0;i<1<<n;i++){
        vector<int> temp;
        for(int j=0;j<n;j++){
            if(i&1<<n-j-1)
                temp.push_back(S[j]);
        }
        ret.push_back(temp);
    }
    return ret;
}

Next Permutation

 by anniekim

Processes: Take A = {1,3,2} as an example:
1. Traverse from back to forth, find the turning point, that is A[i] = 3.
2. Sort from the turning point to the end (A[i] to A[end]), so {3,2} becomes {2,3}.
3. If i equals to 0, finish! Else, goto 4.
4. Let j = i, search from A[j] to A[end] to find the first elem which is larger than A[i-1], '2' here.
5. Swap the elem A[j] with A[i-1].
Finally, the next permutation is {2,1,3}.

void nextPermutation(vector<int> &num) {
    int i = num.size() - 1;
    while (i > 0 && num[i] <= num[i-1])
        i--;
    sort(num.begin() + i, num.end());
    if (i == 0)
        return;
    int j = i;
    while (j < num.size() && num[j] <= num[i-1])
        j++;
    swap(num[j], num[i-1]);
}

peking2 面试题总结

发信人: peking2 (clojure), 信区: JobHunting
标  题: 我的面试题总结
发信站: BBS 未名空间站 (Sat Oct 26 19:32:12 2013, 美东)

好多人问，我就发到这里吧。

面试题的构成和分类

首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。


我认为一道面试题由以下几个方面组成的

Question

Data structure in question

Data structure in solution

Algorithm in solution

Coding


题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。


问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构


解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。


算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定，相应的数据结构也就确定了。这两个没有先后的关系，但解决方案
中的数据结构和算法具有非常紧密的联系。


代码：非常关键。代码就是解决方案的数据结构和算法的实现了。目前来看，题目，数
据结构和算法在面试中出现的类型比较固定，因此代码的好坏则是拉开面试者水平的一
个有效手段。这也是为什么F，G如此看中代码的质量了。我发现上面几点比较容易突击
，但是写代码的功力还是需要实打实的积累的。


总结面试题目的关键就是要把面试题目进行分类之后分析。由于面试题目由以上几个部
分组成并且混杂在一起，因此怎样合理的分类就变得非常的困难。其实Careercup150的
分类就比较好，它是这样进行分类的。

数据结构：Arrays and Strings, Linked Lists, Stacks and Queues, Trees and
Graphs

算法：Bit Manipulation, Mathematics and Probability, Recursion and
Dynamic Programming, Sorting and Searching

但是我感觉这样分类比较适合初级阶段学习，并不适合系统地对面试题目进行分析。我
其实目前也没有什么特别好的idea，想跟着感觉先来，可能慢慢就能悟出更多了。


Peking2面试题总结(2) - Two/Three pointers
简称two pointers吧。大概把分类粗略的搞了一遍（http://leetcode.cloudfoundry.com/),
发现利用two pointers解决的题目数量很大。two pointers我指的是一类题，而不一定
是真正的two pointers,
比如可能是three pointers, 也可能不是pointer， 而是index。这类题基本上就是发
生在array,
string, linked
list这三种数据结构上，是一种基本的算法和编程技巧，同样超高频率的出现，可以说
是面试必遇的题。

two pointers常常和其他的算法混杂起来出现。比如binary search本身也可以归类为
two
pointers的。如果这样算的话，Leetcode上边1/4的题目都跟它相关。因此，two
pointers是必须熟练掌握的基本编程技巧。


Two pointers大概分三种类型

1. 两个pointers从头往后走：感觉绝大多数的linked
list的题目都涉及到这个操作，当然还有array。这类题目很多时候又可以称为sliding
window。

Implement strStr()

Longest Substring Without Repeating Characters

Minimum Window Substring

Remove Duplicates from Sorted Array &
II

Remove Duplicates from Sorted List & II

Remove Element

Remove Nth Node From End of List

Reverse Linked Llist II

Rotate List

Substring with Concatenation of All Words

Swap Nodes in Pairs
2.
两个pointers从两头往中间走：一般面试出现的的都是singly linked list,
因此这类题主要是array题。

3Sum

3Sum Closest

4Sum

Container With Most Water

Sort Colors

Trapping Rain Water

Two Sum

Binary search (will discuss it in a separate section)
3.
两个pointers控制两个不同的数组或链表：一般出现在跟merge相关的题目上。

Add Binary

Add Two Numbers

Merge Sorted Array

Merge Two Sorted Lists

Multiply Strings

Partition List


Peking2面试题总结(3) - Permutation and Combination
基本题，但是非常重要。面试中碰到任何一题一点也不奇怪。PIE,
CC150和Leetcode都不约而同地包含了这类题。把这些题目做熟是必须的。基本上来说
这类题的解法都是DFS，程序的大体框架非常类似，只是根据题目的要求代码稍作修改
。当然每道题也有不同的解法，但是你应该根据自己的喜好把这类题目的解决方案统一
化。熟悉了这类题目以后对于DFS(will
be discussed in a separate section)
的理解会非常深刻。基本上一般的DFS的题目应该没什么问题了。

无论是排列还是组合，这类题都有一个变形，就是要求不能有重复的输出。PIE和CC150
都没有提到相应的解法，大家应该很好的体会一下。如果没有相应的准备，属于面试的
时候比较容易跪的题目。


Permutation

输入没有重复：Permutations, CC150 9.5, PIE Chapter7 Permutations of a
String
输入有重复，输出不能有重复：Permutations
II


Next Permutation: 经典算法，背吧

Permutation Sequence: 非常有意思的题目


Combination

纯粹的subset

输入没有重复：Subsets, CC150 9.4, PIE Chapter7 Combinations of a
String
输入有重复，输出不能有重复：Subsets
II


需要满足一定要求的组合

一个元素只能取一次(输入没有重复): Combinations

一个元素可以取多次(输入没有重复): Combination Sum, CC150
9.8
一个元素只能取一次(输入有重复，输出不能有重复）:
Combination Sum II


Gray Code: 具有subset的序列特点 （考虑CC150 9.4 Solution#2:
Combinatorics)


Peking2面试题总结(4) - 数据结构和算法

下边是我认为面试中常见的数据结构和算法，以Java的类库作为标准。


数据结构

Array, ArrayList

String, StringBuffer

LinkedList

HashMap, HashSet

Stack and Queue

Tree:

BT: binary tree

BST: binary search tree,

Balanced BST (red-black tree): TreeMap, TreeSet

Trie: prefix tree

Heap: PriorityQueue
Grpah


注意：

Array和Linkedlist是最最基本的数据结构，因为他们可以构造很多其他的数据结构，
比如String
(C语言里String就是字符数组），HashMap, Stack和Queue
(Java里Queue就是LinkedList实现了Queue的interface;
Ruby里stack和queue都是array）, 以及Heap。

Heap is a tree logically, but array physically.

HashMap, Stack and
Queue通常不会出现在问题里的数据结构中，因此一般作为solution的数据结构。但是
面试中也常会让你实现这三种数据结构，另外就是CC150的3.2和3.5都是典型的Stack和
Queue的题。Leetcode中并不涵盖这些内容，这几种数据结构在Leetcode中都是作为
solution数据结构出现的
(没有的原因是这些题目不太适合OJ，因此需要单独练习）。

目前Leetcode还不包含graph的题型



算法

Sort: quick sort, merge sort, count sort, heap sort, bucket sort,
radix sort, external sort, K selection etc.

Merge: 2 array/list merge, k-way merge, interval merge
etc.

Binary search:

Stack:

Recursion and Iteration:

DFS：pre-order, in-order, post-order for trees

BFS: 需要用Queue

DP: Top down and bottom up

Greedy:

Toposort: 需要用Queue


注意：

Leetcode并没有包含各种sort算法，而通常面试很少让你直接去实现sort算法，但是大
部分的相关编程技巧是包含在很多题目当中的,
比如quick sort的two pointers。

Merge跟sort是紧密相关的，单独拿出来是因为有很多这个类型的题目，需要一起总结
。Merge操作的对象基本都是已经排好序的。

Stack虽说是数据结构，但是一般出现在solution里，因此代表了一类算法

Toposort面试作为难题也很有可能遇到，目前Leetcode还没有包括进去


Peking2面试题总结(5) - Binary search and divide and conquer

玩竞赛对面试不利的一个地方就是面试经常遇到的数据结构比如LinkedList, Tree, 和
算法Binary
search，竞赛很少涉及到，因此一直心里都感觉到有些不安。

Binary search非常tricky，虽说道理简单，但是面试的时候却很容易出bug，因此总结
一下是必须的。假设i=0,
j=A.length-1, 我做了一下LeetCode上的所有binary
search的题目，发现了以下几点值得注意。


终止条件不同 i<=j, i<j

mid的上下取向不同 i+(j-i)/2, j-(j-i)/2

如何合理分半

分半的时候取=mid, mid-1, or mid+1


Search a 2D Matrix： 这是一道普通的binary search。终止条件i<=j,
mid取向i+(j-i)/2, 分半的时候=mid-1 or mid+1。

Search for a Range：这道题需要终止条件i<j,
mid取向两种都需要用到，分半的时候需要用到=mid。我发现一般＝mid的时候，终止条
件往往是i<j,
不然会有死循环。


如何合理分半：下边这几道题都很tricky，分半的时候都有各自的特点，很不容易一次
写对。需要多多练习和体会。

Search in Rotated Sorted Array

Search in Rotated Sorted Array II

Median of Two Sorted Arrays


还有一个有趣的现象就是很多数学相关的题目也是通过binary search来解决的：

Divide Two Integers：这题没做过面试也容易跪

Pow(x, n)

Sqrt(x)：其实算是一道典型的binary
search题目，不过里边包括了几个tricky的地方，很难一次写对


总的来说，LeetCode上边的这些binary
search的题目cover的还比较全面，而且题目全部是面试高频题，需要练习一次写对。



Peking2面试题总结(6) - Linked List




首先LeetCode上几乎所有的Linked list的题目都可以用two pointers来解决，或者会
用到two
pointers这个基本编程技巧。因此two pointers跟linked list是紧密相关的。因为two
pointers以前已经总结过了，就不多讲了。


其次，因为LinkedList和Array/ArrayList一样都具备有List的特性，因此很多题目都
出现在了两种数据结构上，或者说很多题目都是可以把这两种数据结构互换的。比如：

Add Two Numbers

Convert Sorted List to Binary Search
Tree

Insert Interval

Merge Intervals

Merge k Sorted
Lists

Merge Two Sorted
Lists

Remove Duplicates from Sorted
List

Remove Duplicates from Sorted List
II


第三，LinkedList的题目大多自然而然使用iteration来解决的，但是我发现有些时候
iteration比较容易出bug，换成recursion实现更容易。面试的时候万一iteration卡住
可以换换recursion的思路。


第四，dummy head非常有用，可以使代码简洁很多，并且容易写bug
free的code。这个技巧可以大量使用。


第五，今天做了一遍LinkedList的题目，发现两个地方容易出bug。一是two pointers
loop完之后常常会有一个收尾的工作，比如Add Two
Numbers需要处理carrier>0的情况。二是在swap了nodes之后，新的tail需要把next置
空，不然就出现死循环了。

面试题总结(7) - Tree

一直没有总结Tree，这次想总结一下结果却发现没有什么太多可以总结的。Leetcode上
tree的题目还是比较全面的。我做了一遍发现基本上跑不出三个套路：

1. Recursive DFS

2. Iterative DFS

3. BFS


有些tree的题目比较tricky一些，但是最终解法还是逃不出这三个套路，所以我觉得面
试的时候代码的质量就变得更加的重要了。因为没有什么太多总结的，下边就随便聊一
下了。

Leetcode上graph的题目涉及的很少，不过从算法和coding来说DFS，BFS完全适用于
tree和graph。因此，把tree的题目练好了，graph的多数题目应该也不会有什么问题才
对。当然graph涉及的算法比tree还是要多的，比如shortest
path,
toposort等等，但是DFS,BFS还是基本中的基本。因此做Leetcode上的tree的题目也相
当于练习了graph的题目了。


由于Tree的题目比较多，我感觉一些可以skip掉，如果时间不充裕的话。或者做一遍即
可，不需要反复练习。这些题目或者太简单，或者面试不太可能碰到。

Balanced Binary Tree

Binary Tree Level Order Traversal II


Maximum Depth of Binary Tree

Minimum Depth of Binary Tree

Same Tree

Symmetric Tree

Unique Binary Search Trees

Unique Binary Search Trees II


Pre-order, In-order, Post-order traversal
需要会recursive和iterative的两种实现方式。可惜Leetcode上只包含了In-order，有
些遗憾。


Tree的serialization/deserialization也是常常被考到的题目，这个Leetcode目前还
没有包含，当然套路还是DFS/BFS。


LinkedList和Binary Tree相互转换的题目。

Convert Sorted List to Binary Search Tree

Flatten Binary Tree to Linked List
(这题原题在CC150是一道双向链表题，不知道Leetcode上怎么改单向了。双向链表应该
更复杂一些，大家要注意一下）

经典面经

捐过leetcode, 找好房子，上一亩三分地贡献下自己找工作的一些经验。我的CS背景较弱，走的是刷题流。
背景: USC EE转CS, GPA 3.5+，两个startup实习，主要投的android和front-end职位
时间表：今年寒假开始刷题，到5月底最后拿到Facebook offer。前后面了10家左右的公司（略去小公司），顺序是Oracle(Offer), Amazon(Rej), Twitter(Rej), Google(Rej), Facebook(Offer), Yahoo(Offer)。每次面试前会把各公司glassdoor及Careercup刷一下，平时则是刷Leetcode和CTCI打基础。到5月底的时候Leetcode总共刷了3遍，CTCI也刷了3遍。面试来源：Oracle是学校的career fair, Amazon,Yahoo和Google是网投，Twitter,Facebook是网上找的内推。在此再度感谢"面试做题-美国CS交流群(167615205)"，提供了新鲜的面经和给力的内推。.

签了NDA, 就不分开说了, 把见过的一些题目罗列如下
Binary Tree Level Order Traversal
Reverse Words In String
Generate Random N using Random 1: Given a random generator of 0/1, generate random number in range 0-N
Get a random node in a tree, O(lgn)
Common Ancestor in a BT/BST.
Insert a node into an ordered circular list
SortColors
WordSearch
2Sum/3Sum
Generate valid words given character set
Triangle
Sort numbers with the requirements: a1>a2<a3>a4...
BestTimeToBuyAndSellStocks.
Anagram
Find Equilibrium Index of a matrix
Prefix/Infix notation evaluation
Longest Increasing Subarray/ Subsequence
Reverse a stack using recursion
Find min and max in array with least number of comparisons
Implement readline() using read4k()
Regular Expression Matching
(Weighted) Interval Scheduling
Find inorder predecessor of a given node in BST
Find median of streaming data
K largest
Quick Select/ Sort
Generate Fibonacci series
Edit distance
Graph clone
Battleship oo design
TicTacTeo oo degisn
Parking lot oo design
Saolei oo design
FizzBuzz
Combination/Permutation
Find shortest path between two nodes on graph
ValidBST
RangeMinimumQuery (Deque, segment tree)
面试是力气活，也是运气活，感谢一起刷题的小伙伴们。
祝大家早日拿到心仪的offer。


楼主给的介绍很详细！请问一下面试的时候除了会问数据结构算法，还一般会问些什么方面的问题？该怎么准备？


每个公司套路不一样，所以还是建议每个公司都要刷glassdoor和面经分别准备。



---------------------------------------------
Bloomberg L.P. Software Engineer Interview Question

"using a log generated by a multiprocessor machine, which contains start and end time of each process, find the longest slot of time in which the machine wasn't idle. the log is sorted by the process's start time."

几家

发信人: jakemajia (jakemajia), 信区: JobHunting
标  题: 报Amazon Offer，附bloomberg等几家面经，发100个包子
发信站: BBS 未名空间站 (Sun Aug 17 18:39:54 2014, 美东)

感谢版上的人报各种面经，小弟也尽量回忆说说自己的面试经历， 希望有所帮助。强
烈推荐大家加入群名称是zalgorithm算法面试QQ群 （229623621）。 喜欢讨论问题的
可以讨论，喜欢潜水的可以看人家讨论激励自己多做题。

我的背景是 new graduate PHD, 由于老板的原因，在一家公司有3-4年的intern经验。
申请的都是编程的工作。

第一个面试过的是新泽西的audible 亚马逊的公司，整体难度不大， 题目在leetcode
里面属于中等偏下。总共2 轮电面，5轮 on-site. OOD 设计题是 design flight
ticket system有一轮没有做题，纯粹说自己做的东西还有behavior questions （
interviewer 是经理，应该是bar risers）。  面试完后一个星期给offer，但是感觉
offer不好，据了。

后面面bloomberg，可能运气好题目也不难。一轮 电话面试包括 best time to sell
stock, 还有一个string排序的问题 （具体不记得）。 On-site的问题包括 2 Sum,
build Stack using Two Queues,  一个数组里重复最多的元素， reverse linked
list,  多个数组找到到在每个数组里面都重复的元素 (比如 [1,2,2,3,4,4],  [1,2,2
,3,3], 第一个数组里面 2和4重复，第二个里面2，3重复， return [2]).    经理面
试没问编程题目，就问了问做的东西，哪里有瓶颈，哪里怎么实现的。 最后拿到了
Offer。

后面面F家 new york 的位置。电话面试题是 检测palindrome string, 找出最长
palindrome string (跟leetcode不一样，方法差不多)。 On site 题目有Merge
Intervals,  Binary Tree Maximum Path Sum。 设计题： 已知有facebook.com, m.
facebook.com (移动端),  o.facebook.com（为贫困山区建的，省数据流量，没有图片
）， 服务器端有各种数据不用你操心，设计一个客户端和服务器端的API。  大概一个
月收到据信。

后面 亚马逊纽约招人，所以又点了下申请。然后Recruiter联系，没有面试给了纽约的
offer。 最后决定接受这个offer。

现在小弟也终于可以内推人了 ^_^.  有需要内推amazon可以联系我




发信人: yaqifighting (yaqi), 信区: JobHunting
标  题: EE 转ＣＳ面经
发信站: BBS 未名空间站 (Wed Apr  9 15:33:18 2014, 美东)

小女ＥＥ小硕一枚，　从刷题到面试整整半年，总算有着落了，在版上学了很多，现在
把自己的面经总结下，希望能帮到别人。
1, Microsoft
on-campus
*Card Shuffle
*设计一个报警器

2, Yelp
phone:
*chain iterator
*给一个特定的message，根据keyword 输出，比如输出所有含yelp food 的message

3, blackrock
1, 设计file system
2, Java refactor 的用法
3， OOP 的基本概念

4， A 家
1， URL group， 输出最常用的URL
2， 黑白格路径问题
3， reverse a linked list ，两种方法
4， Design bus schedule system


还有一些记不太清楚，总体来讲觉得对EE 的同学来说从cracking the coding 开始是
个不错的选择，然后再做一些leetcode, 对语言的基本概念要清楚。祝大家都能找到理
想的工作。



发信人: Zhuimeng1314 (  追梦一生), 信区: JobHunting
标  题: Facebook面经
发信站: BBS 未名空间站 (Sat Aug 16 12:34:34 2014, 美东)

都不难，非常注重代码的速度跟简洁性。不过俺已挂。大家加油。
电面
Clone graph
onsite
1. 一个manager 先聊behavior， 然后做了一个小题
    isOneEditDistance 判断两个string是不是只差一个编辑距离。
2. 3Sum 变体，每个数字可以重复用。
3. System design设计手机上读取photo feeds的app。
    功能： 读取好友的最近图片
               阅览好友的相册
    要求： 满足功能的同时减少对手机的能耗。
4. (1) 一维度向量相乘。每个向量很长，billion个数字。
    (2) 多线程 reader 跟 writer 的经典问题。
加面
1. 求 LCA 两种情况，有parent结点跟没有parent的结点的情况都要回答。
2. search in rotated sorted array LC原题。
    decode ways LC原题。

--------------------------------------------

g 最新2014.7月电面


把一个list的字符串  编码成 一个字符串

再把这个编码过的字符串 转回原来的list
String encode(List<String> strings){

}

List<String> decode(String s){

}



Ans:
用"\"作为转义字符:

我找了一下，看到一个不错的答案。就是先将每个单词里面的反斜杠'\'加倍变成连续2个'\'，然后将每个每个单词里面的逗号','前面加上一个反斜杠'\'。最后在每个单词中间加上一个逗号','。得到输出的字符串。
反序列化的时候遇到第一个反斜杠就先跳过，然后加上后面的字符。这样就可以解码了。说起来不太描述，大家可以看一下这个链接里的第一个答案，然后在纸上比划比划。

http://stackoverflow.com/questions/853475/whats-the-simplest-way-to-encoding-liststring-into-plain-string-and-decode-it

Ans2:
字符串编码的话有现成的方案。
BitTorrent规范里用到的BEncoding就是，字符串长度+冒号+字符串。
直接照着BEncoding的规范做List<String>序列化和反序列化就行了。
---------------------

Given a string s, remove duplicate adjacent characters from s recursively.(注意这里的recursively 不是指必须写recursive函数)

For example:
Input: "abbac"
Output: "c", first remove adjacent duplicated 'b's, then remove adjacent
duplicated 'a'.

Input: "acbbcad"
Output" "d", first remove 'b', then remove 'c', then remove 'a'.

Input: "acbbcda"
Output: "ada"

other example:
string str1 = "geeksforgeeg";
Output: gksfor

string str2 = "azxxxzy";
Output: ay （3个x相邻，全删掉，然后删除z）

string str3 = "caaabbbaac";
Output: empty string

Do it with one pass over the string.

发信人: rtscts (syslink), 信区: JobHunting
标  题: Re: 请教一道题：Remove adjacent duplicate char recursively fro
发信站: BBS 未名空间站 (Tue Jun  3 20:52:35 2014, 美东)

push into stack and popup if next char is the same.

  public static String removeDup(String str)
        {
            if(str == null || str.length() <= 1)
                return str;
            Stack <Character> stack = new Stack<Character>();
            Character last = ' ';
            for(int i = 0; i < str.length(); i++)
            {
                char ch = str.charAt(i);
              
                if(ch!=last && (stack.isEmpty() || ch != stack.peek()))
                {
                    stack.push(ch);
                }
                else if(!stack.isEmpty() && ch == stack.peek())
                {
                        stack.pop();
                }
                else if (ch == last);
              
                last=ch;
            }

            return stack.toString();
        }




Expand a random range from 1–5 to 1–7



Adam Rosenfield's solution:

关于思路也可参考：
http://ariya.blogspot.com/2007/11/random-number-15-to-17.html
   

There is no (exactly correct) solution which will run in a constant amount of time, since 1/7 is an infinite decimal in base 5. One simple solution would be to use rejection sampling, e.g.:


int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

This has an expected runtime of 25/21 = 1.19 iterations of the loop, but there is an infinitesimally small probability of looping forever.





This is equivalent to Adam Rosenfield's solution, but may be a bit more clear for some readers. It assumes rand5() is a function that returns a statistically random integer in the range 1 through 5 inclusive.

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.

Like Adam said, this can run forever in the worst case, but statistically the worst case never happens. :)




2

design a Data structure that satisfies: insert, remove, contains, get random element, all at O(1)



Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.

    insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
    remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
    contains(value): return H.contains(value)
    getRandomElement(): let r=random(current size of A). return A[r].

since the array needs to auto-increase in size, it's going to be amortize O(1) to add an element, but I guess that's OK.





3.

A zero-indexed array A consisting of N integers is given. A magnitude pole of this array is an integer Q such that:
0 ≤ Q < N;
A[P] ≤ A[Q] for 0 ≤ P < Q;
A[Q] ≤ A[R] for Q < R < N.
For example, consider array A consisting of ten elements such that:
  A[0] = 4 
  A[1] = 2 
  A[2] = 2
  A[3] = 3 
  A[4] = 1 
  A[5] = 4
  A[6] = 7 
  A[7] = 8 
  A[8] = 6
  A[9] = 9
Number 5 is a magnitude pole of this array, because all elements to the left of A[5] have values smaller than or equal to A[5] (4, 2, 2, 3 and 1 are smaller than or equal to 4) and all elements to the right of A[5] have values greater than or equal to A[5] (7, 8, 6 and 9 are greater than or equal to 4). Number 9 is also a magnitude pole of this array.
Write a function:
class Solution { public int solution(int[] A); }
that, given a zero-indexed array A consisting of N integers, returns any of its magnitude poles. The function should return ?1 if array A does not have a magnitude pole.
For example, given array A consisting of ten elements such that:
  A[0] = 4 
  A[1] = 2 
  A[2] = 2
  A[3] = 3 
  A[4] = 1 
  A[5] = 4
  A[6] = 7 
  A[7] = 8 
  A[8] = 6
  A[9] = 9
the function may return 5 or 9, as explained above.
Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [?2147483648..2147483647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.















Answer:

use two array. one array records the max value till now. the other records the min value in the range [cur_pos, end].




5.Given a file, find the ten most frequently occuring words as efficiently as possible


Answer:


I think the trie data structure is a choice.

In the trie, you can record word count in each node representing frequency of word consisting of characters on the path from root to current node.

The time complexity to setup the trie is O(Ln) ~ O(n) (where L is number of characters in the longest word, which we can treat as a constant). To find the top 10 words, we can traversal the trie, which also costs O(n). So it takes O(n) to solve this problem.


Also: trie+minheap    http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

related:
ebay interview:

    a. how to get top 10 frequent words in a small file?
    b. how to get top 10 frequent words in a large file (cannot fit into memory)?
    c. how to get top n frequent words in a large file (cannot fit into memory, n could be dynamically changed, this function would be called for several times)?
    d. how to get top n frequent words in a word stream?




find longest increasing sub sequence in 2d array.
(bit more expl..)
ex: finding length of the snake in snake game
---------
the sequence must not be diagonally.
but it can be any like top-bootm,bottom-left-top ........
increasing means one step
ex: 10,11,12,13 (correct)
12,14,15,20(wrong)
Ex: input: consider 4x4 grid
 2 3  4  5
 4 5 10 11
20 6  9 12
 6 7  8 40

output : 4 5 6 7 8 9 10 11 12



Answer:(此题应该用dp的memoization, as it is said in CLRS, if some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required.)



we can do it by dynamic programming. here are the steps:
1. create a new 2d array (let say named temp[][]) of same dimension as original. the element temp[i][j] contains the length of the LIS starting at this point.
2. first fill this temp array with 0's.
3. now, start filling this temp array. let say given array's dimension is MxN.

int arr[M][N]; // given array.
int temp[M][N];

for (i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] == 0){
fill(temp,i,j);
}
}
}

here is fill() function.
int fill(int temp[][], int i, int j){
if(i<0 || j< 0 || i>=M || j>=N)
return 0;

if(temp[i][j] != 0)
return temp[i][j];

int left=0,right=0,up=0,down=0;
if(arr[i-1][j] = arr[i][j] +1)
up = fill(temp,i-1,j);
if(arr[i+1][j] = arr[i][j] +1)
down = fill(temp,i+1,j);
if(arr[i][j-1] = arr[i][j-1] +1)
left = fill(temp,i,j-1);
if(arr[i][j+1] = arr[i][j+1] +1)
right = fill(temp,i,j+1);

temp[i][j] = max(up,down,left,right) + 1;
return temp[i][j];
}

thus it will calculate each element of temp array only once.

4. now, find the maximum element in the array. it's value will be the length of LIS.
max_x=0,max_y=0;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] > temp[max_x][max_y]){
max_x = i;
max_y = j;
}
}
}

5. Above will give the length of LIS. now, to find the LIS, we will check it's neighbours whose LIS value difference is 1.

i=max_x, j= max_y ;
printf("%d ",temp[i][j]);
while(temp[i][j] != 1){
if(temp[i-1][j] == temp[i][j] -1){
i = i-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i+1][j] == temp[i][j] -1){
i = i+1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j-1] == temp[i][j] -1){
j = j-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j+1] == temp[i][j] -1){
j = j+1;
printf("%d ",temp[i][j]);
continue;
}

}


time complexity is: O(M.N)


相关题目：Longest Increasing Sequence 2D matrix（除了上下左右，对角线也要考虑）


int original[m][n] = {...};
int longest[m][n] = {0};

int find() {
    int max = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int current = findfor(i, j);
            if (current > max) { max = current; }
        }
    }
    return max;
}

int findfor(int i, int j) {
    if (longest[i][j] == 0) {
        int max = 0;
        for (int k = -1; k <= 1; k++) {
            for (int l = -1; l <= 1; l++) {
                if (!(k == 0 && l == 0) &&
                    i + k >= 0 && i + k < m &&
                    j + l >= 0 && j + l < n &&
                    original[i + k][j + l] > original[i][j]
                   )
                    int current = findfor(i + k, j + l);
                    if (current > max) { max = current; }
            }
        }
       
        longest[i][j] = max + 1;
    }
    return longest[i][j];
}