上海同余Java工程师（二面）

非技术相关：对工作地点和薪资待遇的期望。

算法相关

Q：快速排序的时间复杂度和空间复杂度？

A：平均时间复杂度：O(nlogn)，划分对称，所选枢轴元素可以将数据中分；

最坏时间复杂度：O(n^2)，初始排序表基本有序或基本逆序时。

平均空间复杂度：O(logn)，划分对称，

最坏空间复杂度：O(n)，初始排序表完全有序或逆序时，要进行n-1次递归调用。  

Q：归并排序的时间复杂度和空间复杂度？

A：时间复杂度：O(nlogn)。每趟归并的时间复杂度为O(n)，共需进行logn（向上取整）趟归并；

空间复杂度：O(n)，需要一个辅助数组。

Q：快速排序和归并排序的区别？

A：快速排序：

在带排序表中选一个元素（一般选首元素）作为基准（枢轴）元素，经过一趟排序将待排序表划分为独立的两部分，使得左边部分中的所有元素都小于等于基准元素，右边部分中的所有元素都大于基准元素。则基准元素被放在了最终位置上，这个过程被称为一趟快速排序。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或为空为止，即所有元素都放在了最终位置上。

二路归并排序；

基于分治的思想。把含有n个记录的待排序表视作n个有序的子表，每个子表的长度为1，然后两两归并，如此重复，直到合并成一个长度为n的有序表为止。 

区别：

• 快速排序是不稳定的（相同关键字的元素的相对次序会发生变化），归并排序是稳定的；
• 快速排序不产生有序的子序列，但每趟都会把一个元素（基准元素）放置到其最终的位置上，归并排序则相反。
• 快速排序是内部排序算法，归并排序是外部排序算法。

Q：HashMap的原理，以及按关键字查找的时间复杂度？

A：没完全答上来，只说了Java中的HashMap由数组、链表和红黑树构成，处理冲突的方式是拉链法（把所有的同义词，即发生碰撞的不同关键字，存储在一个线性链表中，这个线性链表由其散列地址唯一标识），链表中元素大于8时变为红黑树，红黑树中元素小于6时变为链表。

【扩展阅读】哈希表是根据关键码的值而直接进行访问的数据结构。一般哈希表都是用来快速判断一个元素是否出现集合里，常用于查询操作。 

HashMap新增元素的时间复杂度：

 put操作的流程：

第一步：key.hashcode()，时间复杂度O(1)。

第二步：找到桶以后，判断桶里是否有元素，如果没有，直接new一个entey节点插入到数组中。时间复杂度O(1)。

第三步：如果桶里有元素，并且元素个数小于6，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(n)=O(n)。

第四步：如果桶里有元素，并且元素个数大于6，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入到链表尾部。时间复杂度O(1)+O(logn)=O(logn)。红黑树查询的时间复杂度是logn。 

通过上面的分析，我们可以得出结论，HashMap新增元素的时间复杂度是不固定的，可能的值有：

O(1)（理想情况下，即没有哈希碰撞发生时）、O(logn)、O(n)。

------------

原文链接：https://www.jianshu.com/p/3dbd0bf55734  

手写代码

1、斐波那契数列

class Main {
  public static void main(String[] args) { 
	int n = 5; // 测试数据
	int res = fib(int n);   
	System.out.println(res); // 测试输出结果
  }
  /**
  * dp五步曲 
  * 1. 确定dp数组及其下标的含义
  * 2. 确定递推公式
  * 3. dp数组如何初始化
  * 4. 确定遍历顺序
  * 5. 举例推导dp数组
  */
  public static int fib(int n) {
	// dp[i] 表示第 i 个 fib（斐波那契数）
	int[] dp = new int[n+1];
	// dp 初始化，⼀般要放在函数开头前单独处理，防⽌数组下标越界
	if (n == 0) return 0;
	if (n == 1) return 1;
	// 初始化 dp
	dp[0] = 0;
	dp[1] = 1;
	// 遍历推导 dp
	for (int i = 2; i <= n; i++) {
	  dp[i] = dp[i-1] + dp[i-2]; // 递推公式
	}
	return dp[n];
  }
}

Q：你写的代码空间复杂度是多少？

A：O(n)，但是如果不使用数组，可以改进为O(1)

Q：那你写下改进后的算法。

// 由于上面的代码中计算 dp[i] 时只用到了dp[i - 1] 和 dp[i - 2] ，
// 因此可以考虑用变量来替换数组
public int fib(int n) {        
  if (n < 2) {            
	return n;        
  }        
  int p = 0, q = 0, r = 1;        
  for (int i = 2; i <= n; ++i) {            
	p = q;             
	q = r;             
	r = p + q;        
  }        
  return r;    
} 

2、快速排序

public class Main {
  public static void main(String[] args) {
	int[] arr = {3,6,7,9,1}; // 测试数据
	quicksort(arr, 0, arr.length - 1);
	for (int n : arr) {
	  System.out.println(n); // 输出排序结果
	}
  }
  /**
   * 快速排序 
   * @param arr 待排序数组 
   * @param l 递归左边界（下标）left 
   * @param r 递归右边界（下标）right 
   */
  public static void quicksort(int[] arr, int l, int r) {
	if (l >= r) return;
	int i = l, j = r;
	// 使得左子区间中的所有元素都小于等于基准元素，右子区间中的所有元素都大于基准元素
	while (i < j) {
	  while (i < j && arr[j] > arr[l]) j--;
	  while (i < j && arr[i] <= arr[l]) i++;
	  //swap i, j
	  int tmp = arr[i];
	  arr[i] = arr[j];
	  arr[j] = tmp;
	}
	// swap i, l
	int tmp = arr[i];
	arr[i] = arr[l];
	arr[l] = tmp;
	quicksort(arr, l, i - 1); // 左子区间排序
	quicksort(arr, i + 1, r); // 右子区间排序
  }
}

感受：还是要重视对时间复杂度和空间复杂度的学习，并且要结合算法本身进行理解记忆。