备战春招(1)

in with 0 comment

面经来自牛客京东一面凉经

题目

  1. 排序有哪些,你比较熟哪些?
  2. 什么排序O(N2),什么排序O(NlogN),什么排序稳定,什么排序不稳定
    快排,归并原理,可以做到稳定吗
  3. 数据结构中散列表说一下?Hash冲突有什么解决方法?
  4. Http有哪些方法?
  5. 你说get是幂等的,幂等是你怎么理解?
  6. post呢?post幂等吗?
  7. put什么意思,说说,header呢?
  8. java容器框架整体架构,说一下?
  9. spring了解吗,说一下你IOC和AOP的实践?
  10. MVC是什么,说一下?
  11. HashMap你知道吗?(我知道啊,源码级别),rehash时机,rehash过程??

解答

排序有哪些

一般常说的排序有八个,分别为直接插入排序,希尔排序,简单选择排序,堆排序,冒泡排序,快速排序,归并排序和基数排序

直接插入排序

将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。
如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
时间复杂度:O(n^2)。
其他的插入排序有二分插入排序,2-路插入排序。

希尔排序

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
希尔排序方法是一个不稳定的排序方法。

简单选择排序

在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。
优化:二元选择排序
简单选择排序,每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序,最多只需进行[n/2]趟循环即可。

堆排序

堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足
image.png
时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

(a)大顶堆序列:(96, 83,27,38,11,09)

  (b)  小顶堆序列:(12,36,24,85,47,30,53,91)
image.png

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序。

因此,实现堆排序需解决两个问题:

  1. 如何将n 个待排序的数建成堆;
  2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。

调整小顶堆的方法:

1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

2)将根结点与左、右子树中较小元素的进行交换。

3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。
image.png

冒泡排序

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

快速排序

快速排序也是Java工具类Collections的sort方法的原理

  1. 选择一个基准元素,通常选择第一个元素或者最后一个元素,
  2. 通过一趟排序讲待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
  3. 此时基准元素在其排好序后的正确位置
  4. 然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

归并排序

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

桶排序/基数排序

桶排序:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序

基数排序:说白了就是**进行多次的桶式排序。**基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

什么排序O(N2),什么排序O(NlogN),什么排序稳定,什么排序不稳定

快排,归并原理,可以做到稳定吗
这里根据上面八个排序做下总结

排序方法平均情况最好情况最坏情况空间复制度稳定性
直接插入O(N2)O(N)O(N2)O(1)稳定
希尔排序O(N1.3)O(N)O(N2)O(1)不稳定
选择排序O(N2)O(N2)O(N2)O(1)不稳定
堆排序O(Nlog2n)O(Nlog2n)O(Nlog2n)O(1)不稳定
冒泡排序O(N2)O(N)O(N2)O(1)稳定
快速排序O(nlog2n)O(nlog2n)O(N2)O(nlog2n)不稳定
归并排序O(nlog2n)O(Nlog2n)O(N)O(1)稳定
直接插入O(d(r+n))O(d(n+rd))O(d(r+n))O(rd+n)稳定

原文出处八大排序算法

数据结构中散列表说一下?Hash冲突有什么解决方法?

哈希表是根据关键码值(key value)而直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
处理Hash冲突有以下方法

  1. 开放寻址法
  2. 再散列法
  3. 链地址法
  4. 建立公共溢出区

Http有哪些方法?

方法描述
GET请求指定的页面信息,并返回实体主体。
HEAD类似于 GET 请求,只不过返回的响应中没有具体的内容,用于获取报头
POST向指定资源提交数据进行处理请求(例如提交表单或者上传文件)。数据被包含在请求体中。POST 请求可能会导致新的资源的建立和/或已有资源的修改。
PUT从客户端向服务器传送的数据取代指定的文档的内容。
DELETE请求服务器删除指定的页面。
CONNECTHTTP/1.1 协议中预留给能够将连接改为管道方式的代理服务器。
OPTIONS允许客户端查看服务器的性能。
TRACE回显服务器收到的请求,主要用于测试或诊断。
PATCH是对 PUT 方法的补充,用来对已知资源进行局部更新 。

