百度面试java

之前去百度面试，整理了一下面试问题。没有笔试，直接和面试官交谈。感觉面试官人挺好的，挺有耐心，每次面试回来不论公司大小，不管能不能拿到offer，但基本都能有一些有价值的输入，还挺开心的。我虽然有4年工作经验，但是不是走纯技术系的，开发，维护，见客户，项目管理什么都干过，最近想换工作，粪发图强恶补算法，数据结构一类大公司特爱考的基础知识。

      这次后几道题答的不好。尤其是有一个关于服务器session优化和数据库表水平拆分策略的，没说到点儿上，回来的路上有了点儿思路，回来百度一下，发现八九不离十。前面几个算法的也都是磕磕碰碰，好歹都说上来了，是不是最优的就不好说了。

      以前做信息系统，更注重业务的获取与功能的实现，虽然所有人都喊性能、架构什么的，但是实际上没人在乎。反正撑死了也就那么点儿人用。互联网公司真的是不一样啊，对并发和大数据量的关注是深入骨髓的。感觉真是惭愧。虽然这几年跑客户谈需求讲ppt自诩也是混场面的，但是从心里希望自己在技术上也能再往前走一步。

 

 

根据记忆整理如下：
java 部分：

一、堆和栈的定义，堆和栈里面的对象，哪个运行速度快。
 

栈(stack)与堆(heap)都是Java用来在Ram中存放数据的地方，Java自动管理栈和堆，程序员不能直接地设置栈或堆。

虚拟机栈描述的是Java方法执行的内存模型：每个方法被执行的时候都会同时创建一个栈帧（Stack Frame①）用于存储局部变量表、操作栈、动态链接、方法出口等信息。每一个方法被调用直至执行完成的过程，就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。

所指的“栈”就是现在讲的虚拟机栈，或者说是虚拟机栈中的局部变量表部分。局部变量表存放了编译期可知的各种基本数据类型（boolean、byte、char、short、int、float、long、double）、对象引用（reference类型，它不等同于对象本身，根据不同的虚拟机实现，它可能是一个指向对象起始地址的引用指针，也可能指向一个代表对象的句柄或者其他与此对象相关的位置）和returnAddress类型（指向了一条字节码指令的地址）。

     栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性，栈数据可以共享。

   
Java虚拟机规范中的描述是：所有的对象实例以及数组都要在堆上分配。

堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。

个人理解：

我用一种“注册”的方式理解他们的过程，

1、当新建New（）时候，JVM会在堆上建一个对象，然后将其地址信息注册到栈上，并把它赋给我们的引用对象，整个创建->注册->赋值过程结束。

2、当时基础数据类型的时候，JVM会在栈上直接注册，由于栈的特殊性决定需要这些BaseType的对象需要共享以提高利用率。

二、wait()方法和notify()方法干什么用的，wait()方法有什么使用限制，是哪儿都能用么？

     Java中提供了对于wait方法超时语意的支持。但是Java在对于wait方法超时语意的支持方面存在模糊性，即在调用具有超时语意的wait方法返回时，无法区分是由于notify的通知还是由于超时触发的。解决方案：核心思路就是在每次wait返回时，计算wait等待的时间，并比较该时间和设定的要等待的时间，如果大于设定的要等待的时间，即确定为超时，否则确定为被notify唤醒。

注意Wait() 和notify()要成对出现。Wait() 是线程等待，notify()是线程唤醒使用这两者的时候，是多线程使用共享资源，防止资源出错，当一个线程使用时，其他线程等待，等该线程使用完毕后，唤醒其它线程notifyAll()。

  

   当某个类的某个方法被标记为synchronized时，这个方法在同一时间只能被一个线程访问。此时这个方法中的所有代码都是被同步的，只有当一个线程执行完所有的代码之后，下一个线程才能开始执行。

1、当被同步的方法代码量比较小，而且每一步执行都非常快的时候仅仅使用synchronized关键字就够了。

2、但是，如果被同步的方法里面有一些代码是可以被共享的，而且这些能够被共享的代码里面存在比较耗时的操作时，仅仅使用synchronized关键字就无法达到最高的效率，这个时候可以使用wait与notify方法来对并发访问做更进一步的控制。

