本文仅作为技术分享，希望大家都能够拥有锻炼的自由，但不鼓励使用技术进行跑步打卡

针对北大的校园体育课跑步打卡，已经有如PKUNoRun这样的开源项目，但是PKUNoRun仅仅支持安卓平台的PKURunner用户，使用如乐动力等其他软件作为打卡方式的并不能很方便的使用。

本文采取的思路为进行GPS定位模拟，从而实际生成跑步轨迹。这种方法的优缺点如下：

• 优点
  • 操作简单，不需要针对APP进行分析和逆向
  • 通用，可以适用于各种打卡平台和系统
• 缺点
  • 耗时，需要挂机等同于跑步本身的时间

网络上已有的大多数教程普遍基于Xcode进行实现，但是由于Xcode版本更新以及使用存在门槛，很多开源教程的方法存在过时的问题。这里采用开源工具LocationSimulator进行GPS模拟定位，比使用Xcode更加用户友好。关于LocationSimulator的具体安装以及使用可以参考GitHub上的项目主页，总体使用方法即使用数据线连接手机，选中已连接的设备，之后便可以通过GPX文件或者手动控制的方式进行GPS模拟了。

在完成软件安装之后，则需要确定对应的打卡地点的经纬度坐标，可以考虑直接在LocationSimulator结合手机地图软件进行标点，来确定对应位置的经纬度，也可以考虑使用google地图等别的方式。在操场跑道一圈标上足够多的点之后，可以考虑利用经纬度坐标加上轻微的随机化来生成跑步轨迹对应的GPX文件。

以北京大学五四操场作为打卡地点违例，在确定操场一圈的经纬度坐标之后，便可以采用以下代码进行GPX文件的生成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import random

print("<?xml version=\"1.0\"?>\n<gpx version=\"1.1\" creator=\"Xcode\">\n")

points = [[39.98670783215012, 116.30664405734012],
          [39.98618352533768, 116.30672865002087],
          [39.98618352533768, 116.30672865002087],
          [39.98581016760418, 116.30678898677019],
          [39.98571908922798, 116.30689433671324],
          [39.98561288688673, 116.30708452367374],
          [39.98565674006142, 116.30742482197985],
          [39.98570648307997, 116.30754884871082],
          [39.98581008421271, 116.30760844737627],
          [39.98630069330874, 116.30760921192963],
          [39.98680940636073, 116.30751827280433],
          [39.98691331279552, 116.30743465659333],
          [39.98701527533597, 116.30723729348047],
          [39.98702174059007, 116.30706010182425],
          [39.98697385542131, 116.30689805739706],
          [39.98687734879176, 116.30675655334059]]

for round in range(100):
    for lat, lon in points:
        print("    <wpt lat=\"{}\" lon=\"{}\"></wpt>\n".format(
            lat + random.random() * 0.00005, lon + random.random() * 0.00005))

print("</gpx>")

之后直接运行Python脚本，将标准输出流重定向到文件，即可得到对应的GPX文件。

1

python gen_gpx.py > circle.gpx

在LocationSimulator通过File -> Open GPX File导入GPX文件，此时GPS坐标就已经在操场上进行规律的运动了。在这个时候打开手机上对应的打卡软件便可以足不出户进行跑步打卡了，同时通过在Walk和Cycle模式当中切换可以调节跑步速度，使得最终的平均速度在打卡范围之内。

P.S.

1. 为保持LocationSimulator可以持续地对GPS定位进行修改，推荐保持电脑/手机屏幕常亮，避免锁屏。

2. 由于连接有切断风险，所以LocationSimulator默认在断开链接之后仍然保持虚拟GPS，每次使用完记得点击左上角的X进行退出。

这是关于Optiver Trivia Night的记录（主要关于最开始的Quiz部分），最开始部分为一个大约30min的Quiz，之后为Optiver实习项目相关的介绍和答疑。其中Optiver是一家全球顶级的做市商，具体信息可以参见官网。

Quiz部分的得分与正确率和答题速度相关，在大家都答对题目的情况下，答题更快的可以获得更高的得分。

第一名可以获得Optiver的终面机会，前五名获得AirPods。

题目总量为四十道，总共用时30min，总共分为几类问题：

• Quick Math (5s) - 基本的数学运算，难度大概在三位数加减法和两位数乘法的水平，重点可能在于时间限制较为紧迫
• Fun Facts (20s) - 询问一些现实生活当中的数字，考察量级估计和现场搜索的能力
• Find Pattern (30s) - 图形找规律，填写下一项是什么
• Easy Brain Teasers (30s) - 较为简单，基本上是基本数学直觉的考察
• Sequence (60s) - 数列找规律，填写下一项是什么
• Medium Brain Teasers (60s) - 普通的概率问题
• Hard Brain Teasers (120s) - 较复杂一些的概率问题

