C++博客-ACTime

［转］frkstyc的poj分类

ACTime — Mon, 22 Mar 2010 14:37:00 GMT

1474 geometry 1000 ad hoc 1003 ad hoc 1004 ad hoc 1005 ad hoc 1008 ad hoc 1023 ad hoc 1045 ad hoc 1046 ad hoc 1047 ad hoc 1079 ad hoc 1102 ad hoc 1126 ad hoc 1140 ad hoc 1207 ad hoc 1218 ad hoc 1220 ad hoc 1289 ad hoc 1306 ad hoc 1316 ad hoc 1326 ad hoc 1423 ad hoc 1450 ad hoc 1477 ad hoc 1488 ad hoc 1491 ad hoc 1493 ad hoc 1517 ad hoc 1519 ad hoc 1528 ad hoc 1552 ad hoc 1565 ad hoc 1583 ad hoc 1628 ad hoc 1635 ad hoc 1657 ad hoc 1658 ad hoc 1663 ad hoc 1665 ad hoc 1759 ad hoc 1775 ad hoc 1781 ad hoc 1809 ad hoc 1859 ad hoc 1868 ad hoc 1936 ad hoc 1942 ad hoc 1969 ad hoc 2000 ad hoc 2006 ad hoc 2013 ad hoc 2015 ad hoc 2017 ad hoc 2027 ad hoc 2083 ad hoc 2105 ad hoc 2109 ad hoc 2126 ad hoc 2136 ad hoc 2140 ad hoc 2141 ad hoc 2144 ad hoc 2159 ad hoc 2190 ad hoc 2196 ad hoc 2231 ad hoc 2249 ad hoc 2262 ad hoc 2272 ad hoc 2301 ad hoc 2305 ad hoc 2309 ad hoc 2316 ad hoc 2321 ad hoc 2328 ad hoc 2330 ad hoc 2350 ad hoc 2351 ad hoc 2379 ad hoc 2380 ad hoc 2390 ad hoc 2403 ad hoc 2419 ad hoc 1131 algebra 1707 algebra 1125 all pairs shortest paths 1375 analytical geometry 1473 analytical geometry 2098 analytical geometry 2242 analytical geometry 1001 arbitrary precision calculation 1354 arbitrary precision calculation 1454 arbitrary precision calculation 1503 arbitrary precision calculation 2389 arbitrary precision calculation 2413 arbitrary precision calculation 2240 Bellman-Ford algorithm 1195 binary indexed tree 1330 binary search 2418 binary search tree 1466 bipartite graph matching 1087 bipartite graph matching or maximum flow 2018 bisection and dynamic programming 1505 bisection and greedy 1434 bisection method 2155 bit operation or binary indexed tree 1111 breadth first search 1562 breadth first search 1724 breadth first search 1753 breadth first search 1915 breadth first search 1924 breadth first search 2225 breadth first search 2243 breadth first search 2251 breadth first search 2312 breadth first search 2386 breadth first search 2415 breadth first search 2426 breadth first search 2435 breadth first search 1209 calendar 2080 calendar 2210 calendar 1031 computational geometry 1127 computational geometry 1648 computational geometry 1654 computational geometry 1675 computational geometry 1912 computational geometry 2099 computational geometry 2150 computational geometry 2318 computational geometry 2398 computational geometry 2423 computational geometry 1032 construction 1147 construction 1148 construction 1702 construction 1844 construction 1898 construction 1906 construction 2085 construction 2319 construction 2356 construction 2402 construction 1426 construction or breadth first search 1606 construction or breadth first search 1113 convex hull 2187 convex hull and enumeration 1010 depth first search 1011 depth first search 1022 depth first search 1054 depth first search 1118 depth first search 1144 depth first search 1190 depth first search 1564 depth first search 1655 depth first search 1904 depth first search 1980 depth first search 2184 depth first search 2186 depth first search 2362 depth first search 2378 depth first search 2438 depth first search 1151 discretization and union of intervals or segment tree 1182 disjoint sets 1291 disjoint sets 1703 disjoint sets 1984 disjoint sets 2021 disjoint sets 2236 disjoint sets 2371 divide and conquer 2388 divide and conquer 1014 dynamic programming 1015 dynamic programming 1018 dynamic programming 1036 dynamic programming 1038 dynamic programming 1050 dynamic programming 1088 dynamic programming 1093 dynamic programming 1156 dynamic programming 1157 dynamic programming 1159 dynamic programming 1160 dynamic programming 1163 dynamic programming 1170 dynamic programming 1191 dynamic programming 1221 dynamic programming 1338 dynamic programming 1458 dynamic programming 1579 dynamic programming 1631 dynamic programming 1651 dynamic programming 1661 dynamic programming 1664 dynamic programming 1678 dynamic programming 1685 dynamic programming 1722 dynamic programming 1732 dynamic programming 1745 dynamic programming 1821 dynamic programming 1909 dynamic programming 1923 dynamic programming 1925 dynamic programming 1953 dynamic programming 2033 dynamic programming 2133 dynamic programming 2151 dynamic programming 2181 dynamic programming 2229 dynamic programming 2247 dynamic programming 2250 dynamic programming 2342 dynamic programming 2353 dynamic programming 2355 dynamic programming 2385 dynamic programming 2393 dynamic programming 2397 dynamic programming 2414 dynamic programming 2430 dynamic programming 2439 dynamic programming 2441 dynamic programming 2442 dynamic programming 2084 dynamic programming and arbitrary precision calculation 1387 dynamic programming and enumeration 1322 dynamic programming or generating function 1012 enumeration 1013 enumeration 1142 enumeration 1171 enumeration 1183 enumeration 1318 enumeration 1411 enumeration 1543 enumeration 1647 enumeration 1650 enumeration 1828 enumeration 1916 enumeration 1930 enumeration 2078 enumeration 2100 enumeration 2191 enumeration 2245 enumeration 2326 enumeration 2346 enumeration 2363 enumeration 2381 enumeration 2436 enumeration 2444 enumeration 1267 enumeration and bisection 1129 enumeration and depth first search 1186 enumeration and hash table 1348 enumration 1472 expression evaluation 2106 expression evaluation 2246 expression evaluation 2269 expression evaluation 2234 game theory 2348 game theory 2425 game theory 1799 geometry 1927 geometry 1939 geometry 1940 geometry 2007 geometry 2208 geometry 2276 geometry 2365 geometry 2405 geometry 1981 geometry and enumeration 1090 Gray code 1832 Gray code 1017 greedy 1042 greedy 1083 greedy 1230 greedy 1328 greedy 1456 greedy 1862 greedy 1922 greedy 2054 greedy 2082 greedy 2209 greedy 2291 greedy 2313 greedy 2325 greedy 2370 greedy 2376 greedy 2431 greedy 2433 greedy 2437 greedy 1405 greedy and arbitrary precision calculation 1659 greedy and construction 1026 group theory 1033 group theory 1286 group theory 1674 group theory 2369 group theory 2409 group theory 2366 hash table or binary search 1521 Huffman tree 1742 knapsack 2392 knapsack 1538 Lagrangian interpolation 2344 linear algebra and greedy 1462 linear systems 1914 linear systems 2440 matrix algebra 1149 maximum flow 1273 maximum flow 1459 maximum flow 2125 maximum flow and minimum cut 2377 maximum spanning tree 1258 minimum spanning tree 1679 minimum spanning tree 1861 minimum spanning tree 2421 minimum spanning tree 1166 modular systems 1222 modular systems 1681 modular systems 2345 modular systems 1905 Newton's iteration 2420 Newton's iteration 2299 number of inversions 1006 number theory 1061 number theory 1067 number theory 1152 number theory 1284 number theory 1320 number theory 1401 number theory 1455 number theory 1597 number theory 1808 number theory 1811 number theory 1845 number theory 1995 number theory 2115 number theory 2407 number theory 2417 number theory 2429 number theory and enumeration 1146 permutation 1256 permutation 1731 permutation 1833 permutation 2079 rotating calipers 2104 search 1177 segment tree 2182 segment tree 2352 segment tree or binary indexed tree 1016 simulation 1028 simulation 1048 simulation 1049 simulation 1051 simulation 1060 simulation 1281 simulation 1298 simulation 1363 simulation 1504 simulation 1573 simulation 1578 simulation 1589 simulation 1592 simulation 1600 simulation 1656 simulation 1660 simulation 1666 simulation 1684 simulation 1926 simulation 1928 simulation 1978 simulation 2014 simulation 2039 simulation 2050 simulation 2051 simulation 2081 simulation 2271 simulation 2317 simulation 2339 simulation 2340 simulation 2359 simulation 2383 simulation 2410 simulation 2424 simulation 2443 simulation 2387 single source shortest paths 2394 single source shortest paths 1002 sorting 1245 sorting 1520 sorting 2092 sorting 2408 sorting 1007 stable sorting 1572 string manipulation 1646 string manipulation 1917 string manipulation 2406 string matching 1128 topological sorting 1785 treap 2201 treap 2255 tree manipulation 1089 union of intervals 1797 variation of Dijkstra's shortest path algorithm 2253 variation of Dijkstra's shortest path algorithm 2395 variation of Dijkstra's shortest path algorithm 2254 vector algebra 2354 vector algebra 2412 vector algebra 1130 vertex connectivity 1308 vertex connectivity 2320 vertex connectivity

