Frank's blog
Frank
2022-04-21
目录

字节青训营练习

# 链接

Day1 题目：https://juejin.cn/post/7083792721265033229

Day2 题目：https://juejin.cn/post/7084921992264024095

DAY3 题目 ：https://juejin.cn/post/7085289525240397854

DAY4 题目：https://juejin.cn/post/7085918881117634590/

DAY5 题目：https://juejin.cn/post/7086662932397817864/

DAY6 题目：https://juejin.cn/post/7087513378062598158/

DAY7 题目：https://juejin.cn/post/7088152977474584607/

DAY8 题目：https://juejin.cn/post/7088881301989621796/

# DAY 1

# 一、【多选】Golang 通过plugin.(*Plugin).Lookup函数可以查找到插件里面定义的哪些东西？

A. 变量

B. 函数

C. 类型

D. 包

# 答案 & 解析：

A、B；

A和B都是能被赋值给interface{}类型的变量，但是C和D不能。因此Lookup方法返回的结果是一个interface{}类型（Symbol类型）的变量，因此C和D不能通过Lookup返回。

参考Lookup方法的说明： func (p *Plugin) Lookup(symName string) (Symbol, error) Lookup searches for a symbol named symName in plugin p. A symbol is any exported variable or function. It reports an error if the symbol is not found. It is safe for concurrent use by multiple goroutines.

# 二、假如在抖音中发布视频时，可以选择带上位置信息，请设计一种数据结构或方案，用于存储检索位置信息（简化为平面坐标 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%'
  • 方法 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)

# DAY２

# 一、【多选】下列关于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，直到满足需求。

# DAY３

# 一、【多选】绝大多数硬盘可以提供哪些写入保证？

A. 单个sector原子写入

B. 单个page原子写入

C. 硬盘顺序执行文件系统发送的操作

D. 以上都不可以

# 答案 & 解析

D；

本题主要考察对于一个数据密集型应用开发者（比如数据库开发者、文件系统开发者），在数据不能出错的前提下，可以依赖磁盘的哪些能力，事实证明几乎没有什么能力可以依赖。 在随时可能断电的情况下，大多数硬件能提供单个sector的原子性写入；但是也有少数硬件连单个sector的写入都无法保证；如果一个page对应多个sector，则单个page的完整写入总是无法得到保障。更加详细的情况可以查看这个讨论：crash - Are disk sector writes atomic? (opens new window)。 对于同时发给硬盘的多个操作（比如写多个不连续的sector），硬盘并不保证操作的顺序。结合其弱原子性，所以硬盘可能处在任何一个中间状态。这主要是由于机械硬盘的寻址优化策略和固态/机械硬盘的缓存策略导致的。

# 二、判断一棵二叉树是否是平衡二叉树。（平衡二叉树要求：树中节点左右子树树高差不超过1。）

# 答案 & 解析

解法一（常规解法）： 分别求左右子树的深度，再进行判断、递归。（此方法会遍历一个节点多次，效率不高。）

bool IsBalanced_Solution1 (BinaryTreeNode * pRoot )
{
    if ( pRoot == NULL ) return true ;
    int left = TreeDepth ( pRoot->m_pLeft );
    int right = TreeDepth ( pRoot->m_pRight );
    int diff = left - right ;
    if ( diff >1|| diff <-1 ) return false ;
    return IsBalanced_Solution1 ( pRoot - >m_pLeft ) && IsBalanced_Solution1 ( pRoot - >m_pRight );
}
1
2
3
4
5
6
7
8
9

解法二（更高效的解法）： 解决了遍历一个问题多次的问题。用后序遍历的方式遍历二叉树的每一个节点，在遍历到一个节点之前我们就已经遍历了它的左右子树。只要在遍历每个节点的时候记录深度，就可以一边遍历一边判断每个节点是不是平衡的。