public class TestThread {
    private boolean isIdle = true;
    public synchronized void work(){
        /*
         * Some work which can be shared
         * 这步份是共享代码	 * 让其它线程把这些完成掉
         */
        try {
            /*
             * to check if we can have this object's monitor
             */
            if(!isIdle){
                System.out.println(Thread.currentThread().toString() + ":I'm waiting....");
            }
            while(!isIdle){
                wait();
            }
            /*
             * to set isIdle to false, I'm working....
             */
            this.isIdle = false;//令其他线程等待
            System.out.println(Thread.currentThread().toString() + ":I'm working....这是比较耗时的操作!!");
            Thread.currentThread().sleep(1000);
            System.out.println(Thread.currentThread().toString() + ":I'm finished....");

            /*
             * to notify all other thread which is waiting for this object's monitor
             */
            this.isIdle = true;// 通知其他线程
            notifyAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

三、Treemap的实现。

    Entry t = root; 

满足下面几个条件(红黑性质)的二叉搜索树，称为红黑树： 

1. 每个结点或是红色，或是是黑色。 

2. 根结点是黑的。 

3. 所有的叶结点(NULL)是黑色的。（NULL被视为一个哨兵结点，所有应该指向NULL的指针，都看成指向了NULL结点。） 

4. 如果一个结点是红色的，则它的两个儿子节点都是黑色的。 

5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。(黑高度相同)

红黑树的每个节点都附加了另一个属性――颜色，可以是红色，也可以是黑色。通过对每条路径上节点颜色的规则进行限定，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过2倍。所以，红黑树是一种近似平衡的二叉搜索树。

四、HashMap

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。

transient Entry[] table;

static class Entry implements Map.Entry {

    final K key;

    V value;

    Entry next;

    final int hash;

    ……

}

public V put(K key, V value) {

    // HashMap允许存放null键和null值。

    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位

置。

    if (key == null)

        return putForNullKey(value);

    // 根据key的keyCode重新计算hash值。

    int hash = hash(key.hashCode());

    // 搜索指定hash值在对应table中的索引。

    int i = indexFor(hash, table.length);

    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个

元素。

    for (Entry e = table[i]; e != null; e = e.next) {

        Object k;

        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 

{

            V oldValue = e.value;

            e.value = value;

            e.recordAccess(this);

            return oldValue;

        }

    }

    // 如果i索引处的Entry为null，表明此处还没有Entry。

    modCount++;

    // 将key、value添加到i索引处。

    addEntry(hash, key, value, i);

    return null;

}

   从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

public V get(Object key) {

    if (key == null)

        return getForNullKey();

    int hash = hash(key.hashCode());

    for (Entry e = table[indexFor(hash, table.length)];

        e != null;

        e = e.next) {

        Object k;

        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

            return e.value;

    }

    return null;

}

 

   有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

  

   3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

数据库部分：

一、数据库各种事务隔离级别

在数据库操作中，为了有效保证并发读取数据的正确性，提出的事务隔离级别。

　为了避免上面出现的几种情况，在标准SQL规范中，定义了4个事务隔离级别，不

同的隔离级别对事务的处理不同。

未授权读取

　　也称为读未提交（Read Uncommitted）：允许脏读取，但不允许更新丢失。如果一个事务已经开始写数据，则另外一个数据则不允许同时进行写操作，但允许其他事务读此行数据。该隔离级别可以通过“排他写锁”实现。

授权读取

　　读提交（Read Committed）：允许不可重复读取，但不允许脏读取。这可以通过“瞬间共享读锁”和“排他写锁”实现。读取数据的事务允许其他事务继续访问该行数据，但是未提交的写事务将会禁止其他事务访问该行。

可重复读取

　　可重复读取（Repeatable Read）：禁止不可重复读取和脏读取，但是有时可能出现幻影数据。这可以通过“共享读锁”和“排他写锁”实现。读取数据的事务将会禁止写事务（但允许读事务），写事务则禁止任何其他事务。

序列化

　　序列化（Serializable）：提供严格的事务隔离。它要求事务序列化执行，事务只能一个接着一个地执行，但不能并发执行。如果仅仅通过“行级锁”是无法实现事务序列化的，必须通过其他机制保证新插入的数据不会被刚执行查询操作的事务访问到。

　　

隔离级别越高，越能保证数据的完整性和一致性，但是对并发性能的影响也越大。对于多数应用程序，可以优先考虑把数据库系统的隔离级别设为Read Committed。它能够避免脏读取，而且具有较好的并发性能。尽管它会导致不可重复读、虚读和第二类丢失更新这些并发问题，在可能出现这类问题的个别场合，可以由应用程序采用悲观锁或乐观锁来控制。

二、数据库的索引通常用什么数据结构实现？为什么用这种数据结构。

1、hash索引

目前我所知道的就只有memory和ndb cluster支持这种索引.

hash索引由于其结构，所以在每次查询的时候直接一次到位，不像b-tree那样一

点点的前进。所以hash索引的效率高于b-tree，但hash也有缺点，主要如下：

(1)由于存放的是hash值，所以仅支持"=","<=>"以及"in"操作.

(2)hash索引无法通过操作索引来排序，这是因为存放的时候经过hash计算，但是

计算的hash值和存放的不一定相等，所以无法排序.

(3)在组合索引里，无法对部分使用索引.

(4)不能避免全表扫描，只是由于在memory表里支持非唯一值hash索引，

就是不同的索引键，可能存在相同的hash值.

(5)当存在大量相同hash值得时候，hash索引的效率会变低.

2、b-tree索引应该是mysql里最广泛的索引

数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

每个数据BLOCK组成BTREE索引的一个节点，一个索引节点主要包括两方面的数据，一方面是索引字段的值和rowid，另一方面是指向另一个节点的指针(指向对应数据记录物理地址的指针)

图1
展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据;

参考

http://jefry.iteye.com/blog/1113280

3、为了实现一个折线图，需要将数据存入一种数据结构，折线图横坐标是时间，纵坐标是值，经常的查询是按时间段进行查询，如select value from t where begin>’20110101’ and end<’20111212’ ,问，使用java中的那种数据结构比较好。 

这个应该用TreeMap，查询的效率会比较高. subMap(K fromKey, K toKey) 

这个题目的关键在于查询上面，因为对于范围的查询，你要是用其它的结构就会面临查范围的时候一个一个的去比较，然后把满足范围的添加到一个集合里面，遍历完了再把结果集返回，这样的效率是比较低的。而TreeMap是基于红黑树的实现，它内部会维持一个排序的关系，你要想找比某个值大或者小的只需用查找它左边或者右边的值就行。而范围的查询效率会更高，只需用指定开始和结束，它就可以返回一个AscendingSubMap集合给你，这个集合就是你需要查询的结果。具体的可以看看TreeMap的实现会更清楚些。

4、如果数据库中有2个表，表a字段为姓名、年龄，表b字段为姓名、单位。现在使用姓名字段做left join查询，假设姓名字段都有索引了。问数据库是怎么实现的。如果把这两个表看为在内存中的数组，要自己实现left join，怎么实现？

   面试官看我实在不知道数据库里leftjoin怎么实现的，就让我自己实现一个内存中的，勉强答出来了吧，但是可能不太好。

5、数据库中有一个表有上亿的数据量，怎么优化？（主要是拆分，除了按业务拆分外，还有什么从技术角度的，可扩展性好的水平拆分方式）

   思路是拆没错，但是面试官问的不是业务拆分策略，而是从技术上考虑。还得考虑扩展性，比如拆好以后，数据量增长迅速，又要拆了，怎么办。这个水平拆分策略有好多，网上能搜到。但是我说的都不是很有体系，以前没弄过，都是现场想。


算法

1.     有一个集合a，里面有n个正整数，乱序排列。给定一个正整数N，求，a中任意两个数相加等于N，共有哪些种组合情况。例如，集合为{1,3,44,2,4,5,54,222,368}  N=6,则结果集为{1,5}，{2,4}

      这个题网上有类似的

 

 

2.   有两个很大的文件，每个文件中都有1亿行，每行一个整数。问这两个集合的交集是什么。给定的前提是机器内存不足以完全装入任意一个文件。

   这个几乎是网上的原题了

 

 

 

 

 

 

ps：当时上新东方的时候，老师说，有的时候虽然你英语不好，但是有几个单词只要你记住了，说的时候塞到句子里，人家就会觉得你特地道，比如absolutely之流。我觉得面试的时候也有这种key words，比如位排序之流，说的时候还得特举重若轻。适用于各类新手和平时工作中压根用不到各种排序算法的人，仅供参考。