V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
greenlake
V2EX  ›  程序员

多少人可以在一小时内做出来,面试题插入排序单链表

  •  
  •   greenlake · 2019-06-10 20:16:05 +08:00 · 6097 次点击
    这是一个创建于 1753 天前的主题,其中的信息可能已经有所发展或是发生改变。
    让你用你熟悉的语言写一个插入排序单链表的算法题,你可以在一小时内写出来吗,并配上单元测试,同时编译通过
    44 条回复    2019-06-11 14:25:50 +08:00
    greenlake
        1
    greenlake  
    OP
       2019-06-10 21:57:32 +08:00
    单元测试 1:
    Input: 4->2->1->3
    Output: 1->2->3->4

    单元测试 2:
    Input: -1->5->3->4->0
    Output: -1->0->3->4->5
    tt67wq
        2
    tt67wq  
       2019-06-10 22:32:21 +08:00 via iPhone   ❤️ 2
    有木有空间复杂度要求啊?我 values 抠出来,排好序再拼成一个链表行不行啊?
    whileFalse
        3
    whileFalse  
       2019-06-10 23:00:27 +08:00 via iPhone
    俺连插入排序是啥都不知道了
    jc89898
        4
    jc89898  
       2019-06-10 23:08:25 +08:00
    10 分钟 算法 101 学的吧
    AlexLixin
        5
    AlexLixin  
       2019-06-10 23:29:15 +08:00   ❤️ 1
    package demo;

    class Node {
    public Node next;
    public int data;

    public Node() {
    }

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

    @Override
    public String toString() {
    StringBuilder sb = new StringBuilder();
    Node p = this;
    while(p!=null) {
    sb.append(p.data+"->");
    p=p.next;
    }
    String string = sb.toString();
    return string.substring(0,string.length()-2);
    }

    }

    public class Demo {
    public static void main(String[] args) {
    test1();
    test2();
    }

    private static void test2() {
    Node head = new Node(new Node(new Node(new Node(null, 3), 1), 2), 4);
    Node sorted = sort(head);
    System.out.println(sorted);
    }

    private static void test1() {
    Node head = new Node(new Node(new Node(new Node(new Node(null,0), 4), 3), 5), -1);
    Node sorted = sort(head);
    System.out.println(sorted);
    }

    private static Node sort(Node head) {
    Node sortedL, sortedR;
    sortedL = head;
    sortedR = head;
    Node current = head;
    while (sortedR.next != null) {
    current = sortedR.next;
    if (current.data < sortedL.data) {
    sortedR.next = current.next;
    current.next = sortedL;
    sortedL = current;
    } else if (sortedL.data <= current.data && current.data < sortedR.data) {
    Node p = sortedL;
    while (p != sortedR) {
    if (p.data <= current.data && current.data < p.next.data) {
    sortedR.next = current.next;
    current.next = p.next;
    p.next = current;
    break;
    }
    p = p.next;
    }
    } else {
    sortedR = current;
    }

    }
    return sortedL;
    }
    }
    ArthurRen
        6
    ArthurRen  
       2019-06-10 23:35:54 +08:00 via Android
    这种题目需要一个小时吗。。。。
    leetcode easy 难度吧
    xuanbg
        7
    xuanbg  
       2019-06-10 23:44:29 +08:00
    话说有谁真的写过链表的实现?
    ayyll
        8
    ayyll  
       2019-06-10 23:51:59 +08:00 via Android
    @xuanbg 这。。。acm 集训队初级成员也要写的吧。。初期应该是禁 stl 的 所以遇到链表的题必须要手写啊
    hx1997
        9
    hx1997  
       2019-06-11 01:19:12 +08:00 via Android   ❤️ 1
    @xuanbg ?大学数据结构课不用写吗🤦
    greenlake
        10
    greenlake  
    OP
       2019-06-11 01:29:57 +08:00
    @ArthurRen 当然大学刚毕业的,或者准备面试的应该可以。但是我想讨论那些在工作岗位上做了几年,但是平时很少用到这样的算法,如果直接让你写,有多少能写出来,天天刷 leetcode 的除外
    greenlake
        11
    greenlake  
    OP
       2019-06-11 01:30:31 +08:00
    @tt67wq 应该是 in place 的排序
    greenlake
        12
    greenlake  
    OP
       2019-06-11 01:32:19 +08:00
    @AlexLixin 请不要 copy & paste
    zhy0216
        13
    zhy0216  
       2019-06-11 01:45:42 +08:00 via Android   ❤️ 2
    闭着眼睛写 认识到自己的不足才能进步 不要奢望每个人都这么弱。
    smdbh
        14
    smdbh  
       2019-06-11 01:59:21 +08:00 via Android
    知易行难
    tyrealgray
        15
    tyrealgray  
       2019-06-11 02:09:04 +08:00
    如果算上搭单元测试的环境而且还用的 C++的话或许会接近一个小时吧。但是这个算法,即使你半路出家一开始没学过数据结构,工作几年还写不出来的话不应该吧。
    jc89898
        16
    jc89898  
       2019-06-11 05:16:18 +08:00
    @xuanbg 链表的实现不是大一基础课教的吗...
    exonuclease
        17
    exonuclease  
       2019-06-11 05:34:33 +08:00 via iPhone
    链表的插入排序挺好写的啊 我记得 leetcode 做出来没超过 20 分钟
    exonuclease
        18
    exonuclease  
       2019-06-11 05:36:08 +08:00 via iPhone
    @exonuclease 记错了 是归并排序
    AlexLixin
        19
    AlexLixin  
       2019-06-11 08:24:16 +08:00
    @greenlake 我三十多分钟写出来的。比想象中花的时间多,平常不怎么用到的话,细节上不可能不出错。
    pwrliang
        20
    pwrliang  
       2019-06-11 08:24:59 +08:00
    我觉得给我半个点能写出来…我中午午休试试
    zchlwj
        21
    zchlwj  
       2019-06-11 08:30:08 +08:00
    easy 难度。多做做 leetcode
    TomVista
        22
    TomVista  
       2019-06-11 08:49:16 +08:00
    2 本毕业一年,得重新学.
    petelin
        23
    petelin  
       2019-06-11 09:04:23 +08:00 via iPhone
    应该只能用冒泡排序吧
    BBCCBB
        24
    BBCCBB  
       2019-06-11 09:12:28 +08:00
    这个用归并排序, leetcode 就有.插入排序也简单..
    shilyx
        25
    shilyx  
       2019-06-11 09:30:41 +08:00
    半小时
    misaka19000
        27
    misaka19000  
       2019-06-11 09:43:46 +08:00
    这个算是非常基础的题目了吧,感觉应该要不了一个小时就够了
    hand515
        28
    hand515  
       2019-06-11 09:44:31 +08:00
    用 python 的话,就 10 分钟吧
    misaka19000
        29
    misaka19000  
       2019-06-11 09:45:35 +08:00
    @xuanbg #7 写的话应该基本上都写过吧,不过在生产环境肯定是不会用自己实现的链表的
    cjh1095358798
        30
    cjh1095358798  
       2019-06-11 10:03:39 +08:00
    三点:1.快速指针找到中点 2.归并 3,合并两条有序链表
    Caballarii
        31
    Caballarii  
       2019-06-11 10:04:03 +08:00
    一个小时,即使你完全没接触过快速排序,拿到算法也应该能自己实现出来了
    tt67wq
        32
    tt67wq  
       2019-06-11 10:06:03 +08:00
    如果插入的话,没啥难度,归并难点
    jorneyr
        33
    jorneyr  
       2019-06-11 10:14:21 +08:00
    链表使用一个空的头结点可以简化插入删除操作

    插入排序时转变一下思路即可:
    数组的插入:前面都是有序的
    链表的插入:后面都是有序的
    xiadong1994
        34
    xiadong1994  
       2019-06-11 10:19:38 +08:00 via iPhone
    @cjh1095358798 那是归并排序……
    whusnoopy
        35
    whusnoopy  
       2019-06-11 10:23:01 +08:00   ❤️ 1
    这种题在 BAT 这个级别的公司里,应该是技术面第一轮暖身题的难度,最低期望应该是 20 分钟内解决。依次对比可以估算下应该多少人会写

    P.S. 当年毕业时某一轮现场面在纸上写了一个完整的 AVL 平衡二叉树,写了 4 页 A4 纸,还跟面试官逐步去纸上调试了一遍,包括各种边界情况
    pwrliang
        36
    pwrliang  
       2019-06-11 11:41:27 +08:00   ❤️ 1
    @greenlake 一到公司就迫不及待,花了有半小时吧,写出来了。包含一个编码、测试,用了 Idea 做调试,直接白板写估计够呛。

    -------------------
    ```
    import java.util.*;

    class Solution {
    class Node {
    Node next;
    int val;

    Node() {

    }

    Node(int val) {
    this.val = val;
    }

    @Override
    public String toString() {
    return val + (next != null ? "->" + next.toString() : "");
    }
    }

    boolean check(Node head) {
    Node p = head.next;

    while (p.next != null) {
    if (p.val > p.next.val) {
    return false;
    }
    p = p.next;
    }

    return true;
    }

    Node asNode(int[] array) {
    Node head = new Node();
    Node p = head;

    for (int e : array) {
    p.next = new Node(e);
    p = p.next;
    }

    return head;
    }

    void sort(Node head) {
    if (head == null || head.next == null)
    return;

    Node prev = head;
    Node curr = prev.next;

    while (prev.next != null) {
    Node p = head;
    boolean changed = false;
    while (p != curr) {
    if (p == head && curr.val < p.next.val || curr.val >= p.val && curr.val < p.next.val) {
    prev.next = curr.next;
    Node tmp = p.next;
    p.next = curr;
    curr.next = tmp;
    changed = true;
    break;
    }
    p = p.next;
    }

    if (changed) {
    curr = prev.next;
    } else {
    prev = prev.next;
    curr = prev.next;
    }
    }
    }
    }


    测试:

    Solution solution = new Solution();
    {
    Solution.Node head = solution.asNode(new int[]{5, 1, 5, 3, 4, 2});
    solution.sort(head);
    assert solution.check(head);
    }

    {
    Solution.Node head = solution.asNode(new int[]{1});
    solution.sort(head);
    assert solution.check(head);
    }

    for (int times = 0; times < 1000; times++) {
    int len = 2000;
    int[] test = new int[len];
    Random random = new Random();
    for (int i = 0; i < len; i++)
    test[i] = random.nextInt();

    Solution.Node head = solution.asNode(test);
    solution.sort(head);
    assert solution.check(head);
    }

    ```
    layorlayor
        37
    layorlayor  
       2019-06-11 13:01:12 +08:00
    这个不就是链表的遍历+节点插入吗
    jmc891205
        38
    jmc891205  
       2019-06-11 13:20:31 +08:00
    工作中经常用链表的表示无压力
    fredshao
        39
    fredshao  
       2019-06-11 13:26:07 +08:00
    啥叫插入排序链表?是必须用插入排序,去排一个链表?
    Tangdixi
        40
    Tangdixi  
       2019-06-11 13:27:19 +08:00
    @whusnoopy 很凶残,但还是没有手写红黑树凶残哈哈哈哈哈哈哈,旋转真的要写到蛋碎
    qq976739120
        41
    qq976739120  
       2019-06-11 13:28:48 +08:00
    @jmc891205 方便问下什么工作经常要使用链表呢?
    x7395759
        42
    x7395759  
       2019-06-11 13:56:43 +08:00
    纯手撸要从链表开始撸吧,这个就有点难了。
    whusnoopy
        43
    whusnoopy  
       2019-06-11 14:18:31 +08:00
    @Tangdixi 毕业后某年从北京去上海面 Google,去之前 HR 说我们会考察某些内容,比如高级数据结构里有平衡二叉树,可以是 AVL 或者 RB-Tree,我回忆起之前那次蛋疼的 AVL,在去上海的高铁上撸了一遍红黑树,最后在过了南京没到上海的时候终于都调通了,用 C 写的代码,加调试大概 600 行(手动捂脸
    linchengzzz
        44
    linchengzzz  
       2019-06-11 14:25:50 +08:00
    不说搞算法了,,大学数据结构也讲队列和链表然后去实现呀
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   954 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 21:20 · PVG 05:20 · LAX 14:20 · JFK 17:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.