奇安信校招笔试题复盘：百分号编码与字符统计的工程陷阱

前几天整理旧电脑翻出2019年秋招时保存的奇安信校招笔试题当时边做边存后面几道大题到现在还留着印象。这套题是我秋招里少有的“做完想复盘”的笔试尤其是第四题一道看起来是送分的字符串题实际写起来处处是坑考完出来跟同学对答案发现每个人对题意的理解都能差出好几个版本。这篇就把“奇安信2019校招笔试题四”里的最后一道大题完整复盘一下包括我当时整理的题目描述、审题时容易漏掉的条件、完整可运行的参考代码以及我在实际提交中踩过的几个典型问题。如果你正在准备网络安全方向或大厂通用开发岗的校招笔试这篇对你应该很有参考价值。这套笔试题整体不算偏难怪但很看重“边界条件”和“工程习惯”不是刷几道 LeetCode 就能稳过的类型。尤其是第四题本质上考的是字符串解析、编码识别的基本功但把“百分号编码”和“字符统计”拼在一起再套上长字符串的输入约束难度一下子就上来了。下面我按当时的环境和记忆把这道题从读题到提交完整过一遍。1. 这套题在考什么先给整套卷子画个像1.1 整套题的题型分布和难度梯度奇安信2019校招的这套题网上流传的版本很多我拿到的这套大致是前面十几道选择题覆盖操作系统、计算机网络、Linux基础、数据库常识外加一两道智力题后面是三道编程题第三题偏数据结构的应用第四题就是接下来要重点讲的字符串处理题。选择题里记忆比较深的是几道关于TCP三次握手、进程调度、Linux文件权限的题目难度中规中矩适合用来检验基础是否扎实。编程题第一题是常规的数组处理第二题有点像“最长连续子序列”的变体第三题开始有了明显的工程味道——不是单纯的算法题而是需要你考虑“这个场景里真正要处理的是什么”。第四题则更明显考的是字符串解析和容错处理这也是很多安全公司笔试里非常常见的一类题因为日常做安全运营、Web日志分析、协议解析本质上都在跟字符串打交道。1.2 为什么安全公司偏爱字符串处理题很多人不理解为什么安全公司笔试不直接考“如何发现漏洞”或者“如何排查入侵”反而考这种看起来比较基础的字符串题。其实原因很简单笔试题要兼顾公平性和可评判性没法让每个人都在本地搭一个靶场去实战所以只能用算法题的形式去考察你处理真实数据的底层能力。以百分号编码为例任何做过Web日志分析或者WAF规则调试的人都会频繁遇到这类编码。日志里一个看似正常的URL后端可能藏着编码后的注入语句一条攻击记录里空格被编码成%20单引号被编码成%27中文参数被编码成UTF-8的十六进制形式。如果连“把%XX还原成原始字符”这种基础操作都写不利索后面做检测规则、写解析脚本就会到处碰壁。所以这道题表面是在考字符串处理背后实际上是模拟了一个非常真实的场景给你一段可能被编码、可能不完整、可能有非法格式的输入你要在有限的时间和内存里把它处理成安全、可用的数据。这种“现实世界数据总是脏的”的意识才是出题人真正想看的。2. 题目原文与考点拆解百分号编码到底在考什么2.1 按当年记忆整理的题目描述这道题我当时保存过但不同渠道流传的版本略有差异以下是我根据考完后的回忆和同学讨论整理出来的一个相对完整的版本应该和大部分人在2019年拿到的第四题比较接近。题目名称字符串解码与字符统计输入一行字符串长度不超过100000可能包含空格和所有可见ASCII字符以及形如%XX的百分号编码片段。其中XX为两位十六进制数字大小写均可。请将字符串按如下规则解码遇到%XX时将其转换为对应的ASCII字符如果%后没有跟两位合法的十六进制数字则该%原样保留继续处理后续字符。解码完成后统计结果字符串中每个字符出现的次数输出出现次数最多的字符及其出现次数。如果有多个字符出现次数相同全部输出字符之间用一个空格分隔按ASCII码值从小到大排列。输入示例Hello%20World%21%21输出示例Hello World!!l 3说明解码后字符串为Hello World!!其中字符l出现3次是出现次数最多的字符。这个版本和我印象中的原题基本一致如果有细微出入不影响解题思路。2.2 这题真正想考察的四个点这道题一眼看过去核心就是一个%XX解析但如果只用“遇到%就读两个字符”这种思路去做很容易在细节上翻车。我后来复盘认为这道题主要考察四个层次的能力。第一个层次是“准确理解编码规则”。%后必须跟两位十六进制数字注意是“两位”且“都是十六进制数字”缺一不可。%2、%GG、%2G这些都不是合法编码%应该原样保留。第二个层次是“处理非法输入”。这是这道题最容易出错的地方。题目里明确说了非法编码就保留%但只保留%还是连后面的字符一起保留这里就体现了审题是否仔细。按题目描述非法时%本身保留然后继续处理后续字符也就是说%2G会解码成%2G而不是丢弃%或者把2吃掉。第三个层次是“统计结果”。很多人解码做对了结果输出格式又错了。题目要求输出出现次数最多的字符如果有多个并列全部输出并且按ASCII码从小到大排列。这个输出逻辑如果不提前想好提交后就会因为格式问题丢分。第四个层次是“性能”。字符串长度上限是100000单纯的解码是O(n)但如果用了不当的字符串拼接方式比如在Python里反复使用result char在数据量大的时候会退化到O(n²)直接超时。2.3 百分号编码的原理和安全背景百分号编码也叫URL编码最初是为了让URL能够传输ASCII字符集之外的字符而设计的。URL本身只允许一部分字符直接出现比如字母、数字以及-、_、.、~其他字符比如空格、中文、、、%等都需要通过编码来传输。编码规则很简单一个字节被表示为%加上该字节的两位十六进制形式。比如空格ASCII码是32十六进制是20所以编码后是%20!的ASCII码是33十六进制是21编码后是%21。这是纯知识性的内容不涉及任何攻击手段但它是理解Web日志、请求参数、响应头的基础所以安全公司把它作为笔试考点非常合理。在这道题里你只需要把%XX还原成对应的字符不需要考虑字符集、编码表、URL语法等额外问题。但如果你知道百分号编码的来龙去脉写起来会更有底气也会更容易想到“%后面跟16进制数字大小写都行”这类细节。3. 解题思路与复杂度分析这题不只是一次遍历3.1 先想清楚解码规则再动手写循环拿到题之后我最先做的是把解码规则在纸上明确列出来避免写到一半逻辑混乱。规则其实可以拆成三步当前字符如果是普通字符不是%直接加入结果。当前字符如果是%检查后面是否还有至少两个字符并且这两个字符都是十六进制数字。如果合法把这两位数字转成十进制数值再转成对应字符加入结果指针向后移动两位如果不合法把%本身加入结果指针向后移动一位。这里要特别注意一个细节%后只有1个字符或者%后面第1个字符是十六进制但第2个不是这两种情况都属于“非法编码”。按题目规则%应该原样保留然后继续处理后续字符而不是跳过两位。也就是说%2G应该被解码成三个字符%、2、G。为什么不是%G因为这里没有“部分合法”的概念要么两位都合法要么整个编码不成立只能从%后重新开始。3.2 十六进制转换的几种写法把XX两个十六进制字符转成十进制数值常见的方式有三种。第一种是用标准库函数比如C里可以用stoi(str.substr(pos, 2), nullptr, 16)但要注意substr会产生临时字符串在循环里大量使用时有一定开销。第二种是自己写一个小函数判断一个字符是否是十六进制数字并把它转成数值。这个函数看起来很基础但能很好地避免调用库函数时的各种边界问题。第三种是直接用查表法用一个长度为128的数组把0-9、a-f、A-F映射到对应的数值其他字符映射为-1这样判断和取值都能在O(1)内完成。我实际写的时候用的是查表法因为逻辑最直白也最不容易写错。下面这段是辅助函数的C实现int hexVal(char c) { if (c 0 c 9) return c - 0; if (c a c f) return c - a 10; if (c A c F) return c - A 10; return -1; }3.3 时间复杂度和空间复杂度估算解码过程从头到尾扫一遍输入字符串每个字符最多被访问一次时间复杂度是O(n)。统计字符频率再扫一遍结果字符串也是O(n)。最后输出最多字符时因为ASCII码总共只有128个或扩展后256个哪怕遍历整个ASCII表去找最大值也只需要常数时间。空间上需要一个和输入长度相当的字符串来保存解码结果因此空间复杂度也是O(n)。在字符串长度100000的限制下这个复杂度非常安全完全不需要担心超时或超内存。但如果有人在统计频率时用了std::map并且对结果字符串做多次排序复杂度就会上升到O(n log n)虽然也能过但没必要。直接用长度为256的数组统计频率是最稳定的做法。4. 完整实现C和Python两版代码照着改就能用4.1 C实现注意读入方式和数组清零C版本我最终提交时用的是全数组手动解析没有依赖过多的标准库函数主要是为了减少在线评测环境里可能出现的不确定性。完整实现如下#include algorithm #include cctype #include iostream #include string #include vector using namespace std; int hexVal(char c) { if (c 0 c 9) return c - 0; if (c a c f) return c - a 10; if (c A c F) return c - A 10; return -1; } int main() { string s; getline(cin, s); string decoded; decoded.reserve(s.size()); int cnt[256] {0}; int n (int)s.size(); for (int i 0; i n; ) { if (s[i] % i 2 n) { int hi hexVal(s[i 1]); int lo hexVal(s[i 2]); if (hi ! -1 lo ! -1) { char ch (char)(hi * 16 lo); decoded.push_back(ch); i 3; } else { decoded.push_back(%); i 1; } } else { decoded.push_back(s[i]); i 1; } } for (char c : decoded) { cnt[(unsigned char)c]; } int best 0; for (int i 0; i 256; i) { best max(best, cnt[i]); } cout decoded endl; bool first true; for (int i 0; i 256; i) { if (cnt[i] best) { if (!first) cout ; cout (char)i; first false; } } cout best endl; return 0; }这里有两个容易踩的点。第一个是用getline而不是cin s因为输入可能包含空格cin s会在空格处断开导致读入的是截断后的字符串后面的内容全丢了。第二个是数组下标用(unsigned char)c而不是直接用char因为当字符的ASCII码大于127时char可能是负数直接做数组下标会越界这是一个特别隐蔽的坑开发环境里不一定暴露但在线评测时可能直接RE。4.2 Python实现避开字符串拼接的陷阱Python版本我平时写脚本时很常用但在笔试里要注意不要用result s[i]这种写法来累积结果因为Python字符串是不可变对象每次拼接都会创建一个新字符串循环100000次性能会很差。正确做法是用列表保存字符最后一次性join。完整实现如下def hex_val(c): if 0 c 9: return ord(c) - ord(0) if a c f: return ord(c) - ord(a) 10 if A c F: return ord(c) - ord(A) 10 return -1 def decode(s): res [] i 0 n len(s) while i n: if s[i] % and i 2 n: hi hex_val(s[i 1]) lo hex_val(s[i 2]) if hi ! -1 and lo ! -1: res.append(chr(hi * 16 lo)) i 3 else: res.append(%) i 1 else: res.append(s[i]) i 1 return .join(res) s input() decoded decode(s) cnt [0] * 256 for ch in decoded: cnt[ord(ch)] 1 best max(cnt) print(decoded) print( .join(chr(i) for i in range(256) if cnt[i] best), best)Python版本里有一个和C不同的地方input()读入时会自动去掉末尾的换行符如果输入行本身末尾有回车不会进到结果字符串里这是符合直觉的行为不用额外处理。但要注意如果输入是个空行input()会拿到空字符串解码结果也是空字符串max(cnt)都是0输出时第二行会是一个空格加0逻辑上没有问题。4.3 笔试环境里的输入输出细节除了代码本身笔试环境里还有很多“隐形规则”经常坑人。第一个是行尾的空格。有些题目要求输出多个字符时用空格分隔但最后一项后面不能有空格否则格式错误。我上面的实现里用bool变量控制是否输出空格保证末尾没有多余空格。第二个是换行符。%0A解码后是换行符如果用cout直接输出会真的换行导致后续输出跑到下一行虽然逻辑上没问题但如果你后面的统计结果输出在同一行就会看起来很怪。题目里没有明确说要对结果中的控制字符做转义所以一般直接输出即可但你要知道这个现象是预期的不是程序跑挂了。5. 边界条件和测试用例设计提交前先自测这七种情况5.1 最常见的边界用例清单这道题的测试用例我后来整理了一个清单覆盖了几乎所有可能出现的情况。建议你在本地跑一遍确认输出和你预期一致。输入解码后最多字符说明Hello%20WorldHello Worldl出现3次正常空格解码abc%abc%c出现1次行尾单独的百分号%%%出现1次只有百分号%1%1%出现1次百分号后只有1位%GG%GG%出现1次百分号后两位都非法%2G%2G%出现1次百分号后第1位合法第2位非法%20%2F%3F/?和/和?都是1次连续多个编码%0A换行符换行符出现1次解码后为控制字符这些用例里最重要的是%2G和%在行尾的情况。前者检验你对“非法编码”的理解后者检验你有没有检查数组越界。如果你在判断%后面两位时没有先确认i 2 n那么abc%这种输入会让代码访问到字符串末尾之后的位置C里这是未定义行为在线评测时可能表现为随机错误。5.2 我当年提交时漏掉的几个细节第一次做这道题时我在“非法编码”的处理上理解偏了。我以为%2G会保留%2再把G当作普通字符处理结果输出是%2G但逻辑上是我把%2算成了一个整体和最终的拼写结果碰巧一样所以单纯看输出是看不出来的。但如果输入是%G2我当时的逻辑会输出%G2而正确结果也还是%G2所以有的用例能过有的用例会挂属于典型的“碰巧对”。后来我总结了一个判断标准解码规则里%后面两位必须同时合法否则%单独保留后面的字符原样继续解析。也就是说解析器永远不以“编码是否部分成功”为逻辑分支只以“整体合法/整体非法”为分支。这样写出来的代码没有歧义。另一个我踩过的坑是统计字符时用char做数组下标。C里char有没有符号是编译器决定的当解码结果里有%80这类高位字符时char可能是负值直接访问数组就访问到了负数下标。后来我改成unsigned char这个问题就消失了一个。这种坑在本地开发时不明显但在不同平台上表现不一样属于笔试里最让人头疼的“环境差异问题”。5.3 大输入下的性能验证字符串长度上限是100000这个规模其实不大理论上随便写都能在1秒内跑完。但为了稳妥我测试了一下把100000个%20拼在一起的情况。这时候输入长度是300000解码后长度是100000用上面的实现C版本大概在十几毫秒内跑完Python版本在几十毫秒级别都完全没问题。但如果用Python的result s[i]来做字符串拼接同样的输入可能要到几百毫秒甚至更久在多个测试点的情况下就会超时。所以笔试里如果时间充裕可以多用列表/数组少用不可变对象的频繁拼接这是一个相当实用的习惯。6. 复盘与备考建议这套题能给校招同学什么提示6.1 整套笔试题的时间分配建议我当年做这套题时前面的选择题控制在30分钟左右后面三道编程题各留了20到30分钟。第四题因为输入输出细节多实际花了将近40分钟导致最后检查其他题的时间有点紧。回过头来看如果你在笔试里遇到类似的“简单但细节多”的题最好的策略是先花一两分钟把规则逐条写清楚再动手写代码而不是边写边猜。网络安全岗位的笔试很多时候并不是在考你算法能力上限而是在考你是不是一个“能够处理脏数据、考虑边界条件、写代码像写工程文档”的人。这种能力短期内突击不来但可以通过类似下面的训练慢慢培养。6.2 字符串处理题怎么练最有效如果你正在准备校招我建议不要把精力都放在刷难题上而是把常见的字符串处理场景做一个清单每个都写一遍并且故意构造各种非法输入来测。比如URL解码、Base64解码、JSON字符串的转义处理、CSV解析、日志行切分。这些场景的共同点是“数据格式不完全可靠”你必须决定遇到非法数据时是丢弃、保留还是报错。练习时可以参照“输入约束 非法输入 边界条件 输出格式”这四个维度去设计测试用例。一道简单的解码题如果能把各种非法情况都测一遍你踩过的坑会沉淀成经验下次遇到类似题就顺很多。我觉得这是比刷十道同类型新题更高效的做法。结合这套真题我的体会是安全公司的笔试题并不可怕它只是用一道编程题把“你今天可能遇到的数据问题”提前问了一遍。处理编码数据要严谨凡事先问一句“如果输入不是合法的怎么办”而不是假设输入一定完美这比记住任何特定算法都更重要。如果你能把这种意识带到代码里不管笔试还是以后做实际工作都会少踩很多坑。