模板
教程
環境
性能
功能
管理
軟件測試 > 測試技術 > 軟件測試工程師職業發展 > 面試精選 >
九月十月百度，迅雷，華為，阿里巴巴，最新校招筆試面試五十題(5)
點評：老題，與caopengcs討論后，得出具體思路為：
?、傧劝?00W個關鍵字hash映射到小文件，根據題意，100W*50B = 50*10^6B = 50M，而內存只有1M，故干脆搞一個hash函數 % 50，分解成50個小文件;
?、卺槍γ總€小文件依次運用hashmap(key，value)完成每個key的value次數統計，后用堆找出每個小文件中value次數最大的top 10;
?、圩詈笠来螌γ績尚∥募膖op 10歸并，得到最終的top 10。
注：很多細節需要注意下，舉個例子，如若hash映射后導致分布不均的話，有的小文件可能會超過1M，故為保險起見，你可能會說根據數據范圍分解成50~500或更多的小文件，但到底是多少呢?我覺得這不重要，勿糾結答案，雖準備在平時，但關鍵還是看臨場發揮，保持思路清晰關注細節即可。OK，更多類似題目參見此文：http://blog.csdn.net/v_july_v/article/details/7382693。
2、求二叉樹的任意兩個節點的最近公共祖先。
點評：何謂最低公共祖先，如下圖所示：節點1和節點7的最低公共祖先便是5
點評：此題看似簡單，實則不簡單，下面參考引用《Cracking the Coding Interview》一書上的解法：
說簡單是因為如果這棵樹是二叉查找樹，則最低公共祖先t必在兩個節點p和q的中間處，即p
說不簡單則是因為如果不是二叉查找樹，則我們必須確定這棵樹的結點是否包含指向父結點的連接，如此：
?、佼敯赶蚋附Y點的連接時，如果每個結點都包含指向父結點的連接，我們就可以向上追蹤p和q的路徑，直至兩者相交。
不過，這么做可能不符合題目的若干假設，因為它需要滿足以下兩個條件之一：1)可將結點標記為isVisited;2)可用另外的數據結構如散列表儲存一些數據。
?、诓话赶蚋附Y點的連接時，另一種做法是，順著一條p和q都在同一邊的鏈子，也就是說，若p和q都在某結點的左邊，就到左子樹中查找共同祖先。
若都在右邊，則在右子樹中查找共同祖先。要是p和q不在同一邊，那就表示已經找到第一個共同祖先。
這種做法的實現代碼如下：
[cpp] view plaincopyprint?
/* 若p為root的子孫，則返回true */
boolean covers(TreeNode root, TreeNode p) {
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
TreeNode commonAncestorHelper(TreeNode root, TreeNode p,
TreeNode q) {
if (root == null) return null;
if (root == p || root == q) return root;
boolean is_p_on_left = covers(root.left, p);
boolean is_q_on_left = covers(root.left, q);
/* 若p和q不在同一邊，則返回root */
if (is_p_on_left != is_q_on_left) return root;
/* 否則就是在同一邊，遍訪那一邊 */
TreeNode child_side = is_p_on_left ? root.left : root.right;
return commonAncestorHelper(child_side, p, q);
}
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (!covers(root, p) || !covers(root, q)) { // 錯誤檢查
return null;
}
return commonAncestorHelper(root, p, q);
}
/* 若p為root的子孫，則返回true */
boolean covers(TreeNode root, TreeNode p) {
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
TreeNode commonAncestorHelper(TreeNode root, TreeNode p,
TreeNode q) {
if (root == null) return null;
if (root == p || root == q) return root;
boolean is_p_on_left = covers(root.left, p);
boolean is_q_on_left = covers(root.left, q);
/* 若p和q不在同一邊，則返回root */
if (is_p_on_left != is_q_on_left) return root;
/* 否則就是在同一邊，遍訪那一邊 */
TreeNode child_side = is_p_on_left ? root.left : root.right;
return commonAncestorHelper(child_side, p, q);
}
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (!covers(root, p) || !covers(root, q)) { // 錯誤檢查
return null;
}
return commonAncestorHelper(root, p, q);
}
但上述代碼存在一些問題，讀者可以進一步思考，后續可能會在編程藝術系列里詳細闡述，可保持關注。
OK，其實本題是常見的Lowest Common Ancestor (LCA) 問題，更多分析可再看看這3篇文章：①http://eriol.iteye.com/blog/1170465;②http://zhedahht.blog.163.com/blog/static/25411174201081263815813/;③http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor。此外，關于二叉樹有很多面試題目，參見：http://blog.csdn.net/luckyxiaoqiang/article/details/7518888。
10月13日，小米2014校招研發筆試-北京站
2小時3道編程題
Q1：給出一個int數組，通過變換使得左邊全為奇數右邊全為偶數。
原文轉自：http://blog.csdn.net/v_july_v/article/details/11921021
