1. 聚能聊>
  2. 话题详情

阿里开发者招聘节 | 面试题01:如何实现一个高效的单向链表逆序输出?

面试,如同玩一场饥饿游戏:既要对环境了然于胸,又要对自身心知肚明。发现一个好工作不容易,但成功应聘又会面临一系列的挑战。

为帮助开发者们提升面试技能、有机会入职阿里,云栖社区特别制作了这个专辑——阿里巴巴资深技术专家们结合多年的工作、面试经验总结提炼而成的面试真题这一次将陆续放出(面试题答案将在专辑结束后统一汇总分享)。并通过这些笔试真题开放阿里巴巴工作机会,让更多的开发者加入到阿里这个大平台。

这一次,不仅是知识的收获,还将间接地与技术大牛们做了直观的沟通,了解他们的出题思路与考察要点,并加以消化吸收,这对自己技术能力本身就是一种极大的提升。走上编程之路,不断丰富自己方能与世接轨,努力做最优秀的自己。

4月24日,我们给开发者的第1道面试题。

如何实现一个高效的单向链表逆序输出?

阿里巴巴出题专家:游亮

阿里云弹性人工智能负责人
,带领团队研发了同时支持Tensorflow、MXNET、PyTorch、Caffe的Perseus加速框架,曾获得Dawnbench推理世界竞赛的性能第一和成本最低双料冠军。曾任阿里云弹性高性能计算、超级计算集群技术架构师,获得过多项专利,拥有10年以上AI技术研发和高性能优化经验。精通针对CPU、GPU、MIC等微架构的计算性能优化以及网络、存储等系统性能优化。曾在英特尔SSG部门工作,并获得过英特尔中国最高成就奖(ICA)。
当人工智能遇上云计算,未来不可限量,欢迎加入阿里云弹性人工智能团队。

_

招聘职位:阿里云-GPU虚拟化研发高级专家

快来在下方回复您的答案吧!

更多面试真题陆续放出,敬请期待!

阿里开发者招聘节 |面试题02-08:NAS(Network Attached Storage)协议NFS和SMB相关问题
阿里开发者招聘节 | 面试题09-14:为什么鹿晗发布恋情的时候,微博系统会崩溃,如何解决?
阿里开发者招聘节 | 面试题15-17:如何看待异构计算在整个云计算中的位置和作用?

参与话题

奖品区域 活动规则 已 结束

  • 奖品一

    阿里云代金券 x 3

  • 奖品二

    云栖定制电脑包 x 1

  • 奖品三

    福禄寿淘公仔 x 1

39个回答

0

stockless 已获得福禄寿淘公仔 复制链接去分享


  1. 如果使用递归输出,小链表还好,数据量稍微增多,由于递归输出每一个元素,时间复杂度线性增加,对于阿里这样的企业,肯定会出问题;
  2. 所以,为了结合小链表递归输出这种简单算法的优势,可以设置一个域值(这种思想在redis里面很多),在此范围内,小链表递归输出时间端、所占用的物理内存也少;当链表超过该域值后,在构建链表时,可以将单项链表转为单项循环链表,此时可以借鉴redis跳表的思想,可以给这个链表分段,段中的元素可以使用一些数据结构存储(譬如大顶堆或者其他的树,不建议用栈来存放,可以试着使用大顶堆中堆<这个是我自己命名的......>,简单说明一下,在大顶堆的基础上,每个节点中存放一个内部的大顶堆,形成堆中堆的效果),这样,输出时,只需要递归每个节点;
  3. 说完了上述思想的基本原理,我们来聊聊如何划分段,段的划分,可谓直接影响链表的输出效率,了解希尔排序的同学应该了解过,不同的增量序列会直接影响希尔排序的效率,所以,段的划分至关重要;最简单的是依据上述构建大顶外堆的节点数和每个节点中内堆的个数,联合起来做哈希运算,这样做的好不好还需要深入研究,此处就不做太多说明了;
  4. 最后,说一句,欢迎沟通,不喜勿喷,天马行空的思想,不喜欢就当我吹牛好啦!夜色渐浓、♨️谢谢**
小哇 回复

个人感觉回答的不错。

游客q3awqln6nco3w 回复

你的联系方便加一下吗,请教你一些问题?3609452931 这个是我的qq

1627440867235038 回复