最后排名为Rank 25/150，感觉如果有一定的面试准备的话应该进前十问题不是很大。大部分题目并不会很难，提供足够的时间都能够做的出来，只是在Quiz的情况下会有很强的时间紧迫感。

以下是一部分的题目记录，其中由于Quick Math部分时间过于紧张，所以基本上没有保存到截图。

部分Fun Facts可能会随着时间改变，这里的结果以2021年9月作为参考

No. 7 (Hard Brain Teasers)

10个人围成一个圈。每个人可以拍一拍左侧或者右侧的人，请问被拍的人的个数的期望是多少？

1. 2.5
2. 5
3. 7.5
4. 8.36

Answer: C

No. 12 (Sequence)

$2,3,7,16,65,?$

序列的下一个数字是什么?

1. 321
2. 81
3. 122
4. 179

No. 13 (Fun Facts)

以下最接近沪深市场一天的流通量的量级的是（以RMB计价）？

1. 10b/day (一百亿)
2. 100b/day (一千亿)
3. 1t/day (一万亿)
4. 10t/day (十万亿)

Answer: C

No. 14 (Sequence)

$15,29,56,108,208,?$

序列的下一个数字是什么?

1. 400
2. 416
3. 438
4. 386

No. 15 (Fun Facts)

世界上最重的猪有多重

1. 1157kg
2. 1312kg
3. 694kg
4. 866kg

No.16 (Hard Brain Teasers)

有5封不同的信来自5个不同的人。如果我们随机分发信件，没有一个人收到Ta自己的信的概率是多少？

1. 4/5
2. 11/30
3. 7/20
4. 5/12

Answer: B

No. 17 (Medium Brain Teasers)

地上有一个10cm * 10cm的无限大网格，你随机扔一枚直径为1cm的硬币。问硬币碰到网格线上的概率是多少？

1. 50%
2. 25%
3. 19%
4. 11%

Answer: C

No. 18 (Find Pattern)

Answer: A

No. 19 (Medium Brain Teasers)

红色柱体的高度是多少？

1. 8
2. 10
3. 20/3
4. 15

No. 21 (Easy Brain Teasers)

下列的哪一个不是素数？

1. 257
2. 289
3. 157
4. 349

No. 22 (Medium Brain Teasers)

你有机会可以对数字1~6进行下注，投掷三个骰子。如果你选择的数字出现一次，你获得$1；如果两次，你获得$2；如果三次，你获得$3。你所获得金额的期望是多少？

1. $0
2. $0.5
3. $1
4. $1/3

Answer: B

No. 23 (Fun Facts)

哪一个整数区间当中包含最多的素数？

1. [1, 100]
2. [101, 200]
3. [201, 300]
4. [301, 400]

Answer: A

No. 24 (Hard Brain Teasers)

$(1+\sqrt{2})^{3000}$小数点后第$100$位的数字是多少？

提示：$(1+\sqrt{2})^{3000} + (1-\sqrt{2})^{3000}$ 是一个整数

1. 0
2. 1
3. 4
4. 9

Answer: D

No. 25 (Medium Brain Teasers)

你站在地球的表面上，你往南走1英里，往西走1英里，往北走1英里，最后你停留在了你开始的地方。地球上有多少点可以让你完成以上的行为？

1. 0
2. 1
3. 2
4. 无穷多个

Answer: D

No. 26 (Sequence)

$91,85,94,83,97,81,?,79$

序列的下一个数字是什么?

1. 80
2. 100
3. 102
4. 95

Answer: B

No. 27 (Hard Brain Teasers)

考虑一个平面上的5个点，在所有的点之间两两连线，你拥有了x条直线。那么以下哪个不可能是x的值？

1. 5
2. 6
3. 7
4. 8

Answer: C

No. 28 (Easy Brain Teasers)

一个立方体的面、棱、顶点数的总和是多少？

1. 26
2. 28
3. 30
4. 24

No. 29 (Sequence)

$99,18,36,9,18$

序列的下一个数字是什么?

1. 36
2. 27
3. 9
4. 3

Answer: C

No. 31 (Fun Facts)

一个标准的奥林匹克游泳池(25m * 50m * 2m) 有多少升水？

1. 250
2. 25000
3. 2500000
4. 250000000