bool IsBalanced_Solution2(BinaryTreeNode * pRoot)
{
    int depth =0 ;
    return IsBalanced(pRoot,& depth);
}
bool IsBalanced(BinaryTreeNode * pRoot, int* pDepth)
{
    if (pRoot == NULL)
    {
        *pDepth=0 ;
        return true ;
    }
    int left, right;
    if (IsBalanced(pRoot-> m_pLeft,& left) && IsBalanced(pRoot-> m_pRight,& right))
    {
        int diff = left - right;
        if (diff <=1&& diff>=-1 )
        {
            *pDepth = 1 + (left> right ? left : right);
            return true ;
        }
    }
    return false ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# DAY 4

# 一、【单选】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；

# DAY 5

# 一、【单选】使用 SQL 语句进行分组检索时，为了去掉不满足条件的分组，应当:

a. 使用 WHERE 子句 b. 在 GROUPBY 后面使用 HAVING 子句 c. 先使用 WHERE 子句，再使用 HAVING 子句 d. 先使用 HAVING 子句，再使用 WHERE 子句

# 答案 & 解析

c； having 是对分组统计结果进行筛选，where 是对基础数据进行筛选。

为什么没有选 b： 这个与sql执行过程有关，where 在最开始发挥作用，having对group by之后的结果发挥作用，所以选择尽量前置，降低group by等阶段的操作数据量。 b 的意思是把where的选择放到having里，所以相当于所有选择都后置了。 注意理解题意哟。

# 二、实现一个 key 为字符串，value 也是字符串的，而且并发安全的 map，拥有方法 set(key string, value string)、get(key string) string、del(key string)。

扩展要求1： 字典初始有64个桶，当有一半以上的队列有多个元素时，进行自动扩容，将桶的数量翻倍。 扩展要求2： 当一半以上的队列都为空或只有一个元素，并且这种情况持续1分钟，则自动缩容，最小缩容到64队列。

# 解析

为了满足基础要求，可以实现一个hash map，并且加一个大锁（读写锁或者互斥锁都可以）即可实现；更近一步，可以考虑为每个桶加一把独立的锁，可以实现更小粒度的锁。接下来可以使用go test的banchmark能力去测试下不同读写压力、不同锁粒度、不同类型的锁下的性能对比。

如果为了实现字典的自动扩缩容，则需要实现两个hash map，一个是current hash map，另一个是next hash map。在每次读写中，将current hash map中的几个key迁移到next hash map。在读操作中，先找current hash map，如果key不存在，再找next hash map；在写操作中，会先删除current hash map中这个key，再写入next hash map。随着不断的读写，则会慢慢current hash map会为空，此时将next hash map改成current hash map即可。

这里有几个难点 :

  1. 如何去遍历current hash map，来做迁移？

需要记录上次遍历到的桶和key，以便于下次继续遍历

  1. 如何判断current hash map已经为空了？

记录一下map中key的个数，如果为0了，则说明为空了。可以使用atomic这个库来实现。

  1. 如何判断需要扩容 / 缩容？

也记录一下不为空的桶的数量。

# DAY 6

# 一、【单选】下列关于 Python 的说法错误的是?

A. Python 是强类型语言

B. Python 中所有变量本质上都是指针

C. Python 运行时会根据类型提示(type hints)检查变量类型

D. Python 不支持尾递归优化

# 答案 & 解析

c；

Python 运行时并不会检查变量类型, 类型提示主要给第三方工具使用, 比如IDE可以据此给出方法/属性的自动补全建议。

# 二、给定包含 N 个任务 task 的数组 tasks 和整数 K，和一个可并发调用的执行函数 execute，要求实现以下逻辑：

  1. execute并发调用次数不超过10
  2. 以最快速度执行完所有task
  3. 使用golang
# 答案 & 解析

利用并发 + channel 缓冲区实现。

type Task int

func handle(tasks []Task, execute func(task Task)) {
   wg := sync.WaitGroup{}
   ch := make(chan struct{}, 10)
   for i, _ := range tasks {
      ch <- struct{}{}
      wg.Add(1)
      task := tasks[i]
      go func() {
         defer wg.Done()
         // execute task
         execute(task)
         <-ch
      }()
   }
   wg.Wait()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# DAY 7

# 一、【多选】下面关于 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 个，直到覆盖整个原始序列。

# DAY 8

# 一、【单选】以下描述正确的是：

A. 表达式和运算符都是执行计划的组成部分。

B. 在火山模型中，执行计划子节点对应的运算符执行完成后，父节点对应的运算符才能开始执行。

C. 排序算法仅仅在 Sort 运算符中使用。

D. 当使用 Index Scan 的时候，任何情况下都需要再回表读取数据。

# 答案 & 解析

A；

在火山模型中，很多情况下执行计划子节点和父节点的运算符是同时执行的。排序算法也可以在 Join，Aggregation 等运算符中使用。Index Scan 如果能够覆盖所有的查询字段，不需要再回表读取数据。

# 二、某应用需要一个可靠的审核管道，为大量用户提供文章的审核入口，并对接了专业的文章审核团队，请为该管道设计一个数据结构。【实现一个并发安全的环形队列】

要求：

  • 因为审核团队的人力有限，管道要起到流量控制作用，满了之后文章无法提交审核
  • 高峰期时，多篇文章同时送审的事情常有发生，审核团队的多位同学也可能同时审核文章
  • 先提交送审的文章应先被审核
  • 进入审核管道的文章不能遗失、重复
  • 每天有大量的文章送审，要尽可能节省审核管道的开销
# 解析：

首先，提炼题目要求：实现一个并发安全的环形队列，进阶/加分项是可以无锁； 然后，并发安全的环形队列的实现是相对比较简单的，主要考察数组的下标操作和边界情况的考虑； 最后，无锁主要有两个思路，考察操作系统/体系结构的基础是否扎实、是否具备较好的高性能并发编程思维：

  • 内存屏障/内存格栅：操作系统未开放 API，对于 C/C++ 语言可以使用编译器的支持来实现，参考 DPDP rte_ring 等。
  • 原子操作：C/C++/Java/Go/Rust 等语言都有支持，相对于内存屏障是更佳的选择。

特别注意，基于 Go channel 的实现不是无锁。

# 模拟

【不定项】关于 top 命令给出的指标，以下说法正确的是： D

A. si 表示系统处理硬中断 cpu 占用比例

B. VIRT 代表进程实际使用物理内存量

C. load average 越高说明系统压力越小

D.zombie 进程数量代表已退出待父进程回 收的进程数量

【不定项】在数据库隔离级别中，Read Committed 隔离级别下，不能避免的问题是： BC

A. 脏读

B. 不可重复读

C. 幻读

D. 以上均不会发生

【编程题】Power of 4

描述：输入一个表示整数的字符串，判断这个字符串是否是4的幂。

输入：一个正整数字符串

输出：返回true或false

输入样例 1

4
1

输出样例 1

true
1

输入样例 2

21
1

输出样例 2

false
1

语言:

C

#include <stdio.h>
bool isPowerOfFour(int num) {
    if(num % 4 = 0) {
          return true;
    } else {
          return false;
    }
}
int main() {
   int num;
   scanf("%d", num);
   printf("%s\n", isPowerOfFour(num)?"true":"false");
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

【主观题】聊聊你对短视频发展的看法。

短视频是现代人在碎片时间获取信息的非常重要的渠道，意义非常重大，受众面也很广，因此具有很高的商业价值。目前短视频赛道已经有抖音，快手，微师，微信视频号，小红书等等产品，竞争非常激烈，要想在这个赛道上取得优势，需要在宣发上加大力度，提高对创作者的激励，并通过技术提高使用者的体验。

在Github中编辑 (opens new window)
上次更新: 2024/04/21, 13:07:28
就这几个简单页面APP，这混小子要我10W块？！大家评评理！
Mysql多版本安装

← Mysql多版本安装→

最近更新
01
面试问题套路
04-21
02
Mysql多版本安装
05-28
03
Go语言基础类型
05-04
更多文章>
Theme by Vdoing | Copyright © 2021-2024 Master Frank | 粤ICP备2021148573号
×