蜜臀av性久久久久蜜臀aⅴ,一本色道久久88加勒比—综合,久久精品亚洲精品国产色婷

�Q��{�Q�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 发表评论

癑ֺ��W�经&面经(zz,详细�Q�赞�Q?

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

癑ֺ��W�经&面经(zz,详细�Q�赞�Q?
2007�q?0�?0�?星期�?16:34发信�? ptlj (PT), 信区: Job_Discuss
�?�? 癑ֺ��W�经&面经发信�? 武汉白云黄鹤�?(2007�q?0�?8�?2:50:13 星期一)
看了一下精华区�Q�好像关于百度的�W�经和面�l�很��，所以上来发一下，�U�攒RP～～PS:我投的是商务搜烦部的引擎研发工程师�?

【笔试】百度的在华�U�的�W�试�?�?1��h��上宣讲会后马上�D行。宣讲会那叫一个�h�׃�h��P�� 很多不是毕业班的��Z��来凑热闹感受一下百度招聘。笔试题目有选择题，�~�程题，�pȝ��?计题三种�c�d��。选择题难度不是很大，但我太水了，很多基础知识都不记得了，正则表达式，shell�~�程～～～汗死，不说了，好多都是蒙的�?�~�程题有3题，�W�一题是扑և�字符�?的最长不重复子串�Q�输出长度。我想了半天�Q�只会O(n^2)的算法，是个人都可以惛_��来的 �W�办法，想着写下来也没啥意义�Q�题目问有没O�Q�n�Q�的�Q�那看来肯定有O�Q�n�Q�的�Q�就不写了，看后面的题算了。第二题是找��Z��个字�W�串的最长回文子丌Ӏ�这个问题好像以前考研复习数据�l�构时看�q�，惌��v来判断一个回文串可以用栈来实玎ͼ��E�微回忆一下，��法思�\ ��出来了。于是提�W�写下了个O(n^3)的算法。汗��M��Q�自己太�W�了�Q�只能想��U�垃圄�� 法，看来癑ֺ�不好混啊。第三题是在2.5亿个整数中找��Z��重复的整敎ͼ�内存�I�间不��以容 �U��2.5亿个整数。这�U�题是百度的特色�Q��v量数据处理，我也没啥思�\。既然不能一�ơ扔 �q�内存，我就分批扔进去，��量减少从外存读�q�内存的�ơ数�Q�然后算了一下，�?�Ҏ(gu��)��q�内存。然后每�Ҏ(gu��)��序，扑և�每批里面不重复的敎ͼ�把这些不重复的再在另一�Ҏ(gu��)��中过一遍，��L��重复的，然后汇怅R��写不出具体代码�Q�只把思�\写了一下。当时心情沮丧极了，想着�Q�挂了，代码不会写，隑־�写出一题又是效率极低的。最后那道系�l?设计题，我压�Ҏ(gu��)��啥好思�\�Q�题目大概是��量数据分布�?00台电(sh��)脑中�Q�想个办法高效统�?��Ҏ(gu��)��据的TOP10。草草写了几�W�，旉��到了，交卷～～～看来，�q�次除非有奇�q�，�?然笔试肯定被BS了�?

考完回到寝室�Q�和兄弟们讨��Z��下题目，�W�一题原来可以用Hash实现�Q�时间复杂度�?到O(n)。自�׃��l�想了一下，整个��法的思�\��清��C��Q�郁闷啊�Q�这么简单的题居然没�?出来�Q�看来自��p��是太菜了。ZZ对第二题�q�有个新颖的��法�Q�学习了一下，赞啊�Q�亏他想得出来，呵呵。第二天�q�有Microsoft的笔试，赶紧拿Primer来抱�׃��(j��ng)脚，�q�么好的一本书 �Q�我学C++时怎么��没看啊�Q�后�(zh��n)�，懊恼充斥着我的大脑�Q�大有相见恨晚的感觉�?虽然自己�W�试很烂�Q�但是还是寄希望于奇�q�出玎ͼ�能有��Z��去面试。于是晚上睡觉开着手机�Q�因为��谈会时百度说如果�W�试通过�Q�当晚凌晨就会出面试通知了。晚上辗转反�?�Q�难以入睡，期待手机铃声响�v�Q�都不知道几�Ҏ(gu��)��睡着。早上�v床一照镜子，大熊猫再现拉�Q�唉�Q��ؓ癑ֺ�消得我憔�(zh��n)�啊。自��q��想也没用�Q�眼前还有MS�{�着我呢。考MS�Ӟ��手机都没养I��q��着癑ֺ��?sh��)话�Q�希望考试时能有电(sh��)话来。果�Ӟ��早上11点多�q�在考试�Ӟ��手机响�v�Q�挂掉，我还在�ؓ了MS�W�试而挠头呢。几分钟后，又响了一�ơ，再次挂掉。考完试，�?考场拿手��Z��看，咦，�?27的哦�Q�好像是个小灵通。回拨，不通，�l�箋回拨�Q�还是不通，不死心，我就不信拨不通你。结果拨�?0多次�q�是不通，��了�Q�只好等他再打来。回实验室，上Q问问�q�个��L��是不是百度的�Q�JG他们说是的，惊喜�Q�Oh�Q�yeah�Q�百度面试来临了�Q?Miracle居然发生了。于是和JG�Q�DJ�Q�Q��D�R��d��毅面癑ֺ�。结果面官说我不接电(sh��)话，他们安排了其它同学面试，叫我�W�二天早�?0点再来面。FT�Q�怎么�q�么曲折啊，不过�l�我�Ҏ(gu��)�� 间复习准备，也好�?

【一面�?晚上好好看了一下项目，把重�Ҏ(gu��)��习了一下。又问了下JG面试问了啥，心里有个底了。第二天�Q�一个�h飞的��M��弘毅�Q�花�?2大洋�Q�好心疼啊。去到昨天那个房��_��看见面官了，一个光��_��和JG昨天的面官一栗��果�Ӟ��他上来就问了我昨天问JG的同样问题，设计一�U�数据结构，�l�合了链表和数组的优炏V��我想了一下，说用Hash链表�Q�这��h��入和查找的效率都比较高，但是有conflict问题要解冟뀂他马上��问我如何解决conflict问题�Q�有没什么好�Ҏ(gu��)��。我说修改hash函数�Q��得hash��g�生的conflict概率��可能低。他问那你怎么设计�Q�我倒，�q�个问题我可没想�q�啊。当场郁闷了�Q�立马陷入苦思状态。想出几个点子，都不��是否可以降低conflict的概率，都和面官说了。他很快��׃�D例否定我好不�Ҏ(gu��)�� 惛_��的点子，说你的办法还是不行哦�Q�有没更好的�Q�打��L��了，我已�l�尽力了啊，没想到这么快��p��他找到反例，郁闷��L��了。不�q�面官�h很好�Q�看我实在想不出更好的了�Q�就不�ؓ难我了，换下一个题目。后面一题是��量日志数据�Q�提取出某日讉K��癑ֺ��ơ数最多的那个IP。想了一下，说了个思�\。面官就问你�q�样需要的存储�I�间太大�Q�有没优化方法。看来思�\是正��的了，但是优化问题嘛，好棘手啊。我又说了个优化的方法，面官不太满意�Q�摇头。完了，实在想不出来了。。。。面官见我苦思冥惻I��也不为难我了。接着��问了下��目�l�验�Q�我balabala一通，他对我的��目不太感冒�Q�没问什么问题�?然后��问�W�试卷子了，他问我第一题干嘛空白？我说了原因，他问我现在有好的��x�� 没？我就把自��p��完后想的O�Q�n�Q�的��法说了一下，他比较满意，没问我什么就问第二题了。我又说了下我当时的��法思想�Q�他问有没更好的优化��法�Q�我说可以做到O�Q�n^2�Q�，把思�\说了下。似乎不是他的满意答案，也没问我啥。接着问第三题�Q�我把我的想法说�?。他��_��你最后还需要折半查找这么麻烦吗�Q�对2个有序的数组�Q�查找A数组的元素是否在 B数组中出现有没更好的��法�Q�我想了一下，�H�然灉|��一动，惌��v归�ƈ排序的算法。就��_�� 是不是像归�ƈ数组那样�Q�直接在B中定位出A的位�|�，�q�样��可以在O(m+n)内实现。他比较满意�Q�说�Q�“是啊，都有序了�Q�你�q�折半这么麻烦啊�Q�”暴汗，看来面官水��^比我高太多了�Q�思维跟不上。然后看面官�ȝ��露出点笑容，忍不住问句：“你觉得我这个算法可以接受不�Q�”他的回�{�让我很吃惊�Q�他��_��“当然可以接受拉�Q�我觉得挺好的啊�Q�不�q�你的算法要访外存，可能旉��效率不是很高。不�q�先要完成题目的��d��Q�再考虑优化。”我赶紧补一句：“是啊，先要让它work�Q�再考虑如何让它work better。”面官还来句�Q�“不�q�这个题最好的��法可以一�ơ把2.5亿数据扔�q�内存，�q�需要你设计一个好的数据结构。”我问：“这个，怎么设计哦？”面官表�C�Z��能告诉我�{�案�Q�让我自己回��L��?�q�时�Q�面官看看表�Q�我也看看表�Q�已�l�面�?0分钟了。他��_��“现在我们再�?道数学推理题。第一题，2个盒子，定w��_��大，现在�?0个红球，50个蓝球，你如何安放这些球�q�盒子，使得我随机抽取一个盒子，然后从里面随机抽一个球�Q�这个球是红球的概率最大？�l�你2分钟旉��考虑�Q�直观分析给出结果。”当场我��晕倒了�Q�从��到大，我都不会做IQ题的啊，�q�可是我的最弱项。没办法�Q�不能直接说我不会啊。只好硬着头皮上，分析一下，我说�Q�“列条概率的表达式，求最��|��可以求出�l�果。”他��_��“你�q�样�?个小�?都算不出�l�果。从直观上分析就可以知道�l�果了。你再想想”，被打��M��。只好��l�想�Q?我想�Q�那�?0个红球放��C��个盒子，另一个盒子全放蓝球，�q�样一个有100�Q�，另一个是0 �Q�，�q�_��下来�?0�Q�。也不理惛_��Q�这个时候，灉|��再次�H�现�Q?0个红球全放一个盒子不是浪费嘛�Q�放1个也�?00�Q�，2个也�?00%�Q�那��放一个好了，其它全部扔到另一个盒子和蓝球一赗��再想一下，�q�样概率�?5�Q�，应该很高了。也没仔�l�想是不是正��答案，��p�� 口而出�Q�说了这�U�放法。面官再�ơ露出笑容，说“正��！”我那时心里好激动啊�Q�没惛_�� q�气�q�么好，居然�q�答对了。接着又来下一题，A��击命中�?0%,B60%,C40%�Q�A,B,C互�ؓ竞争�Ҏ(gu��)��Q�每人都知道另外2人的命中率，3个�h同场竞技互相��击�Q�同时开了第一枪，问第一枪射后，谁最有可能挂掉？我分析了一下，说了�{�案�Q�他问我思�\�Q�我说了我的思�\后，他居然来句：“你的思维和别��Z�� 一栗��”FT�Q�我和别��Z��一��P��估计说错了，自己��实回答IQ题比别�h�W�一截，没办法。面官说�Q�“好了，旉��差不多了。你有什么问题问我不�Q�”我问：“如果我有幸通过一面，什么时候会二面�Q�”“通过的话�Q�明早就二面。”然后，和面官握了下手，��p��L��束了我的一面�?面完一面后�Q�去找LP吃饭�Q�下午陪她上自习�Q�感觉自�׃��面还行吧�Q�大部分题都�{�出了思�\�Q�虽然进一步的优化没有惛_��_��而且�q�气也好得不得了�Q�连最�?题居然还被我蒙对1题，如果�q�不�?面，只能说明自己��ȝ��度的要求�q�是差距太大了。结果好�q�再�ơ降��_��晚上6点多接到�?sh��)话�Q�通知�W�二天早�?0点去二面�Q�呵呵，竟然�q�了二面�Q�真�?too lucky�?

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

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

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

卡特兰数�Q�Catalan敎ͼ�

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

原理

　　令h(1)�Q?,h(0)=1�Q�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,...)

　　卡特兰数的应�?br>　　�Q�实质上都是递归�{�式的应用）
　　

括号化问�?/h3>
　　矩阵链乘�Q?P=a1×a2×a3×……×an�Q�依据乘法结合律�Q�不改变光��序，只用括号表示成对的乘�U�，试问有几�U�括号化的方案？(h(n)�U?
　　

出栈�ơ序问题

　　一个栈(无穷�?的进栈序列�ؓ1�Q?�Q?�Q?#8230;�Q�n�Q�有多少个不同的出栈序列?
　　分析�Q�对于每一个数来说�Q�必��进栈一�ơ、出栈一�ơ。我们把�q�栈设�ؓ状�?#8216;1’�Q�出栈设为状�?#8216;0’。n个数的所有状态对应n�?和n�?�l�成�?n位二�q�制数。由于等待入栈的操作数按�?‥n的顺序排列、入栈的操作数b大于�{�于出栈的操作数a(a≤b)�Q�因此输出序列的��L��?由左而右扫描由n�?和n�?�l�成�?n位二�q�制敎ͼ�1的篏计数不小�?的篏计数的方案种数�?br>　　�?n位二�q�制��C��填入n�?的方案数为c(2n,n),不填1的其余n位自动填0。从中减��M��W�合要求�Q�由左而右扫描�Q?的篏计数大于1的篏计数�Q�的�Ҏ(gu��)��数即为所求�?br>　　不符合要求的数的特征是由左而右扫描�Ӟ��必然在某一奇数�?m+1位上首先出现m+1�?的篏计数和m�?的篏计数�Q�此后的2(n-m)-1位上有n-m�?1和n-m-1�?。如若把后面�q?(n-m)-1位上�?�?互换�Q��之成为n-m�?和n-m-1�?�Q�结果得1个由n+1�?和n-1�?�l�成�?n位数�Q�即一个不合要求的数对应于一个由n+1�?和n-1�?�l�成的排列�?br>　　反过来，��M��一个由n+1�?和n-1�?�l�成�?n位二�q�制敎ͼ��׃��0的个数多2个，2n为偶敎ͼ�故必在某一个奇��C��上出�?的篏计数��过1的篏计数。同样在后面部分0�?互换�Q��之成为由n�?和n�?�l�成�?n位数�Q�即n+1�?和n-1�?�l�成�?n位数必对应一个不�W�合要求的数�?br>　　因而不合要求的2n位数与n�Q?�?�Q�n�Q?�?�l�成的排列一一对应�?br>　　昄��Q�不�W�合要求的方案数为c(2n,n+1)。由此得�?输出序列的��L��?c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)�?br>　　�Q�这个公式的下标是从h(0)=1开始的�Q?br>　　�c�M��Q�有2n个�h排成一行进入剧场。入��5元。其中只有n个�h有一�?元钞��，另外n人只�?0元钞��，剧院无其它钞��，问有多少中方法��得只要有10元的��Z��，售票处就�?元的钞票��N��Q?��持5元者到达视作将5元入栈，�?0元者到达视作��栈中�?元出�?
　　

凸多边�Ş的三角剖分问�?/h3>
　　
　　求将一�?a target="_blank" style="color: rgb(51, 102, 204); text-decoration: underline; ">凸多边�Ş区域分成三角形区域的�Ҏ(gu��)��数�?br>　　�c�M��Q�一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她�?n个街区去上班。如果她从不�I�越�Q�但可以��到�Q�从家到办公室的对角�U�，那么有多��条可能的道路？
　　�c�M��Q�在圆上选择2n个点,��这些点成对�q�接��h��使得所得到的n条线�D�不�怺�的方法数?
　　

用给定节点组成二叉树的问�?/h3>
　　
　　�l�定N个节点，能构成多��种不同�?a target="_blank" style="color: rgb(51, 102, 204); text-decoration: underline; ">二叉�?/a>�Q?br>　　�Q�能构成h�Q�N�Q�个�Q?/span>

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

【做题计划�?-5

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

BUPT OJ

1094ACM的组�?/div>

1095探险家Javaman

1096老鹰捉小�?/div>

1098机器人工�?/div>

1099Plant

1010Snooper

1011PrisonBreak

1012SuperRock教授的教�?/div>

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

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

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

题目描述�Q�求从指定�v点到指定�l�点每条可能路径上各�D�边的最��?/div>

注意事项�Q�有向图�Q�无向图

提交情况�Q?�ơRuntime Error�Q�是最开始尝试用Kruskal旉��接排序的数组r大小只开了MAXN个；3�ơWA的主要原因是无向图按照有向图做的。用��L��表存储图时一定要注意有向囑֒�无向囄��问题�Q�已�l�出错好几次了�?/div>

心得体会�Q�本道题实际是按照Prim求最大生成树的思�\�Q�逐条��d��边；在添加的�q�程中，注意�?点出发，在遇到n�Ӟ��即��最大生成树仍没有构造完�Q�也可以从函��C��q�回了。最开始以为是��单的生成树问题，所有用Kruskal来作�Q�遇到�v点和�l�点都访问过��退出，但此�Ӟ��构造的生成树可能根本就没有�q�接�Q�而Prim在构造的初始��是从一��|��开始拓展的�Q�不会出现这个问题。需要对每个具体的算法有更深入的理解�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 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

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

题目描述�Q�求方程的根的个�?/div>

注意事项�Q�hash可以用char�Q�避免占用内存过�?/div>

提交情况�Q?�ơMLE�Q�用int开数组太大�?/div>

心得体会�Q�暂�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 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

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

所用算法：枚�D�Q?1枚�D�Q?/div>

注意事项�Q�注意位操作�Q�要�l�心

提交情况�Q�半个月前（12�?��P��两次wa�Q�，今天重新读题又完全换思�\重写了一遍，ac

心得体会�Q�数据量��，直接枚�D��可以，�q�不一定必��要深搜或剪枝。这道题如果深搜的话�Q�剪枝的条�g也是非常明显的。代码很乱，希望半个月后review的话�q�能看得懂�?/div>

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�Q�bfs求最短�\�Q�迷宫）

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

摘要: 题目链接�Q�http://acm.pku.edu.cn/JudgeOnline/problem?id=3083题目描述�Q�求最短�\�Q�求沿特定方向走�q�宫的步数所用算法：最短�\用bfs求，特定方向走迷宫直接用while计数�Q�这里写的比较繁琐，要细心，本来看题目分�c�L��在dfs里面的，以�ؓ�q�要用dfs�Q�细��x��不用�Q�而求�q�宫最短�\径，bfs应该是首选了�Q�提交情况：1�ơwa(忘了�?lt;stdio.h>�?.. 阅读全文

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

POJ 1936 All in All

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

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

所用算法：字符�?/div>

提交情况�Q?A

注意事项�Q�无

心得体会�Q�水�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 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

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

题目描述�Q�求冒��排序的交换次�?/div>

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

提交情况�Q?�ơtle(直接冒��排序n^2的复杂度�Q�对�?000000的数据量�Q�必然超�?�Q?�ơwa�Q�统计个数时整数溢出了）�Q?a

心得体会�Q�初看题目很��单，没有往数据量方面想�Q�直接冒泡计数提交，然后看着poj上一直running&&judging直到tle, 旉��7000ms呀。没做过逆序数的�c�M��问题�Q�而且题目本��n分类也在排序那，然后考虑是不是能快排一下，比较排序前和排序后各个数的位�|�。考虑再三�Q�发现解决不了。去论坛上瞄了一��|��看到可以用逆序数解�Q�于是百度＋��法��D��Q�学��C��如何用归�q�排序计��逆序数的数目�Q�写成程序，中间�q�出��C��一�ơwa�Q�然后就ac了。我在看��法��D��Ӟ��因�ؓmerge在书一开始讲的，惛_�^时排序都是快排�ؓ��L��Q�就没有仔细惌��merge可能的变�U�，�q�道题充分印证了�Q�即使merge本��n可能用的不多�Q�但分冶的思想却是无所不在

�c�M��题目�Q�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 }

�?/div>

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