No. 34 (Hard Brain Teasers)

一个密码只能以字母而不能以数字开头，那么po88p881有多少种排列可以是密码？

1. 315
2. 420
3. 525
4. 840

No. 35 (Fun Facts)

火星的平均温度是多少？

1. -100°C
2. -60°C
3. -20°C
4. 20°C

No. 36 (Medium Brain Teasers)

考虑一个时钟，一天当中时针和分针会重合多少次？

1. 22
2. 23
3. 24
4. 26

Answer: A

No. 37 (Easy Brain Teasers)

如果下列命题有正确的话，哪一个命题是正确的？

1. 在列表中至少有1个命题是错误的
2. 在列表中至少有2个命题是错误的
3. 在列表中至少有3个命题是错误的
4. 在列表中至少有4个命题是错误的

No. 38 (Sequence)

$-3,3,27,69,129,?$

序列的下一个数字是什么?

1. 178
2. 207
3. 312
4. 268

No. 39 (Find Pattern)

Answer: B

No. 40 (Hard Brain Teasers)

一个国际象棋棋盘的每个小正方形边长都为2。请问在棋盘上作一个圆，能够使得整个圆的圆周都在黑色方形内部的最大的圆半径为多少？

1. Sqrt(2)
2. 2
3. Sqrt(10)
4. Sqrt(34)

Answer: C

所谓的72规则是一个用来在已知年化收益的情况下，估计投入资金实现翻倍需要年数的估算公式，公式表示如下：

$\text{Years to Double} = \frac{72}{\text{Interest Rate}}$

首先通过homebrew安装rustup管理工具：

1

$ brew install rustup

安装完后发现并不能够找到rustup指令，通过brew list进行查询，发现实际上安装的为rustup-init，于是再在命令行执行：

1

$ rustup-init

顺着流程安装完成之后，重启终端便可以安装好rust环境以及相关的工具链。

可以查看对应rustc以及cargo的版本：

1
2

$ rustc --version
rustc 1.53.0 (53cb7b09b 2021-06-17)

1
2

$ cargo --version
cargo 1.53.0 (4369396ce 2021-04-27)

简单的创建一个rust语言版的Hello World进行测试：

1
2
3

fn main() {
    println!("Hello World!");
}

将其保存为hello.rs。

在命令行使用rustc将其编译为可执行文件：

1

$ rustc hello.rs

之后直接执行可执行文件，便可以在终端看到对应的输出了！

1
2

$ ./hello
Hello World!

Bob和Alice被邀请参加一个卡牌游戏。庄家从一组扑克牌（4种花色，A-K）给Bob随机发放5张。Bob可以选择其中4张给Alice看，然后Alice被要求猜测Bob手中剩下的一张牌的花色和点数。

问：

Bob和Alice能否仅仅根据牌的花色和点数设计出一个策略，使得无论Bob拿到的是哪五张牌，Alice都能成功猜测出最后一张牌的花色和点数。

$13 = 2 * 3! + 1$

有人直接给出了这么一个式子，感觉思考思考还是很有意思的。

首先两个重要前提，一个在于Bob可以自由选择翻牌的顺序，另一个就是可以选择让Alice猜哪一张牌。

而确定一张牌需要花色加上点数。

首先是花色，花色由于抽屉原理，一定会有两张相同花色的牌。那么可以将一张牌当作被猜的牌，另一张被第一个翻出，当作花色指示牌。

对于点数而言，剩下三张牌可以考虑预先对于花色和点数的组合大小进行一个定义，那么三张不同的牌一共涉及$3!=6$种排列方式，而$13$张牌A-K排成一个圆周，每一张牌到剩下十二张牌的距离都在$6$以内（顺时针或逆时针）。于是可以预先定义顺/逆时针，然后以第一张标示牌沿顺/逆时针走$k$格。$k$为之后三张牌组合出来对应的数字，由于Bob拥有一定的自主选择权，可以通过对调第一张牌和最后一张牌的方式来确保一定是可达的。

此时再回头看最开始的那个式子，只用一个公式描述清楚了整个状态，非常精妙！

涉及时间序列的数据当中常常会碰到需要将其转换成一个个滑动窗口来构造对应训练数据的场景，PyTorch里面提供了torch.Tensor.unfold()方法可以直接完成操作。

接受的三个参数依次如下：

• dimension (int) – unfold操作所作用的维度
• size (int) – 滑动窗口的窗口大小
• step (int) – 滑动窗口的步长

以下为使用的样例：

1
2
3
4
5
6
7
8
9
10