ACTime 2010-03-22 22:37 发表评论

百度笔经&面经(zz,详细！赞！)

ACTime — Sun, 21 Feb 2010 08:37:00 GMT

百度笔经&面经(zz,详细！赞！)
2007年10月20日星期六 16:34发信人: ptlj (PT), 信区: Job_Discuss
标题: 百度笔经&面经发信站: 武汉白云黄鹤站 (2007年10月08日12:50:13 星期一)
看了一下精华区，好像关于百度的笔经和面经很少，所以上来发一下，积攒RP～～PS:我投的是商务搜索部的引擎研发工程师。

【笔试】百度的在华科的笔试在9月21号晚上宣讲会后马上举行。宣讲会那叫一个人山人海，很多不是毕业班的人也来凑热闹感受一下百度招聘。笔试题目有选择题，编程题，系统设计题三种类型。选择题难度不是很大，但我太水了，很多基础知识都不记得了，正则表达式，shell编程～～～汗死，不说了，好多都是蒙的。编程题有3题，第一题是找出字符串的最长不重复子串，输出长度。我想了半天，只会O(n^2)的算法，是个人都可以想出来的笨办法，想着写下来也没啥意义，题目问有没O（n）的，那看来肯定有O（n）的，就不写了，看后面的题算了。第二题是找出一个字符串的最长回文子串。这个问题好像以前考研复习数据结构时看过，想起来判断一个回文串可以用栈来实现，稍微回忆一下，算法思路就出来了。于是提笔写下了个O(n^3)的算法。汗死了，自己太笨了，只能想出这种垃圾算法，看来百度不好混啊。第三题是在2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。这种题是百度的特色，海量数据处理，我也没啥思路。既然不能一次扔进内存，我就分批扔进去，尽量减少从外存读进内存的次数，然后算了一下，分2批扔进内存。然后每批排序，找出每批里面不重复的数，把这些不重复的再在另一批数中过一遍，去掉重复的，然后汇总。写不出具体代码，只把思路写了一下。当时心情沮丧极了，想着，挂了，代码不会写，难得写出一题又是效率极低的。最后那道系统设计题，我压根没啥好思路，题目大概是海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。草草写了几笔，时间就到了，交卷～～～看来，这次除非有奇迹，不然笔试肯定被BS了。

