FB面试题一道的follow up - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

FB面试题一道的follow up

FB面试题一道的follow up# JobHunting - 待字闺中

l*42015-03-26 07:03

1 楼

题目很简单：
1. 给一个linked list, 求长度
2. 实现在linked list中append一个节点
3. 实现在linked list中prepend一个节点
4. 利用上面的函数，实现将一个数组变成linked list.
但是有一个follow up：
5. 要求提高4的性能。
在哪些方面能提高？4已经是线性复杂度了

b*52015-03-26 07:03

2 楼

我觉得时append和prepend同时来？

【在 l***4 的大作中提到】

: 题目很简单：
: 1. 给一个linked list, 求长度
: 2. 实现在linked list中append一个节点
: 3. 实现在linked list中prepend一个节点
: 4. 利用上面的函数，实现将一个数组变成linked list.
: 但是有一个follow up：
: 5. 要求提高4的性能。
: 在哪些方面能提高？4已经是线性复杂度了

t*32015-03-26 07:03

3 楼

4要用1、2、3的函数，可能你之前的三个方法的性能有问题

【在 l***4 的大作中提到】

b*52015-03-26 07:03

4 楼

为什么要用1,2,3？傻逼点的话, 不就一个个append?

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

: 4要用1、2、3的函数，可能你之前的三个方法的性能有问题

p*u2015-03-26 07:03

5 楼

repost:
they might want u 2 use vector to construct this linked list:
1: a vector is cache friendly;
2. O(1) random access: append is O(1) too, not O(n);

【在 b**********5 的大作中提到】

: 为什么要用1,2,3？傻逼点的话, 不就一个个append?

l*42015-03-26 07:03

6 楼

我能想到的是在链表类里面keep一个尾节点这样append也是O1
同时prepend和append应该也可行

★ 发自iPhone App: ChineseWeb 1.0.2

【在 b**********5 的大作中提到】

: 为什么要用1,2,3？傻逼点的话, 不就一个个append?

l*42015-03-26 07:03

7 楼

感谢分享

★ 发自iPhone App: ChineseWeb 1.0.2

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

: repost:
: they might want u 2 use vector to construct this linked list:
: 1: a vector is cache friendly;
: 2. O(1) random access: append is O(1) too, not O(n);