字节跳动数据开发面试复盘

字节跳动数据开发面试复盘

Hive 数据仓库分层

可以看我这篇文章
Hive 数据仓库分层

爬楼梯问题

经典的递归问题,也可以优化一下
题目来源: LeetCode 70. 爬楼梯

递归解法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else{
            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }
}

递归优化算法

用常规的递归去解决这个问题,但会带来一个问题,即超出时间限制
因此,可以用 Map 去做一个缓存,类似于减枝的效果,可以显著降低递归带来的重复计算问题
这里呢,有点像是动态规划,用一个缓存表去减少递归的计算量,由于我也不太会动态规划,后期有更优的算法再修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    Map<Integer,Integer> map = new HashMap<>();

    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else{
            if(!map.containsKey(n - 1)){
                map.put(n - 1,climbStairs(n - 1));
            }
            if(!map.containsKey(n - 2)){
                map.put(n - 2,climbStairs(n - 2));
            }
            return map.get(n - 1) + map.get(n - 2);
        }
    }
}

组内排序 HQL

row_number() over (partition by 字段 a order by 计算项 b desc ) as rank
按字段 a 进行分组,按计算项 b 进行分组排序

  • partition by 子句指定如何分组分配 row_number,每个分组内,行的编号重新开始
  • order by 子句指定按哪个列排序,从而为行分配编号
  • 如果没有 partition by ,那么整个表按 order by 的列排序
  • asc 默认为升序,desc 为降序

创建测试数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
create database if not exists hql;

use hql;

drop table if exists student_score;

create external table if not exists student_score
(
    id           int,
    class        string,
    student_name string,
    score        int
) row format delimited fields terminated by ','
    lines terminated by '\n'
    stored as textfile
    location '/hive_learn/hql/row_number';

数据预览

1
2
3
4
5
6
7
8
9
10
11
12
13
+-------------------+----------------------+-----------------------------+----------------------+
| student_score.id  | student_score.class  | student_score.student_name  | student_score.score  |
+-------------------+----------------------+-----------------------------+----------------------+
| 1                 | 1班                   | 小A                         | 78                   |
| 2                 | 2班                   | 小B                         | 89                   |
| 3                 | 1班                   | 小C                         | 99                   |
| 4                 | 3班                   | 小D                         | 80                   |
| 5                 | 1班                   | 小E                         | 88                   |
| 6                 | 2班                   | 小F                         | 92                   |
| 7                 | 1班                   | 小G                         | 90                   |
| 8                 | 3班                   | 小H                         | 95                   |
| 9                 | 1班                   | 小I                         | 93                   |
+-------------------+----------------------+-----------------------------+----------------------+

求每个班级成绩第一名的学生的信息
首先要按班级进行分组,统计每个组内学生的成绩排名,然后根据排名查出第一名的学生的相关信息

1
2
3
4
5
select *
from (select id, class, student_name, score,
             row_number() over (partition by class order by score desc) rank
      from student_score) as t
where rank = 1;