考完回到寝室，和兄弟们讨论一下题目，第一题原来可以用Hash实现，时间复杂度降到O(n)。自己仔细想了一下，整个算法的思路就清晰了，郁闷啊，这么简单的题居然没想出来，看来自己还是太菜了。ZZ对第二题还有个新颖的算法，学习了一下，赞啊，亏他想得出来，呵呵。第二天还有Microsoft的笔试，赶紧拿Primer来抱抱佛脚，这么好的一本书，我学C++时怎么就没看啊？后悔，懊恼充斥着我的大脑，大有相见恨晚的感觉。虽然自己笔试很烂，但是还是寄希望于奇迹出现，能有机会去面试。于是晚上睡觉开着手机，因为座谈会时百度说如果笔试通过，当晚凌晨就会出面试通知了。晚上辗转反侧，难以入睡，期待手机铃声响起，都不知道几点才睡着。早上起床一照镜子，大熊猫再现拉，唉，为百度消得我憔悴啊。自己空想也没用，眼前还有MS等着我呢。考MS时，手机都没关，就等着百度电话，希望考试时能有电话来。果然，早上11点多还在考试时，手机响起，挂掉，我还在为了MS笔试而挠头呢。几分钟后，又响了一次，再次挂掉。考完试，出考场拿手机一看，咦，是027的哦，好像是个小灵通。回拨，不通，继续回拨，还是不通，不死心，我就不信拨不通你。结果拨了10多次还是不通，算了，只好等他再打来。回实验室，上Q问问这个号码是不是百度的，JG他们说是的，惊喜，Oh，yeah，百度面试来临了， Miracle居然发生了。于是和JG，DJ，Q拼车去弘毅面百度。结果面官说我不接电话，他们安排了其它同学面试，叫我第二天早上10点再来面。FT，怎么这么曲折啊，不过给我点时间复习准备，也好。

