两道面试题

末蓝、 2022-08-03 05:29 214阅读 0赞

1.请随机返回链表里面的一个节点（链表长度未知，不允许改变链表，不要占用太多的空间）。函数原型:ListNode\* random\_node(ListNode\* head);

面试的时候我提出了几种方案，面试的人觉得不好，他的意思是尽量不要遍历链表。

回来后我在继续想这个问题，我觉得这个题目很难办，如果链表是固定的就好办了，也就是链表不要作为参数传进去就好办。如果是这样，这个问题就可以转换为类似索引顺序表的查找了（参见严蔚敏版数据结构225页）。也就是使用一定空间记录前几次的返回结果，然后在下次返回时从前几次结果中选择最近的节点开始来返回节点。

2.HttpServer里面有一个线程需要检查处理用户请求的线程是否超时，如果超时，就应该结束那个线程并返回500错误，请给出一种算法，能够开始地坚持超时线程。

面试时我的想法是按照运行时间建立多级链表，然后根据运行时间快速查找。这种策略有点像线程调度。面试的人说能不能给出不需要查找链表的算法。

回来后我想这个问题可以转换为堆排序（参见严蔚敏版数据结构280页），每次线程更新时重建一下堆就可以了。

昨天是有生以来第一次出去面试，一来有点紧张，二来前面一直在忙项目，没啥准备，发挥不太好，不过收获很多，其中一个就是做算法题尽量考虑将题目转换为常见的算法。只要你知道了转换，后面就好办了。我这个人的有一个特点是不喜欢记东西，但喜欢建索引。我看过的东西，一般就会一直记得这个东西在哪本书的哪章里面讲到过（这本书如果看过多边的话，基本可以记住页数），但是我基本一两天就会忘记里面一些具体步骤。所以当别人问我问题时，我可以迅速地告诉你是这个问题在哪里可以找到解决方法，但我不能马上告诉该怎么样解决，我需要再看一遍具体步骤。

最近写了一些类似于总结的东西，完全是被面试逼的，主要是方便记忆。不知道那个公司能够变换一下面试的方式，允许带资料，允许用搜索引擎，请在五分钟解决这个问题，我觉得这种方式是最接近日常的思考方式的。不知道大家对大学里面的闭卷考试感觉怎么样，虽然我考的很好，但我就觉得数学和计算机里面的考试就应该是开卷考试的，这样老师就会想新的题目，学生也会去思考，而不是背诵。还有一个是，现在的很多面试是：请问xxx是什么？我觉得最好这样：请问你知道xxx是什么吗？如果知道，请谈谈你对xxx的理解。如果不知道，请在5分钟内去查阅资料，再谈谈你的理解。

如果你有更好的方案，欢迎提出，大家讨论讨论。