字节跳动后端笔试真题解析：三道编程题背后的算法思维

2018年秋招那会儿字节跳动后端方向的校招笔试里有一套题后来被整理成“字节跳动2018校招后端方向第三批”挂在牛客网上直到今天还有不少人拿它当模拟卷做。我当年也实际参加过这批笔试后来帮学弟学妹做模拟面试时发现这三道编程题几乎可以被当作字节后端算法岗的一个缩影不考偏题怪题也不要求你背冷门模板但每道题都在逼你想清楚一个问题——暴力做法是什么冗余在哪怎么一步步优化到能跑的数据规模。这篇文章就把第三批的三道题完整过一遍包括题目还原、思路推导、可运行的AC代码、复杂度分析以及我当时实际踩过的坑。无论你是准备大厂校招、日常实习还是单纯想练算法思维都可以把这份内容当成一套带详解的模拟题来用。文章里的代码以Python为主但思路部分我会尽量讲透方便你迁移到Java、C或者其他你熟悉的语言。1. 这批笔试题的构成与备考定位先明确一件事字节跳动2018校招后端方向第三批一共三到四道编程题题目都来自牛客网的在线笔试系统没有选择题全是代码题。当时题目的数据范围给得比较狠尤其是第一题N最大可以到500000这就直接劝退了上来就写O(N^2)暴力的人。第三批的主要题目可以归纳成下面这几道题号题目名核心考点数据规模特征1最大点排序 单调性扫描点数量最多50万2用户喜好哈希表分组 二分查找用户数、查询数都很大3字母交换模型抽象 搜索 / 状态压缩字符串长度较小但状态空间需要设计很多人做这套题的时候有一个误区以为字节的笔试会考特别偏的算法比如后缀自动机、网络流这种竞赛内容。实际上不是。这三道题全部落在一个很朴素的区间里——排序、二分、哈希、枚举、线性扫描。它和LeetCode上动辄Hard标签的题也不完全一样区别在于它更强调“在给定数据规模下你能不能把复杂度从显然的暴力降到正解”。我当初备考的时候也走过弯路先刷了三百道LeetCode再去笔试结果发现这套题里面没有一道是直接背模板能过的。它更接近真实工作里的状态需求给你了数据量给你了你要自己判断用什么数据结构、什么复杂度能接住。所以这篇文章里我会反复强调一件事不要只记解法要把“为什么用这个工具”记下来。面试官真正想看的不是你背了多少题而是你面对一个陌生问题时能不能快速把它拆解成几个基础算法模型的组合。2. 最大点排序方向错了整道题都会写歪2.1 原题描述P为给定的二维平面整数点集。定义P