【一面】晚上好好看了一下项目，把重点温习了一下。又问了下JG面试问了啥，心里有个底了。第二天，一个人飞的去了弘毅，花了22大洋，好心疼啊。去到昨天那个房间，看见面官了，一个光头，和JG昨天的面官一样。果然，他上来就问了我昨天问JG的同样问题，设计一种数据结构，结合了链表和数组的优点。我想了一下，说用Hash链表，这样插入和查找的效率都比较高，但是有conflict问题要解决。他马上就问我如何解决conflict问题，有没什么好方法。我说修改hash函数，使得hash值产生的conflict概率尽可能低。他问那你怎么设计？我倒，这个问题我可没想过啊。当场郁闷了，立马陷入苦思状态。想出几个点子，都不管是否可以降低conflict的概率，都和面官说了。他很快就举例否定我好不容易想出的点子，说你的办法还是不行哦，有没更好的？打击死了，我已经尽力了啊，没想到这么快就被他找到反例，郁闷死我了。不过面官人很好，看我实在想不出更好的了，就不为难我了，换下一个题目。后面一题是海量日志数据，提取出某日访问百度次数最多的那个IP。想了一下，说了个思路。面官就问你这样需要的存储空间太大，有没优化方法。看来思路是正确的了，但是优化问题嘛，好棘手啊。我又说了个优化的方法，面官不太满意，摇头。完了，实在想不出来了。。。。面官见我苦思冥想，也不为难我了。接着就问了下项目经验，我balabala一通，他对我的项目不太感冒，没问什么问题。然后就问笔试卷子了，他问我第一题干嘛空白？我说了原因，他问我现在有好的想法没？我就把自己考完后想的O（n）的算法说了一下，他比较满意，没问我什么就问第二题了。我又说了下我当时的算法思想，他问有没更好的优化算法？我说可以做到O（n^2），把思路说了下。似乎不是他的满意答案，也没问我啥。接着问第三题，我把我的想法说了。他说，你最后还需要折半查找这么麻烦吗？对2个有序的数组，查找A数组的元素是否在 B数组中出现有没更好的算法？我想了一下，突然灵机一动，想起归并排序的算法。就说，是不是像归并数组那样，直接在B中定位出A的位置，这样就可以在O(m+n)内实现。他比较满意，说：“是啊，都有序了，你还折半这么麻烦啊？”暴汗，看来面官水平比我高太多了，思维跟不上。然后看面官总算露出点笑容，忍不住问句：“你觉得我这个算法可以接受不？”他的回答让我很吃惊，他说：“当然可以接受拉，我觉得挺好的啊，不过你的算法要访外存，可能时间效率不是很高。不过先要完成题目的任务，再考虑优化。”我赶紧补一句：“是啊，先要让它work，再考虑如何让它work better。”面官还来句：“不过这个题最好的算法可以一次把2.5亿数据扔进内存，这需要你设计一个好的数据结构。”我问：“这个，怎么设计哦？”面官表示不能告诉我答案，让我自己回去想。这时，面官看看表，我也看看表，已经面了50分钟了。他说：“现在我们再做2道数学推理题。第一题，2个盒子，容量足够大，现在有50个红球，50个蓝球，你如何安放这些球进盒子，使得我随机抽取一个盒子，然后从里面随机抽一个球，这个球是红球的概率最大？给你2分钟时间考虑，直观分析给出结果。”当场我就晕倒了，从小到大，我都不会做IQ题的啊，这可是我的最弱项。没办法，不能直接说我不会啊。只好硬着头皮上，分析一下，我说：“列条概率的表达式，求最值，可以求出结果。”他说：“你这样搞2个小时都算不出结果。从直观上分析就可以知道结果了。你再想想”，被打击了。只好继续想，我想，那把50个红球放到一个盒子，另一个盒子全放蓝球，这样一个有100％，另一个是0 ％，平均下来有50％。也不理想啊，这个时候，灵感再次突现，50个红球全放一个盒子不是浪费嘛？放1个也是100％，2个也是100%，那就放一个好了，其它全部扔到另一个盒子和蓝球一起。再想一下，这样概率有75％，应该很高了。也没仔细想是不是正确答案，就脱口而出，说了这种放法。面官再次露出笑容，说“正确！”我那时心里好激动啊，没想到运气这么好，居然还答对了。接着又来下一题，A射击命中率80%,B60%,C40%，A,B,C互为竞争对手，每人都知道另外2人的命中率，3个人同场竞技互相射击，同时开了第一枪，问第一枪射后，谁最有可能挂掉？我分析了一下，说了答案，他问我思路，我说了我的思路后，他居然来句：“你的思维和别人不一样。”FT，我和别人不一样，估计说错了，自己确实回答IQ题比别人笨一截，没办法。面官说：“好了，时间差不多了。你有什么问题问我不？”我问：“如果我有幸通过一面，什么时候会二面？”“通过的话，明早就二面。”然后，和面官握了下手，就这样结束了我的一面。面完一面后，去找LP吃饭，下午陪她上自习，感觉自己一面还行吧，大部分题都答出了思路，虽然进一步的优化没有想完整，而且运气也好得不得了，连最后2题居然还被我蒙对1题，如果进不了2面，只能说明自己离百度的要求还是差距太大了。结果好运再次降临，晚上6点多接到电话，通知第二天早上10点去二面，呵呵，竟然进了二面，真是 too lucky。

