头条面经

提前批算法题

1. 给定数组nums=[1,2,3,2,3,2,3],和一个常数K，找到数组里面出现次数>(N/k)次的数
   比如k=3，那么N/k=7/3=2，数组里面出现此时>2的有2、3。
2. 打家劫舍：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
   给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
   示例 1:
   输入: [1,2,3,1]
   输出: 4
   解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
   偷窃到的最高金额 = 1 + 3 = 4 。
3. 给一个数组，返回倒数第k大的数（可能有重复，用快排的思想，时间复杂度为：n+n/2+n/4+n/8+...=n(1+1/2+1/4+1/8+...)，属于等比数列，结果为2*n，故时间复杂度为O(n)）
4. 给一个数组，当前数组的值为能够前进的步数，问最少多少步能够走完这个数组。比如数组[3,4,1,2,3,4,2,3]，arr[0]=3代表能够从当前位置往后走3格，可以选择其中任意一格停下，然后读取当前格的值继续前进。

基础题

1. 锁膨胀：
   偏向锁->轻量级锁（自旋锁、自适应自旋锁，也叫作非阻塞同步、乐观锁）->重量级锁（又被叫做互斥锁MutexLock、阻塞同步、悲观锁）
2. 事务、分布式事务
3. 设计模式：单例模式
4. 这个有2个面试官都问了，问的都是四次挥手的细节，为什么最后time_wait要有2msl，三次握手、四次挥手、TIME_WAIT和CLOSE_WAIT阶段的作用
5. 输入url发生了什么（有DNS转换啊，ip网络寻址啊，三次挥手啊，可能还有NAT地址转换啊，还有ARP啊）
6. TCP 和 UTP 有什么区别？（一个面向连接一个非面向连接，一个可靠一个非可靠，TCP有流量控制，拥塞控制，面向流以及基于这些区别，他们的使用场景）
7. 面试HashMap之追命5连问
8. hashmap：线程安全、如何保证安全、不安全会发生什么
9. 这个是我写了spark，他问的，不会spark应该不会问scala统计单词个数
10. 就是对与一个mysql表，问select * from xxx和select id from xxx效率问题。