字节青训营 | 刷题打卡活动

DAY 1

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

a. 变量
b. 函数
c. 类型
d. 包

答案&解析

a，b

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

二、假如在抖音中发布视频时，可以选择带上位置信息，请设计一种数据结构或方案，用于存储检索位置信息（简化为平面坐标 x, y），以实现搜索附近视频的功能（如附近 3km）。

答案&解析

方法一：geohash：把二维问题降为一维

如坐标（示例非标准 geohash，只是演示了思想）：

(12, 345) -> (012, 345) -> “031425”

(13, 348) -> (013, 348) -> “031438”

(2, 789) -> (002, 789) -> “070829”

最终做字符串前缀匹配，可得 “031425” 和 “031438” 匹配到的位数最多，二者距离最近。求 3km 内的坐标，只需提前算出需匹配前几位即可，如匹配前 4 位，按 sql 表达是 LIKE ‘0314%’

方法二：变通距离为方圆 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 2

一、【多选】下列关于Join 运算不正确的是：

a、Nested Loop Join 不能使用索引做优化。
b、如果左表太大，不能放入内存中，则不能使用 Hash Join。
c、如果 Join 的一个输入表在 Join Key 上有序，则一定会使用 Sort Merge Join。
d、Broadcast Join 适用于一张表很小，另一张表很大的场景。

答案&解析

Nested Loop Join 可以使用索引优化（Index Nested Loop Join）；

如果左表太大，不能放入内存，可以先对量表做分区，再对每个分区做 Hash Join （Parititioned Hash Join）；

如果Join的一个输入表在Join Key上有序，也可以 Hash Join，具体使用哪种 Join 方式取决于优化器的代价估计结果。

二、给定一个正整数数组 arrs 和整数 K ，请找出该数组内乘积小于等于 k 的连续的子数组的个数，算法时间复杂度o(n)。

答案

package main

import "fmt"

func main() {
	var n int
	var k int
	fmt.Scanf("%d%d", &n, &k)
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &nums[i])
	}
	if k == 0 || k == 1 {
		return
	}
	l, r := 0, 0	// 左右指针
	cur := 1
	ans := 0
	for r < len(nums) {
		cur *= nums[r]
		for cur >= k {	// 如果乘了之后会超过k，则l++
			cur /= nums[l]
			l ++
		}
		ans += r - l + 1
		r ++
	}
	fmt.Printf("%d\n", ans)
}

DAY 3

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

a. 单个sector原子写入

b. 单个page原子写入

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

d. 以上都不可以

答案&解析

d；

本题主要考察对于一个数据密集型应用开发者（比如数据库开发者、文件系统开发者），在数据不能出错的前提下，可以依赖磁盘的哪些能力，事实证明几乎有

什么能力可以依赖。

在随时可能断电的情况下，大多数硬件能提供单个sector的原子性写入；但是也有少数硬件连单个sector的写入都无法保证；如果一个page对应多个sector，单

个page的完整写入总是无法得到保障。更加详细的情况可以查看这个讨论：crash - Are disk sector writes atomic?。对于同时发给硬盘的多个操作（比如写多个不

连续的sector），硬盘并不保证操作的顺序。结合其弱原子性，所以硬盘可能处在任何一个中间状态。这主要是由于机械硬盘的寻址优化策略和固态/机械硬盘的缓

存策略导致的。

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

答案

后序递归写法（最优）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var res bool

func isBalanced(root *TreeNode) bool {
    res = true
    dfs(root)
    return res
}

func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := dfs(root.Left)
    right := dfs(root.Right)
    if abs(left - right) > 1 {
        res = false
    }
    return max(left, right) + 1;
}

func abs(x int) int {
    if (x < 0) {
        return -x;
    }
    return x;
}

func max(x int, y int) int {
    if (x > y) {
        return x
    } else {
        return y
    }
}

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队列。

DAY 6

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

a. Python 是强类型语言

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

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

d. CPython 不支持尾递归优化

答案&解析

c；

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

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

答案&解析

package main

import (
	"fmt"
	"sync/atomic"
)

var(
	tasks = []string{
		"task1","task2","task3","task4","task5","task6","task7","task8","task9","task10",
		"task11","task12","task13","task14","task15","task16","task17","task18","task19","task20",
	}
	taskChan = make(chan string,len(tasks))
	opts = int32(len(tasks))
)

func execute(ch chan bool) {
	for {
		if atomic.LoadInt32(&opts) == 0 {
			break
		}
		atomic.AddInt32(&opts, -1)
		fmt.Println(<-taskChan + "被执行了")
		if ch != nil {
			ch <- true
		}
	}
}

func ChannelStart() {
	for _, task := range tasks {
		taskChan <- task
	}
	maxCore := 10
	ch := make(chan bool)
	for i := 0; i < maxCore; i ++ {
		go execute(ch)
	}
	for i := 0; i < maxCore; i ++ {
		<- ch
	}
	close(taskChan)
}

func main() {
	ChannelStart()
}

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 大的节点。

leetcode148，使用归并

DAY 8

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

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

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

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

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

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

要求：

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

杂烩

#字节跳动 #青训营

字节青训营 | 刷题打卡活动

https://2w1nd.github.io/2022/04/13/杂烩/字节青训营-刷题打卡活动/

作者

w1nd

发布于

2022年4月13日

许可协议

6.824 Lab1：MapReduce 上一篇

Project4：Concurrency Control 下一篇