择题部分考得比较基础，但是考的面比较广，数据结构，计算机网络，算法常识，概率题，C，C++,都有。大题如下：
1.在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。请编写一个函数，使用递归方法生成N位的格雷码，并且保证这个函数的健壮性。
数的健壮性。
什么事格雷码？00,01,11,10.右边变一下，从右边开始第一个1的左边变一下。右边变一下......
000,001,011,010,110,111,101,100
法一：就是上面那个。
法2：找规律用递归。递归就是n==1的情况,假设n==k-1的情况弄好了,再去算k的情况。
000
001
011
010
110
111
101
100第一位不看，三位的格雷码就是由二位的格雷码生成的，
{
N位的格雷码。
String a[]=new String[math.pow(2,n)];
If(n==1){a[0]==0;a[1]==1; return a;}
A=F(k-1);
For(int i=0;i<math.pow(2,n);i++)
{
String b=a[i];
A[i]=”0”+b;
A[lenght-1]=”1”+b;
}
Return a;
}
递归都是n==1的情况，然后假设第k-1次完成了，然后推出第k次的。
2. 有下图的题解，请用C/C++代码来列出满足下图0-100内的所有答案。
3. 如图所示，系统中有三个进程Producer，Transmitter和Consumer。Producer和Transmitter共用缓冲区ProduceBuf，Consumer和Transmitter共用缓冲区ConsumeBuf。
Producer进程负责不断地将输入信息送入ProduceBuf；Transmitter进程负责从ProduceBuf中取出信息进行处理，并将处理结果送到ConsumeBuf；Consumer进程负责从ConsumeBuf中读取结果并输出。
假设ProduceBuf中最多可放12个信息，现已放入了3个信息；ConSumeBuf最多可放6个信息。试写出正确实现进程Producer,Transmitter和Consumer的同步与互斥的算法
（要求：用类C语言描述，条理清楚，注释恰当；）
4. 春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
法一：同事去掉两个不同的数。
法二：下标为中间的肯定是这个数。所以用padition函数(返回下标)，一直调用，直到返回的下标是中间的下标。Padition你想快排。可以弄三个参数。Int [],start,end,或者四个length。
给出一个字符串str及指定一个位置p，交换p的前后两段字符串，要求额外空间开销尽量小。例如给出str=”people”,p=2,结果串变为str=”oplepe”。其实只要一个char型变量作为临时空间，将p前的字符一个一个“沉”到最后就OK了，当时没想得出来真是丢脸啊！呜呜！ 给出串A=”iqwqrpwpetppwanepnvomzlplte”,B=”people”,问能否通过在串B的任意位置插入位置个字符生成串A，如果可以，计算出有多少种不同的生成方法，要求时间复杂度尽量小。一看这道题很容易误导思维，让人以B为考虑的出发点。事实上，换过来思考，问题就是找串A中有没有顺序地出现过B中的所有字符，这样就简单多啦，时间复杂度仅为O(m+n)！第二问来不及思考，有时间的同学可以想想，呵呵。
OSI模型有几层？
7层：
说说C++的多态？为什么使用虚函数比非虚函数耗费的时间更多？
虚成员函数的位置和非虚成员函数的在在内存存放的位置不一样，虚函数在虚表，虚表多的话，寻找一个虚函数就需要遍历所有虚表，但是成员函数可以直接通过偏移而得到。
接着问到了TCP的过程，建立连接，销毁连接的过程，为什么要三次握手，为什么四次挥手，
两次握手的情况，三次挥手的情况。
为什么要等待2msl，为了确保A最后一次的确认报文能准确到达。最后一个确认报文如果不等待2msl，超时后A已关，b没关，b等待，a也不可能重传，所以就是确保他能到达。
为什么要四次挥手：确保数据能够完成传输。第二次与第三次之间有数据传送。
拥塞控制和流量控制分别是什么概念，流量控制的过程，分别要解决什么问题。建立连接的第二个syn作用是啥，我当时也不知道怎么想的，说了个建立服务端到客户端的连接，因为tcp是全双工通信，下来之后我才知道这个说法不对，当时他也没说啥，
TCP为啥挥手要比握手多一次？因为被动关闭方发送ACK和FIN需要两次，发送ACK的时候还没有传完自己的数据； TCP三次握手有哪些漏洞，有没有被攻击的可能，怎么被攻击。答不上来，后来查了一下，是有漏洞的，主要是如果收到一个恶意攻击的ip一直请求连接，然后服务器会发送ack确认，但是永远等不到回复，就会导致服务器的NIC，内存，cpu占用率超载，这种攻击方式叫做基于TCP半开回话的洪水攻击
100 亿个数字中找出最大的 1000 个，提醒数据非常多，放不进内存。（算是比较老的一个题目）
简单思考了一下，考虑用 BitMap，可以将数据放进内存。面试官提示，里面数字可能非常大，BitMap 会很稀疏，仍然放不进内存。然后又提示用哪种数据结构，可以实现每次插入一个数字，取出最大的。想到用堆，接着被问到用什么堆实现，我说用最大堆，然后面试官让我再仔细想想。（面试官不是很满意）
用小顶堆，首先读入前1000个数字，调整好堆。然后每次读入一个数，和堆顶比较，如果堆顶大，那么丢弃该数字，否则，弹出堆顶，将新的数入堆，调整堆结构。
最喜欢哪一个排序算法，为什么？算法实现的时间复杂度？
回答说是快排，然后时间复杂度平均 O(nlogn)，最差O(n2 )。实现的话就是一个 partition 和递归快速排序。
对双向链表排序怎么整？ 把双向链表弄成二插排序树，然后中序遍历。
觉得String类少一个功能，你会怎么办？ Collection 和 Map 接口下有哪些实现类 如果Map下的实现类，针对value进行排序，如何实现
这里讨论list、set、map的排序，包括按照map的value进行排序。 1）list排序 可以直接采用Collections的sort方法，也可以使用Arrays的sort方法归根结底Collections就是调用Arrays的sort方法。 public static <T> void sort(List<T> list, Comparator<? super T> c) { Object[] a = list.toArray(); Arrays.sort(a, (Comparator)c); ListIterator i = list.listIterator(); for (int j=0; j<a.length; j++) { i.next(); i.set(a[j]); } } 如果是自定义对象，需要实现Comparable接口使得对象自身就有“比较”的功能，当然我们也可以在外部使用Comparator来规定其排序。 例如： package com.fox; /** * @author huangfox * @data 2012-7-5 * @email huangfox009@126.com * @desc */ public class User implements Comparable<User> { private String name; private int age; public User() { } public User(String name, int age) { super(); this.name = name; this.age = age; } @Override public String toString() { return "name:" + name + ",age:" + age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public int compareTo(User o) { if (o.age < this.age) return 1; else if (o.age > this.age) return -1; else return 0; } /** * @param args */ public static void main(String[] args) { User u1 = new User("fox", 11); User u2 = new User("fox2", 21); System.out.println(u2.compareTo(u1)); } } 排序： // List<User> us = new ArrayList<User>(); List<User> us = new LinkedList<User>(); us.add(new User("f5", 12)); us.add(new User("f2", 22)); us.add(new User("f3", 2)); us.add(new User("f4", 14)); us.add(new User("f5", 32)); us.add(new User("f4", 12)); us.add(new User("f7", 17)); us.add(new User("f8", 52)); System.out.println(us.toString()); long bt = System.nanoTime(); Collections.sort(us, new Comparator<User>() { @Override public int compare(User o1, User o2) { if (o1.getAge() < o2.getAge()) return -1; else if (o1.getAge() > o2.getAge()) return 1; else return o1.getName().compareTo(o2.getName()); } }); long et = System.nanoTime(); System.out.println(et - bt); System.out.println(us.toString()); 当然这里可以直接Collections.sort(us)，这里用Comparator对User自身的比较方法compareTo做了一点点优化（对相同年龄的人根据用户名排序，String的排序）。 简单提一下，Arrays的排序采用的是插入排序和归并排序，当数组长度较小时直接插入排序。 2）set排序 set包括HashSet和TreeSet，HashSet是基于HashMap的，TreeSet是基于TreeMap的。 TreeMap是用红黑树实现，天然就具有排序功能，“天然就具有排序功能”是指它拥有升序、降序的迭代器。 那么HashSet怎么排序呢？我们可以将HashSet转成List，然后用List进行排序。 例如： Set<User> us = new HashSet<User>(); // Set<User> us = new TreeSet<User>(); // Set<User> us = new TreeSet<User>(new Comparator<User>() { // // @Override // public int compare(User o1, User o2) { // if (o1.getAge() < o2.getAge()) // return -1; // else if (o1.getAge() > o2.getAge()) // return 1; // else // return o1.getName().compareTo(o2.getName()); // } // }); us.add(new User("f5", 12)); us.add(new User("f2", 22)); us.add(new User("f3", 2)); us.add(new User("f4", 14)); us.add(new User("f5", 32)); us.add(new User("f4", 12)); us.add(new User("f7", 17)); us.add(new User("f8", 52)); // set -> array List<User> list = new ArrayList<User>(us); System.out.println(list); Collections.sort(list); System.out.println(list); 也可以将HashSet转换成数组用Arrays排序。 3）map排序 map包括HashMap和TreeMap，上面已经提过，TreeMap用红黑树实现，天然具有排序功能。 那么HashMap怎么按“key”排序呢</span>？方法很简单，用HashMap来构造一个TreeMap。 Map<String, Integer> us = new HashMap<String, Integer>(); // Map<String, Integer> us = new TreeMap<String, Integer>(); us.put("f1", 12); us.put("f2", 13); us.put("f5", 22); us.put("f4", 42); us.put("f3", 15); us.put("f8", 21); us.put("f6", 123); us.put("f7", 1); us.put("f9", 19); System.out.println(us.toString()); System.out.println(new TreeMap<String, Integer>(us)); 怎么按照“value”进行排序？// 按照value排序 用map.entry()对象来存储<key,value>的 Set<Entry<String, Integer>> ks = us.entrySet(); List<Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>( ks); Collections.sort(list, new Comparator<Entry<String, Integer>>() { @Override public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) { if (o1.getValue() < o2.getValue()) return -1; else if (o1.getValue() > o2.getValue()) return 1; return 0; } }); System.out.println(list); 将map的Entry提出成set结构，然后将set转成list，最后按照list进行排序。
JVM有哪些初始化参数 说一下JVM、GC 这大概是答得最好的一个，以致面试官都听不下去了，忙说够了够了 Spring中AOP IOC，描述一下作用和实现 ，IOC如果不用配置文件，还可以怎么实现
setter方法注入
构造器注入
静态工厂注入
自动装配
上面三种方法都需要编写配置文件，在spring2.5中还提供了不编写配置文件的ioc实现。需要注意的是，无配置文件指bean之间依赖，不基于配置文件，而不是指没有spring配置文件。
Spring MVC 中的注解，注解如何实现的，是否写过自定义注解 nginx 如何配置 ajax 是什么
AJAX = 异步 JavaScript和XML（标准通用标记语言的子集）。 通过在后台与服务器进行少量数据交换，AJAX 可以使网页实现异步更新。这意味着可以在不重新加载整个网页的情况下，对网页的某部分进行更新。 传统的网页（不使用 AJAX）如果需要更新内容，必须重载整个网页页面。
百度一面：约 1.5 小时
首先是四个算法题：
· 不用临时变量怎么实现 swap(a, b)——用加法或者异或都可以
· 二维有序数组查找数字——剑指 offer 第 3题
· 亿级日志中，查找登陆次数最多的十个用户——（不确定对不对，我的思路是）先用哈希表保存登陆次数和ID，然后用红黑树保存最大的十个数。剑指 offer 第 30题
· 简述排序算法——快排，partion 函数的原理，堆排（不稳定），归并排序，基数排序。
？？？？？
求数组中和为某个值的所有子数组，比如数组是 [5,5,10,2,3] 一共有四个子数组的和是 15，比如[5,10]，[5,10]，[10,2,3]，[5,5,2,3]。这个就是简单的递归了，分两种情况，当前位置的数字在子数组中，以及不在子数组中。
？？？？？？
谈一下 Collection 包： hashmap 底层实现，用了什么方法解决 hash 冲突（基于 jdk 版本），具体是如何实现（ jdk1.5 链表头插还是尾插），为什么不安全？如何变得安（ concurrent 包下集合类）， concurrentHashmap 实现原理是？
ConcurrentHashMap具体是怎么实现线程安全的呢，肯定不可能是每个方法加synchronized，那样就变成了HashTable。
从ConcurrentHashMap代码中可以看出，它引入了一个“分段锁”的概念，具体可以理解为把一个大的Map拆分成N个小的HashTable，根据key.hashCode()来决定把key放到哪个HashTable中。所以多个修改可以同时进行。因为是多个segments
在ConcurrentHashMap中，就是把Map分成了N个Segment，put和get的时候，都是现根据key.hashCode()算出放到哪个Segment中：
HashMap 类没有分类或者排序。它允许一个 null 键和多个 null 值。不是同步的。
Hashtable 类似于 HashMap，但是不允许 null 键和 null 值。同步的。
HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key
HashTable 是 HashMap 的线程安全版本。 内部的实现几乎和HashMap一模一样
JDK8 中的 HashMap 如果有很多哈希冲突的话，那么是可能会把链表变成红黑树以此来提高效率。但是这里HashTable并没有这样做。
HashTable 实现多线程同步的主要方式是通过加synchronized关键字。就是说每个方法都加sychorinized关键字。
？？Hashtable中hash数组默认大小是11，增加的方式是old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
Hashtable使用Enumeration，HashMap使用Iterator。
什么是OO:可重用，可扩展，可维护。
linux：系统调用里面有一个sleep()函数，还有一个usleep()函数，然后usleep()函数号称自己是微秒级，你相信它真的能达到这么快吗？或者说系统调用可以达到微秒速度吗（这道题我没理解是什么意思）；
进程间的通讯方法，我说了管道，命名管道，信号量，套接字，消息队列。信号。他一直追问我还有一个是什么，让我仔细想一想，我想了好久说不记得了。后来才想起来是共享内存，不知道这是不是在试探我的抗压能力？
操作系统： 说一下操作系统的几种进程调度算法 我说了先来先服务，短作业优先，时间片轮转，基于优先级的调度，他追问linux的进程调度方法，我不知道
Linux进程调度采用的是抢占式多任务处理，所以进程之间的挂起和继续运行无需彼此之间的协作。 调度方式：时间片，优先级，还有就是时间片加优先级混合，默认是第三种
线程间的通信：wait await 管道 消息队列。
