面试刷题11-10 算法

2019.8-2019.10
到了秋招提前批的阶段了，自己的Java简历也完成了，在本科的基础上新增了一些东西，以更简洁更完善的方式呈现出来，同时回顾并总结本科时期的Java项目，并慢慢开始复习，备战。下面开始讲面经了。
毫无准备

8.14 阿里巴巴一面（新零售供应链，凉了，这是我的第一场面试），大概30分钟
HashMap和HashTable区别

HashMap线程不安全，HashTable线程安全，HashTable是JDK1.0引入的，锁住整个数组，效率低

HashMap实现原理（put、resize())

put 方法将对象放入到HashMap中的合适位置， resize() 将HashMap进行扩容操作

StringBuffer和StringBuilder区别

线程安全，线程不安全

数据库事务隔离级别

读未提交，读提交，可重复度，串行化

如何避免幻读

什么是幻读
事务不是独立执行时发生的一种现象，例如第一个事务对一个表中的数据进行了修改，这种修改涉及到表中的全部数据行。同时，第二个事务也修改这个表中的数据，这种修改是向表中插入一行新数据。那么，以后就会发生操作第一个事务的用户发现表中还有没有修改的数据行，就好象发生了幻觉一样。
mysql如何实现避免幻读
- 在快照读读情况下，mysql通过mvcc来避免幻读。
- 在当前读读情况下，mysql通过next-key来避免幻读
什么是mvcc
mvcc全称是multi version concurrent control（多版本并发控制）。mysql把每个操作都定义成一个事务，每开启一个事务，系统的事务版本号自动递增。每行记录都有两个隐藏列：创建版本号和删除版本号
- select：事务每次只能读到创建版本号小于等于此次系统版本号的记录，同时行的删除版本号不存在或者大于当前事务的版本号。
- update：插入一条新记录，并把当前系统版本号作为行记录的版本号，同时保存当前系统版本号到原有的行作为删除版本号。
- delete：把当前系统版本号作为行记录的删除版本号
- insert：把当前系统版本号作为行记录的版本号
什么是next-key锁
可以简单的理解为X锁+GAP锁
什么是快照读和当前读
- 快照读：简单的select操作，属于快照读，不加锁。(当然，也有例外，下面会分析)
  - select * from table where ?;
- 当前读：特殊的读操作，插入/更新/删除操作，属于当前读，需要加锁。
  - select * from table where ? lock in share mode;
  - select * from table where ? for update;
  - insert into table values (…);
  - update table set ? where ?;
  - delete from table where ?;

?????
数据库引擎（Innodb）的事务支持粒度
如何实现乐观锁
可以通过CAS实现
Synchronized实现原理
tcp三次握手，四次回首
osi7层模型
最后问了两个智力题：
两个粗细不均匀、长短不一的的绳子，燃烧一根分别需要60分钟，如何利用两根绳子，测量出15分钟？
一个篮球可以装多个乒乓球？

8.21有赞一面（凉了）20分钟
HashMap和ArrayList默认容量分别是多少？

16， 10

HashMap和HashTable区别
HashMap什么时候扩容，几倍？

2 倍扩容

ArrayList什么时候扩容，几倍？

1.5 倍扩容

讲讲Java内存模型
讲讲gc算法

标记 -清除算法
复制算法
标记-压缩算法
分代收集算法

01背包问题，我说了dp的方案，但面试官说使用贪心算法（性价比最高优先，我当时屈服了），但是后来发现，贪心不行。

【面试刷题11-10】1
2
3
4
5
6 反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

8.26 美团二面（估计凉了，但还没收到拒信）
一面:（25号晚上做了美团笔试，很差，3道算法题，只过了30%）
上来先吐槽我算法很烂，然后要考察我基础。
进程调度方式

时间片轮转，先来先服务，短时作业优先

进程与线程区别
多线程优点

程序并发执行效率高

进程同步有哪些方式
osi七层模型，以及对应都有什么协议
tcp三次握手和四次挥手
udp和tcp区别
http报文都有什么
客户端发起http到服务端返回的详细过程
编程实现求二叉数深度
还有一题忘了。
二面：
二面主要考察场景题，让我从自己的项目出发，如果项目需要上线了，需要考虑什么问题。
看过那些架构的设计。
平时的学习方法。
8.27阿里国际（深圳）一面（凉了）
GC算法都知道哪些？分别讲讲（serial pal new、parelle scavge、serial old、parelle old、CMS）主要讲了下cms
JVM内存模型。
Zookeeper原理，当有3台服务器，一个挂了，怎么保证服务的正常使用？
Spring 怎么接受web请求（应该是Spring MVC）流程是怎样的。
AOP原理
Spring Boot启动加载过程。

9.3 葡萄城（一面+机试+二面，凉了）（C#做控件开发）
一面，两个面试官，问了计算机网络，还是那些常问的问题，我就不列出来了。
问java有什么优缺点，我说单继承，接口可以多实现，就问为什么？多承继为什么不好？（自己给自己挖了个坑）
还喜欢什么？集合。
都有哪些集合？balabala……
HashMap是怎么实现的？baabala
HashMap可以解决什么问题？我说字符频率统计。
怎么做的？比较hashcode，然后比较equals
如果字符串是变量怎么办，“abc abc”，两个abc的地址不同？暗示hashcode不同，没答出来…
git常用操作都有哪些，查看日志用啥？
如果不小心把一个很大的文件2gb，push了上去，然后发现后在远端删除了，之后别人执行git clone，会把所有的历史信息给clone下来，如何解决这个问题？
重点提的是，让我讲述项目难点的时候，我提到了跨域问题，我当时对项目还没有完全熟悉（2年前做的），一直在那讨论为什么会出现跨域（这也导致我回去之后，把项目仔细看了下，发现是我当时对项目不够书序，导致描述错误）
二面，机试：用#画直方图，输入一组数据：

1
2
3
4
5
6
7
8
9
10
11
12
13 [
{value:2,label:”a”},
{value:5,label:“b”},
{value:3,label:”c”}
]
输出：用空格分割每列
#
#
##
###
###
———-------
abc