>>> x = torch.arange(1., 8)
>>> x
tensor([ 1.,  2.,  3.,  4.,  5.,  6.,  7.])
>>> x.unfold(0, 2, 1)
tensor([[ 1.,  2.],
        [ 2.,  3.],
        [ 3.,  4.],
        [ 4.,  5.],
        [ 5.,  6.],
        [ 6.,  7.]])

写在前面

希望在寒假加上开学前两周自学完MIT 6.824课程，这个是MIT分布式系统的博士课程，应该也是分布式系统入门的神课。

采用的材料是2020Spring学期的材料，如果没有弃坑的话，对应的Lab解答都会同步更新到博客里面。

课程主页：http://nil.csail.mit.edu/6.824/2020/schedule.html

个人代码Repo：https://github.com/Phimos/6.824-2020Spring

实现过程

Lab1的主要任务就是通过Golang来实现一个MapReduce的算法，具体的内容可以从Lab1的官方文档中获取。

首先定义任务的类型，具体如下，最关键的就是对应的类型/状态/编号。同时利用MapFile和ReduceFiles字段来提供对应任务的输入。

1
2
3
4
5
6
7
8
9
10
11

type MapReduceTask struct {
	TaskType   string // Map / Reduce / Wait
	TaskStatus string // Unassigned / Assigned / Finished
	TaskNum    int

	MapFile     string   // Input of Map task
	ReduceFiles []string // Input of Reduce task

	NumReduce int
	NumMap    int
}

之后定义RPC相关的参数和返回值，对于请求有两种，当是finish情况时，需要提供对应的Task字段便于修改Master里面的人物状态。

1
2
3
4
5
6
7
8
9
10

// Args for RPC
type MapReduceArgs struct {
	MessageType string // request / finish
	Task        MapReduceTask
}

// Reply for RPC
type MapReduceReply struct {
	Task MapReduceTask
}

对于Master的类型，实际上最关键的只有MapTasks、ReduceTasks以及mu三项，用来存储所有任务的状态。剩下的字段其实都可以根据任务的信息来进行统计，只是处于方便进行监测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

type Master struct {
	// Your definitions here.
	NumMap            int
	NumMapFinished    int
	NumReduce         int
	NumReduceFinished int
	mu                sync.Mutex

	MapTasks    []MapReduceTask
	ReduceTasks []MapReduceTask

	MapFinish    bool
	ReduceFinish bool
}

之后就根据Lab文档当中所给的Hints来梳理整个Lab1的内容。

One way to get started is to modify mr/worker.go’s Worker() to send an RPC to the master asking for a task. Then modify the master to respond with the file name of an as-yet-unstarted map task. Then modify the worker to read that file and call the application Map function, as in mrsequential.go.

Worker()当中仿照样例里面的内容发送RPC请求，结果分为三类执行对应的Map 、Reduce、 Wait三类任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func Worker(mapf func(string, string) []KeyValue,
	reducef func(string, []string) string) {

	// Your worker implementation here.
	for {
		args := MapReduceArgs{MessageType: "request"}
		reply := MapReduceReply{}

		resp := call("Master.MapReduceHandler", &args, &reply)

		if !resp {
			break
		}

		switch reply.Task.TaskType {
		case "Map":
			mapTask(mapf, reply.Task)
		case "Reduce":
			reduceTask(reducef, reply.Task)
		case "Wait":
			waitTask()
		}
	}
}

对于Map的任务，主体部分直接参考mrsequential.go当中的代码，这里只需要从得到的task里面获取输入，并且修改对应的输出内容即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func mapTask(mapf func(string, string) []KeyValue, task MapReduceTask) {
	filename := task.MapFile

	file, err := os.Open(filename)
	if err != nil {
		log.Fatalf("cannot open %v", filename)
	}
	content, err := ioutil.ReadAll(file)
	if err != nil {
		log.Fatalf("cannot read %v", filename)
	}
	file.Close()

	kva := mapf(filename, string(content))

	kvaa := make([][]KeyValue, task.NumReduce)
	for _, kv := range kva {
		idx := ihash(kv.Key) % task.NumReduce
		kvaa[idx] = append(kvaa[idx], kv)
	}

	for i := 0; i < task.NumReduce; i++ {
		storeIntermediateFile(kvaa[i], intermediateFilename(task.TaskNum, i))
	}

	defer finishTask(task)
}

The application Map and Reduce functions are loaded at run-time using the Go plugin package, from files whose names end in .so.