【二面】第二天准时去到面试房间，换了位面官面我。一上来就问我一道海量数据处理题。题目是：很多记录数据，有ID号，还有几个不同的属性域，现在要根据ID号高速查询到对应 ID号的数据，设计个算法。然后，现在要根据特定的属性域排序查询，既要高效找到排名在第N-M名的记录，还要经常插入，删除记录。我说，查询ID可以用Hash表查询，把ID号hash，然后可以在O(1)查到对应的记录。第二个问题，有点复杂，类似于结合数组和链表的优点设计数据结构。我说了好几种方案，问他这样行不行。他说：“你自己觉得行不行啊，现在是我面你，不是你面我啊，你自己考虑答案啊。”晕倒，我实在想不出更好的，也不知道应该如何抉择，备选方案都各有优缺点啊。最后，还是选了其中一种，回答了这个问题。面官说：“其实这个问题很难有最佳方案，就看你怎么选择，权衡，选一种较好的方案。”唉，也不知道我的答案可不可以接受，完全没了一面时的灵感了。然后面官看了下我简历，惊讶地说道：“你是武汉理工毕业的？”我也很惊讶：“你听说过这个学校？ ”因为我感觉，武汉理工又不是很有名，在北方，连华中科技名气都不是很响，没想到面官竟然知道武汉理工。结果面官说：“我就是武汉理工毕业的啊。”一听，心中窃喜，居然还有校友，赶紧套一下亲近。问他哪一级的，什么时候毕业啊，加入百度多久了之类的问题。然后自己又说了一下个人对武汉理工的感觉，尤其是当年放弃保研名额，选择去考研。他听着也觉得有点意思，我就继续说：“觉得学习氛围很重要，身边的同学对自己的影响很大。本科时，很多同学沉溺于网游，都堕落了，自己想找个人讨论问题都没有。现在去了华中科技，身边的同学都很优秀，经常和同学讨论问题，一起进步，感觉很好。”他听了后点点头，说：“你这个决定挺正确的。......blabala一通，他也不感冒。他又问我：“干嘛想加入百度公司？”我说：“自己对互联网技术很感兴趣，从本科起对数据结构和算法就有浓厚的兴趣。加上自己将来想搞研发，百度公司的技术很吊，里面的人很强，加入百度可以得到很好的锻炼，学到很多东西。百度公司现在发展很快，对自己的职场生涯很有帮助。”然后，他问我：“你对搜索引擎了解不？”我说：“之前不了解，听了座谈会后了解了一些。”他又问：“你对自然语言分析处理了解不？”“不懂”说完，我汗死了，完全不懂，有点不祥的预感了。谁知道，更郁闷的事还在后头。他接着来一句：“你做的项目都是网络安全方面的，和我们的活不对口啊？”最让我担心的事终于发生了，我故作镇定说：“恩，既有网络安全，也有网络应用和管理方面的。”然后面官就说：“好了，我的问题差不多了，你有什么问题要问吗？”我看了下表，倒，才面了30分钟就没问题了，看来我方向不对口，他对我已经没兴趣了，不行，这样草草了结，二面肯定挂掉了，得扯点他感兴趣的问题才行。马上把自己本科的那个毕业设计网络五子棋里面涉及的算法问题拿出来问问他，看看他有什么优化的方法。他想了一会，说：“这个问题有点复杂哦。”我窃喜，哈哈，该不会把你难倒了吧？接着他来句：“你当时是怎么做的？”我心想，你还真行，把问题又丢回来给我了。我就说了我当时的做法，也得到了他的认可和赞许。恩，第一步目标达成。然后又问他我投的那个职位对哪方面的要求比较高？他说：“良好的算法和数据结构的基础最重要。”我又问：“那数据库，脚本语言，网络编程方面呢？”这些都是我的弱项哦。他说：“这些都有很多现成的成果可以直接利用了，算法和数据结构可能比较难提高，所以需要有个良好的基础才行。”听完，心里有点高兴，自己的强项就是算法和数据结构方面，既然弱项不是很重要，那看来对我的影响不大。这又让我想起李开复的一句话：“ 你进MS时，懂C＃很好，不懂也不要紧，来了可以学。但是如果你不懂得如何学习，那就糟糕了。”看来，基础和学习能力是很多大公司所看重得。然后又和面官聊一下武汉理工的变化，和在华中科技读研的一些生活。最后，面官说了句：“其实，你的技术还是不错的。”听了这句后，很高兴，但是自己对搜索引擎的不了解和专业的不对口又让自己产生一丝隐忧。最后问了下“还会有3面不？”“Maybe。”和面官say goodbye，然后结束了二面。

【后记】二面后就是漫长的等待（其实也就等了6天而已，但是自己已经觉得很漫长了）。期间没有任何消息，BBS说二面过了就发offer，二面不过就去三面。对这个说法，我持保留意见，身边很多大牛都去3面了，3面是非技术面，都问你期望的月薪的，自己觉得应该是过了2面的才有3面机会吧。自己一直没等来3面的电话通知，已经觉得自己挂了。期间找 LP诉苦，她安慰我说：“说不定就像BBS说的那样，二面过了就不用三面了吧。你干着急也没用啊，好好复习等消息吧。”虽然是安慰我的话，但是在等待的日子里有个人可以诉苦感觉还是挺好的。联系了一下内推的那个人，他说他也不知道结果，问我是谁面我的。我说一面是光头，把二面面官的名字报了一下。他说：“光头是他们部门经理。”我很惊讶，啊？部门经理？看不出来啊，既然部门经理都让我过1面了，应该机会还挺大的啊，自我感觉一面比二面好多了。每天逛BBS，不仅看白云，还看珞珈山水，交大思源，还有天大求实。等待真是种煎熬啊，虽然各方面的信息都是朝着不利的一面发展，但是自己还是不死心，一天没发offer，就还有机会；既然没发据信，那就还有希望。等啊等，终于在国庆前一天发offer了，居然自己也有！回顾这次百度之旅，感觉运气太好了。一面是部门经理，其实过了他这关基本问题就不大了。恰好自己那天状态超好，灵感不时出现，临场超水平发挥，总算过了第一关。第二关在形势很不利的情况下（连说几个“不懂”），自己给自己找加分项目，朝着职位的要求往上靠。既然算法和数据结构要求高，我就要表现出自己这个方面有优势，扯毕业设计的算法设计和面官聊，表示自己对这方面有兴趣，基础不差。还有突出一下自己其它方面的优点，例如上进，好学，对技术有偏执（百度系统部老大的经典说法）等。觉得面试时还有一点做得不错的就是，当面对一个自己没什么思路的问题时，只要你有什么新想法，不要管这个想法是否可行，是否可以真的解决问题，先把它说给面官听，让他觉得你的思考问题的能力还是很强的。一定不要想了半天，结果说“不知道”这样面官对你的印象就会很差。虽然你的idea可能不是很work,但是只要是朝着正确的方向前进就OK拉，面试官会给你一定的指引的。你继续朝着那个方向想，说不定很快就可以解决问题了。以前都是看别人的面经，获益良多，这次自己写写笔经，面经，希望对大家有帮助。最后，希望大家都能找到自己满意的工作，其实付出和收获真是成正比的。可以从事自己喜欢的工作，真是很高兴。目标和准备方向的正确可能是我这次应聘成功的最主要因素之一吧。我投简历只投研发的岗位，对不搞技术的公司压根没投，不管公司有多大有多好，像P&G，MARS，国企，公务员等。一来不想占用别人的机会，二来也知道自己更适合在技术方面发展，去非技术类公司自己的发展可能不如技术类公司。呵呵，写得我好累啊，就写到这吧，希望能对大家有用。

