一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1382|回复: 9
收起左侧

[算法题] 一道whatsapp的面试题,求解答!

[复制链接] |试试Instant~ |关注本帖
鱼吃鱼翅 发表于 2015-2-12 23:48:41 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
以下有两个函数,一个是prepend一个node在单链表头之前,第二个函数是产生1 - n的sequence,这个是O(n)的解法了。但面试官要求想个办法比这个解法要快两倍。求大神们帮帮忙啊!

static Node prepend(Node root, int data){
    Node node = new Node(data);
    node.next = root;
    return node;
}

//generate 1 ->2 -> 3 ... -> n   
static Node generateSequence(int n){
    Node node = null;
    for(int i = n; i > 0; i--){
        node = prepend(node, i);
    }
    return node;
}
CrackerCracked 发表于 2015-2-13 08:33:18 | 显示全部楼层
不太明白。。。就算factor上快两倍也依然是O(n)吧。。。
回复 支持 反对

使用道具 举报

li24yang75 发表于 2015-2-14 04:19:09 | 显示全部楼层
递归一次 生成两个新节点?
回复 支持 反对

使用道具 举报

 楼主| 鱼吃鱼翅 发表于 2015-2-14 05:40:53 | 显示全部楼层
li24yang75 发表于 2015-2-14 04:19
递归一次 生成两个新节点?

我觉得可能是考多线程吧。。。
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-2-23 11:24:25 | 显示全部楼层
你这有个问题,每次prepend以后,没重新更新链表的root让他指向新节点

所以每次prepend要执行两次赋值,一句更新新节点的Next指向root,第二句更新root到新节点

如果一次把所有新节点都生成,并且连接好,只把最后一个节点连到当前链表root上,理论上是可以少一半时间的,以为少了一半赋值语句

感觉这么做太简单了点,也许我没get到点上。
回复 支持 反对

使用道具 举报

 楼主| 鱼吃鱼翅 发表于 2015-2-24 06:37:19 | 显示全部楼层
silenceleaf 发表于 2015-2-23 11:24
你这有个问题,每次prepend以后,没重新更新链表的root让他指向新节点

所以每次prepend要执行两次赋值, ...

没有 这样不会有效的减少时间。。。所以我最后的解决办法就是用thread
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-2-24 11:41:34 | 显示全部楼层
鱼吃鱼翅 发表于 2015-2-24 06:37
没有 这样不会有效的减少时间。。。所以我最后的解决办法就是用thread

多线程(加锁),肯定可以提高2倍的
回复 支持 反对

使用道具 举报

atlas1017 发表于 2015-10-4 01:12:51 | 显示全部楼层
谁能给一段code 参考一下么... 多谢!!
回复 支持 反对

使用道具 举报

cdqnn 发表于 2015-10-5 11:08:45 | 显示全部楼层
加锁的话,每次只有一个线程可以对链表进行操作,速度不会增快的。
两个线程,分别构造n/2的链表,然后链起来才可以。
回复 支持 反对

使用道具 举报

lrn0304 发表于 2015-10-29 05:39:14 | 显示全部楼层
单线程应该不会一半计算量, 多线程 DnC 在合并吧.
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 13:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表