get是幂等的,幂等是你怎么理解?

GET方法用于获取资源,不应有副作用,所以是幂等的。
幂等操作的特点是其任意多次执行所产生的影响均与一次执行的影响相同。幂等函数或幂等方法,是指可以使用相同参数重复执行,并能获得相同结果的函数。这些函数不会影响系统状态,也不用担心重复执行会对系统造成改变。即多次执行的结果与第一次执行的结果是相同的。

post呢?post幂等吗?

POST所对应的URI并非创建的资源本身,而是资源的接收者。
举个例子,就是我们在某个网站注册的时候,一般都是使用的post请求,在第一次注册的时候,会显示注册成功。而使用同一个账号和密码再次进行注册,返回的就不再是注册成功了。即第二次请求重复请求执行结果与第一次不同
所以post并不幂等。

put什么意思,说说,header呢?

参考 Http有哪些方法?

java容器框架整体架构,说一下?

Java容器框架,即list,set,map
list和set都继承自Collection接口
image.png
而map本身就是一个接口,他的实现就有我们最常说的HashMap,HashTable等

spring了解吗,说一下你IOC和AOP的实践?

spring的IOC就是控制反转了,也是我们经常使用的,所谓IOC就是将类创建的控制权交由Spring处理,其内部是一个IOC容器,里面存放了我们需要使用的Bean,在使用方面,比如在MVC三层架构中,Controller层调用Service层,Service调用Dao层,这个调用关系就可以使用IOC和DI来完成。
AOP,面向切面编程,原理是动态代理在Sring中的实现方式有两种,一种是jdk自带动态代理对象,另一种是cglib。在使用方面,就是可以来写用户操作日志。定义前置通知或者后置通知方法来完成这个需求。
之前有写过一篇博客Spring概述

MVC是什么,说一下?

MVC模式,即Model View Controller,在目前的软件开发过程中,它已经成为了一种设计规范。

MVC 分层有助于管理复杂的应用程序,因为您可以在一个时间内专门关注一个方面。例如,您可以在不依赖业务逻辑的情况下专注于视图设计。同时也让应用程序的测试更加容易。

MVC 分层同时也简化了分组开发。不同的开发人员可同时开发视图、控制器逻辑和业务逻辑。

HashMap你知道吗?rehash时机,rehash过程??

HashMap的内部实现机制有两个参数,DEFAULT_INITIAL_CAPACITY和DEFAULT_LOAD_FACTOR,DEFAULT_INITIAL_CAPACITY是table数组的容量,DEFAULT_LOAD_FACTOR则是为了最大程度避免哈希冲突,提高HashMap效率而设置的一个影响因子,将其乘以DEFAULT_INITIAL_CAPACITY就得到了一个阈值threshold,当HashMap的容量达到threshold时就需要进行扩容,这个时候就要进行ReHash操作了,代码如下。

void addEntry(int hash, K key, V value, int bucketIndex) { 
ntry<K,V> e = table[bucketIndex]; 
      table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
      if (size++ >= threshold) 
          resize(2 * table.length); 
  }

但是扩容的过程中需要进行ReHash操作,而这是非常耗时的,在实际中应该尽量避免。

总结

这篇面经,总的来说,算是一个很偏门的基础问题,也就是这些偏门的低频问题,让人面试难受,我之前就被这样难受过。。
首先,进一步扎实了关于排序算法的分类,实现思路和算法的稳定性。
其次在http方法,回顾以下,和有关get,post幂等性的问题,学到了一手。
接着就是复习之前的知识,比如Spring的,MVC和HashMap源码。
又一次了解到了处理Hash冲突的方法。
如果我面试遇到了这些问题,在写完这篇博客前,我只能给我自己打个6分把。苦笑