当前位置:首页 > 程序 > 正文

SQL进阶 面试常见的4种sql算法考试题(四):分块排序

2019-09-24 09:30 点击:4次 作者:biucz 我来投稿

SQL进阶 面试常见的4种sql算法考试题(四):分块排序

近期在不同群里有小伙伴们提出了一些在面试和笔试中遇到的Hive SQL问题,Hive作为算法工程师的一项必备技能,在面试中也是极有可能被问到的,所以有备无患,本文将对这四道题进行详细的解析,还是有一定难度的,希望你看完本文能够有所收获。

分块排序

最后一题感觉是比较有难度的一道题目:

2014,1
2015,1
2017,0
2018,0
2019,1
2020,1
2021,1
2022,0
2023,0
=>
2014,1,1
2015,1,2
2017,0,1
2018,0,2
2019,1,1
2020,1,2
2021,1,3
2022,0,1
2023,0,2

简单描述下题目,col1是有序的,然后按照col2分块计数,每当col2发生变化,就重新开始计数,计数的结果当作col3返回。

这道题我想到的方法可能比较笨,先上代码,然后咱们一步步解析:

select year,
       num,
       row_number() over(partition by min_year order by year asc) as new_rank
    from
    (
        select year,
               base.num as num,
               min_year,
               row_number() over(partition by base.year order by min_year desc) as rank
          from (
                select *
                  from default.a3
               ) base
         inner join (
                select min_year,
                       num,
                       pre_num
                  from (
                        select year as min_year,
                               num,
                               lag(num,1) over(order by year) as pre_num
                          from default.a3
                       ) a
                 where num!=pre_num
                    or pre_num is null
               ) min_year
            on base.num = min_year.num
         where base.year >= min_year.min_year
       ) cc
 where rank = 1
 order by year

输出结果符合预期:

SQL进阶 面试常见的4种sql算法考试题(四):分块排序

接下来,一步步解析下上面的过程:

1)使用lag函数,得到其前面一个数:

select year as min_year,
      num,
      lag(num,1) over(order by year) as pre_num
    from default.a3

2)判断当前数和前面一个数的关系,得到分块最小值。

如果两个数不相等,说明在此处数发生了变化,是一个新的分块的开始,除此之外,如果没有前一个数,说明当前行是第一行,同样作为一个分块的开始。这样,我们可以得到每个分块的开始:

select min_year,
       num,
       pre_num
from (
     select year as min_year,
            num,
            lag(num,1) over(order by year) as pre_num
     from default.a3
     ) a
where num!=pre_num
    or pre_num is null

这里的结果如下:

SQL进阶 面试常见的4种sql算法考试题(四):分块排序

四个分块的开始分别是2014、2017、2019、2022。

3)判断每一行属于哪个分块

我们需要拿第二步得到的结果与原结果使用第二列进行join,然后判断每一行属于哪个分块。决定每一行的所属分块有两个条件,首先该行第一列的值要大于或等于分块的最小值;其次,在所有满足条件的分块最小值中,选择最大的一个,便是该行所在分块的最小值。

所以这里我们首先进行join操作,然后使用row_number()得到了每一行所在的分块:

select year,
       num,
       min_year
    from
    (
        select year,
               base.num as num,
               min_year,
               row_number() over(partition by base.year order by min_year desc) as rank
          from (
                select *
                  from default.a3
               ) base
         inner join (
                select min_year,
                       num,
                       pre_num
                  from (
                        select year as min_year,
                               num,
                               lag(num,1) over(order by year) as pre_num
                          from default.a3
                       ) a
                 where num!=pre_num
                    or pre_num is null
               ) min_year
            on base.num = min_year.num
         where base.year >= min_year.min_year
       ) cc
 where rank = 1
 order by year

结果如下:

SQL进阶 面试常见的4种sql算法考试题(四):分块排序

4)把分块最小值作为分组键,进行分组排序

好了,这四道题就解析完毕了,抓紧时间去练习一下吧~~

推荐阅读:

SQL进阶 面试常见的4种sql算法考试题(一):多列转多行

SQL进阶 面试常见的4种sql算法考试题(二):排序后相邻两行均值

SQL进阶 面试常见的4种sql算法考试题(三):获取字符串索引列表

SQL进阶 面试常见的4种sql算法考试题(四):分块排序