二、国内一线互联网公司内部面试题库
JAVA基础
1.接口的意义:
规范、扩展、回调
2.抽象类的意义:
为其子类提供一个公共的类型 封装子类中得重复内容 定义抽象方法,子类虽然有不同的实现 但是定义是一致的
3.内部类的作用:
1)内部类可以用多个实例,每个实例都有自己的状态信息,并且与其他外围对象的信息相互独立。
2)在单个外围类中,可以让多个内部类以不同的方式实现同一个接口,或者继承同一个类。
3)创建内部类对象的时刻并不依赖于外围类对象的创建。
4)内部类并没有令人迷惑的“is-a”关系,他就是一个独立的实体。
5)内部类提供了更好的封装,除了该外围类,其他类都不能访问
4.父类的静态方法能否被子类重写:
不能
子类继承父类后,用相同的静态方法和非静态方法,这时非静态方法覆盖父类中的方法(即方法重写),父类的该静态方法被隐藏(如果对象是父类则调用该隐藏的方法),另外子类可继承父类的静态与非静态方法,至于方法重载我觉得它其中一要素就是在同一类中,不能说父类中的什么方法与子类里的什么方法是方法重载的体现
5.java排序算法
八大种排序算法【java实现】


a)冒泡排序 /* * 冒泡排序 * 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 * 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 * 针对所有的元素重复以上的步骤,除了最后一个。 * 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 * @param numbers 需要排序的整型数组 */ public static void bubbleSort(int[] numbers) { int temp = 0; int size = numbers.length; for(int i = 0 ; i < size-1; i ++) { for(int j = 0 ;j < size-1-i ; j++) { if(numbers[j] > numbers[j+1]) //交换两数位置 { temp = numbers[j]; numbers[j] = numbers[j+1]; numbers[j+1] = temp; } } } } b)快速排序 把整个序列看做一个数组,把第零个位置看做中轴,和最后一个比,如果比它小交换,比它大不做任何处理;交换了以后再和小的那端比,比它小不交换,比他大交换。这样循环往复,一趟排序完成,左边就是比中轴小的,右边就是比中轴大的,然后再用分治法,分别对这两个独立的数组进行排序。

代码实现如下:
1.查找中轴(最低位作为中轴)所在位置:

/**

  • 查找出中轴(默认是最低位low)的在numbers数组排序后所在位置
  • @param numbers 带查找数组
  • @param low 开始位置
  • @param high 结束位置
  • @return 中轴所在位置
    */
    public static int getMiddle(int[] numbers, int low,int high)
    {
    int temp = numbers[low]; //数组的第一个作为中轴
    while(low < high)
    {
    while(low < high && numbers[high] >= temp)
    {
    high--;
    }
    numbers[low] = numbers[high];//比中轴小的记录移到低端
    while(low < high && numbers[low] < temp)
    {
    low++;
    }
    numbers[high] = numbers[low] ; //比中轴大的记录移到高端
    }
    numbers[low] = temp ; //中轴记录到尾
    return low ; // 返回中轴的位置
    }
    2、 递归形式的分治排序算法:

/**

  • @param numbers 带排序数组
  • @param low 开始位置
  • @param high 结束位置
    */
    public static void quickSort(int[] numbers,int low,int high)
    {
    if(low < high)
    {
      int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
      quickSort(numbers, low, middle-1); //对低字段表进行递归排序
      quickSort(numbers, middle+1, high); //对高字段表进行递归排序
    }

}
3、快速排序提供方法调用:

/**

  • 快速排序
  • @param numbers 带排序数组
    /
    public static void quick(int[] numbers)
    {
    if(numbers.length > 0) //查看数组是否为空
    {
    quickSort(numbers, 0, numbers.length-1);
    }
    }
    分析:
      快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。
    c)选择排序
    /
    *
  • 选择排序算法
  • 在未排序序列中找到最小元素,存放到排序序列的起始位置
  • 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。
  • 以此类推,直到所有元素均排序完毕。
  • @param numbers
    */
    public static void selectSort(int[] numbers)
    {
    int size = numbers.length; //数组长度
    int temp = 0 ; //中间变量

for(int i = 0 ; i < size ; i++)
{
int k = i; //待确定的位置
//选择出应该在第i个位置的数
for(int j = size -1 ; j > i ; j--)
{
if(numbers[j] < numbers[k])
{
k = j;
}
}
//交换两个数
temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
}
d)插入排序
/**

  • 插入排序
  • 从第一个元素开始,该元素可以认为已经被排序
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置中
  • 重复步骤2
  • @param numbers 待排序数组
    */
    public static void insertSort(int[] numbers)
    {
    int size = numbers.length;
    int temp = 0 ;
    int j = 0;

for(int i = 0 ; i < size ; i++)
{
temp = numbers[i];
//假如temp比前面的值小,则将前面的值后移
for(j = i ; j > 0 && temp < numbers[j-1] ; j --)
{
numbers[j] = numbers[j-1];
}
numbers[j] = temp;
}
}
  4、效率:
时间复杂度:O(n^2).

e)希尔排序

/**希尔排序的原理:根据需求,如果你想要结果从大到小排列,它会首先将数组进行分组,然后将较大值移到前面,较小值

  • 移到后面,最后将整个数组进行插入排序,这样比起一开始就用插入排序减少了数据交换和移动的次数,可以说希尔排序是加强
  • 版的插入排序
  • 拿数组5, 2, 8, 9, 1, 3,4来说,数组长度为7,当increment为3时,数组分为两个序列
  • 5,2,8和9,1,3,4,第一次排序,9和5比较,1和2比较,3和8比较,4和比其下标值小increment的数组值相比较
  • 此例子是按照从大到小排列,所以大的会排在前面,第一次排序后数组为9, 2, 8, 5, 1, 3,4
  • 第一次后increment的值变为3/2=1,此时对数组进行插入排序,
    *实现数组从大到小排
    */


public static void shellSort(int[] data) 
{
    int j = 0;
    int temp = 0;
    //每次将步长缩短为原来的一半
    for (int increment = data.length / 2; increment > 0; increment /= 2)
    {
    for (int i = increment; i < data.length; i++) 
    {
        temp = data[i];
        for (j = i; j >= increment; j -= increment) 
        {
        if(temp > data[j - increment])//如想从小到大排只需修改这里
        {   
            data[j] = data[j - increment];
        }
        else
        {
            break;
        }

        } 
        data[j] = temp;
    }

    }
}

4、效率:
时间复杂度:O(n^2).
f)归并排序

基本思想:
  归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序示例:

合并方法:
设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

1、j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
2、若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
3、//选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
否则,rf[k]=r[j]; j++; k++; 转⑵
4、//将尚未处理完的子表中元素存入rf
如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空
5、合并结束。



算法实现:
/**

  • 归并排序
  • 简介:将两个(或两个以上)有序表合并成一个新的有序表 即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
  • 时间复杂度为O(nlogn)
  • 稳定排序方式
  • @param nums 待排序数组
  • @return 输出有序数组
    */
    public static int[] sort(int[] nums, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
    // 左边
    sort(nums, low, mid);
    // 右边
    sort(nums, mid + 1, high);
    // 左右归并
    merge(nums, low, mid, high);
    }
    return nums;
    }