ACTime 2010-02-21 16:37 发表评论

卡特兰数（Catalan数）

ACTime — Sat, 06 Feb 2010 02:43:00 GMT

原理

　　令h(1)＝1,h(0)=1，catalan数满足递归式：
　　h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
　　另类递归式：
　　h(n)=((4*n-2)/(n+1))*h(n-1);
　　该递推关系的解为：
　　h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

　　卡特兰数的应用
　　（实质上都是递归等式的应用）
　　

括号化问题

　　矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)

出栈次序问题

　　一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
　　分析：对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。
　　在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。
　　不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
　　反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
　　因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应。
　　显然，不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。
　　（这个公式的下标是从h(0)=1开始的）
　　类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
　　

凸多边形的三角剖分问题

　　
　　求将一个凸多边形区域分成三角形区域的方法数。
　　类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
　　类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
　　

用给定节点组成二叉树的问题

　　
　　给定N个节点，能构成多少种不同的二叉树？
　　（能构成h（N）个）

ACTime 2010-02-06 10:43 发表评论

【做题计划】2-5

ACTime — Thu, 04 Feb 2010 16:48:00 GMT

BUPT OJ

1094ACM的组队

1095探险家Javaman

1096老鹰捉小鸡

1098机器人工厂

1099Plant

1010Snooper

1011PrisonBreak

1012SuperRock教授的教案

ACTime 2010-02-05 00:48 发表评论

POJ 1797 Heavy Transportation（最大树最小边变形）

ACTime — Fri, 01 Jan 2010 06:24:00 GMT

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1797

题目描述：求从指定起点到指定终点每条可能路径上各段边的最小值

注意事项：有向图／无向图

提交情况：3次Runtime Error，是最开始尝试用Kruskal时间接排序的数组r大小只开了MAXN个；3次WA的主要原因是无向图按照有向图做的。用邻接表存储图时一定要注意有向图和无向图的问题，已经出错好几次了。

心得体会：本道题实际是按照Prim求最大生成树的思路，逐条添加边；在添加的过程中，注意从1点出发，在遇到n时，即使最大生成树仍没有构造完，也可以从函数中返回了。最开始以为是简单的生成树问题，所有用Kruskal来作，遇到起点和终点都访问过就退出，但此时，构造的生成树可能根本就没有连接，而Prim在构造的初始就是从一棵树开始拓展的，不会出现这个问题。需要对每个具体的算法有更深入的理解。

1 #include<queue>
2 #include<stdio.h>
3 #include<string.h>
4 using namespace std;
5
6 #define MAXN 1010
7 #define MAXM 1000010
8
9 struct Edge
10 {
11     int start;
12     int end;
13     int weight;
14
15     bool operator>(const Edge &e) const
16     {
17         return weight<e.weight;
18     }
19 };
20
21 Edge edge[2*MAXM];
22 int visited[MAXN];
23 int first[MAXN];
24 int next[2*MAXM];
25
26 int Prim(int n)
27 {
28     memset(visited,0,sizeof(visited));
29     int result = 10000000;
30     priority_queue<Edge,vector<Edge>,greater<Edge> > pq;
31     for(int e=first[1];e!=-1;e=next[e])
32     {
33         pq.push(edge[e]);
34     }
35     visited[1]=1;
36
37     while(!pq.empty())
38     {
39         int start = pq.top().start;
40         int end = pq.top().end;
41         int weight = pq.top().weight;
42         pq.pop();
43
44         if(visited[end]==1)
45             continue;
46         visited[end] = 1;
47
48         if(weight<result)
49             result = weight;
50         if(end==n)
51            break;
52         for(int e=first[end];e!=-1;e=next[e])
53         {
54             if(visited[edge[e].end]==0)
55             {
56                 pq.push(edge[e]);
57             }
58         }
59     }
60     return result;
61 }
62
63 int main()
64 {
65     int snum;
66     scanf("%d",&snum);
67     for(int i=1;i<=snum;i++)
68     {
69         int n,m,start,end,weight;
70         scanf("%d%d",&n,&m);
71
72         memset(first,-1,sizeof(first));
73         for(int j=0;j<2*m;j+=2)
74         {
75             scanf("%d%d%d",&start,&end,&weight);
76
77             edge[j].start = start;
78             edge[j].end = end;
79             edge[j].weight = weight;
80
81             edge[j+1].start = end;
82             edge[j+1].end = start;
83             edge[j+1].weight = weight;
84
85             next[j] = first[start];
86             first[start] = j;
87
88             next[j+1] = first[end];
89             first[end] = j+1;
90
91         }
92
93         int result = Prim(n);
94         printf("Scenario #%d:\n",i);
95         printf("%d\n\n",result);
96     }
97 }

