Matrix 面试 - 算法&计网篇
开局暴击
算法
面试官给了我一道力扣上的动态规划题，虽然我之前浅浅看过，但没刷过题，一时确实做不出来，然后他换了一道标着“简单”的动规题———经典爬楼梯，still，我还是不会，甚至思路来到了传说中的——递归（逃
直到面试结束后我才一拍脑门，原来递规与动归的区别是前者从后向前推，而后者从前向后推！
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
分析
不难看出，这题就是求一个斐波那契数列，即有
$$
f(n) = f(n-1) + f(n-2)
$$
如果用递归，那么就是从 $f(n)$ 开始向前推，显然，这样的复杂度是 $O(2^n)$ 。
但如果考虑动规，那么就是从 $f(1)$ 开始向后推，不难看出，此时复杂度就神奇般变成了—— $O(n)$ 。
计算机网络
前段时间由于众所周知的原因，学校把我们平时用的论坛屏蔽了，具体表现在用校园网打不开论坛的网页。后来发现是内网 DNS 搞的鬼，也就兴致勃勃地研究起计算机网络来，上课摸鱼的时候粗略看了一下网络层与网络互连的内容，然后写简历的时候就作死住上填了个“计网初步”，再然后——我就寄了。（安详）——引子
问：同一个子网一台主机向另一台主机发送数据，这个数据是否会直接被转发到另一台主机？
七层网络模型，从底到顶分别是：物理层，数据链路层，网络层，传输层，会话层，表示层，应用层（现在好像简化成四层来着），总之这个问题大概归到网络层和数据链路层的。
然后呢，答案就是，我不知道！
其实呢，我一开始以为自己知道了，但越看越不知道了，最后可能得把整个计网翻上一遍才能彻底整明白了。（没错这就是传说中的递归学习）
下面简单介绍几个概念，要理解这个问题就逃不开。
- 物理地址
首先有一件事就是，IP 地址是逻辑网络上的东西，数据链路层是不能直接用的，就好像你要寄信给小 X 家，地址总不能直接填个“小 X 家”。而详细地址，在计网中叫物理地址，才是物理网络所认的标识。 - ARP
现在我们有了 IP 地址，就需要用ARP 协议(Address Resolution Protocol)来找到对应的物理地址。两者并非是简单的映射关系，而且也会动态变化，就像小 X 搬个家，那里就不叫小 X 家了，过一会搬个小 Y 来，又成了小 Y 家。 - ARP cache
为了解决这个问题，主机里就设置了个 ARP 高速缓存，即 ARP cache，上面存着本局域网上各主机和路由器的 IP 地址和物理地址的映射表。主机 A 向本局域网中的另一台主机 B 发送 IP 数据报时，就先看看里面有没有主机 B 的记录，有的话就好办了，把主机 B 的物理地址写入 MAC 帧里，然后丢进通信链路里就完事。
But 事情总不可能这么简单，有相当大的概率表上是没有主机 B 的，这时主机 A 就会在所在局域网上广播一个 ARP 请求分组，这个广播可以类似生活中广播的概念，可以做到无差别攻击，就是局域网上的所有主机都会收到。这个 ARP 请求分组上有主机 A 的 IP 地址和物理地址，也有主机 B 的 IP 地址，主机 B ，说这不是我嘛，当即发一个单播回去，很快啊，上面有主机 B 的 IP 地址和物理地址。注意到，由于已经收到包含主机 A 物理地址的 ARP 请求分组，所以主机 B 能精准投递到主机 A ，而不用再广播了。显然这时双方都知道对方的物理地址，就写进各自的 ARP cache 中，以后通信就能直接扔过去了。
至此，问题已经逐渐明朗，但有一个关键点，以上的讨论都是基于同一个局域网，而局域网和子网并无直接联系。 - 局域网
这个概念非常广泛，一般来讲就是指一个小范围的网络，但这样事情就解释不通了，两台网线都不接的主机放在一起算不算同在一个局域网？说不清。
所以较真点讲局域网指的是VLAN（Virtual LAN），即虚拟局域网，虚拟局域网
待更新…
参考
Matrix 面试 - 算法&计网篇