/**

  • 将数组中low到high位置的数进行排序

  • @param nums 待排序数组

  • @param low 待排的开始位置

  • @param mid 待排中间位置

  • @param high 待排结束位置
    */
    public static void merge(int[] nums, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;// 左指针
    int j = mid + 1;// 右指针
    int k = 0;

    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
    if (nums[i] < nums[j]) {
    temp[k++] = nums[i++];
    } else {
    temp[k++] = nums[j++];
    }
    }

    // 把左边剩余的数移入数组
    while (i <= mid) {
    temp[k++] = nums[i++];
    }

    // 把右边边剩余的数移入数组
    while (j <= high) {
    temp[k++] = nums[j++];
    }

    // 把新数组中的数覆盖nums数组
    for (int k2 = 0; k2 < temp.length; k2++) {
    nums[k2 + low] = temp[k2];
    }
    }
    g)堆排序算法

1、基本思想:
  堆排序是一种树形选择排序,是对直接选择排序的有效改进。
  堆的定义下:具有n个元素的序列 (h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。
  思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个 堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对 它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
2、实例:
初始序列:46,79,56,38,40,84
  建堆:



  交换,从堆中踢出最大数:



依次类推:最后堆中剩余的最后两个结点交换,踢出一个,排序完成。
3.算法实现:

public class HeapSort {
public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
int arrayLength=a.length;
//循环建堆
for(int i=0;i<arrayLength-1;i++){
//建堆
buildMaxHeap(a,arrayLength-1-i);
//交换堆顶和最后一个元素
swap(a,0,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
}
//对data数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex){
//从lastIndex处节点(最后一个节点)的父节点开始
for(int i=(lastIndex-1)/2;i>=0;i--){
//k保存正在判断的节点
int k=i;
//如果当前k节点的子节点存在
while(k2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2
k+1;
//如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex<lastIndex){
//若果右子节点的值较大
if(data[biggerIndex]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if(data[k]<data[biggerIndex]){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{
break;
}
}
}
}
//交换
private static void swap(int[] data, int i, int j) {
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
}
6.常用查找算法
A、顺序查找
1 /顺序查找平均时间复杂度 O(n) 
2   @param searchKey 要查找的值 
3  
 @param array 数组(从这个数组中查找) 
4   @return  查找结果(数组的下标位置) 
5  
/  
6 public static int orderSearch(int searchKey,int[] array){  
7     if(array==null||array.length<1)  
8         return -1;  
9     for(int i=0;i<array.length;i++){  
10         if(array[i]==searchKey){  
11             return i;  
12         }  
13     }  
14     return -1;  
15       
16 }  
B、二分查找
1 /
 
2   二分查找又称折半查找,它是一种效率较高的查找方法。 【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。 
3  
  
4   @param array 
5  
            有序数组  
6  
 @param searchKey 
7              查找元素  
8   @return searchKey的数组下标,没找到返回-1 
9  
/  
10 public static int binarySearch(int[] array, int searchKey)  
11   
12     int low = 0;  
13     int high = array.length - 1;  
14     while (low <= high) {  
15         int middle = (low + high) / 2;  
16         if (searchKey == array[middle]) {  
17             return middle;  
18         } else if (searchKey < array[middle]) {  
19             high = middle - 1;  
20         } else {  
21             low = middle + 1;  
22         }  
23     }  
24     return -1;  
25 }  
C、分块查找
1 /** 
2   分块查找 
3  
  
4   @param index 
5  
            索引表,其中放的是各块的最大值 
6   @param st 
7  
            顺序表, 
8   @param key 
9  
            要查找的值 
10   @param m 
11  
            顺序表中各块的长度相等,为m 
12   @return 
13  
/  
14 public static int blockSearch(int[] index, int[] st, int key, int m) {  
15     // 在序列st数组中,用分块查找方法查找关键字为key的记录  
16     // 1.在index[ ] 中折半查找,确定要查找的key属于哪个块中  
17     int i = binarySearch(index, key);  
18     if (i >= 0) {  
19         int j = i > 0 ? i  m : i;  
20         int len = (i + 1) 
 m;  
21         // 在确定的块中用顺序查找方法查找key  
22         for (int k = j; k < len; k++) {  
23             if (key == st[k]) {  
24                 System.out.println("查询成功");  
25                 return k;  
26             }  
27         }  
28     }  
29     System.out.println("查找失败");  
30     return -1;  
31 }  
D.哈希查找
哈希表查找是通过对记录的关键字值进行运算,直接求出结点的地址,是关键字到地址的直接转换方法,不用反复比较。假设f包含n个结点,Ri为其中某个结点(1≤i≤n),keyi是其关键字值,在keyi与Ri的地址之间建立某种函数关系,可以通过这个函数把关键字值转换成相应结点的地址,有:addr(Ri)=H(keyi),addr(Ri)为哈希函数。
解决冲突的方法有以下两种:  
(1)开放地址法  
如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。  
(2)链地址法
将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。

Java代码  
1 /**** 
2   Hash查找 
3  
  
4   @param hash 
5  
 @param hashLength 
6   @param key 
7  
 @return 
8  /  
9 public static int searchHash(int[] hash, int hashLength, int key) {  
10     // 哈希函数  
11     int hashAddress = key % hashLength;  
12   
13     // 指定hashAdrress对应值存在但不是关键值,则用开放寻址法解决  
14     while (hash[hashAddress] != 0 && hash[hashAddress] != key) {  
15         hashAddress = (++hashAddress) % hashLength;  
16     }  
17   
18     // 查找到了开放单元,表示查找失败  
19     if (hash[hashAddress] == 0)  
20         return -1;  
21     return hashAddress;  
22   
23 }  
24   
25 /
** 
26   数据插入Hash表 
27  
  
28   @param hash 
29  
            哈希表 
30   @param hashLength 
31  
 @param data 
32  */  
33 public static void insertHash(int[] hash, int hashLength, int data) {  
34     // 哈希函数  
35     int hashAddress = data % hashLength;  
36   
37     // 如果key存在,则说明已经被别人占用,此时必须解决冲突  
38     while (hash[hashAddress] != 0) {  
39         // 用开放寻址法找到  
40         hashAddress = (++hashAddress) % hashLength;  
41     }  
42   
43     // 将data存入字典中  
44     hash[hashAddress] = data;  
45 }  

7.java的集合和继承关系


8.JVM特性
Java语言的一个非常重要的特点就是与平台的无关性。而使用Java虚拟机是实现这一特点的关键。一般的高级语言如果要在不同的平台上运行,至少需要编译成不同的目标代码。而引入Java语言虚拟机后,Java语言在不同平台上运行时不需要重新编译。Java语言使用模式Java虚拟机屏蔽了与具体平台相关的信息,使得Java语言编译程序只需生成在Java虚拟机上运行的目标代码(字节码),就可以在多种平台上不加修改地运行。Java虚拟机在执行字节码时,把字节码解释成具体平台上的机器指令执行。
9.进程与线程的区别
简而言之,一个程序至少有一个进程,一个进程至少有一个线程。线程的划分尺度小于进程,使得多线程程序的并发性高。
进程在执行过程中拥有独立的内存单元,而多个线程共享内存,从而极大地提高了程序的运行效率。线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源.一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行.
10.HashMap实现原理
1 HashMap概述:    HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
2 HashMap的数据结构: 在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。



从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。

11.string-stringbuffer-stringbuilder区别-小米-乐视-百度
String 字符串常量
StringBuffer 字符串变量(线程安全)
StringBuilder 字符串变量(非线程安全)

在大部分情况下 StringBuilder > StringBuffer > String
简要的说, String 类型和 StringBuffer 类型的主要性能区别其实在于 String 是不可变的对象, 因此在每次对 String 类型进行改变的时候其实都等同于生成了一个新的 String 对象,然后将指针指向新的 String 对象,所以经常改变内容的字符串最好不要用String ,因为每次生成对象都会对系统性能产生影响,特别当内存中无引用对象多了以后,JVM 的 GC 就会开始工作,那速度是一定会相当慢的。
在一般情况下我们推荐使用 StringBuffer ,特别是字符串对象经常改变的情况下。而在某些特别情况下, String 对象的字符串拼接其实是被 JVM 解释成了 StringBuffer 对象的拼接,所以这些时候 String 对象的速度并不会比 StringBuffer 对象慢,而特别是以下的字符串对象生成中, String 效率是远要比 StringBuffer 快的:
String S1 = "This is only a" + "simple" + " test";
StringBuffer Sb = new StringBuffer("This is only a").append("simple").append("test");
你会很惊讶的发现,生成 String S1 对象的速度简直太快了,而这个时候 StringBuffer 居然速度上根本一点都不占优势。其实这是 JVM 的一个把戏,在 JVM 眼里,这个  String S1 = “This is only a” + “ simple” + “test”; 其实就是:  String S1 = “This is only a simple test”; 所以当然不需要太多的时间了。但大家这里要注意的是,如果你的字符串是来自另外的 String 对象的话,速度就没那么快了,譬如:  String S2 = “This is only a”; String S3 = “ simple”; String S4 = “ test”; String S1 = S2 +S3 + S4; 这时候 JVM 会规规矩矩的按照原来的方式去做

StringBuffer
Java.lang.StringBuffer线程安全的可变字符序列。一个类似于 String 的字符串缓冲区,但不能修改。虽然在任意时间点上它都包含某种特定的字符序列,但通过某些方法调用可以改变该序列的长度和内容。
可将字符串缓冲区安全地用于多个线程。可以在必要时对这些方法进行同步,因此任意特定实例上的所有操作就好像是以串行顺序发生的,该顺序与所涉及的每个线程进行的方法调用顺序一致。
StringBuffer 上的主要操作是 append 和 insert 方法,可重载这些方法,以接受任意类型的数据。每个方法都能有效地将给定的数据转换成字符串,然后将该字符串的字符追加或插入到字符串缓冲区中。append 方法始终将这些字符添加到缓冲区的末端;而 insert 方法则在指定的点添加字符。
java.lang.StringBuilder
java.lang.StringBuilder一个可变的字符序列是5.0新增的。此类提供一个与 StringBuffer 兼容的 API,但不保证同步。该类被设计用作 StringBuffer 的一个简易替换,用在字符串缓冲区被单个线程使用的时候(这种情况很普遍)。如果可能,建议优先采用该类,因为在大多数实现中,它比 StringBuffer 要快。两者的方法基本相同

12.多态实现必要条件
多态存在的三个必要条件
一、要有继承; 二、要有重写; 三、父类引用指向子类对象。
13.线程阻塞
1 sleep() 方法:sleep() 允许 指定以毫秒为单位的一段时间作为参数,它使得线程在指定的时间内进入阻塞状态,不能得到CPU 时间,指定的时间一过,线程重新进入可执行状态。 典型地,sleep() 被用在等待某个资源就绪的情形:测试发现条件不满足后,让线程阻塞一段时间后重新测试,直到条件满足为止。
2 suspend() 和 resume() 方法:两个方法配套使用,suspend()使得线程进入阻塞状态,并且不会自动恢复,必须其对应的resume() 被调用,才能使得线程重新进入可执行状态。典型地,suspend() 和 resume() 被用在等待另一个线程产生的结果的情形:测试发现结果还没有产生后,让线程阻塞,另一个线程产生了结果后,调用 resume() 使其恢复。
3 yield() 方法:yield() 使得线程放弃当前分得的 CPU 时间,但是不使线程阻塞,即线程仍处于可执行状态,随时可能再次分得 CPU 时间。调用 yield() 的效果等价于调度程序认为该线程已执行了足够的时间从而转到另一个线程.
4 wait() 和 notify() 方法:两个方法配套使用,wait() 使得线程进入阻塞状态,它有两种形式,一种允许 指定以毫秒为单位的一段时间作为参数,另一种没有参数,前者当对应的 notify() 被调用或者超出指定时间时线程重新进入可执行状态,后者则必须对应的 notify() 被调用.
初看起来它们与 suspend() 和 resume() 方法对没有什么分别,但是事实上它们是截然不同的。区别的核心在于,前面叙述的所有方法,阻塞时都不会释放占用的锁(如果占用了的话),而这一对方法则相反。
14、容器类之间的区别-乐视-美团
http://tianmaying.com/tutorial/java_collection
15、一次http请求


最后由 BF 编辑于2017年09月13日 11:49