1. 用java写一个冒泡排序？
2. 介绍一下，排序都有哪几种方法？请列举出来。
参考回答：
排序的方法有：插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），
归并排序，分配排序（箱排序、基数排序）
快速排序的伪代码。
/ /使用快速排序方法对a[ 0 :n- 1 ]排序
从a[ 0 :n- 1 ]中选择一个元素作为middle，该元素为支点
把余下的元素分割为两段left 和right，使得left中的元素都小于等于支点，而right 中的元素都大于等于支点
递归地使用快速排序方法对left 进行排序
递归地使用快速排序方法对right 进行排序
所得结果为 left + middle + right
3.介绍一下，归并排序的原理是什么？
参考回答：
（1）归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
（2）首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
（3）解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
4.介绍一下，堆排序的原理是什么？
参考回答：
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
（1）最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
（2）创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆。
（3）堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
堆排序
5. 谈一谈，如何得到一个数据流中的中位数？
参考回答：
数据是从一个数据流中读出来的，数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，当有新的数据流中读出来时，这些数据就插入到数据容器中。
数组是最简单的容器。如果数组没有排序，可以用 Partition 函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度是 O(1)和 O(n)。
我们还可以往数组里插入新数据时让数组保持排序，这是由于可能要移动 O(n)个数，因此需要 O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要 O(1)时间即可完成。
排序的链表时另外一个选择。我们需要 O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表的中间结点（如果链表的结点数目是奇数，那么这两个指针指向同一个结点），那么可以在 O（1）时间得出中位数。此时时间效率与及基于排序的数组的时间效率一样。
如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。
因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需 O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是 O(1)。
6. 你知道哪些排序算法，这些算法的时间复杂度分别是多少，解释一下快排？
参考回答：
排序
快排：快速排序有两个方向，左边的i下标一直往右走（当条件a[i] <= a[center_index]时），其中center_index是中枢元素的数组下标，一般取为数组第0个元素。
而右边的j下标一直往左走（当a[j] > a[center_index]时）。
如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。
7.请你解释一下，内存中的栈(stack)、堆(heap) 和静态区(static area) 的用法。
参考回答：
通常我们定义一个基本数据类型的变量，一个对象的引用，还有就是函数调用的现场保存都使用内存中的栈空间；而通过new关键字和构造器创建的对象放在堆空间；程序中的字面量（literal）如直接书写的100、"hello"和常量都是放在静态区中。栈空间操作起来最快但是栈很小，通常大量的对象都是放在堆空间，理论上整个内存没有被其他进程使用的空间甚至硬盘上的虚拟内存都可以被当成堆空间来使用。
String str = new String("hello");
上面的语句中变量str放在栈上，用new创建出来的字符串对象放在堆上，而"hello"这个字面量放在静态区。
8. 说一说，heap和stack有什么区别。
参考回答：
栈是一种线形集合，其添加和删除元素的操作应在同一段完成。栈按照后进先出的方式进行处理。
堆是栈的一个组成元素。
9.介绍一下，堆与栈的不同是什么？
考回答：
（1）Java的堆是一个运行时数据区，类的对象从中分配空间。通过比如：new等指令建立，不需要代码显式的释放，由垃圾回收来负责。
优点：可以动态地分配内存大小，垃圾收集器会自动回收垃圾数据。
缺点：由于其优点，所以存取速度较慢。
（2）栈：
其数据项的插入和删除都只能在称为栈顶的一端完成，后进先出。栈中存放一些基本类型的 变量 和 对象句柄。
优点：读取数度比堆要快，仅次于寄存器，栈数据可以共享。
缺点：比堆缺乏灵活性，存在栈中的数据大小与生存期必须是确定的。
举例：
String是一个特殊的包装类数据。可以用：
String str = new String("csdn");
String str = "csdn";
两种的形式来创建，第一种是用new()来新建对象的，它会在存放于堆中。每调用一次就会创建一个新的对象。而第二种是先在栈中创建一个对String类的对象引用变量str，然后查找栈中有没有存放"csdn"，如果没有，则将"csdn"存放进栈，并令str指向”abc”，如果已经有”csdn” 则直接令str指向“csdn”。
10.什么是Java优先级队列(Priority Queue)？
参考回答：
PriorityQueue是一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。在创建的时候，我们可以给它提供一个负责给元素排序的比较器。PriorityQueue不允许null值，因为他们没有自然顺序，或者说他们没有任何的相关联的比较器。最后，PriorityQueue不是线程安全的，入队和出队的时间复杂度是O(log(n))。
优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。PriorityQueue是从JDK1.5开始提供的新的数据结构接口。如果想实现按照自己的意愿进行优先级排列的队列的话，需要实现Comparator接口。如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列。
11.请你讲讲LRU算法的实现原理？
参考回答：
①LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也很高”，反过来说“如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”，两种理解是一样的；常用于页面置换算法，为虚拟页式存储管理服务。
②达到这样一种情形的算法是最理想的：每次调换出的页面是所有内存页面中最迟将被使用的；这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。
为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU 算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到 。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。
算法实现的关键
命中率：
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，缓存污染情况比较严重。
复杂度：
实现起来较为简单。
存储成本：
几乎没有空间上浪费。
代价：
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。
12. 为什么要设计 后缀表达式，有什么好处？
参考回答：
后缀表达式又叫逆波兰表达式，逆波兰记法不需要括号来标识操作符的优先级。
13.请你设计一个算法，用来压缩一段URL？
参考回答：
该算法主要使用MD5 算法对原始链接进行加密（这里使用的MD5 加密后的字符串长度为32 位），然后对加密后的字符串进行处理以得到短链接的地址。
14.谈一谈，id全局唯一且自增，如何实现？
参考回答；
SnowFlake雪花算法
雪花ID生成的是一个64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成：
snowflake id生成规则
1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。
41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。
10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。
12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号
优点
简单高效，生成速度快。
时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增。
灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求。
缺点
依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成。
在分布式环境上，每个服务器的时钟不可能完全同步，有时会出现不是全局递增的情况。
网友评论