关于 go 语言的考查题解没有收录，主要收录算法相关题目
# DAY1
一、【多选】Golang 通过 plugin.(*Plugin).Lookup 函数可以查找到插件里面定义的哪些东西
a. 变量
b. 函数
c. 类型
d. 包
二、假如在抖音中发布视频时，可以选择带上位置信息，请设计一种数据结构或方案，用于存储检索位置信息（简化为平面坐标 x, y），以实现搜索附近视频的功能（如附近 3km）。
答案 & 解析：
坐标范围检索，有四叉树、geohash 等几种标准解法。这道题本质并不是考察对高阶算法的掌握，而是想发掘在学习教材 btree 等基础二分思想后，能否进一步思考解出更复杂的问题；
另外考察思维灵活程度，看是否能变通的解决问题，如距离并没有限定必须是欧式距离；位置可以不精确，可以容忍有误差等。
- 方法 1，四叉树（QTree）：在二叉树左、右节点的思想下，加入上、下、前、后等更多的方向，演进为四叉树和八叉树。高阶树比较超纲，相关实现省略
- 方法 2，geohash：把二维问题降为一维
如坐标（示例非标准 geohash，只是演示了思想）：
(12, 345) -> (012, 345) -> "031425"
(13, 348) -> (013, 348) -> "031438"
(2, 789) -> (002, 789) -> "070829"
最终做字符串前缀匹配，可得"031425"和"031438" 匹配到的位数最多，二者距离最近。求 3km 内的坐标，只需提前算出需匹配前几位即可，如匹配前 4 位，按 sql 表达是 LIKE '0314%'
geohash 算法详解 - 方法 3，变通距离为 方圆 3km（曼哈顿距离），即 deltaX = 1500, deltaY = 1500，通过数据库解决 Create table tb_name (x int, y int) 并添加索引。
假如原点是 (x0, y0)，sql 如下：
WHERE (x > x0 - 1500) AND (x < x0 + 1500) AND (y > y0 - 1500) AND (y < y0 + 1500)
# DAY2
一、【多选】下列关于 Join 运算不正确的是：
a. Nested Loop Join 不能使用索引做优化。
b. 如果左表太大，不能放入内存中，则不能使用 Hash Join。
c. 如果 Join 的一个输入表在 Join Key 上有序，则一定会使用 Sort Merge Join。
d. Broadcast Join 适用于一张表很小，另一张表很大的场景。
答案 & 解析：
a、b、c；
Nested Loop Join 可以使用索引优化（Index Nested Loop Join）；
如果左表太大，不能放入内存，可以先对量表做分区，再对每个分区做 Hash Join （Parititioned Hash Join）；
如果 Join 的一个输入表在 Join Key 上有序，也可以 Hash Join，具体使用哪种 Join 方式取决于优化器的代价估计结果。
二、给定一个正整数数组 arrs 和整数 K ，请找出该数组内乘积小于等于 k 的连续的子数组的个数，算法时间复杂度 o (n)。
答案 & 解析：
双指针思想，对于每个 right, 不断单调的移动 left，直到满足需求。
# DAY3
一、【多选】绝大多数硬盘可以提供哪些写入保证？
a. 单个 sector 原子写入
b. 单个 page 原子写入
c. 硬盘顺序执行文件系统发送的操作
d. 以上都不可以
答案 & 解析：
d；
本题主要考察对于一个数据密集型应用开发者（比如数据库开发者、文件系统开发者），在数据不能出错的前提下，可以依赖磁盘的哪些能力，事实证明几乎没有什么能力可以依赖。
在随时可能断电的情况下，大多数硬件能提供单个 sector 的原子性写入；但是也有少数硬件连单个 sector 的写入都无法保证；如果一个 page 对应多个 sector，则单个 page 的完整写入总是无法得到保障。
对于同时发给硬盘的多个操作（比如写多个不连续的 sector），硬盘并不保证操作的顺序。结合其弱原子性，所以硬盘可能处在任何一个中间状态。这主要是由于机械硬盘的寻址优化策略和固态 / 机械硬盘的缓存策略导致的。
二、判断一棵二叉树是否是平衡二叉树。（平衡二叉树要求：树中节点左右子树树高差不超过 1。）
答案 & 解析：
public boolean isBalanced(TreeNode root) { | |
return isBalance(root) != -1; | |
} | |
private int isBalance(TreeNode root){ | |
if(root == null ){ | |
return 0; | |
} | |
int leftLength = isBalance(root.left); | |
if(leftLength == -1){ | |
return -1; | |
} | |
int rightLength = isBalance(root.right); | |
if(rightLength == -1){ | |
return -1; | |
} | |
if(Math.abs(leftLength-rightLength)>1){ | |
return -1; | |
} | |
return Math.max(leftLength,rightLength)+1; | |
} |
# DAY4
一、【单选】go test 默认是以什么顺序执行测试的？
a. 多个 module 并发执行，单 module 下多个测试并发执行
b. 多个 module 并发执行，单 module 下多个测试串行执行
c. 多个 module 串行执行，单 module 下多个测试并发执行
d. 多个 module 串行执行，单 module 下多个测试串行执行
答案 & 解析：
b；
多个 modules 会并发编译，然后并发执行测试，除非添加了额外的参数 - p=1。单个 modules 下多个测试会串行执行，除非在测试函数内执行 t.Parallel ()。
二、【分布式文件处理，获取最多的 URL】如果有一个 20g 的日志文件，日志文件记录着用户访问过的 url，每一行为一个 url，给你一台 512M 的主机，找出出现次数最多的 10 个 url。
答案 & 解析：
Top K 算法：使用堆排序算法＋大顶堆＋10 个元素的数组。
- IP 地址最多有 2^32=4G 种取值情况，所以不能完全加载到内存中处理；
- 可以考虑采用 “分而治之” 的思想，按照 IP 地址的 Hash (IP)%1024 值，把海量 IP 日志分别存储到 1024 个小文件中。这样，每个小文件最多包含 4MB 个 IP 地址；
- 对于每一个小文件，可以构建一个 IP 为 key，出现次数为 value 的 Hash map，同时记录当前出现次数最多的那个 IP 地址；
- 可以得到 1024 个小文件中的出现次数最多的 IP，再依据常规的排序算法得到总体上出现次数最多的 IP；
Top K 问题详解
# DAY5
一、【单选】使用 SQL 语句进行分组检索时，为了去掉不满足条件的分组，应当:
a. 使用 WHERE 子句
b. 在 GROUP BY 后面使用 HAVING 子句
c. 先使用 WHERE 子句，再使用 HAVING 子句
d. 先使用 HAVING 子句，再使用 WHERE 子句
答案 & 解析：
c；
having 是对分组统计结果进行筛选，where 是对基础数据进行筛选。
为什么没有选 b：
这个与 sql 执行过程有关，where 在最开始发挥作用，having 对 group by 之后的结果发挥作用，所以选择尽量前置，降低 group by 等阶段的操作数据量。
b 的意思是把 where 的选择放到 having 里，所以相当于所有选择都后置了。
# DAY6
略.
# DAY7
一、【多选】下面关于 HTTP1.x 的性能优化方式，正确的有：
a. 对域名进行分片，使得客户端可以创建更多的 TCP 连接提高请求并发度
b. 设置 Connection: Keep-Alive Header 保持长连接，减少 TCP 连接握手的开销
c. 利用 ServerPush 将页面上的关键静态资源直接推送到客户端，无需等待客户端请求
d. 将小的静态资源直接嵌入到页面中，减少 HTTP 请求次数
答案 & 解析：
a，b，d；
ServerPush 为 HTTP2 协议才具备的能力，无法应用在 HTTP1.x 的优化中。
二、时间复杂度 O (nlogn) 空间复杂度 O (1) (非递归) 的限制下从单链表中找出第 K 大的节点 。
答案 & 解析：
快排思路的逆向，快排递归思路是对序列持续拆成两个子序列处理，逆向过程就是每 2 个相邻的元素做合并排序，然后每相邻 4 个相邻的元素合并排序（因为之前一轮已经使这 4 个元素由两个长度为 2 的子序列构成），然后 8 个，16 个，直到覆盖整个原始序列。
# DAY8
一、【单选】以下描述正确的是：
a. 表达式和运算符都是执行计划的组成部分。
b. 在火山模型中，执行计划子节点对应的运算符执行完成后，父节点对应的运算符才能开始执行。
c. 排序算法仅仅在 Sort 运算符中使用。
d. 当使用 Index Scan 的时候，任何情况下都需要再回表读取数据。
答案 & 解析：
a； 在火山模型中，很多情况下执行计划子节点和父节点的运算符是同时执行的。排序算法也可以在 Join，Aggregation 等运算符中使用。Index Scan 如果能够覆盖所有的查询字段，不需要再回表读取数据。
二、某应用需要一个可靠的审核管道，为大量用户提供文章的审核入口，并对接了专业的文章审核团队，请为该管道设计一个数据结构。【实现一个并发安全的环形队列】
要求：
- 因为审核团队的人力有限，管道要起到流量控制作用，满了之后文章无法提交审核
- 高峰期时，多篇文章同时送审的事情常有发生，审核团队的多位同学也可能同时审核文章
- 先提交送审的文章应先被审核
- 进入审核管道的文章不能遗失、重复
- 每天有大量的文章送审，要尽可能节省审核管道的开销
答案 & 解析：
首先，提炼题目要求：实现一个并发安全的环形队列，进阶 / 加分项是可以无锁；
然后，并发安全的环形队列的实现是相对比较简单的，主要考察数组的下标操作和边界情况的考虑；
最后，无锁主要有两个思路，考察操作系统 / 体系结构的基础是否扎实、是否具备较好的高性能并发编程思维：
- 内存屏障 / 内存格栅：操作系统未开放 API，对于 C/C++ 语言可以使用编译器的支持来实现，参考 DPDP rte_ring 等。
- 原子操作：C/C++/Java/Go/Rust 等语言都有支持，相对于内存屏障是更佳的选择。