这边的话是通过.so文件来直接获取用于Map和Reduce过程的具体函数，包括最终进行test的脚本文件也是通过加载不同的.so来实现不同的测试效果，例如对crash情况的模拟。以下是worker.go中的对应的内容，直接通过已有的loadPlugin()进行加载就可以了。

1
2
3
4
5
6
7
8
9
10

func main() {
	if len(os.Args) != 2 {
		fmt.Fprintf(os.Stderr, "Usage: mrworker xxx.so\n")
		os.Exit(1)
	}

	mapf, reducef := loadPlugin(os.Args[1])

	mr.Worker(mapf, reducef)
}

If you change anything in the mr/ directory, you will probably have to re-build any MapReduce plugins you use, with something like go build -buildmode=plugin ../mrapps/wc.go

**这里每次都要重新build！**不然直接会出错，一开始没有注意到检查了挺久。

This lab relies on the workers sharing a file system. That’s straightforward when all workers run on the same machine, but would require a global filesystem like GFS if the workers ran on different machines.

由于是在同一台机器上去实现这样一个分布式的MapReduce方法，对文件系统实际上进行了一定程度的简化。

A reasonable naming convention for intermediate files is mr-X-Y, where X is the Map task number, and Y is the reduce task number.

这边利用一个函数来规范化对应N x M个中间文件的命名，具体的命名方式采用如上的mr-X-Y格式。

1
2
3

func intermediateFilename(numMapTask int, numReduceTask int) string {
	return fmt.Sprintf("mr-%v-%v", numMapTask, numReduceTask)
}

The worker’s map task code will need a way to store intermediate key/value pairs in files in a way that can be correctly read back during reduce tasks. One possibility is to use Go’s encoding/json package. To write key/value pairs to a JSON file:

1 2 3