ACTime 2010-01-01 14:24 发表评论

Poj 1840 Eqs

ACTime — Tue, 22 Dec 2009 04:32:00 GMT

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1840

题目描述：求方程的根的个数

注意事项：hash可以用char，避免占用内存过多

提交情况：1次MLE，用int开数组太大了

心得体会：暂无

1 #include<stdio.h>
2 #include<string.h>
3
4 int calCube(int x)
5 {
6     return x*x*x;
7 }
8
9 char hash[25000010];
10
11 int main()
12 {
13     int a1,a2,a3,a4,a5;
14     scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
15
16     int result;
17     memset(hash,0,sizeof(hash));
18     for(int i=-50;i<=50;i++)
19     {
20         if(i==0)
21             continue;
22         for(int j=-50;j<=50;j++)
23         {
24             if(j==0)
25                 continue;
26             for(int k=-50;k<=50;k++)
27             {
28                 if(k==0)
29                     continue;
30                 result=a1*calCube(i)+a2*calCube(j)+a3*calCube(k);
31                 if(result>12500000||result<-12500000)
32                     continue;
33                 hash[result+12500000]++;
34             }
35         }
36     }
37
38     int ans=0;
39     for(int i=-50;i<=50;i++)
40     {
41         if(i==0)
42             continue;
43         for(int j=-50;j<=50;j++)
44         {
45             if(j==0)
46                 continue;
47             result=a4*calCube(i)+a5*calCube(j);
48             result=-result;
49             ans+=hash[result+12500000];
50         }
51     }
52
53     printf("%d\n",ans);
54 }

ACTime 2009-12-22 12:32 发表评论

POJ 1416 Shredding Company

ACTime — Sat, 19 Dec 2009 11:36:00 GMT

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1416

所用算法：枚举（01枚举）

注意事项：注意位操作，要细心

提交情况：半个月前（12月4号，两次wa），今天重新读题又完全换思路重写了一遍，ac

心得体会：数据量小，直接枚举就可以，并不一定必须要深搜或剪枝。这道题如果深搜的话，剪枝的条件也是非常明显的。代码很乱，希望半个月后review的话还能看得懂。

1 #include<iostream> 2 #include<stdio.h> 3 #include<math.h> 4 #include<stdlib.h> 5 #include<string.h> 6 using namespace std; 7 8 int calvalue(int t,int sum) 9 { 10 int result=0; 11 int j=0; 12 for(int i=0;i<=5;i++) 13 { 14 if(t&(1<<i)) 15 { 16 result=result+sum%(int)pow(10,j+1); 17 sum=sum/(int)pow(10,j+1); 18 //printf("%d %d\\n",result,sum); 19 j=0; 20 } 21 else 22 { 23 j++; 24 } 25 } 26 return result+sum; 27 } 28 29 int printvalue(int t,int sum) 30 { 31 int stack[10]; 32 int top=0; 33 int j=0; 34 for(int i=0;i<=5;i++) 35 { 36 if(t&(1<<i)) 37 { 38 stack[top++]=sum%(int)pow(10,j+1); 39 sum=sum/(int)pow(10,j+1); 40 j=0; 41 } 42 else 43 { 44 j++; 45 } 46 } 47 stack[top++]=sum; 48 while(top!=1) 49 { 50 printf("%d ",stack[--top]); 51 52 } 53 printf("%d\\n",stack[0]); 54 } 55 56 int main() 57 { 58 int target; 59 char num[7]; 60 //freopen("data.in","r",stdin); 61 while(scanf("%d%s",&target,num)==2) 62 { 63 if(target==0&&num[0]=='0') 64 break; 65 int sum=0; 66 int flag=0; 67 int length=strlen(num); 68 int minvalue=0; 69 int partition=-1; 70 for(int i=0;i<length;i++) 71 { 72 sum=10*sum+num[i]-'0'; 73 minvalue+=num[i]-'0'; 74 } 75 76 if(sum==target) 77 { 78 printf("%d %d\\n",target,sum); 79 continue; 80 } 81 else if(minvalue>target) 82 { 83 printf("error\\n"); 84 continue; 85 } 86 else 87 { 88 minvalue=0; 89 int mysum=0; 90 int times=1<<(length-1); 91 for(int j=0;j<times;j++) 92 { 93 mysum=calvalue(j,sum); 94 if(mysum==minvalue) 95 { 96 flag=1; 97 } 98 else if(mysum<=target&&mysum>minvalue) 99 { 100 minvalue=mysum; 101 flag=0; 102 partition=j; 103 } 104 } 105 } 106 if(flag==1) 107 { 108 printf("rejected\\n"); 109 } 110 else 111 { 112 printf("%d ",minvalue); 113 printvalue(partition,sum); 114 } 115 116 } 117 } 118

