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，所以需要取负数来实现此题。

Prefix tree

• 208. Implement Trie (Prefix Tree)
• 1032. Stream of Characters
• 336. Palindrome Pairs

这两个题都提到了一种树：Trie，也叫做 prefix tree 或者 digital tree，属于所搜树的一种。通常用于字符串的分段搜索，也可以用来做输入提示，即给出一些字母，搜索后续可用的路径。搜索方式属于 DFS，每个节点可以通过带有一些属性，从而实现其他功能，比如不同的action等等。

第三题呢，乍一看跟 Trie 没关系但是，用 Trie 可以大大提高效率。

第一个题是中等，后两个都是困难题。

CSAPP 4 处理器架构

CPU Pipeline 的基本原理，通过将任务拆解成不同的阶段，并行执行多个任务，增加 throughput，相应的会提高延迟。不过这样可以提高CPU的时钟频率，降低延迟。

这是比指令集更低一个的一个层次，每一个指令集指令都被分解成多个不同的阶段，由对应的硬件分别执行。分解后，为并行提供了可能。

1
2
3

A B C
  A B C
    A B C

Pipeline 的复杂度在于错误处理、每个阶段的延迟等等。

CSAPP 5 程序的优化

优化方式：

• 程序层面
  • loop unrolling
  • 减少内存renference
  • 减少函数调用
  • 分支优化
• 内存优化
  • 读写循环优化

现代CPU都有独立的功能组件进行内存的读取和写入，这些组件通常都有自己的缓存。比如Intel i7处理器的读取单元可以缓存48个读取指令，他们通常可以在一个cycle内完成一个操作。