可是这样单量表的维护就很麻烦了。跳表虽然快,但是通用性不是很高,redis之所以采用这个数据结构很大程度上是因为redis设计的key只能是字符串,而且采用字典顺序。开发语言一般会实现红黑树而不是调表应该也是部分原因。而且一旦引入hash的概念,也会引入hash冲突的问题。如果维护跟开发过于复杂的话那就不选择单向量表了吧,维护开发成本高何不变成双向链表。(来自菜鸡的看法,大佬如果觉得不对还请指出,别凶我~~~)

stockless 回复

我可不会凶的呀,这里言论自由的

评论
1

游客bn7idibiniiea 已获得云栖定制电脑包 复制链接去分享

0.  需要考虑因素,高效应权衡多方面因素
数据量是否会很大
空间是否有限制
原始链表的结构是否可以更改
时间复杂度是否有限制
一个链表节点需要输出的元素是否有多个,例如链表中存的是自定义对象,有多个字段

  1. 直接递归(简单,但O(n)空间复杂度不支持大数据量)
  2. 采用栈进行存储(O(n)时间复杂度,但不支持大数据量,栈中需要存储所有节点)
    3. 直接遍历(不需要额外存储空间,但O(n^2)时间复杂度)
  3. 翻转链表再遍历(O(n)时间复杂度且不需要额外存储空间,但需要改变原始链表结构)
  4. 头插法新建空链表(简单,但是O(n)空间复杂度)
1

GodGnidoc 已获得阿里云代金券 复制链接去分享

个人认为,如果条件允许,最好使用汇编来实现,如下是C语言版本的定义假设

struct node {
    node* next;
    long data;
};

假设环境是x86_64架构,如下是实现逆序打印的nasm语法汇编代码,假设print方法提供了打印一个数字的功能。

; @method revprint : 逆序打印
; @desc :
;   逆序打印传入的单链表
; @param head : 链表头指针
; @return void : 无返回值
revprint:
  push 0
  .P:
    test rdi, rdi
    jz .R
    push rdi
    mov rdi, [rsp]
    jmp .P
  .R:
    pop rdi
    test rdi, rdi
    jz .E
      mov rdi, [rdi+8]
      call print
      jmp .R
  .E:
  ret
0

benxtfb 已获得阿里云代金券 复制链接去分享

1.递归 :2* O(n) 时间 + O(n) 空间,尾递归的情况下O(1)空间
2.遍历入栈然后逆序输出 : 2* O(n) 时间 + O(n) 空间
3.遍历一遍调转指针,然后顺序输出, 完了再调转一次指针 : 4* O(n)时间
4.不能改变原有数据并且空间紧张的情况下,可以分段输出,前面的可以写外存,然后逆序输出

0

yaojunwang 已获得阿里云代金券 复制链接去分享

  问题的应该是要同时考虑空间和时间的前提下。
  单纯的递归在数据量到一定级别的时候时间和空间都是难以接受的。
   分治加递归的关键是分治的协调和分治划分的具体实现。如果数据内容和规模变化对分治影响较小,可以尝试找各种分治规模下的最佳参数。如果数据变化对分治有较大影响,这个方法也是有不确定性的。
   调转链表(栈或者直接指针调转),再输出,需要2O(n),并不够高效。
   监听订阅机制,前一个元素订阅后一个元素的输出事件,后一个输出完成,自动激活前一个输出。需要修改链表,觉得不是算法上的优化了
2

云服务器吧 复制链接去分享

加入阿里云建议先考下ACP认证,之前一直有用户问:“阿里云ACP认证的含金量?”阿里云作为国内第一云,企业上云首选都是阿里云,如果你未来会从事云计算相关领域,建议考取ACP认证,会给自己加分的,尤其是加入阿里云https://edu.aliyun.com/certification/acp01?source=5176.11533457&userCode=r3yteowb&type=copy

1

1860766576284864 复制链接去分享

方法不止一种,取舍于实际场景对时间复杂度和空间复杂度的要求,比如桶排序、递归排序、冒泡排序都可以,如果量不大,申请一倍的空间,直接入栈再出栈即可。

0

秀才好吧 复制链接去分享

俩字 递归

游客e2jaose7njahs 回复

好看

评论
1

黄二刀 复制链接去分享

递归岂不美哉????????

0

1670524816961810 复制链接去分享

