面试题

算法数据结构

1、输入两个递增排序的链表，合并这两个链表并使新链表中的节点依然是递增顺序的。

ListNode* MergeList(ListNode* ListHeadNodeOne, ListNode* ListHeadNodeTwo){
     if (NULL == ListHeadNodeOne)
     {
         return ListHeadNodeTwo;
     }
     else if (NULL == ListHeadNodeTwo)
     {
         return ListHeadNodeOne;
     }
     
     ListNode* ListResultNode = NULL;
     if (ListHeadNodeOne->NodeValue < ListHeadNodeTwo->NodeValue)
     {
         ListResultNode = ListHeadNodeOne;
         ListResultNode->NextNode = MergeList(ListHeadNodeOne->NextNode, ListHeadNodeTwo);
     }
     else
     {
         ListResultNode = ListHeadNodeTwo;
         ListResultNode->NextNode = MergeList(ListHeadNodeOne, ListHeadNodeTwo->NextNode);
     }

     return ListResultNode;
}

2、快速排序

private static int partition(int[] arr, int low, int high) {
    //指定左指针i和右指针j
    int i = low;
    int j= high;

    //将第一个数作为基准值。挖坑
    int x = arr[low];

    //使用循环实现分区操作
    while(i<j){//5  8
        //1.从右向左移动j，找到第一个小于基准值的值 arr[j]
        while(arr[j]>=x && i<j){
            j--;
        }
        //2.将右侧找到小于基准数的值加入到左边的（坑）位置， 左指针想中间移动一个位置i++
        if(i<j){
            arr[i] = arr[j];
            i++;
        }
        //3.从左向右移动i，找到第一个大于等于基准值的值 arr[i]
        while(arr[i]<x && i<j){
            i++;
        }
        //4.将左侧找到的打印等于基准值的值加入到右边的坑中，右指针向中间移动一个位置 j--
        if(i<j){
            arr[j] = arr[i];
            j--;
        }
    }

    //使用基准值填坑，这就是基准值的最终位置
    arr[i] = x;//arr[j] = y;
    //返回基准值的位置索引
    return i; //return j;
}

private static void quickSort(int[] arr, int low, int high) {//???递归何时结束
    if(low < high){
        //分区操作，将一个数组分成两个分区，返回分区界限索引
        int index = partition(arr,low,high);
        //对左分区进行快排
        quickSort(arr,low,index-1);
        //对右分区进行快排
        quickSort(arr,index+1,high);
    }

}

3、2叉树的下一节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
    }
};

TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
    if(pNode==NULL)return NULL;
    if(pNode->right)//如果有右子树，那么沿右子树往下最左边的节点即为下一个节点
    {
        TreeLinkNode *p=pNode->right;
        while(p->left)p=p->left;
        return p;
    }else{//如果没有右子树，看父节点
        TreeLinkNode *father=pNode->next;
        if(father==NULL)return NULL;//如果没有父节点，返回NULL
        else{
            if(father->left==pNode)return father;//如果该节点为父节点的左孩子，则中序遍历下一个节点即为父节点
            else{
                TreeLinkNode *grandFather=father->next;
                while(grandFather)//如果该节点为父节点的右孩子，则往上不断查找曾祖父节点，直到有一个节点是其父节点的左孩子
                {
                    if(grandFather->left==father)return grandFather;
                    father=grandFather;
                    grandFather=father->next;
                }
                return NULL;//如果找不到，返回NULL
            }
        }
    }
}

4、请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配]

bool match(char* str, char* pattern)
{
    if (str == NULL || pattern == NULL)
        return false;
    return matchCore(str,pattern);
}
bool matchCore(char* str, char* pattern)
{
    if (*str == '\0'&&*pattern == '\0') return true; //迭代终止条件
    if (*str != '\0'&&*pattern == '\0') return false;//迭代终止条件
    if (*(pattern + 1) == '*')
    {
        if (*str == *pattern||(*pattern=='.'&&*str!='\0'))
            return matchCore(str + 1, pattern) || matchCore(str, pattern + 2);
        else
            return matchCore(str, pattern + 2);
    }
    if (*str == *pattern || (*pattern=='.'&&*str!='\0'))
        return matchCore(str+1,pattern+1);
    
    return false;
}

Android 基础

5、多线程并发
sleep 和 wait 区别
(1)这两个方法来自不同的类，sleep是来自Thread，wait是来自Object；
(2)sleep方法没有释放锁，而wait方法释放了锁。
(3)wait,notify,notifyAll只能在同步控制方法或者同步控制块里面使用，而sleep可以在任何地方使用。

6、ArrayList和LinkedList的区别，以及应用场景
ArrayList是基于数组实现的，ArrayList线程不安全。
LinkedList是基于双链表实现的：
使用场景：
（1）如果应用程序对各个索引位置的元素进行大量的存取或删除操作，ArrayList对象要远优于LinkedList对象；
( 2 ) 如果应用程序主要是对列表进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象；

7、Http https区别，https的加密原理，非对称加密
https协议需要到ca申请证书，一般免费证书较少，因而需要一定费用。
http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。
http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。
https实现原理：
（1）客户使用https的URL访问Web服务器，要求与Web服务器建立SSL连接。
（2）Web服务器收到客户端请求后，会将网站的证书信息（证书中包含公钥）传送一份给客户端。
（3）客户端的浏览器与Web服务器开始协商SSL连接的安全等级，也就是信息加密的等级。
（4）客户端的浏览器根据双方同意的安全等级，建立会话密钥，然后利用网站的公钥将会话密钥加密，并传送给网站。
（5）Web服务器利用自己的私钥解密出会话密钥。
（6）Web服务器利用会话密钥加密与客户端之间的通信。
8、自定义View流程，onMeasure 中的 MeasureSpec 是如何计算的?
onMeasure->onLayout->onDraw

1.UNSPECIFIED ：父试图不对子试图有任何的约束，它可以达到这几所需要的尺寸大小，例如：ListView，ScrollView等，一般在我们在自定义控件中不会用到这个测量模式的。

2.EXACTLY：父视图指定了确切的大小，无论子视图指定多大的尺寸，子视图必须在父视图指定的大小范围内，对应的属性为match_parent或者具体的值，父控件可以通过MeasureSpec.getSize(measureSpec)直接得到子控件的尺寸。

3.AT_MOST：父控件为子控件指定一个最大尺寸，子视图必须确保自己的孩子视图可以适应在该尺寸范围内，对应的属性为wrap_content，这种模式下父控件无法测量子view的大小，只能由子控件自己根据需求去计算自己的尺寸，这种模式就是我们自定义视图需要实现测量逻辑的情况。这就是大部分要重写onMeasure处理的过程，在wrap_content模式下，自定义view要显示多大，还是说显示父容器显示的大小，这个由你控制）

总结: OnMeasure（int widthMeasureSpec, int heightMeasureSpec）该方法就是我们自定义控件中测量逻辑的方法，该方法中的参数是父view传递给子view测量width与height大小的要求。在我们自定义视图中，要做的就是根据widthMeasureSpec与heightMeasureSpec进行对view宽高的一个测量，不同的测量模式，测量的逻辑是不同的。

9、三方开源库，原理分析，retrofit, leakCanacy,EventBus等。
10、Jetpack使用过哪些组件？具体用过哪些场景。
11、Kotlin掌握情况。