腰马合一神功 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

腰马合一神功

腰马合一神功# Joke - 肚皮舞运动

n*n2013-05-28 07:05

1 楼

2.2 implement an algorithmm to find the kth to last element of a singly
linked list.
我翻了翻答案，好几种，难道不是直接遍历把linked list的长度算出来，再traverse
n-k步拿到kth to last element吗？这个算法又直接，时间上不比那几个solution差，
难道我哪里想错了？

h*o2013-05-28 07:05

2 楼

12 Days till Nov 16 DC Rally:
Check out our latest flyer design:
https://mobile.twitter.com/haifeng_xiao/status/661391201946329089
Various volunteers are now working on handouts/Placards/Banners with best
design! Stay tuned!

x*o2013-05-28 07:05

3 楼

g*y2013-05-28 07:05

4 楼

时间复杂度是一样的，但是如果链表不是在内存中，而是一个流或者是序列化在外存
储器上的话，读两遍的消耗就会比较大，所以就要只读一遍。

H*g2013-05-28 07:05

5 楼

这个访谈怎么总是能遇到一些神人？

n*n2013-05-28 07:05

6 楼

“你是不是‘永远’都会为了效率牺牲可读性”？

【在 g****y 的大作中提到】

: 时间复杂度是一样的，但是如果链表不是在内存中，而是一个流或者是序列化在外存
: 储器上的话，读两遍的消耗就会比较大，所以就要只读一遍。

R*d2013-05-28 07:05

7 楼

倒栽葱

【在 x****o 的大作中提到】

p*22013-05-28 07:05

8 楼

刚才看了一下，你这个问题CC150已经有解答了。

t*32013-05-28 07:05

9 楼

这就是农民工兄弟平时没有业余活动导致武侠书看多了的后果

z*e2013-05-28 07:05

10 楼

第四版就有了，很老的问题了
不过楼主问的意思大概是
既然不增加复杂度，为什么不用相对更简洁明了的方式？
从某种意义上说，楼主未必错，软件工程里面就很强调代码的可读性
因为跟维护成本呈最直接的相关
能领悟到这一层，楼主有一定悟性
面试时候要看对方想知道什么
如果可能的话，先给一个最简单的解决方案
然后如果对方要求，再逐步深入
如果一上来就给出貌似很高明的解决方案，下一个问题估计就是
这题你是不是做过？来，我们换一题

【在 p*****2 的大作中提到】

: 刚才看了一下，你这个问题CC150已经有解答了。

H*g2013-05-28 07:05

11 楼

开始我以为他像憨豆那样在车顶上开车，后来仔细看是前面有个人开，真失望

【在 t****3 的大作中提到】

: 这就是农民工兄弟平时没有业余活动导致武侠书看多了的后果

p*22013-05-28 07:05

12 楼

我说的意思就是CC150已经回答了LZ的问题了，不是这个题目的解答。

【在 z****e 的大作中提到】

: 第四版就有了，很老的问题了
: 不过楼主问的意思大概是
: 既然不增加复杂度，为什么不用相对更简洁明了的方式？
: 从某种意义上说，楼主未必错，软件工程里面就很强调代码的可读性
: 因为跟维护成本呈最直接的相关
: 能领悟到这一层，楼主有一定悟性
: 面试时候要看对方想知道什么
: 如果可能的话，先给一个最简单的解决方案
: 然后如果对方要求，再逐步深入
: 如果一上来就给出貌似很高明的解决方案，下一个问题估计就是

g*n2013-05-28 07:05

13 楼

紧张的，面对镜头临场发挥不好。平时在村里小芬小芳她们面前表演都挺好的

n*n2013-05-28 07:05

14 楼

我手头上这本是最新的版本，让我们来看看solution #3:
A more optimal, but less straightforward solution is to implement this
iteratively. We can use two pointers, p1 and p2. We place them k nodes apart
in the linked list by putting p1 at the beginning and moving p2 k nodes
into the list. Then, when we move them at the same space, p2 will hit the
end of the linked list after length-k steps. At that point, p1 will be
Length-k nodes into the list, or k nodes from the end.
在我看来，the sum of total move is 2*Length-k for both p1 and p2.如果是这样
，直接算出Length of linked list 长度，然后用所谓的trivial solution 1,其实两
者的running time是一样的，但后者显然更直接，让容易理解

【在 p*****2 的大作中提到】

:
: 我说的意思就是CC150已经回答了LZ的问题了，不是这个题目的解答。

t*32013-05-28 07:05

15 楼

我见过红脖皮卡车斗里的狗的腰马合一都比他练得好

【在 H********g 的大作中提到】

: 开始我以为他像憨豆那样在车顶上开车，后来仔细看是前面有个人开，真失望

h*s2013-05-28 07:05

16 楼

2楼说的行吗

apart

【在 n****n 的大作中提到】

: 我手头上这本是最新的版本，让我们来看看solution #3:
: A more optimal, but less straightforward solution is to implement this
: iteratively. We can use two pointers, p1 and p2. We place them k nodes apart
: in the linked list by putting p1 at the beginning and moving p2 k nodes
: into the list. Then, when we move them at the same space, p2 will hit the
: end of the linked list after length-k steps. At that point, p1 will be
: Length-k nodes into the list, or k nodes from the end.
: 在我看来，the sum of total move is 2*Length-k for both p1 and p2.如果是这样
: ，直接算出Length of linked list 长度，然后用所谓的trivial solution 1,其实两
: 者的running time是一样的，但后者显然更直接，让容易理解