万字详细面试被吊打的总结(SE->数据结构->MYSQL)

本文涉及的产品
云数据库 RDS MySQL,集群版 2核4GB 100GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介: 万字详细面试被吊打的总结(SE->数据结构->MYSQL)

力扣138.随机链表的问题(经典——重要)

我是有思路,但是20分钟,确实我的头脑没有转那么快,没有做出来,我就想到拆分,把它依次连接

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;
 
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
 
class Solution {
   public static Node copyRandomList(Node head) {
       if (head==null)
        return null;
        Node cur=head;
        while(cur!=null){
            Node a=new Node(cur.val);
            a.next=cur.next;
            cur.next=a;
            cur=cur.next.next;
        }
        Node newhead=head.next;
        cur=newhead;
        Node prev=head;
        while(cur!=null&&cur.next!=null){
            if(prev.random!=null){
                cur.random=prev.random.next;
            }
            prev=prev.next.next;
            cur=cur.next.next;
        }
        if(prev.random!=null){
        cur.random=prev.random.next;}
        cur=newhead;
        prev=head;
 
        while(cur!=null&&cur.next!=null){
            prev.next=prev.next.next;
            cur.next=cur.next.next;
            prev=prev.next;
            cur=cur.next;
        }
            prev.next=null;
     
        return newhead;
    }
}

面试题1:java创建对象有几种方式

1.new 对象这个就不用说了,简单
2.反射 Class对象调用newInstance()接口
 String m = "Node";
 Class clas=Class.forName(m);
 Node t=(Node) clas.newInstance();
3.使用Constructor类的newInstance方法
 Constructor<Node> constructor =Node.class.getConstructor();
        Node t2=constructor.newInstance();
        System.out.println(t2);
这两种都叫反射,事实上Class对象的newInstance在内部也是调用的Constructor这个类
4.Object类实现的clone接口
public class Node implements  Cloneable{
        int val;
        Node next;
        Node random;
 
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
//需要重写这个方法
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
 
    public Node() {
    }
}
 public static void main(String[] args) throws ClassNotFoundException, InstantiationException, IllegalAccessException, CloneNotSupportedException {
//       String m = "Node";
//       Class clas=Class.forName(m);
//       Node t=(Node) clas.newInstance();
        Node t1=new Node(5);
        Node t2=(Node)t1.clone();
        System.out.println(t1==t2);
 
    }
5.通过序列化来创建对象

面试题2:hashmap的底层数据结构?hashcode重写为什么必须要重写equals?

hashmap(JDK1.7的时候,是使用的拉链法,只有数组和链表

但是JDK1.8的时候,有了数组,链表,红黑树,扩容的时候resize(),红黑树拆分树的节点,小于6个退化成链表)我准备挺多的,但是hashcode这块确实没有看(只能说知道啥意思,但是具体的忘记了)

拿到一个hash值之后,利用key的hashcode重新hash计算在数据中下标。

equals是比较两个对象是否相等,

hashcode用于获取对象的哈希码。

如果equal()方法判断为相等,则他们的hashcode必须返回相同的值,这是因为使用哈希表等数据结构时,会先根据对象的哈希码确定存储位置,然后再使用 equals() 方法进行比较来确保唯一性。

1.如果重写了equals,但是没有重写hashcode()方法,可能会导致对象放入哈希表中,hashcode返回的不是相同的值,从而无法正常操作这个对象

2.当使用哈希集合的时候,由于HashCode返回的不是相同的值,哈希集合也无法判断这两个对象是否相等,从而又可能会导致set 有重复元素.

面试题3:ArrayList和LinkedList的区别

ArrayList基于数组,LinkedList基于双向链表

对于随机访问,ArrayList优于LinkedList

对于插入和删除操作,LinkedList优于ArrayList(详细:LinkedList优于ArrayList头插,因为LinkedList只需要移动指针,但是ArrayList需要搬运元素)

LinkedList中间的插入数据慢,ArrayList中间插入数据较快)LinkedList尾插慢,ArrayList尾插速度快,不需要移动位置

ArrayList的内部

 
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
 
    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
 
    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
 
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
 
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
 
    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

DEFAULT_CAPACITY默认容量为10.

