CSAPP 8 异常控制流（ECF）

异常控制流，Exception Control Flow，是操作系统实现IO、进程、虚拟内存、并发等等功能的的重要基础工具。

异常

这里提到的异常不是通常意义的异常，而是分成四类：Interrupt, faults, aborts, and trap.

进程

Python3.10的新特性！

新版本的Python 3.10主要有三个大变化：

• 增加模式匹配
• 更好的错误提示
• 更好的类型检查

结构化模式匹配

模式匹配主要通过mathc和case关键字，具有如下实现方法：

CSAPP 7 连接，Linking

连接是将程序的不同部分（指令和数据）组合成一个二进制文件，该文件可以被读入内存并被CPU执行。连接可以发生在编译时，即程序从源代码转换成机器码的过程中（Static Linking）；也可以发生在装载阶段，即程序被读入内存的阶段（Dynamic Linking）；甚至可以在运行时，即程序已经被读入内存且已经开始执行的时候。

连接器操作的对象被称为目标文件：Relocatable object file, Executable object file, Shared object file。

目标文件的格式是约定俗成的，最常见的是ELF, Executable and Linkable Format。

在C语言中，static 关键字通常用来隐藏变量或者函数。

874. Walking Robot Simulation

• 874. Walking Robot Simulation

这是一个简单，但是设计的很好的面试题。并没有困难的算法，考验的是一个软件工程师能都写出清晰、简洁代码的能力，以及一些细节问题。

问题

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

A robot on an infinite XY-plane starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees,
-1: turn right 90 degrees, or
1 <= k <= 9: move forward k units.
Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi).

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the maximum Euclidean distance that the robot will be from the origin squared (i.e. if the distance is 5, return 25).

Note:

North means +Y direction.
East means +X direction.
South means -Y direction.
West means -X direction.

CSAPP 6 存储的层次

本书之前讨论的模型注重CPU执行程序的过程和方式，而其中内存被当做一个简单的byte array，可以实现O(1)访问。但是，这个内存模型是简化的，实际计算的内存是一个层状模型，每一层都有不同的承载力和访问开销。

Locality

Temporal Locality：一个内存地址如果被引用了一次，那么它很可能在将来还会被引用。Spatial Locality：一个地址如果被引用，那么它周围的地址也能被引用。

现代计算机和操作系统都会做上述假设，如果程序可以满足上述假设，那么程序的运行速度就会提升。

1192. Critical Connections in a Network

• 1192. Critical Connections in a Network
• 797. All Paths From Source to Target

1192. Critical Connections in a Network

问题

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.

Tree层遍历

• 102 Binary Tree Level Order Traversal
• 107 Binary Tree Level Order Traversal II
• 1302. Deepest Leaves Sum
• 637 Average of Levels in Binary Tree

102 Binary Tree Level Order Traversal

题目

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

一个简单的算术 LL(1) Parser

这篇文章探索如何手写一个简单的算术表达式 Parser。

问题

我们要解决的问题是把一个算术表达式字符串转化成语法树（Abstract Syntax Tree，AST），就像通用计算机语言一样，然后evaluate该AST。算术表达式包含：+ - * / ( ) 以及数字。

LL(1) Parsing

回溯，DFS

• 46. Permutations
• 47. Permutations II
• 1466. Reorder Routes to Make All Paths Lead to the City Zero
• 679. 24 Game
• 282. Expression Add Operators

46. Permutations

问题

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Heap（堆）的使用

• 1046. Last Stone Weight
• 703. Kth Largest Element in a Stream
• 1792. Maximum Average Pass Ratio
• 621. Task Schedule

1046. Last Stone Weight

思路

此题比较直接，直接采用heap来维护最重的数值在头部，需要注意的是 Python 的 heap 都是 min heap，所以需要取负数来实现此题。