迫真面试宝典·链表的里技

Feb 24, 2021

见习魔法师

在114514年,下北泽已经成为世界上计算机产业最发达的地区,存在许多著名的会社,来这些企业面试的人络绎不绝,但是大多数人因为不是homo而被拒之门外。与此同时,JavaScript,python等语言因为耗电而在环保主义组织的抗议下而被废止。Go语言因为和下北泽的信仰之神名字相同,因为受到世人的追捧,人们还对其刚刚加入的新功能,字符串插值字面量感恩戴德。但是,还是存在少数比他们更加耗电的技术却因为环保主义者不知道而幸存了下来。

田所浩二作为下北泽最著名的影星,因为经常出演反派角色而被怀疑本人生活作息混乱,导致接不到电影可拍,只能去应聘。

下北泽的公司虽然先进,但是却不知为何保留了最传统的纸笔技术面试。不知为何还在考网上随处可见的数据结构题。

田所浩二进入公司,发现面试官是老朋友MUR,老朋友虽然已经成为了HOMO总监,但是仍然一副池沼模样。“啊,是野兽啊,写一个链表吧。”MUR说到,不知道是池沼还是大智若愚,可能是大道至简吧。

“好啊,来啊,链表写在纸上,纸上!”田所浩二不假思索说出了自己的名台词,因为是与众不同的homo,所以不会用nonke都在用的C++。很快,似乎在写什么魔法咒语一般,在纸上写下了:

(define (list ...xs) xs)
(define (cons head tail) (list head ...tail))

“喂你这骗子,你根本只是使用了语言内置的特性,你根本没实现吧。”没想到MUR在南极的冰川下挖掘到了被GitHub Archive的Lisa代码。

“我有什么实现的必要吗?链表是内置的特性啊?真是拿你没办法呢。”于是田所浩二在纸上写下了另外的代码:

(define (cons head tail) &(if # tail head))
(define (list) ())
(define (list head ...tail)
    (cons head (list ...tail)))

“喂你这骗子,你写的根本不是链表吧。”MUR疑惑不解的神情显得更加池沼。MUR打开电脑,写入代码却发现,这个链表却不是链表,是一个闭包。 [0]: Closure = #Closure[(#)],这种结果究竟是什么啊kora。这么屑的链表有什么存在的必要吗,数据都拿不出来吧?

野兽的眼神变得犀利了起来,“这么想看那就让你看个够吧。”说出了MUR的名言之后,野兽夺过了电脑 ,在REPL界面上写下了:

(define (car s) (s false))
(define (cdr s) (s true))
(define (print-list ls)
    (print! "(")
    (define (go ()) (println! ")"))
    (define (go ls)
        (print! (car ls))
        (if (not (nil? (cdr ls))) (print! " "))
        (go (cdr ls)))
    (go ls))

接着又写下了(print-list (list 1 1 4 5 1 4)),看见输出了正确的结果之后,MUR沉默了半晌,才说出了“波加曼”,至今没人明白这究竟意味着什么。如同波加曼那么大的汗珠从MUR的硕大的脸颊上倾泻了下来,只能往下继续流程:“我说野兽你啊,赶紧让他反转一下吧。”

野兽不假思索写下了:

(define (reverse ls)
    (if (nil? ls) ls
        (list (... (reverse (cdr ls))) (car ls))))

“啊,你这骗子,你绝对做错了吧。”MUR写下了:(reverse (cons 3 (cons 6 (cons 4 (cons ........总计写了364364个cons之后,得到了一个StackOverflowError,“你看,递归算法肯定会栈溢出的吧,快看啊。”就在MUR要为这场糟糕的面试写下No Hire的时候,野兽马上写下了一个新的函数:

(define (reverse ls)
    (define (recur () l) l)
    (define (recur first second)
        (recur (cdr first) (cons (car first) second)))
    (recur ls ()))

你这骗子,你这还是递归算法吧。MUR说着写下了相同的样例,这次程序正确运行了。虽然题目做出来了,但是这注定是一场糟糕的面试,可能下北泽的公司没有YJSNPI的容身之处吧。

MUR起身,整了整衣服,掩盖住了池沼的表情,半晌挤出来几个字:“喂野兽啊,你回去等结果吧。“第一轮面试就要回去等结果显然只有被拒绝的结局,YJSNPI只能走出公司大门,步入小田急下北泽站,回家寻找其他机会了。

想着可能无法再回到以前的状态,见到心爱的TON了后辈了。“你是一个一个一个一个,啊,啊~”,也不知道这个“你”究竟是个什么,也不知是泪水还是什么其他液体,不禁冲了出来。

r{{ post.created = '1919/1/14'; }} r{{ post.lastEdit = '1919/5/14 19:19'; }}