size:当前ArrayList元素个数

elementData:用于存储实际元素的数组

MAX_ARRAY_SIZE: 数组的最大容量,一般为Integer.MAX_VALUE - 8

扩容的触发条件:

1.添加元素:size>elementData的长度

2.使用带有指定初始容量的构造方法,并且该初始容量大于默认容量,也会触发扩容

新容量一般为原先容量的1.5倍

为什么说快排的空间复杂度最优情况下是O(N)*(logN),最坏情况下是O(N^2)?(知识点:堆排序,快排,归并)

第一次Partiation应该是需要对整个数组扫描一遍,做n次比较,他是递归的过程,一层一层的去遍历,那么也就是说我们需要求他的层数,总结点,是一个等比数列求和,每一层是2的等比数列,累加在一起,然后我们使用log ,来求出他的层数,最后就是N*log,但是不好的情况就是N^2,因为他这个时候,就不是一个树,更像是类似于链表,都是连起来的,那么层高就是N,所以复杂度就是O(N^2)

这里首先要全面的写一下堆和快排和归并排序

堆最好是一颗完全二叉树(用数组存储),假如不是,会造成空间浪费)

小根堆/大根堆

根节点都比左右孩子小。(小根堆特性中序遍历,全部顺序。)

建立的是一个大根堆

import java.util.Arrays;
 
public class TestHeap {
    //自己去写一个堆
    public int[] elem;
 
    public int usedSize;
 
    public TestHeap() {
        this.elem = new int[10];
    }
 
