数年前电话面试

某A开头的互联网公司，题目是这样的：

给出两个链表

表示的大整数，高位存在前面，求用另一个链表表示两个整数的和。

我提出第一个方法，被否决，对方的原因是：你读了两遍链表，我们公司都是要处理Billion级别的数据的，你不能读两遍。

提出第二个方法，否决，原因是不能修改输入数据。

第三个方法，否决，原因是不能开额外存储

。

我实在没辙了，我都恨不得给他数学证明

为啥不行了。忍着问了一句您能给个hint么实在是不会了。

对面说，你能不能考虑一下递归？

能不能考虑一下递归？

递归？

。。。。。。

递你妈归啊，我当时一怒直接怼回去了，不行。

“为啥不行啊？”

“你说的要处理billion级数据啊，你家栈能有billion级深度么？你不让开额外空间，栈空间就不是额外空间了？”

对面沉默了十秒，说，你能不能假设就三五个数据啊？我就是想让你写个递归。。。。



挂了。




对，电话也挂了，面试当然也挂了。