???

爱团拍 回复

???

评论
0

architect_code 复制链接去分享

简单方法也可以吧,递归一定是高效的吗?不知道下面的这能满足要求不
public class List001 {

private class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
    }
}

public Node reverse(Node head) {
    Node pre = null;
    Node cur = head;
    while (cur != null) {
        Node next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

}

0

风雪载途 复制链接去分享

递归

0

游客oyfmropk3dilk 复制链接去分享

专人专业负责制,根据产品特点对应开展工作;或推广销售、跟踪。

0

游客xg2ly2pfnpm3k 复制链接去分享

看不懂,不过比以前的好就是高效

0

1933898547510999 复制链接去分享

如果量不大可以用递归,量大可以分治,不过具体情况而定吧;如果经常量大的话,我觉得是设计问题了,必须要做优化业务逻辑才行,要不然空间和时间都会被消耗。

0

timeshift 复制链接去分享

数据量不大的场景
单链表的逆序输出分为两种情况,一种是只逆序输出,实际上不逆序;另一种是把链表逆序
1.逆序输出

**#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;

typedef struct node{
    int data;
    node * next;
}node;

//尾部添加
node * add(int n, node * head){
    node * t = new node;
    t->data = n;
    t->next = NULL;
    if (head == NULL){
        head = t;
    }
    else if (head->next == NULL){
        head->next = t;
    }
    else{
        node * p = head->next;
        while (p->next != NULL){
            p = p->next;
        }
        p->next = t;
    }
    return head;
}

//顺序输出
void print(node * head){
    node * p = head;
    while (p != NULL){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

//递归
void reversePrint(node * p){
    if (p != NULL){
        reversePrint(p->next);
        cout << p->data << " ";
    }
}

//栈
void reversePrint2(node * head){
    stack<int> s;
    while (head != NULL){
        s.push(head->data);
        head = head->next;
    }

    while (!s.empty()){
        cout << s.top() << " ";
        s.pop();
    }
}

int main(){

    node * head = NULL;
    for (int i = 1; i <= 5; i++){
        head = add(i, head);
    }
    print(head);
    reversePrint(head);
    reversePrint2(head);
    system("pause");
    return 0;
}
**
  1. 单链表逆序
**#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;


typedef struct node{
    int data;
    node * next;
}node;

node * add(int n, node * head){
    node * t = new node;
    t->data = n;
    t->next = NULL;
    if (head == NULL){
        head = t;
    }
    else if (head->next == NULL){
        head->next = t;
    }
    else{
        node * p = head->next;
        while (p->next != NULL){
            p = p->next;
        }
        p->next = t;
    }
    return head;
}

//循环
node * reverse(node * head){

    if (head == NULL || head->next == NULL){
        return head;
    }

    node * p1 = head;
    node * p2 = head->next;
    node * p3 = NULL; 
    head->next = NULL;

    while (p2 != NULL){
        p3 = p2;
        p2 = p2->next;
        p3->next = p1;
        p1 = p3;
    }
    head = p1;
    return head;
}

void print(node * head){
    node * p = head;
    while (p != NULL){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}


//递归
node * reverse2(node * p){
    if (p == NULL || p->next == NULL){
        return p;
    }

    node * newHead = reverse2(p->next);
    p->next->next = p;
    p->next = NULL;
    return newHead;
}


int main(){

    node * head = NULL;
    for (int i = 1; i <= 5; i++){
        head = add(i, head);
    }
    print(head);
    head = reverse(head);
    print(head);
    head = reverse2(head);
    print(head);

    system("pause");
    return 0;
}

**
0

游客b53zqlyjay4e2 复制链接去分享

让我们大师来回答

0

黄二刀 复制链接去分享

兄弟,能不能把这些题目整理成一个pdf文档,我们企业面试的时候也能参考下。

0

1860766576284864 复制链接去分享

方法不止一种,取舍于实际场景对时间复杂度和空间复杂度的要求,比如桶排序、递归排序、冒泡排序都可以,如果量不大,申请一倍的空间,直接入栈再出栈即可。

0

1860766576284864 复制链接去分享

方法不止一种,取舍于实际场景对时间复杂度和空间复杂度的要求,比如桶排序、递归排序、冒泡排序都可以,如果量不大,申请一倍的空间,直接入栈再出栈即可。

2