    //创建一个大根堆
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            //向下调整,需要给的数字,当前父亲位置,结束位置
            shiftDown(parent, usedSize);
        }
    }
 
 
 
    /**
     * @param parent 每颗子树根节点
     * @param len    每个子树的结束位置
     */
    //向下调整,已知孩子下标len-1拿到,父亲节点(len-1-1)/2
    public void shiftDown(int parent, int len) {
        int child = parent * 2 + 1;
        //看他是否有左孩子
        while (child < len) {
            if(child+1<len){
            if(elem[child]<elem[child+1]){
                child=child+1;
            }
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[parent];
                elem[parent] =elem[ child];
                elem[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
 
 
    //保证仍然原先是大根堆,还是小根堆(当插入一个元素的时候,先插入到最后一个位置),插入后,直接和根比较
    //向上调整
    public void push(int val){
        //检查是否满了
        //2.存数据
        if(isFull()){
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        usedSize++;
 
        shiftUp(usedSize-1);
    }
 
 
 
    public  boolean isFull(){
        return usedSize==elem.length;
    }
 
 
 
    public void shiftUp(int child){
        int parent=(child-1)*2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }
    //假如只能删除堆顶,还要保持他是一个大根堆的形态(那么就要头和最下面的换,然后去,向下调整)
public void  poll(){
        int tmp =elem[0];
        elem[0]=elem[usedSize-1];
        //让0下标元素和最下面的元素交换,然后再去向下调整(把size--即可)
        elem[usedSize-1]=tmp;
        usedSize--;
        shiftDown(0,usedSize);
 
}
//堆排序
    public void headSort(){
        int end=usedSize-1;
        while(end>0){
            //本身已经是一个大根堆
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);
            end--;
        }
    }
 
 
 
}

建立堆的时间复杂度约等于O(N),向下调整

关于PriorityQueue的问题(类似于堆,所以,他内部会有一个比较的操作):

1.PriorityQueue放置的元素必须能够比较大小,不能插入无法比较的对象,否则就会抛出ClassCastException(类型转换异常)

倘若非要添加一个自定义类型,你要实现Comparable,这个方法

2.不能插入NULL,不然会抛空指针

3.没有容量限制,内部会自动扩容

4.底层是使用了堆堆数据结构

5.默认是小堆

equal:所有的类继承自Object,所以直接覆写,但是只能比较是否相等

Comparable.compareTo:手动实现接口,对类的侵入性强,要在类的里面,一旦实现,每次用这个类,都有顺序,属于其内部顺序

Comparator.compare:实现一个比较器对象,对类的侵入性弱,可以仅仅写一个类的属性的比较,这样易扩展。

TOP-K问题(找到十个数字中,最小的5个数)

1.排序后取5个数字,就是最小的

2.堆,建立一个小根堆(建立一个堆O(N),弹一个元素要去调整->k*log(N)+O(N)

  static class Imp implements  Comparator<Integer>{
 
          @Override
          public int compare(Integer o1, Integer o2) {
               return o2-o1;
          }
     }
     public  static  int[] smallestK2(int []array,int k){
          
          int []ret=new int[k];
          if(k==0){
               return ret;
          }
          //PriorityQueue必须大于0
          PriorityQueue <Integer>maxHeap=new PriorityQueue<>(new Imp());
          for(int i=0;i<k;i++){
               maxHeap.offer(array[i]);
          }
          for(int i=k;i< array.length;i++){
               int top=maxHeap.peek();
               if(top>array[i]){
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
               }
          }
         
          for(int i=0;i<k;i++){
               ret[i]=maxHeap.poll();
          }
          return ret;
     }

怎么从小到大排序:要求数组本身有序

(堆很多都是反的情况)建立大根堆。

不断调整堆,然后堆顶和堆尾换(最后一个未排序的结果end)

1.交换

2.调整(0下标)

  /**
     * @param parent 每颗子树根节点
     * @param len    每个子树的结束位置
     */
    //向下调整,已知孩子下标len-1拿到,父亲节点(len-1-1)/2
    public void shiftDown(int parent, int len) {
        int child = parent * 2 + 1;
        //看他是否有左孩子
        while (child < len) {
            if(child+1<len){
            if(elem[child]<elem[child+1]){
                child=child+1;
            }
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[parent];
                elem[parent] =elem[ child];
                elem[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
 
 
//堆排序
    public void headSort(){
        int end=usedSize-1;
        while(end>0){
            //本身已经是一个大根堆
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);
            end--;
        }
    }

快速排序(N*log(N),好的情况(完全二叉树,正好均匀分割,不稳定的排序)

面试题的回答:

不断去找基准,然后去排序。

public class Sort {
 
    public void  quickSort(int []array){
        quick(array,0, array.length-1);
    }
    private static int parttion(int []array,int left,int right){
        int i=left;
        int key=array[left];
        while(left<right){
            //这里一定要有等于符号
            //测试用例:6,1,2,7,5,3,4,5,10,6    这个情况,left和right是一直不会动动
           //左边的key,要从右边开始先移动
//为什么先移动右边
//答案:为了避免平移交换过程中, pivot自己被交换掉。
            while(left<right&&array[right]>=key){
                right--;
            }
            while(left<right&&array[left]<=key){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }
 
    private static void swap(int[] array, int i, int left) {
        int tmp=array[i];
        array[i]=array[left];
        array[left]=tmp;
    }
 
    private static  void quick(int[]array,int start,int end){
        if(start>=end){
            return ;
        }
        int pivot=parttion(array,start,end);
 
        quick(array,0,pivot-1);//左树
        quick(array,pivot+1,end);//右树
    }
//挖坑法
 private  int pattion1(int []array,int left,int right){
        int tmp=array[left];
        while(left<right){
            while (left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
 
//快排非递归
   public   void  quickSort1(int[]array){
        //  使用栈
        Stack<Integer> stack=new Stack<>();
        int start=0;
        int end=array.length-1;
        int pivot=parttion(array,start,end);
        //至少有两个元素才可以入栈
        //保证左边
        if(pivot>start+1){
            stack.push(start);
            stack.push(pivot-1);
        }
        //保证右边
        if(pivot<end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
        while(!stack.isEmpty()){
            end= stack.pop();
            start=stack.pop();
            //弹出后,再去找基准
            pivot=parttion(array,start,end);
            if(pivot>start+1){
                stack.push(start);
                stack.push(pivot-1);
            }
            //保证右边
            if(pivot<end-1){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }
 
 
 
}

归并排序(N*log(N),空间复杂度O(N),稳定的排序)

ublic void mergeSort(int []array){
        mergeSortFunc(array,0,array.length-1);
}
private   void  mergeSortFunc(int[]array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
    //这两个相当于遍历到二叉树的最下面了
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        
        merge(array,left,mid,right);
}
public void merge(int[]array,int left,int mid,int right){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int []tmpArr=new int[right-left+1];
        int k=0; //tmpArr数组的下标
    while(s1<=e1&&s2<=e2){
        if(array[s1]<=array[s2]){
            tmpArr[k++]=array[s1];
            s1++;
        }else{
            tmpArr[k++]=array[s2];
            s2++;
        }
        k++;
    }
    while(s1<=e1){
        tmpArr[k]=array[s1];
        s1++;
        k++;
    }
    while(s2<=e2){
        tmpArr[k]=array[s2];
        s2++;
        k++;
    }
    //tmpArr放入所有有序的数据
    for(int i= 0;i<k;i++){
        array[i+left]=tmpArr[i];
    }
}
//归并非递归
    public void mergerSort(int[]array){
        int gap=1;
        while (gap<array.length){
            for(int i=0;i<array.length;i=i+gap*2){
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                //这个是进行合并的操作
                if(mid>array.length){
                    mid=array.length-1;
                }
                if(right>array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap=gap*2;
        }
    }
 


相关实践学习
基于CentOS快速搭建LAMP环境
本教程介绍如何搭建LAMP环境,其中LAMP分别代表Linux、Apache、MySQL和PHP。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
1月前
|
SQL Oracle 关系型数据库
mysql面试题库
mysql面试题库
|
19天前
|
SQL 关系型数据库 MySQL
java面试之MySQL数据库篇
java面试之MySQL数据库篇
24 0
java面试之MySQL数据库篇
|
28天前
|
存储 关系型数据库 MySQL
架构面试题汇总:mysql索引汇总(2024版)
架构面试题汇总:mysql索引汇总(2024版)
|
1月前
|
SQL 关系型数据库 MySQL
字节面试:MySQL自增ID用完会怎样?
字节面试:MySQL自增ID用完会怎样?
36 0
字节面试:MySQL自增ID用完会怎样?
|
19天前
|
SQL 关系型数据库 MySQL
mysql面试之分库分表总结
mysql面试之分库分表总结
35 0
|
27天前
|
SQL 关系型数据库 MySQL
【面试高频 time:】关于MYsql性能优化的理解
【面试高频 time:】关于MYsql性能优化的理解
28 0
|
28天前
|
存储 关系型数据库 MySQL
架构面试题汇总:40道题吃透mysql(2024版)
架构面试题汇总:40道题吃透mysql(2024版)
|
1月前
|
Java Android开发 Kotlin
Android面试题:App性能优化之Java和Kotlin常见的数据结构
Java数据结构摘要:ArrayList基于数组,适合查找和修改;LinkedList适合插入删除;HashMap1.8后用数组+链表/红黑树,初始化时预估容量可避免扩容。SparseArray优化查找,ArrayMap减少冲突。 Kotlin优化摘要:Kotlin的List用`listOf/mutableListOf`,Map用`mapOf/mutableMapOf`,支持操作符重载和扩展函数。序列提供懒加载,解构用于遍历Map,扩展函数默认参数增强灵活性。
21 0
|
18天前
|
存储 关系型数据库 MySQL
探索MySQL:关系型数据库的基石
MySQL,作为全球最流行的开源关系型数据库管理系统(RDBMS)之一,广泛应用于各种Web应用、企业级应用和数据仓库中
|
16天前
|
缓存 运维 关系型数据库
数据库容灾 | MySQL MGR与阿里云PolarDB-X Paxos的深度对比
经过深入的技术剖析与性能对比,PolarDB-X DN凭借其自研的X-Paxos协议和一系列优化设计,在性能、正确性、可用性及资源开销等方面展现出对MySQL MGR的多项优势,但MGR在MySQL生态体系内也占据重要地位,但需要考虑备库宕机抖动、跨机房容灾性能波动、稳定性等各种情况,因此如果想用好MGR,必须配备专业的技术和运维团队的支持。 在面对大规模、高并发、高可用性需求时,PolarDB-X存储引擎以其独特的技术优势和优异的性能表现,相比于MGR在开箱即用的场景下,PolarDB-X基于DN的集中式(标准版)在功能和性能都做到了很好的平衡,成为了极具竞争力的数据库解决方案。