记某店面试题

发表于 | 更新于: | 分类于
阿里云产品限时红包，最高 ￥1888 元，立即领取。

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 年，很久没有参加面试了，也没有遇到面这些题目的。没有准备到，回答时只能根据自己临时的思路，回答的不尽如人意，比较遗憾。