[2483] Linked List Interview Problem

Title Text:I’d traverse it myself, but it’s singly linked, so I’m worried that I won’t be able to find my way back to 2021.

Origin:https://xkcd.com/2483/

https://www.explainxkcd.com/wiki/index.php/2483:_Linked_List_Interview_Problem

链表面试问题

我想过要自己遍历它,但那是个单向链表,所以我有点担心我找不到回2021年的路。

脚注:
编码岗位的面试有时会考一些算法题,这题是要求遍历(traverse)一个单链表(linked list)。
单链表是一种数据结构,由一些结点组成,每个结点里面保存了一些数据和指向下一个结点的指针。
通过这个指针就可以遍历链表,然后传进来的head Pointer是指向链表第一个结点的指针。
这里面试官是让cueball写这个遍历算法的,然后cueball却是在代码里发了封邮件给科技博物馆,把这个headPointer(也就是这条链表)捐出去了。
捐的理由应该是title text里说的不敢自己遍历,遍历了就回不来了所以让专业的人来(因为单链表只有前一个结点有指向后一个结点的指针,后一个结点没有指向前一个结点的指针。

http://xkcd.in/comic?lg=cn&id=2483

这是Randall 的 另一个技巧,这次是 Coding 面试技巧。

在计算机编程中,链表是一种数据结构,它在整个内存中存储数据以及下一个(可能是上一个)数据点的内存地址,为数据集合建立相对顺序。几个常见的软件工程面试问题涉及操作链表或以其他方式与链表交互。可能是因为当今的程序员很少直接使用链表,Randall 建议这种结构属于“技术博物馆”,并认为将列表通过电子邮件发送到这样的博物馆而不是执行任何有用的工作对人类更有益用它。

链表是一种在计算机内存中存储顺序数据的方法。每条数据都存储有指向下一条数据的指针。这使得在中间添加新数据变得非常容易,因为只有一个现有指针必须更改为指向新数据。天真的实现的缺点可能是查找数据可能需要遵循整个链。技术编程面试官喜欢看申请人是否熟悉结构和计算复杂性概念本身。

从历史上看,链表是表示顺序数据和数组的两种主要数据结构之一。与数组不同,由于不需要重新分配整个结构,它们具有O(1)插入和删除的理论优势,但具有 O(n) 随机访问(参见比较)。然而,现代处理器的缓存结构有利于彼此相邻的数据,预取相邻的项目,并且现代处理器可以执行批量内存移动,使调整大小操作更快。最后,使用链表通常意味着动态分配每个列表成员,而不是为大量项目保留内存,然后在必须添加项目时使用该内存。在现代系统上内存分配往往很慢,并增加了管理信息的开销,哪个字节分配给什么项目,这可能很重要,特别是对于较小的数据项目;许多小的分配也往往会导致内存碎片化,这可能导致它被浪费并且以后无法供应用程序使用,特别是在诸如 Web 服务器之类的长时间运行的进程中。

现代编程语言通常提供抽象(通常称为“数组”、“向量”或“列表”),它们在内存级别与顺序数据交互,在使用数组、链表、上述技术的混合时提供对这些数据的访问,或其他方法,程序员不一定需要关心一种或另一种方式。然而,在创建可很好地扩展到大数据的快速运行代码、避免(例如)一遍又一遍地遍历列表或执行特别低效的操作时,了解基础概念仍然很有用。

Cueball 的代码实现了一个例程,其名称暗示它执行一项平凡的任务,特别是遍历链表,但实际上将列表的内容通过电子邮件发送到技术博物馆。这可能会泄露可能存储在链接列表中的私人数据,例如银行帐号、医疗信息、密码等,因此是一个糟糕的主意。这就是面试官——大概是求职面试官——会“变得非常生气”的原因。

在标题文本中,单向链表包含仅在一个方向上遍历列表的指针;即从头到尾。相比之下,双向链表中的每个元素都包含指向“下一个”和“上一个”元素的指针,从而可以在任一方向上进行遍历。Randall 继续暗示此类列表已过时,暗示遍历此类列表类似于时间旅行。如果没有“前一个元素”指针,兰德尔担心他将无法逆转时间旅行,因为他无法以相反的方向遍历列表。

Leave a Reply

Your email address will not be published. Required fields are marked *

Categories