面试相关之数据结构&算法
1. 怎么理解数据结构？
参考回答：
研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
按照逻辑结构分类
- 线性结构：线性表、栈、队列
- 非线性结构：树、图
按照存储结构分为顺序结构、链式结构、索引结构、哈希结构
2. 什么是斐波那契数列？
参考回答：
斐波那契数列指的是这样的数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...即这个数列从第3项开始，每一项都等于前两项之和，数学表示F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）
3. 迭代和递归的特点，并比较优缺点
参考回答：
递归和迭代都是循环的一种，特点：
递归就是通过重复调用函数自身实现循环；满足终止条件时会逐层返回来结束循环
迭代通过函数内某段代码实现循环；使用计数器结束循环
| 类型 | 优点 | 缺点 |
|---|---|---|
| 递归 | 代码更简洁清晰，可读性更好 | 需要调用函数，会造成空间的浪费；使用栈机制，循环次数太多易造成堆栈溢出 |
| 迭代 | 效率高；无额外开销，节省空间 | 代码不如递归简洁 |
4. 了解哪些查找算法，时间复杂度都是多少？
参考回答：
java实现常见查找算法
5. 了解哪些排序算法，并比较一下，以及适用场景?
参考回答：
十大经典排序算法最强总结
6. 快排的基本思路是什么？最差的时间复杂度是多少？如何优化？
参考回答：
快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小；再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。当待排序列有序时会出现最坏时间复杂度O(n2)。几种优化方式：
- 当待排序序列的长度较小时采用直接插入排序
- 优化所选取数轴的计算方法，如三数取中
- 迭代取代递归，效率高
- 存储数轴值，节省无必要的交换
7. 二叉排序树插入或删除一个节点的过程是怎样的？
参考回答：
二叉排序树插入操作：先查找该元素是否存在于二叉排列树中并记录其根节点，若没有则比较其和根节点大小后插入相应位置
二叉排序树删除操作：
待删除节点是叶子节点，直接删除即可
待删除节点是仅有左或右子树的节点 ，上移子树即可
待删除节点是左右子树都有的节点 ，用删除节点的直接前驱或直接后继来替换当前节点
8. 什么是红黑树？
参考回答：
红黑树是一种自平衡二叉查找树，包含性质：
节点是红色或黑色
根节点是黑色
叶子节点是黑色
每个红色节点的两个子节点都是黑色
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
9. 100盏灯问题？
参考回答：
100盏灯的问题
10. 老鼠和毒药问题，加个条件，必须要求第二天出结果
参考回答：
- 二分查找思路，每次均分两组，每组各取一滴水混合成新溶剂喂给老鼠，继续对导致老鼠死亡的一组水进行同上操作。假如是第1瓶有毒，过程演绎如下，第一只老鼠死于前一堆（mid=(0+6)/2=3，即服用了第1、2、3、4瓶的混合溶剂），第二只老鼠死于前一堆（mid=(0+3)/2=1，即服用了第1、2瓶的混合溶剂），第三只老鼠随意试一瓶，根据服用后状态即可判断有毒的水。
- 二进制编码思路，对每瓶水二进制编码，所需编码位数正好为三位，将第一位是1的水混为新溶剂喂给第一个老鼠，以此类推，看三只老鼠服用状态（死亡=1，存活=0）得出对应的编码，找到对应的水即可。假如是第1瓶有毒，编码之后，让第一只老鼠服用第4、5、6、7瓶的混合溶剂，第二只老鼠服用第2、3、6、7瓶的混合溶剂，第三只老鼠服用第1、3、5、7瓶的混合溶剂，最终第一只和第二只老鼠存活，第三只老鼠死亡，对应编码为001，对应的水是第一瓶，故此瓶有毒。
**
第一瓶水 001
第二瓶水 010
第三瓶水 011
第四瓶水 100
第五瓶水 101
第六瓶水 110
第七瓶水 111
**
11. 海量数据问题
参考回答：
海量数据处理面试题集锦
12. （手写算法）二分查找
参考代码：
public static int binarySearch(int[] a, int key) {
int low, mid, high;
low = 0;//最小下标
high = a.length - 1;//最大小标
while (low <= high) {
mid = (high + low) / 2;//折半下标
if (key > a[mid]) {
low = mid + 1; //关键字比折半值大，则最小下标调成折半下标的下一位
} else if (key < a[mid]) {
high = mid - 1;//关键字比折半值小，则最大下标调成折半下标的前一位
} else {
return mid; //关键字和折半值相等时返回折半下标
}
}
return -1;
}
13. （手写算法）反转链表
参考代码：
//节点类
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
//方法1
public ListNode reverseLinkedList(ListNode head){
if (head == null || head.next == null){
return head;
}
ListNode p = new ListNode(-1);//拟一个头节点
p.next = head;
ListNode nextNode = head.next;
while (nextNode != null){
//后一个节点调整到最前
head.next = nextNode.next;
nextNode.next = p.next;
p.next = nextNode;
nextNode = head.next;
}
return p.next;
}
//方法2，递归
public ListNode reverseLinkedList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pNode = reverseLinkedList(head.next);
head.next.next = head;
head.next = null;
return pNode;
}
14. （手写算法）用两个栈实现队列
参考代码：
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
//入队
public void add(int node) {
stack1.push(node);
}
//出队
public int poll() {
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
15. （手写算法）用三个线程，顺序打印字母A-Z，输出结果是1A、2B、3C、1D 2E...
参考代码：
private static char c = 'A';
private static int i = 0;
public static void main(String[] args) {
Runnable runnable = new Runnable() {
public void run() {
synchronized (this) {//加锁
try {
int threadId = Integer.parseInt(Thread.currentThread().getName());
while (i < 26) {
if (i % 3 == threadId - 1) {
System.out.println(threadId +""+ (char) c++);
i++;
notifyAll();// 唤醒处于等待状态的线程
} else {
wait();// 释放当前锁并进入等待状态
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}//执行结束释放当前锁
}
};
Thread t1 = new Thread(runnable, "1");
Thread t2 = new Thread(runnable, "2");
Thread t3 = new Thread(runnable, "3");
t1.start();
t2.start();
t3.start();
}
16. （手写算法）如何判断一个链有环
参考代码：
//节点类ListNode同上
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead == null || pHead.next == null){
return null;
}
ListNode p1 = pHead;
ListNode p2 = pHead;
while(p2 != null && p2.next != null ){
p1 = p1.next;//p1每次走一步
p2 = p2.next.next;//p2每次走两步
if(p1 == p2){
p2 = pHead;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
if(p1 == p2){
return p1;//p1和p2相遇点正好是环的入口点
}
}
}
return null;
}
}
17. （手写算法）如何判断两条链交叉
参考：
JAVA 判断两个单链表是否相交并求交点
18. （手写算法）快速从一组无序数中找到第k大的数/前k个大的数
参考代码：
public class QuickSort {
public int partition(int[] arr,int low,int high){
int temp=arr[low];
while(low<high){
while(arr[high]<=temp&&high>low){
high--;
}
arr[low]=arr[high];
while(arr[low]>=temp&&low<high){
low++;
}
arr[high]=arr[low];
}
arr[high]=temp;
return high;
}
public void findK(int k,int[] arr,int low,int high){
int temp=partition(arr,low,high);
if(temp==k-1){
System.out.print("第"+k+"大的数是："+arr[temp]);
}else if(temp>k-1){
findK(k,arr,low,temp-1);
}else{
findK(k,arr,temp+1,high);
}
}
}
19. （手写算法）从字符串中找出一个最长的不包含重复数字的子字符串的长度。例如在字符串中”arabcacfr”，最长非重复子字符串为“rabc”或”acfr”，长度为4。
参考代码：
private int findLongestSubstringLength(String string){
if (string == null || string.equals("")) {
return 0;
}
int maxLength = 0;//最长不重复子字符串的长度
int[] positions = new int[26];//存储当前字符上次出现的位置，-1表示没有出现过
for (int i = 0; i < positions.length; i++){
positions[i] = -1;
}
int[] lines = new int[string.length()];//存储以当前字符为尾的最长不重复子字符串的长度
lines[0]=1;
positions[string.charAt(0) - 'a']=0;
for (int i = 1; i < string.length(); i++){
int prePosition = positions[string.charAt(i) - 'a'];
if(prePosition>=0){//当前字符非第一次出现
if((i-prePosition)>lines[i-1]){
lines[i]=lines[i-1]+1;
}else{
lines[i]=i-prePosition;//若加入当前字符会出现重复，需要截断
}
}else{//当前字符是第一次出现
lines[i]=lines[i-1]+1;
}
positions[string.charAt(i) - 'a'] = i;
if(lines[i]>maxLength){
maxLength=lines[i];
}
}
return maxLength;
}
推荐：
剑指 offer 题解
