模板
教程
环境
性能
功能
管理
软件测试 > 测试技术 > 软件测试工程师职业发展 > 面试精选 >
九月十月百度，迅雷，华为，阿里巴巴，最新校招笔试面试五十题(5)
点评：老题，与caopengcs讨论后，得出具体思路为：
①先把100W个关键字hash映射到小文件，根据题意，100W*50B = 50*10^6B = 50M，而内存只有1M，故干脆搞一个hash函数 % 50，分解成50个小文件;
②针对对每个小文件依次运用hashmap(key，value)完成每个key的value次数统计，后用堆找出每个小文件中value次数最大的top 10;
③最后依次对每两小文件的top 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
说不简单则是因为如果不是二叉查找树，则我们必须确定这棵树的结点是否包含指向父结点的连接，如此：
①当包含指向父结点的连接时，如果每个结点都包含指向父结点的连接，我们就可以向上追踪p和q的路径，直至两者相交。
不过，这么做可能不符合题目的若干假设，因为它需要满足以下两个条件之一：1)可将结点标记为isVisited;2)可用另外的数据结构如散列表储存一些数据。
②不包含指向父结点的连接时，另一种做法是，顺着一条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
