架构师第 8 周练习

用户头像
小蚂蚁
关注
发布于: 2020 年 07 月 29 日

1、有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。

 算法思路:

(1)比较两个链表到长度,计算两个链表到长度差m,让较长链表头指针挪动m位。

(2)之后比较两个链表的头指针对应到数据,如果一样则返回该节点;不一样则头指针分别往后移动一位,一直到挪动到链表表尾。

 

public Object getJoinNode(LinkedList a,LinkedList b) {

        //最短的那个链表长度

        int slenth = 0;

        //比较大小、计算两个链表的长度差m,挪动较长链表的头指针m位

        if(a.size()>=b.size()) {

            int m = a.size()-b.size();

            //长链表的头指针m位

            for (int i = 0; i < m; i++) {

                a.poll();

            }

           

             slenth = b.size();

       

           

        }else {

            int m = b.size()-a.size();

            //长链表的头指针m位

            for (int i = 0; i < m; i++) {

                b.poll();

            }

           

             slenth = a.size();

        }

       

        //比较两个链表的头指针对应到数据,如果一样则返回该节点;不一样则头指针分别往后移动一位,一直到挪动到链表表尾,如果未找到,返回空。

        for (int i = 0; i < slenth; i++) {

            Object ao = a.poll();

            Object bo = b.poll();

            if(ao ==bo) {

                return ao;

            }

        }

       

        return null;

    }

2、请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。



用户头像

小蚂蚁

关注

还未添加个人签名 2018.08.10 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”,便于分类
2020 年 07 月 29 日 17:45
回复
没有更多了
架构师第8周练习