记某店面试题

1. 有 n 个整数元素的数组,如何获取其中最大的 k 个数?

a. 先对数组的元素进行排序,然后再取其中的 k 个数。时间复杂度主要在排序算法上,可以做到 nlog(n)

b. 循环 1 - k,每个循环内对数组做一次冒泡取最大值,则时间复杂度 kn

c. 先取 k 个元素,建立小顶堆,再遍历剩下的元素,如果元素比堆顶大,则放入堆中根据需要调整堆形态。最终堆中的元素就是最大的 k 个。

面试时很自然想到了 a 方案;b 想过,不过现场没有描述清楚;c 是参考了网络上的答案。

2. 有 n 级台阶,一次可以走 1 步或者 2 步,问有多少种走法?

分析:n=1 的时候,只有走 1 步的方案;n=2 的时候,有走 2 个 1 步或 1 个 2 步 2个方案;而 n 步可以归纳为走 n-1 步的所有方案和走 n-2 步的所有方案的和。

a. 递归

1
2
3
4
5
public int f(int n) {
if (n <= 2) return n;
int x = f(n-1) + f(n-2);
return x;
}

b. 迭代

1
2
3
4
5
6
7
8
9
10
11
public int f(int n) {
if (n<=2) return n;
int n1 = 1, n2 = 2;
int n3 = 0;
for(int i=3; i<=n; i++){
n3 = n1 + n2;
n1 = n2;
n2 = n3;
}
return n3;
}

面试时最先想到的了 a 方案;b 方案脑海中一直没有想起来递归对应的迭代这个词。

3. Mysql 数据库中 一张 user 表,包含 id,name,reg_date(格式:yyyy-MM-dd,如2019-03-20) 字段,使用一条语句找出注册用户个数大于 100 的 reg_data

1
2
3
4
5
6
7
8
9
select 
reg_date, total
from
(select
reg_date, count(*) as total
from user
group by reg_date) as tmp
where total > 100
order by total desc;

面试时没有给出这条语句,group by 与 order by 各想了一部分,没有拼成一条语句。回来后用实例测试了一下。平时在应用中基本走简单查询。

4. 数据库事务相关,如下:

1
2
3
4
5
6
7
a = 4;

// 开启事务
a = 5; ----
---②
a = 6; ---
// 提交事务

问线程 A 运行到②时,线程 B 将读取到 a 的值是多少?

面试时想到了数据库的事务隔离级别。未提交读、读已提交(不可重复读)、可重复读、串行化。
答曰:未提交读时结果是 5,读已提交时是 4。

拓展:MySQL的四种事务隔离级别

5. 100 的阶乘的最终结果有多少个 0?

最终的结果是 24 个。

每个 5 和 10,会使结果多一个 0,其中 25,50,75,100 会多两个,所以 10 个 5 + 10 个 10 + 4 = 24 个。

面试时给了 22 个的结果。未考虑到 25 和 75。

总结

题目 1,2,5 都是网上现成的题目,其实还是比较简单的。工作 10 年,很久没有参加面试了,也没有遇到面这些题目的。没有准备到,回答时只能根据自己临时的思路,回答的不尽如人意,比较遗憾。