[toc]

算法题

1、二分查找算法（海量有序数据快速查询）

面试原题：百亿条有序时间数据，怎么最快查到某条记录？

原理背诵：有序数组，每次取中间值比较，折半缩小范围；时间复杂度O(logN)。

大数据场景：Hive分区查找、索引查询、Doris有序列快速过滤、日志时间检索。

面试话术：海量有序数据优先二分查找，比遍历快得多；数仓中用于分区裁剪、有序索引定位。

2、双指针算法（去重、有序合并、区间判断）

原理：快慢指针、左右指针；一次遍历完成去重、合并、区间筛选。

大数据场景：有序大文件合并、日志去重、连续时间段筛选、行为轨迹分析。

面试举例：两个有序超大日志文件，双指针一趟遍历合并为一个有序文件。

3、链表算法（LRU底层、Flink状态链表）

原理背诵：单向链表、双向链表；插入删除快、查询慢；LRU底层=哈希表+双向链表。

大数据场景：Redis缓存、Flink状态管理、Kafka偏移量链表维护。

4、栈&队列算法（消息积压、任务调度）

栈：后进先出；用于括号匹配、递归回溯、任务回滚。

队列：先进先出；Kafka消息队列、任务排队、流量削峰。

阻塞队列：Flink线程池、Spark资源调度、生产消费模型。

5、递归算法（树形层级、维度层级）

原理：自己调用自己，拆分重复子问题；注意递归深度防止栈溢出。

数仓场景：商品类目层级、地区树形结构、部门层级、血缘溯源。

6、二叉树算法（血缘分析、层级结构）

面试必考：前序、中序、后序、层序遍历。

大数据场景：数据血缘树、任务依赖树、菜单类目树、索引B+树。

面试话术：数据平台血缘分析底层采用二叉树遍历，递归追溯上游依赖表。

7、多路归并算法（海量文件合并）

面试原题：100个有序大文件，合并成一个全局有序文件？

原理：每个文件保留一个指针，最小堆维护最小值；每次取出最小写入结果。

生产场景：Hive合并小文件、日志合并、离线大排序、历史数据规整。

8、频率统计算法（热门商品、热点key排查）

原理：Hash统计频次，结合TopK找出高频key。

数仓用途：倾斜key排查、热点用户、爆款商品、恶意IP限流。

9、雪花算法（分布式唯一ID）

结构背诵：时间戳+机器码+序列号；全局唯一、趋势递增、无重复。

大数据场景：订单ID、埋点日志ID、分布式数据表主键、Flink唯一标识。

10、负载均衡算法（中间件必考）

轮询：均匀分发；
随机：随机分发；
加权轮询：高性能节点多分配；
一致性哈希：固定key固定节点；

场景：Kafka分区分发、Redis集群、服务网关、集群负载。

11、限流三大算法（实时风控、流量压测）

计数器限流：固定时间计数，简单粗暴；
滑动窗口限流：平滑流量，避免临界突刺；
令牌桶：允许突发流量，实时大屏流量控制；

生产场景：埋点日志限流、风控防刷、Kafka流量削峰。

12、字典树Trie（前缀匹配、日志过滤）

原理：字符逐层存储，公共前缀共享节点；查询极快、节省内存。

场景：URL黑名单、敏感词过滤、日志前缀筛选、域名匹配。

13、正则匹配算法（数据清洗）

数仓用途：清洗手机号、身份证、URL、特殊乱码、脏数据过滤；DWD层高频使用。

14、哈希算法（大数据基石）

面试话术：哈希算法将任意长度数据转为定长哈希值；用于去重、分片、加密、路由。

生产应用：shuffle分区、分桶、一致性哈希、布隆过滤器、文件校验。

8、一致性哈希算法（Kafka、Redis、分库分表必考）

面试原题：Kafka分区为什么能保证同一个key发送到同一个分区？扩容为什么不会大量迁移数据？

原理背诵：

构建0~2^32环形哈希环；
节点IP哈希落在环上，数据key哈希顺时针找最近节点；
新增节点只影响相邻一小部分数据，不会全局重分布；
优化：增加虚拟节点，解决数据倾斜、节点不均匀。

大数据应用：Kafka分区路由、Redis集群、分库分表、数据分片。

1、洗牌算法（随机打乱、抽样）

适用场景：用户随机抽样、风控随机打散。

算法思想：从后往前遍历，当前位置与随机位置交换，时间复杂度O(n)。

面试背诵话术：Fisher-Yates洗牌，保证概率均匀、无偏，大数据抽样常用，Hive中order by rand()底层就是洗牌算法。