enc := json.NewEncoder(file) for _, kv := ... { err := enc.Encode(&kv)

and to read such a file back:

1 2 3 4 5 6 7 8

dec := json.NewDecoder(file) for { var kv KeyValue if err := dec.Decode(&kv); err != nil { break } kva = append(kva, kv) }

正如在上面所提到的，利用encoding/json对于中间结果进行存取，只需要对于以上的代码进行简单修改即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func storeIntermediateFile(kva []KeyValue, filename string) {
	file, err := os.Create(filename)
	defer file.Close()

	if err != nil {
		log.Fatalf("cannot open %v", filename)
	}
	enc := json.NewEncoder(file)
	if err != nil {
		log.Fatal("cannot create encoder")
	}
	for _, kv := range kva {
		err := enc.Encode(&kv)
		if err != nil {
			log.Fatal("cannot encode")
		}
	}
}

func loadIntermediateFile(filename string) []KeyValue {
	var kva []KeyValue
	file, err := os.Open(filename)
	defer file.Close()

	if err != nil {
		log.Fatalf("cannot open %v", filename)
	}
	dec := json.NewDecoder(file)
	for {
		kv := KeyValue{}
		if err := dec.Decode(&kv); err != nil {
			break
		}
		kva = append(kva, kv)
	}
	return kva
}

The map part of your worker can use the ihash(key) function (in worker.go) to pick the reduce task for a given key.

这是mapTask()当中对应的代码部分，在下面的第5行可以看到，通过ihash(key) % nReduce来得到对应的中间输出文件，进行中间结果的划分。

1
2
3
4
5
6
7
8
9
10
11

kva := mapf(filename, string(content))

kvaa := make([][]KeyValue, task.NumReduce)
for _, kv := range kva {
	idx := ihash(kv.Key) % task.NumReduce
	kvaa[idx] = append(kvaa[idx], kv)
}

for i := 0; i < task.NumReduce; i++ {
	storeIntermediateFile(kvaa[i], intermediateFilename(task.TaskNum, i))
}

You can steal some code from mrsequential.go for reading Map input files, for sorting intermedate key/value pairs between the Map and Reduce, and for storing Reduce output in files.

读书人的事情，能够叫做偷吗

既然说了让抄，那就直接从mrsequential.go里面抄就好了，对应的输入输出需要进行修改，主体部分直接粘贴即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func reduceTask(reducef func(string, []string) string, task MapReduceTask) {
	var intermediate []KeyValue
	for _, filename := range task.ReduceFiles {
		intermediate = append(intermediate, loadIntermediateFile(filename)...)
	}
	sort.Sort(ByKey(intermediate))
	oname := fmt.Sprintf("mr-out-%v", task.TaskNum)
	ofile, _ := os.Create(oname)

	//
	// call Reduce on each distinct key in intermediate[],
	// and print the result to mr-out-0.
	//
	i := 0
	for i < len(intermediate) {
		j := i + 1
		for j < len(intermediate) && intermediate[j].Key == intermediate[i].Key {
			j++
		}
		values := []string{}
		for k := i; k < j; k++ {
			values = append(values, intermediate[k].Value)
		}
		output := reducef(intermediate[i].Key, values)

		// this is the correct format for each line of Reduce output.
		fmt.Fprintf(ofile, "%v %v\n", intermediate[i].Key, output)

		i = j
	}

	ofile.Close()

	defer finishTask(task)
}

The master, as an RPC server, will be concurrent; don’t forget to lock shared data.

这里需要上锁的是Master，防止多个Worker进行同时的修改，我这里采用了一个非常暴力的大锁，在MapReduceHandler()的最开始对Master上锁，然后利用defer在函数退出之后进行锁的释放，保证每次只有一个MapReduceHandler()对Master当中的结构进行修改，确保对并发可以正确处理。

1
2
3
4
5
6
7

// Your code here -- RPC handlers for the worker to call.
func (m *Master) MapReduceHandler(args *MapReduceArgs, reply *MapReduceReply) error {
	m.mu.Lock()
	defer m.mu.Unlock()
  ...
}

Use Go’s race detector, with go build -race and go run -race. test-mr.sh has a comment that shows you how to enable the race detector for the tests.

这边是课上所提到的检验race的方法，go语言可以通过对于内存进行监控的情况来查看是否有race发生，但是不会被执行的代码当中的race错误是不会被分析出来的，因为go语言并没有对race进行一个静态的分析。

Workers will sometimes need to wait, e.g. reduces can’t start until the last map has finished. One possibility is for workers to periodically ask the master for work, sleeping with time.Sleep() between each request. Another possibility is for the relevant RPC handler in the master to have a loop that waits, either with time.Sleep() or sync.Cond. Go runs the handler for each RPC in its own thread, so the fact that one handler is waiting won’t prevent the master from processing other RPCs.

暂时还没有新的Task分配的状况，会在Map的任务已经全部分配下去但是还没有全部完成的情况出现。这个时候Master给Worker一个Wait的指令，通过time.Sleep()等待之后再次发送一个申请新任务的RPC请求。

1
2
3

func waitTask() {
	time.Sleep(time.Second)
}

The master can’t reliably distinguish between crashed workers, workers that are alive but have stalled for some reason, and workers that are executing but too slowly to be useful. The best you can do is have the master wait for some amount of time, and then give up and re-issue the task to a different worker. For this lab, have the master wait for ten seconds; after that the master should assume the worker has died (of course, it might not have).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

if args.MessageType == "request" {
	if !m.MapFinish {
		for index, task := range m.MapTasks {
			if task.TaskStatus == "Unassigned" {
				m.MapTasks[index].TaskStatus = "Assigned"
				reply.Task = m.MapTasks[index]
				go m.checkTimeout("Map", index, 10)
				return nil
			}
		}
		reply.Task.TaskType = "Wait"
		return nil
	} else if !m.ReduceFinish {
		for index, task := range m.ReduceTasks {
			if task.TaskStatus == "Unassigned" {
				m.ReduceTasks[index].TaskStatus = "Assigned"
				reply.Task = m.ReduceTasks[index]
				go m.checkTimeout("Reduce", index, 10)
				return nil
			}
		}
		reply.Task.TaskType = "Wait"
		return nil
	} else {
		return nil
	}
}

具体的checkTimeout()实现如下，就是进行一定时间的Sleep，之后检查任务是否完成，如果仍然没有完成处于Assigned状态的话，说明对应的Worker可能已经crash了。于是将其标为Unassigned状态，在之后进行重分配，保证MapReduce流程可以继续运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func (m *Master) checkTimeout(taskType string, num int, timeout int) {
	time.Sleep(time.Second * time.Duration(timeout))
	m.mu.Lock()
	defer m.mu.Unlock()
	if taskType == "Map" {
		if m.MapTasks[num].TaskStatus == "Assigned" {
			m.MapTasks[num].TaskStatus = "Unassigned"
		}
	} else {
		if m.ReduceTasks[num].TaskStatus == "Assigned" {
			m.ReduceTasks[num].TaskStatus = "Unassigned"
		}
	}
}

To test crash recovery, you can use the mrapps/crash.go application plugin. It randomly exits in the Map and Reduce functions.

Test的最后一个部分就是crash test，会使用crash.so文件，事实上，在上面利用一个go routine取检查超时，如果一个worker在工作过程中crash了，那么就无法在最后返回个master一个Finish的RPC。所以利用以上的超时检查机制，是可以简单的对于Lab当中的crash进行正确重分配任务，保证MapReduce流程正常进行。

To ensure that nobody observes partially written files in the presence of crashes, the MapReduce paper mentions the trick of using a temporary file and atomically renaming it once it is completely written. You can use ioutil.TempFile to create a temporary file and os.Rename to atomically rename it.

这边只需要修改对应的输出为TempFile -> Rename的流程就可以，这里就不进行修改了。

test-mr.sh runs all the processes in the sub-directory mr-tmp, so if something goes wrong and you want to look at intermediate or output files, look there.

执行sh test-mr.sh的结果如下所示，可以发现对于Lab1的所有测试都完全通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

*** Starting wc test.
2021/02/03 16:24:03 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- wc test: PASS
*** Starting indexer test.
2021/02/03 16:24:09 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- indexer test: PASS
*** Starting map parallelism test.
2021/02/03 16:24:12 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- map parallelism test: PASS
*** Starting reduce parallelism test.
2021/02/03 16:24:20 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- reduce parallelism test: PASS
*** Starting crash test.
2021/02/03 16:24:28 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- crash test: PASS
*** PASSED ALL TESTS

体验

• Golang上手的感觉还行，感觉和C语言差别不大，有C语言的基础熟悉一下语言特性应该就可以上手。
• 难度一般，可能是Lab1的缘故，总体实现上困难不是很大。
• 从文档和代码上看，整个Lab的结构上感觉没有6.828课程的巧妙，但是已经非常完备了，远超国内学校课程作业的实用程度。

2020

有所得

有所失

面试完全没有提到跟简历有关的内容，基本就是问智力题，感觉答得非常一般。

最终面试结果为未通过。

1. （博弈论）ABC三家公司，在0-100的101个整数点上都存在住户，按照ABC的顺序每个人依次选择1-100当中的一个位置作为公司的办公地点，住户会选择离他最近的公司。为了最大化收益（最大化到自己公司的用户数量），A的最优选择是什么？

就是一个博弈论的问题，应该算Best Response逐层上推就好了，当时面试只讲了思路，没有算出来。

2. 有$N$个序列，每个序列有3个数字，任意两组之间的correlation都小于0.7，问$N$可能的最大取值是多少。

将其转变成一个三维的单位球，问求表面能够取多少向量，两两之间夹角的余弦值小于0.7。可以通过用正三角形的构造方法，来利用立体角构造上界。但并不知道怎么计算准确值，当时面试官说可以计算出准确的结果。

3. 一个没有记忆功能科学计算器，加减乘除和数字键都坏了，可以采用类似三角函数，取倒数，对数，开方，阶乘等操作。最开始只有一个0，如何得到任意整数？如何得到任意有理数？

本质是利用直角边为$\sqrt{n}$和$1$的直角三角形。

首先通过取$\cos$得到$1$，然后依次采用$\arctan$，$\cos$，取倒数，平方，就可以得到$2$。开方之后再次通过以上流程就可以得到$3$，依次类推可以得到任意整数。

对于任意有理数，实际上要可以得到任意的$\frac{m}{n}$，由上面的流程，我们可以在知道$r$的情况下，得到$r+1$，同时可以得到任意的$\frac{1}{n}$。

那么对于任意的$\frac{m}{n}$，总是用大的减去小的，就可以最终化成一个$\frac{1}{k}$的形式，这个是可以得到的，之后再反复利用倒数和$+1$的操作反推回去，就可以得到任意有理数了。

4. 笔试当中提到的，最奇怪的交易股票的策略。

CQ资产的笔试题目，笔试时间为40分钟，题量为9道。总体感觉笔试难度适中，时间有一点紧。由于笔试题目本身为英文，这里不做额外的翻译，解答为笔者所做，可能存在错误。

个人笔试结果为通过。

1. Given the following function definition: (4 min, score = 3)

   1 2 3 4 5

   Define f(x): result = 1 For i from 1 to x (inclusively): result = result + i return result

   How many additions will take place while evaluating f(f(f(3)))?

Solution:

$\begin{aligned} f(x) &= 1 + ( 1+ \ldots+x) \\ &=1 + \frac{x(1+x)}{2} \\ &= \frac{x^2 + x + 2}{2} \end{aligned}$

Total additions:$3+f(3) + f(f(3)) = 3+7+29=39$.

2. A stock’s price fluctuates every day by going up exactly 5% or going down exactly 5%. Assume that each direction is equally likely. Assume zero trading cost, zero interest rate, and no dividends and splits. What strategy is most likely to be profitable after 100 days?
   (3 min, score = 3)

   A. Buy or sell will produce same profitable

   B. Cannot know / no strategy can be profitable

   C. Buy the stock

   D. Sell the stock

Solution:

D

3. Below is a list of asymptotic complexities of 8 functions, each with length N input:

   1. O(N^3)

   2. O(Log(N))

   3. O(Sqrt(N))

   4. O(N * log(N))

   5. O(2^N)

   6. O(N^N)

   7. O(N!)

   8. O(Log(Log(N)))

   Please sort the functions by order of growth, with slower growing functions first. (your answer shall be a sequence of letters, for example “BACDFHGE􏰀”)
   (4 min, score = 3)

Solution:

HBDCAEGF

4. What is the maximum possible variance of a random variable taking values in the interval [0, 10]?
   (2 min, score = 2)

Solution:

Half is $0$, half is $10$.

$Var(x) = E[X-E(X)]^2 = 5^2 = 25$

5. How many integers $n$ such that $n^n$ is a perfect square are there in range [100: 400]?
   (5 min, score = 4)

Solution:

If $n$ is even, $n = 2k$, then $\sqrt{n^n} = \sqrt{n^{2k}} = n^k$, so it’s a perfect square.

If $n$ is odd, $n = 2k+1$, then $\sqrt{n^n} = \sqrt{n^{2k+1}} = n^k\sqrt{n}$, it’s a perfect square if and only if $n$ is a perfect square.

We have:

$10^2 = 100 \qquad 20^2 = 400$

So there are 5 odds that meet the condition, $11^2,13^2,\ldots,19^2$.

Totally, $151 + 5 = 156$ integers.

6. Assume there are three random variables $X, Y, Z$. All pairwise correlations are equal: $corr (x,y)=corr(y,z)=corr(x,z) = r$. What is the range of possible values of $r$? (list a range, like $[-0.3:0.7]$, for example)
   (6 min, score = 12)

Solution:

$\begin{aligned} \left|\begin{array}{cccc} 1 & r & r \\ r & 1 & r\\ r & r & 1 \end{array}\right| &= 1 -r^2 + r(r^2-r) + r(r^2 - r) \\ &= 2r^3 - 3r^2 + 1 \\ &= (r - 1)^2 (2r+1)\ge 0 \end{aligned}$

So the range of possible values of $r$ is $[-1/2, 1]$.

7. Assume there are three random variables $X, Y, Z$. We would like to use one number to describe their relations, just like the pairwise correlation of 2 variables $corr(x,y)$. We need the number to be normalized. Please list the possible mathematical formulas to calculate such number, the more the better.
   (6 min, score = 12)

Solution:

$\frac{corr(x,y) + corr(y, z) + corr(x, z)}{3}$

8. Triangle ABC has sides of length 45, 60 and 75. A point $X$ is placed randomly and uniformly inside the triangle. What is the expected value of the sum of perpendicular distance from point X to this triangle’s three sides?
   (9 min, score = 10)

Solution:

$45^2 + 60^2 = 75^2$

It’s easy to know, triangle ABC is a right triangle.

$\begin{aligned} E[l]&=15 * \frac{1}{6}\int_0^4\int_0^{(12-3x)/4} \left(x+y+\frac{12-3x-4y}{5}\right) dydx \\ &= 15 * \frac{1}{6}\int_0^4\int_0^{(12-3x)/4} \left(\frac{12}{5}+\frac{2x}{5}+\frac{y}{5}\right) dydx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{12+2x}{5} \frac{12-3x}{4}+\frac{1}{10}(\frac{12-3x}{4})^2\right)dx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{3}{10}(24-2x-x^2)+\frac{1}{10}\frac{9}{16}(16-8x+x^2)\right)dx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{81}{10} - \frac{21}{20}x -\frac{39}{160}x^2 \right)dx \\ &= 15 * \frac{1}{6}\left(\frac{81}{10} * 4 - \frac{21}{20}*\frac{4^2}{2} -\frac{39}{160}*\frac{4^3}{3}\right) \\ &= 15 * 1/6 * 18.8 \\ &= 47 \end{aligned}$

9. Please list one of your most “strange” or “crazy” idea to predict stock’s return. You can assume you have all available public data and strong computing power. The answer shall be as “strange” as possible.
   (6 min, score = 10)

Solution:

Use the stock code to select stocks. If the stock code is a prime number, buy it and hold. The strategy is pretty strange because there should be no useful information in the stock code.