链接：[https://www.nowcoder.com/discuss/35473]
首先进行一个小时的笔试。一面的主要内容就是讨论笔试题，然后聊了一些简历上的东西。面试官人很和蔼，沟通起来不累。笔试题如下：
1、有一个数组包含1000w个整数，给定一个整数n，在数组中找到所有ai和bi，使得ai+bi=n，写出代码。
首先想到了暴力法，时间复杂度是O(n^2)，然后使用了一个桶排序优化暴力。其实能不能优化心里也不清楚，感觉可以就写上了。
补充：感谢 @zssasa
Two Sum问题：[http://blog.csdn.net/u010429424/article/details/77648989]
public int[] twoSum(int[] numbers,int target){
HashMap<Integer,Integer> map=new HashMap<>();
int[] res=new int[2];
for (int i = 0; i <numbers.length ; i++) {
if(map.containsKey(numbers[i])){
res[0]=map.get(numbers[i])+1;
res[1]=i+1;
break;
}else {
map.put(target-numbers[i],i);
}
}
return res;
}
2、二叉树，找到两个节点的最近公共父节点，写出代码。
由于题目没有给出二叉树的输入形式，因此根据以往的做题经验，如果二叉树以数组的形式给出，则直接用公式就能计算出父节点。比如二叉树【1，2，3，4，5】，则4、5的父节点下标为(3-1)/2 = 1和(4-1)/2 = 1。
20170828123905634.jpg
如果二叉树以树的形式给出，分两种情况考虑，如果二叉树节点中有指向父节点的指针，则可以通过这个指针很方便地找到公共父节点。如果二叉树中没有指向父节点的指针，则先通过dfs找到根节点到4、5节点的路径：1、2、4和1、2、5，路径使用链表存储，然后从4、5向前找到第一次出现的公共节点。
但是面试官说，通过遍历树会有更好的方法。
补充：通过后续遍历，可以解决这个问题：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == p || root == q || root == null)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
3、一个袋中有n个球，球上面有标号，标号可以相同也可以不同。如果袋中球的编号之和大于编号之积，则叫做幸运袋，反之就是不幸运的。比如【1、3】1+3 > 1* 3就是幸运的；【2、3】，2+3 < 2 * 3就是不幸运的。现在给出一个有n个球的袋子，可以去掉m个球使得剩余的球构成幸运袋，问能够成的幸运袋的个数，写出代码。
深度优先遍历
public class YiQiu {
public static int getNum(int[] a,int start,long sum,long multi){
int res=0;
for (int i = start; i <a.length ; i++) {
sum+=a[i];
multi*=a[i];
if(sum>multi){
res+=1+getNum(a,i+1,sum,multi);
}
else if(a[i]==1){
res+=getNum(a,i+1,sum,multi);
}
else {
break;
}
sum=sum-a[i];
multi=multi/a[i];
for (; (i < (a.length-1))&&(a[i]==a[i+1]); i++) ;
}
return res;
}
public static void main(String[] args) {
int[] a={1,1,2,3};
System.out.println(getNum(a,0,0,0));
}
}
4、通过IP怎么查找到城市。给出一组IP地址和对应的城市名，问使用怎样的数据结构，能够找到城市，写出代码。
第一个思路使用Trie树来存储IP，叶子节点对应城市。但看到题目的函数输入是整型的ip，瞬间感觉也可以用Hash来做，key是ip，value是对应的城市。因为不知道怎样把ip转换成int，被面试官鄙视了。。。。（当时说ip本质上也是用二进制来表示的，因此可以通过位运算转换成int）
补充：Ip转long http://www.mkyong.com/java/java-convert-ip-address-to-decimal-number/
public long ipToLong(String ipAddress){
String[] ipAddressArray=ipAddress.split("\\.");
long res=0;
for (int i = 0; i <ipAddressArray.length ; i++) {
int power=3-i;
int ip=Integer.parseInt(ipAddressArray[i]);
res += ip*Math.pow(256,power);
}
return res;
}
5、编辑器的undo撤销，redo恢复怎样实现，写出代码。
看到这道题的第一反应就是Git。但是不懂git的数据结构，只能装模作样地设计了一个双向链表。这样，通过指针的改变就能很快地前移和后退。结构又被面试官鄙视了~
（补充：后来听同学讲可以用两个栈来实现，
参考：
http://blog.csdn.net/cb0912cn/article/details/444393）
一 定义栈结构
Public Type stack
Num As Integer '记录栈的大小
contents As String '记录内容
Pos As Long '记录光标位置
End Type
分别需要两个栈，一个栈stackundo来存放撤消内容，一个栈stackredo来存放恢复内容
二 在文本内容改变的同时，将文本内容，以及此时光标位置存入栈stackundo中。
三 进行undo操作后，把undo前的内容和光标位置存入栈stackredo中，同时在栈stackundo中清除该内容。
四 进行redo操作后，把redo前的内容和光标位置存入栈stackundo中，同时在栈stackredo中清除该内容。
通过上述过程就能很简单的实现无限次undo和redo操作。
