Matrix 面试 - 算法&计网篇

开局暴击

算法

面试官给了我一道力扣上的动态规划题,虽然我之前浅浅看过,但没刷过题,一时确实做不出来,然后他换了一道标着“简单”的动规题———经典爬楼梯,still,我还是不会,甚至思路来到了传说中的——递归(逃

直到面试结束后我才一拍脑门,原来递规与动归的区别是前者从后向前推,而后者从前向后推!

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

分析

不难看出,这题就是求一个斐波那契数列,即有
$$
f(n) = f(n-1) + f(n-2)
$$
如果用递归,那么就是从 $f(n)$ 开始向前推,显然,这样的复杂度是 $O(2^n)$ 。
但如果考虑动规,那么就是从 $f(1)$ 开始向后推,不难看出,此时复杂度就神奇般变成了—— $O(n)$ 。

计算机网络

前段时间由于众所周知的原因,学校把我们平时用的论坛屏蔽了,具体表现在用校园网打不开论坛的网页。后来发现是内网 DNS 搞的鬼,也就兴致勃勃地研究起计算机网络来,上课摸鱼的时候粗略看了一下网络层与网络互连的内容,然后写简历的时候就作死住上填了个“计网初步”,再然后——我就寄了。(安详)——引子

:同一个子网一台主机向另一台主机发送数据,这个数据是否会直接被转发到另一台主机?

七层网络模型,从底到顶分别是:物理层,数据链路层,网络层,传输层,会话层,表示层,应用层(现在好像简化成四层来着),总之这个问题大概归到网络层和数据链路层的。
然后呢,答案就是,我不知道!
其实呢,我一开始以为自己知道了,但越看越不知道了,最后可能得把整个计网翻上一遍才能彻底整明白了。(没错这就是传说中的递归学习)

下面简单介绍几个概念,要理解这个问题就逃不开。

  1. 物理地址
    首先有一件事就是,IP 地址是逻辑网络上的东西,数据链路层是不能直接用的,就好像你要寄信给小 X 家,地址总不能直接填个“小 X 家”。而详细地址,在计网中叫物理地址,才是物理网络所认的标识。
  2. ARP
    现在我们有了 IP 地址,就需要用ARP 协议(Address Resolution Protocol)来找到对应的物理地址。两者并非是简单的映射关系,而且也会动态变化,就像小 X 搬个家,那里就不叫小 X 家了,过一会搬个小 Y 来,又成了小 Y 家。
  3. 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 中,以后通信就能直接扔过去了。
    至此,问题已经逐渐明朗,但有一个关键点,以上的讨论都是基于同一个局域网,而局域网子网并无直接联系。
  4. 局域网
    这个概念非常广泛,一般来讲就是指一个小范围的网络,但这样事情就解释不通了,两台网线都不接的主机放在一起算不算同在一个局域网?说不清。
    所以较真点讲局域网指的是VLAN(Virtual LAN),即虚拟局域网,虚拟局域网

待更新…

参考

https://blog.csdn.net/jeffleo/article/details/54174835

作者

未央

发布于

2022-04-03

更新于

2024-03-26

许可协议

评论