2、蓄水池抽样算法（海量数据随机取样）

面试原题：亿级数据随机抽取100条，内存放不下全部数据怎么做？

原理背诵：

先初始化蓄水池，放入前k条数据；
遍历后续每条数据，以k/i概率替换蓄水池；
最终每条数据被选中概率相等。

使用场景：Hive抽样、日志随机采样、风控黑名单抽样。

3、数据倾斜算法（高频）

原理话术：数据倾斜本质是hash分区不均匀，热点key落在同一个reduce。解决方案：空值打散、加盐随机、热点key拆分、局部聚合。

4、LRU缓存淘汰算法（Redis、维度缓存必考）

面试原题：Redis缓存满了怎么淘汰？

原理背诵：最近最少使用淘汰，链表维护访问顺序，头部最新、尾部最久未使用；淘汰尾部节点；Redis近似LRU。

数仓场景：Redis缓存维度表、用户画像、热点特征，使用LRU淘汰冷数据。

5、布隆过滤器（去重、黑名单）

面试话术：二进制数组+多个哈希函数；判断一定不存在、不一定存在；优点内存极小；缺点无法删除、存在误判。

业务场景：用户去重、黑名单过滤、日志重复判断。

6、TopK 海量数据求最大/最小K个数（大数据必考）

面试原题：10亿条访问日志，找出访问量最高的100个IP，内存放不下全部数据怎么做？

算法原理（背诵）：

采用小顶堆解决最大TopK；大顶堆解决最小TopK；
维持堆容量为K，遍历全部数据；
堆未满直接放入，堆满后比较堆顶；大于堆顶替换堆顶；
遍历结束堆内即为最大K个数据。

大数据生产应用：热门商品、热点IP、倾斜key排查、流量TOP排行。

面试话术：海量数据求TopK不能全局排序，时间复杂度太高；使用小顶堆，时间复杂度O(nlogK)，内存只保留K个元素，适合超大数据量。

7、位图算法 BitMap（海量去重、状态标记）

面试原题：1亿用户ID，判断用户是否登录，怎么极致节省内存？

原理背诵：

利用二进制bit位存储状态，一个int占4字节可以存32个状态；
ID对应下标，存在置为1，不存在置为0；
优点：极度省内存、查询极快；
缺点：ID必须为整型、连续、不能过大。

数仓应用场景：日活用户去重、签到状态、用户黑白名单、用户留存标记。

9、滑动窗口算法（Flink实时必考）

面试原题：Flink滚动窗口、滑动窗口底层原理？

算法原理：

固定窗口大小，不断向前滑动；
滑动步长 < 窗口大小产生数据重叠；
只维护窗口内最新数据，过期数据丢弃；
时间复杂度极低，适合流式实时计算。

业务场景：实时最近1小时交易额、最近30秒流量、实时告警、滑动留存。

10、快速排序（大数据最常用排序、面试手写）

原理背诵：选取基准值，小于基准放左边、大于基准放右边；递归拆分；平均时间复杂度O(nlogn)。

大数据优化点：Hive、Spark底层排序都是优化快排；结合外排序解决磁盘海量数据排序。

面试话术：大数据生产不用冒泡，全部使用快速排序，无序海量数据效率最高。

11、外排序算法（海量大文件排序）

面试原题：一个100G日志文件，内存只有4G，怎么排序？

解题步骤（必背）：

拆分：大文件切分成多个小文件；
内排序：内存中快速排序，生成有序小文件；
归并排序：多路归并，最终输出一个全局有序大文件。

生产应用：Hive大表排序、离线超大日志排序、历史数据规整。

12、中位数算法（海量数据求中位数）

面试原题：十亿条交易金额，求交易中位数，内存放不下？

解法话术：双堆法，大顶堆存前半段、小顶堆存后半段；堆顶即为中位数；海量数据配合分片抽样，近似中位数。

13、贪心算法（数仓指标、资源调度）

原理：每一步只做当前最优选择，不回溯；局部最优推全局最优。

大数据场景：Azkaban调度资源分配、任务优先级、压缩策略、冷热数据存储选型。

14、冷热分离算法（中高级数仓必问）

原理背诵：

热数据：近7天，高频查询，存放SSD、Doris、Kafka；
温数据：近30天，中低频，存放HDFS；
冷数据：超90天，归档、压缩、低成本存储。

生产作用：降低存储成本、提升查询速度、优化集群压力。

15、大数据去重三大算法（面试总结）