ACTime 2009-12-19 19:36 发表评论

POJ 3083 Children of the Candy Corn（bfs求最短路／迷宫）

ACTime — Fri, 18 Dec 2009 06:27:00 GMT

摘要: 题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3083题目描述：求最短路，求沿特定方向走迷宫的步数所用算法：最短路用bfs求，特定方向走迷宫直接用while计数（这里写的比较繁琐，要细心，本来看题目分类是在dfs里面的，以为这要用dfs，细想想不用，而求迷宫最短路径，bfs应该是首选了）提交情况：1次wa(忘了加头... 阅读全文

ACTime 2009-12-18 14:27 发表评论

POJ 1936 All in All

ACTime — Fri, 18 Dec 2009 03:55:00 GMT

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1936

所用算法：字符串

提交情况：1A

注意事项：无

心得体会：水题

1 #include<stdio.h>
2
3 char s[100010];
4 char t[100010];
5
6 int judge(char s[],char t[])
7 {
8     int i=0;
9     int j=0;
10     while(s[i]!='\0'&&t[j]!='\0')
11     {
12         if(s[i]==t[j])
13         {
14             i++;
15             j++;
16         }
17         else
18         {
19             j++;
20         }
21     }
22     if(s[i]=='\0')
23         return 1;
24     else
25         return 0;
26 }
27
28 int main()
29 {
30     //freopen("data.in","r",stdin);
31     while(scanf("%s %s",s,t)==2)
32     {
33         if(judge(s,t))
34             printf("Yes\n");
35         else
36             printf("No\n");
37     }
38 }

ACTime 2009-12-18 11:55 发表评论

POJ 2299 Ultra-QuickSort

ACTime — Thu, 17 Dec 2009 06:00:00 GMT

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2299

题目描述：求冒泡排序的交换次数

所用算法：用归并排序，求逆序数的个数

提交情况：1次tle(直接冒泡排序n^2的复杂度，对于5000000的数据量，必然超时)，1次wa（统计个数时整数溢出了），1a

心得体会：初看题目很简单，没有往数据量方面想，直接冒泡计数提交，然后看着poj上一直running&&judging直到tle, 时限7000ms呀。没做过逆序数的类似问题，而且题目本身分类也在排序那，然后考虑是不是能快排一下，比较排序前和排序后各个数的位置。考虑再三，发现解决不了。去论坛上瞄了一眼，看到可以用逆序数解，于是百度＋算法导论，学到了如何用归并排序计算逆序数的数目，写成程序，中间还出现了一次wa，然后就ac了。我在看算法导论时，因为merge在书一开始讲的，想平时排序都是快排为主流，就没有仔细想过merge可能的变种，这道题充分印证了，即使merge本身可能用的不多，但分冶的思想却是无所不在

类似题目：poj1804

1 #include<iostream>
2 #include<stdio.h>
3 using namespace std;
4
5 int num[500010];
6 int left_t[500010];
7 int right_t[500010];
8
9 long long count=0;
10
11 void merge(int a[],int p,int q,int r)
12 {
13     int n1=q-p+1;
14     int n2=r-q;
15     for(int i=1;i<=n1;i++)
16     {
17         left_t[i]=a[p+i-1];
18     }
19     for(int i=1;i<=n2;i++)
20     {
21         right_t[i]=a[q+i];
22     }
23     left_t[n1+1]=0x7fffffff;
24     right_t[n2+1]=0x7fffffff;
25
26     int i=1;
27     int j=1;
28     for(int k=p;k<=r;k++)
29     {
30         if(left_t[i]<=right_t[j])
31         {
32             a[k]=left_t[i];
33             i=i+1;
34         }
35         else
36         {
37             a[k]=right_t[j];
38             j=j+1;
39             count+=n1-i+1;
40         }
41     }
42 }
43
44 void merge_sort(int a[],int p,int r)
45 {
46     if(p<r)
47     {
48         int q=(p+r)/2;
49         merge_sort(a,p,q);
50         merge_sort(a,q+1,r);
51         merge(a,p,q,r);
52     }
53 }
54
55 int main()
56 {
57     int n;
58     scanf("%d",&n);
59     while(n!=0)
60     {
61         for(int i=0;i<n;i++)
62         {
63             scanf("%d",&num[i]);
64         }
65         merge_sort(num,0,n-1);
66         printf("%lld\n",count);
67         count=0;
68         scanf("%d",&n);
69     }
70 }

的

ACTime 2009-12-17 14:00 发表评论