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

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

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

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

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

    P.S. 当年毕业时某一轮现场面在纸上写了一个完整的 AVL 平衡二叉树,写了 4 页 A4 纸,还跟面试官逐步去纸上调试了一遍,包括各种边界情况
        36
    pwrliang   129 天前   ♥ 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);
    }

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