布隆过滤器：超大批量、允许误判、不删除；黑名单、日志去重。
BitMap位图：整型连续ID、极致省内存；用户签到、日活去重。
Hash表：精准去重、占用内存大；中小批量明细去重。

大数据算法面试终极总结（一句话背诵）

抽样：蓄水池抽样、洗牌算法；
去重：布隆过滤器、位图、Hash；
排序：快速排序、外排序；
TopK：大小顶堆；
流式：滑动窗口、水位线；
分片：一致性哈希；
优化：贪心、冷热分离。

大数据算法终极分类（一页纸背诵清单）

1、海量数据处理：蓄水池、位图、布隆、外排序、多路归并、TopK

2、分片路由算法：一致性哈希、哈希取模、负载均衡

3、流式实时算法：滑动窗口、水位线、限流、令牌桶

4、基础高频算法：快排、二分、双指针、递归、栈队列、链表

5、工程实用算法：雪花ID、字典树、正则、贪心、冷热分离

6、去重算法三件套：BitMap > 布隆过滤器 > Hash表

算法一页纸极简口诀（面试前10分钟速背）

说明：全部最短口诀，不记原理、不记代码，面试张口就说，专门针对大数据数仓开发。

一、海量数据处理（超大文件、内存不够）

洗牌算法：倒序遍历、随机交换、均匀抽样，hive rand()底层。
蓄水池抽样：先存k个、概率替换、海量无偏抽样。
TopK堆排序：大堆求最小、小堆求最大，内存只留k个。
外排序：大文件切小文件、内部快排、多路归并。
中位数：双堆维护，一大一小，堆顶为中位。

二、去重算法（面试最高频）

BitMap位图：整型id、bit存状态、极致省内存、不能存大数。
布隆过滤器：二进制数组+多哈希、能判不存在、不能删、有误判。
Hash表：精准去重、占用内存大、中小数据使用。

三、分片&路由（中间件必考）

哈希算法：任意长度转定长，分区、分桶、去重全靠它。
一致性哈希：环形哈希、新增节点少迁移、kafka、redis用。
负载均衡：轮询均匀、加权择优、哈希固定、随机分发。

四、实时流式算法（Flink必考）

滑动窗口：窗口固定、步长滑动、数据重叠、统计最近时段。
水位线：标记时间、处理乱序、容忍延迟、剔除迟到。
限流算法：计数器简单、滑动平滑、令牌桶扛突发流量。
LRU缓存：哈希+双向链表、淘汰最久未使用、redis底层。

五、基础手撕算法（简单但必问）

快排：基准值、左右划分、递归、大数据默认排序。
二分查找：有序数据、折半查询、速度最快。
双指针：一趟遍历、合并有序、去重、区间筛选。
链表：增删快、查询慢、flink状态、偏移量。
栈队列：栈后进先出，队列先进先出，消息削峰。
二叉树：前中后层序遍历，数据血缘、索引底层。

六、工程实战算法（工作常用）

数据倾斜：分区不均、热点key、空值加盐、拆分打散。
多路归并：最小堆合并有序文件、hive合并小文件。
雪花算法：时间+机器+序号、全局唯一递增id。
字典树：前缀匹配、敏感词、url黑名单过滤。
贪心算法：局部最优、资源调度、任务优先级。
冷热分离：热数据ssd、温数据hdfs、冷数据归档压缩。
正则匹配：清洗脏数据、手机号、特殊字符剔除。

七、算法终极顺口溜（背这一段全部拿捏）

海量抽样蓄水池，去重位图布隆池；

分片一致哈希环，实时窗口水位齐；

堆求top快排序，二分指针最简单；

倾斜加盐打散用，冷热归档省机器；

工程雪花唯一id，缓存LRU永不弃。

SQL

面试手写SQL万能模板（直接默写）

1、通用开窗模板

1	row_number() over(partition by 分组字段 order by 排序字段 desc) rn

2、通用去重模板

1
2
3

select * from (
    select *,row_number() over(partition by id order by dt desc) rn
)t where rn=1

3、累计求和模板

1	sum(col) over(order by dt rows between unbounded preceding and current row)

4、分组内占比模板

1	count(1)/sum(count(1)) over(partition by class_id)

高频题目

一、窗口函数

1. 分组取TopN（高频手撕）

业务场景：每个部门薪资最高前2人、每个商品类目销量TOP3。

标准答案SQL：

select * from (
    select 
        dept_id,
        user_name,
        salary,
        row_number() over(partition by dept_id order by salary desc) as rn
    from emp
) t
where rn <= 2;

2. 累计求和（逐月累计）

SELECT
  month,
  amount,
  SUM(amount) OVER(ORDER BY month) AS total_acc
FROM sales;

3. 移动平均（近 3 日均值）

1	AVG(price) OVER(ORDER BY dt ROWS BETWEEN 2 PRECEDING AND CURRENT ROW)

4. 去重方案（面试追问）

方式1：distinct（少量数据、简单去重）

1	select distinct user_id from log;

方式2：group by（大数据量去重，推荐）

1	select user_id,max(dt) from log group by user_id;

方式3：row_number（复杂条件去重，生产最常用）

select * from (
    select *,row_number() over(partition by user_id order by dt desc) rn
    from log
)t where rn=1;

面试话术：生产环境禁止大表distinct，容易触发数据倾斜，优先row_number分组去重。

二、行列转换面试必写

1. 行转列（多行变一行，逗号拼接）

Hive/Spark SQL

SELECT
  user_id,
  CONCAT_WS(',', COLLECT_LIST(course)) AS course_list
FROM user_course
GROUP BY user_id;

面试话术背诵：行转列使用collect_list无序聚合、collect_set去重聚合，搭配concat_ws拼接字符串，常用于标签合并、多属性合并。

2. 列转行（一行拆多行）

SELECT
  user_id,
  course
FROM user_course
LATERAL VIEW EXPLODE(SPLIT(course_list, ',')) tmp AS course;

面试话术背诵：使用lateral view炸裂函数，搭配explode数组拆分，split切割字符串，实现列转行，常用于标签拆分、多维拆解。

三、数据倾斜 SQL 写法（面试高频）

1. 空值 / 大量 NULL 倾斜优化

-- 原写法倾斜
WHERE city IS NULL

-- 优化：加盐打散
SELECT *
FROM table
WHERE IF(city IS NULL, CONCAT('rand_', RAND()), city) 
  = IF(city IS NULL, CONCAT('rand_', RAND()), city);

2. Key 热点倾斜加盐两阶段聚合

-- 第一层：局部聚合加盐
SELECT key, CONCAT(key,'_',CAST(RAND()*10 AS INT)) AS salt_key, COUNT(1) AS cnt
FROM log
GROUP BY key, CONCAT(key,'_',CAST(RAND()*10 AS INT));

-- 第二层：去掉盐全局聚合
SELECT REPLACE(salt_key,'_',SUBSTRING_INDEX(salt_key,'_',-1)) AS key, SUM(cnt)
FROM tmp
GROUP BY REPLACE(salt_key,'_',SUBSTRING_INDEX(salt_key,'_',-1));

3. Join 倾斜优化

小表广播 Join：/*+ BROADCAST(small_table) */
大表倾斜 Key 单独处理，其余正常 Join，再 Union

SELECT /*+ BROADCAST(b) */ a.* 
FROM big_table a
JOIN small_table b 
ON a.key = b.key;

四、经典业务 SQL 真题

1. 连续登录天数（超高频）

思路：日期减去行号，相同即为连续

# 连续登陆超过3天
SELECT user_id, MIN(dt), MAX(dt), COUNT(1) AS continue_days
FROM (
  SELECT
    user_id,
    dt,
    DATE_SUB(dt, ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY dt)) AS flag
  FROM login_log
) t
GROUP BY user_id, flag
HAVING COUNT(1) >= 3;

2. 留存率计算（次日留存）

需求：计算每日新增用户、次日留存、7日留存。

留存定义：当天新增用户，后续某天再次活跃。

面试话术背诵：留存使用自关联，当天新增表关联未来活跃表；离线留存T+1计算，实时留存使用Flink状态做当日留存。

标准答案SQL：

# 次日留存
select 
    today.dt,
    count(distinct today.user_id) as new_user,
    count(distinct tomorrow.user_id) as retain_1d
from (
    select dt,user_id from user_new
) today
left join (
    select dt,user_id from user_active
) tomorrow 
on today.user_id = tomorrow.user_id 
and tomorrow.dt = date_add(today.dt,1)
group by today.dt;

# 一段时间内的留存，7天为例

3. 漏斗转化分析（电商、金融必问）

业务：浏览-加购-下单-支付，每一步转化率。

解题思想：同一用户行为路径、判断是否走完下一个节点。

select 
    sum(if(step=1,1,0)) as view_cnt,
    sum(if(step=2,1,0)) as cart_cnt,
    sum(if(step=3,1,0)) as order_cnt,
    sum(if(step=4,1,0)) as pay_cnt
from user_funnel;

面试话术：漏斗核心逻辑是用户行为埋点、行为编号，分层统计人数，计算转化率；大厂一般使用Flink实时漏斗、离线Hive漏斗。

4. 累计指标（日累计销售额、累计用户）

开窗函数 rows between 边界，生产高频。

select 
    dt,
    sale_amount,
    sum(sale_amount) over(order by dt rows between unbounded preceding and current row) as total_amount
from sale_data;

关键字背诵：unbounded preceding（首行）、current row（当前行）。

大数据 SQL 通用优化口诀（面试背）

尽早过滤：先 where 后 join，减少 shuffle
分组前过滤，聚合少数据
小表广播 Join，避免 shuffle 倾斜
避免 select *，只查需要字段
分区过滤必加，禁止全表扫描
倾斜 Key：加盐打散、局部 + 全局聚合
用好开窗代替子查询，简洁高效

SQL优化高频问答（面试必问）

where和having区别？ where分组前过滤，不经过shuffle；having分组后过滤，性能差；优先where过滤。
order by底层原理？ Hive两次排序，map端局部排序、reduce端全局排序，数据量大产生磁盘溢写。
开窗函数优缺点？ 优点：减少join、代码简洁；缺点：大数据量分区容易倾斜、内存占用高。
大表关联优化？ 前置过滤、分区裁剪、广播join、倾斜key打散、避免笛卡尔积。

算法题

1、二分查找算法（海量有序数据快速查询）

2、双指针算法（去重、有序合并、区间判断）

3、链表算法（LRU底层、Flink状态链表）

4、栈&队列算法（消息积压、任务调度）

5、递归算法（树形层级、维度层级）

6、二叉树算法（血缘分析、层级结构）

7、多路归并算法（海量文件合并）

8、频率统计算法（热门商品、热点key排查）

9、雪花算法（分布式唯一ID）

10、负载均衡算法（中间件必考）

11、限流三大算法（实时风控、流量压测）

12、字典树Trie（前缀匹配、日志过滤）

13、正则匹配算法（数据清洗）

14、哈希算法（大数据基石）

8、一致性哈希算法（Kafka、Redis、分库分表必考）

1、洗牌算法（随机打乱、抽样）

2、蓄水池抽样算法（海量数据随机取样）

3、数据倾斜算法（高频）

4、LRU缓存淘汰算法（Redis、维度缓存必考）

5、布隆过滤器（去重、黑名单）

6、TopK 海量数据求最大/最小K个数（大数据必考）

7、位图算法 BitMap（海量去重、状态标记）

9、滑动窗口算法（Flink实时必考）

10、快速排序（大数据最常用排序、面试手写）

11、外排序算法（海量大文件排序）

12、中位数算法（海量数据求中位数）

13、贪心算法（数仓指标、资源调度）

14、冷热分离算法（中高级数仓必问）

15、大数据去重三大算法（面试总结）

大数据算法面试终极总结（一句话背诵）

大数据算法终极分类（一页纸背诵清单）

算法一页纸极简口诀（面试前10分钟速背）

一、海量数据处理（超大文件、内存不够）

二、去重算法（面试最高频）

三、分片&路由（中间件必考）

四、实时流式算法（Flink必考）

五、基础手撕算法（简单但必问）

六、工程实战算法（工作常用）

七、算法终极顺口溜（背这一段全部拿捏）

SQL

面试手写SQL万能模板（直接默写）

1、通用开窗模板

2、通用去重模板

3、累计求和模板

4、分组内占比模板

高频题目

一、窗口函数

1. 分组取TopN（高频手撕）

2. 累计求和（逐月累计）

3. 移动平均（近 3 日均值）

4. 去重方案（面试追问）

方式1：distinct（少量数据、简单去重）

方式2：group by（大数据量去重，推荐）

方式3：row_number（复杂条件去重，生产最常用）

二、行列转换 面试必写

1. 行转列（多行变一行，逗号拼接）

2. 列转行（一行拆多行）

三、数据倾斜 SQL 写法（面试高频）

1. 空值 / 大量 NULL 倾斜 优化

2. Key 热点倾斜 加盐两阶段聚合

3. Join 倾斜优化

四、经典业务 SQL 真题

1. 连续登录天数（超高频）

2. 留存率计算（次日留存）

3. 漏斗转化分析（电商、金融必问）

4. 累计指标（日累计销售额、累计用户）

大数据 SQL 通用优化口诀（面试背）

SQL优化高频问答（面试必问）

二、行列转换面试必写

1. 空值 / 大量 NULL 倾斜优化

2. Key 热点倾斜加盐两阶段聚合