实习面试记录

2020-03-27  本文已影响0人  抬头挺胸才算活着

参考资料：
[1]. 协程
[2]. 冒泡排序
[3.] Why Hashtable does not allow null keys or values?
[4.] redis的特点
[5.] 深度解读Tomcat中的NIO模型
[6.] Java线程池「异常处理」正确姿势：有病就得治
[7].HashMap工作原理和扩容机制
[8].MySQL 乐观锁与悲观锁

面试感悟：
1、大厂的实习面试比较偏重基础。
2、有时聊得好并不代表结果好，发现如果前面几个问题不能让面试官满意的话，那么后面可能就瞎扯起项目来，虽然感觉他们很感兴趣的样子，但其实就是他们在向下兼容你，走完整个面试流程。
3、知识的掌握很多还是不够扎实的话，很快就被问蒙了。
4、运气也是其中很大一部分，同学问到的都是前面准备好的问题，但却栽在心理面试上，我却被问到几个不懂的问题，前面问的问题全都没有被问到。

3.25 腾讯实习面试

  1. N个数据，每个都在N的范围里面，找两个重复数字，时间复杂度O(n)，空间复杂度O(1)

  1. 用过哪些数据库？表锁跟行锁的区别？
    MYSQL

  2. java垃圾回收机制
    参考：思维导图

  3. 三次握手有哪些攻击方式？
    Syn攻击就是 攻击客户端 在短时间内伪造大量不存在的IP地址，向服务器不断地发送syn包，服务器回复确认包，并等待客户的确认，由于源地址是不存在的，服务器需要不断的重发直 至超时，这些伪造的SYN包将长时间占用未连接队列，正常的SYN请求被丢弃，目标系统运行缓慢，严重者引起网络堵塞甚至系统瘫痪。
    Syn攻击是一个典型的DDOS攻击。检测SYN攻击非常的方便，当你在服务器上看到大量的半连接状态时，特别是源IP地址是随机的，基本上可以断定这是一次SYN攻击.在Linux下可以如下命令检测是否被Syn攻击。

  4. 进程线程协程的区别
    线程和进程的区别：进程包含线程，线程比进程要更轻量，进程切换的时候是操作系统级别；线程共享同一个进程的资源，而进程与进程之间是独立的。进程是资源分配的最小单位，线程是CPU调度的最小单位。
    协程：我的理解，在一个线程中控制函数的切换，“因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显。”，跟子函数有点像，但是运行的时候可以在子函数之间切换。
    优点：单线程，减少线程开销，不需要线程的锁机制。需要多核的时候，需要开启多个进程然后在每个进程里面开启一个协程。

  5. 进程通信方式+信号量的实现机制
    信号量，队列，共享内存，套接字
    共享内存：
    共享内存是进程间通信中最简单的方式之一。共享内存允许两个或更多进程访问同一块内存，就如同 malloc() 函数向不同进程返回了指向同一个物理内存区域的指针。当一个进程改变了这块地址中的内容的时候，其它进程都会察觉到这个更改。
    因为系统内核没有对访问共享内存进行同步，您必须提供自己的同步措施。例如，在数据被写入之前不允许进程从共享内存中读取信息、不允许两个进程同时向同一个共享内存地址写入数据等。解决这些问题的常用方法是通过使用信号量进行同步。

  6. TCP拥塞控制和流量控制区别
    都拥有一个窗口，拥塞控制是根据固定的流程自己计算出来，流量控制是接收方发送过来的。
    拥塞控制是为了避免网络流量过大，流量控制是为了协调接收方的缓存区大小。

3.27 阿里实习面试

1、Redis 是一个基于内存的高性能key-value数据库，
2、Redis最大的魅力是支持保存多种数据结构，此外单个value的最大限制是1GB，不像 memcached只能保存1MB的数据，支持list，集合等数据类型。
3、Redis也可以对存入的Key-Value设置expire时间，因此也可以被当作一 个功能加强版的memcached来用。（丰富的特性）
4、支持事务，操作都是原子性，所谓的原子性就是对数据的更改要么全部执行，要么全部不执行。
5、可以持久化。
6、memcached所有的值均是简单的字符串，redis作为其替代者，支持更为丰富的数据类型。

乐观锁（Optimistic Lock），顾名思义，就是很乐观，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在提交更新的时候会判断一下在此期间别人有没有去更新这个数据。乐观锁适用于读多写少的应用场景，这样可以提高吞吐量。
乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。
乐观锁一般来说有以下2种方式：
使用数据版本（Version）记录机制实现，这是乐观锁最常用的一种实现方式。
何谓数据版本？即为数据增加一个版本标识，一般是通过为数据库表增加一个数字类型的 “version” 字段来实现。当读取数据时，将version字段的值一同读出，数据每更新一次，对此version值加一。当我们提交更新的时候，判断数据库表对应记录的当前版本信息与第一次取出来的version值进行比对，如果数据库表当前版本号与第一次取出来的version值相等，则予以更新，否则认为是过期数据。
使用时间戳（timestamp）。乐观锁定的第二种实现方式和第一种差不多，同样是在需要乐观锁控制的table中增加一个字段，名称无所谓，字段类型使用时间戳（timestamp）, 和上面的version类似，也是在更新提交的时候检查当前数据库中数据的时间戳和自己更新前取到的时间戳进行对比，如果一致则OK，否则就是版本冲突。

1)Non-blocking IO（非阻塞IO）
IO流是阻塞的，NIO流是不阻塞的。
Java NIO使我们可以进行非阻塞IO操作。比如说，单线程中从通道读取数据到buffer，同时可以继续做别的事情，当数据读取到buffer中后，线程再继续处理数据。写数据也是一样的。另外，非阻塞写也是如此。一个线程请求写入一些数据到某通道，但不需要等待它完全写入，这个线程同时可以去做别的事情。
Java IO的各种流是阻塞的。这意味着，当一个线程调用 read() 或 write() 时，该线程被阻塞，直到有一些数据被读取，或数据完全写入。该线程在此期间不能再干任何事情了
2)Buffer(缓冲区)
IO 面向流(Stream oriented)，而 NIO 面向缓冲区(Buffer oriented)。
Buffer是一个对象，它包含一些要写入或者要读出的数据。在NIO类库中加入Buffer对象，体现了新库与原I/O的一个重要区别。在面向流的I/O中·可以将数据直接写入或者将数据直接读到 Stream 对象中。虽然 Stream 中也有 Buffer 开头的扩展类，但只是流的包装类，还是从流读到缓冲区，而 NIO 却是直接读到 Buffer 中进行操作。
在NIO厍中，所有数据都是用缓冲区处理的。在读取数据时，它是直接读到缓冲区中的; 在写入数据时，写入到缓冲区中。任何时候访问NIO中的数据，都是通过缓冲区进行操作。
最常用的缓冲区是 ByteBuffer,一个 ByteBuffer 提供了一组功能用于操作 byte 数组。除了ByteBuffer,还有其他的一些缓冲区，事实上，每一种Java基本类型（除了Boolean类型）都对应有一种缓冲区。
3)Channel (通道)
NIO 通过Channel（通道） 进行读写。
通道是双向的，可读也可写，而流的读写是单向的。无论读写，通道只能和Buffer交互。因为 Buffer，通道可以异步地读写。
4)Selector (选择器)
NIO有选择器，而IO没有。
选择器用于使用单个线程处理多个通道。因此，它需要较少的线程来处理这些通道。线程之间的切换对于操作系统来说是昂贵的。 因此，为了提高系统效率选择器是有用的。
3. AIO (Asynchronous I/O)
AIO 也就是 NIO 2。在 Java 7 中引入了 NIO 的改进版 NIO 2,它是异步非阻塞的IO模型。异步 IO 是基于事件和回调机制实现的，也就是应用操作之后会直接返回，不会堵塞在那里，当后台处理完成，操作系统会通知相应的线程进行后续的操作。
AIO 是异步IO的缩写，虽然 NIO 在网络操作中，提供了非阻塞的方法，但是 NIO 的 IO 行为还是同步的。对于 NIO 来说，我们的业务线程是在 IO 操作准备好时，得到通知，接着就由这个线程自行进行 IO 操作，IO操作本身是同步的。（除了 AIO 其他的 IO 类型都是同步的，这一点可以从底层IO线程模型解释，推荐一篇文章：《漫话：如何给女朋友解释什么是Linux的五种IO模型？》 ）
查阅网上相关资料，我发现就目前来说 AIO 的应用还不是很广泛，Netty 之前也尝试使用过 AIO，不过又放弃了。

拓展：Tomcat运用NIO
简单来说，LimitLatch控制连接的数量，Poller的线程轮询Acceptor，如果有新的事件，Poller好连接交给线程池去执行。


def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

if (map.contains(key)) {
    return map.get(key);
} else {
    throw new KeyNotFoundException;
}

4.4 腾讯实习面试初试

这次面试体验非常好，面试官循循善诱，给提示，问到你不会为止。

当map中包含的Entry的数量大于等于threshold = loadFactor * capacity的时候，且新建的Entry刚好落在一个非空的桶上，此刻触发扩容机制，将其容量扩大为2倍。（为什么2倍，而不是1.5倍，3倍，10倍；解释见最后的补充）
当size大于等于threshold的时候，并不一定会触发扩容机制，但是会很可能就触发扩容机制，只要有一个新建的Entry出现哈希冲突，则立刻resize。

2倍的原因

通过限制length是一个2的幂数，h & (length-1)和h % length结果是一致的。这就是为什么要限制容量必须是一个2的幂的原因。

StringBuffer is synchronized, StringBuilder is not.

堆：堆是Java对象的存储区域，任何用new字段分配的Java对象实例和数组，都被分配在堆上，Java堆可使用-Xms -Xmx进行内存控制，值得一提的是从JDK1.7版本之后，运行时常量池从方法区移到了堆上。

方法区：它用于存储已被虚拟机加载的类信息，常量，静态变量，即时编译器编译后的代码等数据，方法区在JDK1.7版本及以前被称为永久代，从JDK1.8永久代被移除。

虚拟机栈：虚拟机栈中执行每个方法的时候，都会创建一个栈帧用于存储局部变量表，操作数栈，动态链接，方法出口等信息。

本地方法栈：与虚拟机栈发挥的作用相似，相比于虚拟机栈为Java方法服务，本地方法栈为虚拟机使用的Native方法服务，执行每个本地方法的时候，都会创建一个栈帧用于存储局部变量表，操作数栈，动态链接，方法出口等信息。

程序计数器：指示Java虚拟机下一条需要执行的字节码指令。
以上五个区域是Java虚拟机内存划分情况，其中方法区和堆被JVM中多个线程共享，比如类的静态常量就被存放在方法区，供类对象之间共享，虚拟机栈，本地方法栈，pc寄存器是每个线程独立拥有的，不会与其他线程共享。

  1. 静态库对函数库的链接是放在编译时期完成的。
  2. 程序在运行时与函数库再无瓜葛，移植方便。

  3. 浪费空间和资源，因为所有相关的目标文件与牵涉到的函数库被链接合成一个可执行文件。
    为什么需要动态库，其实也是静态库的特点导致，空间浪费是静态库的一个问题。另一个问题是静态库对程序的更新、部署和发布页会带来麻烦。如果静态库liba.lib更新了，所以使用它的应用程序都需要重新编译、发布给用户（对于玩家来说，可能是一个很小的改动，却导致整个程序重新下载，全量更新）。
    动态库在程序编译时并不会被连接到目标代码中，而是在程序运行是才被载入。不同的应用程序如果调用相同的库，那么在内存里只需要有一份该共享库的实例，规避了空间浪费问题。动态库在程序运行是才被载入，也解决了静态库对程序的更新、部署和发布页会带来麻烦。用户只需要更新动态库即可，增量更新。
    动态链接：




    动态库特点总结：
    动态库把对一些库函数的链接载入推迟到程序运行的时期。
    可以实现进程之间的资源共享。（因此动态库也称为共享库）
    将一些程序升级变得简单。
    甚至可以真正做到链接载入完全由程序员在程序代码中控制（显示调用）。
    动态链接缺点：
    （1）当系统中多个应用程序都用了一个动态链接库，但是要求的版本不同，这时动态链接库之间就会相互干扰，容易出现dll地狱的问题。
    （2）性能开销。动态链接库为了做到“共享代码，但是不共享数据”，引入了不小的开销，调用动态链接库中的函数，需要好几次间接内存访问才能走到函数入口，全局数据也是。

什么是僵尸进程？
Unix进程模型中，进程是按照父进程产生子进程，子进程产生子子进程这样的方式创建出完成各项相互协作功能的进程的。当一个进程完成它的工作终止之后，它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。如果父进程没有这么做的话，会产生什么后果呢？此时，子进程虽然已经退出了，但是在系统进程表中还为它保留了一些退出状态的信息，如果父进程一直不取得这些退出信息的话，这些进程表项就将一直被占用，此时，这些占着茅坑不拉屎的子进程就成为“僵尸进程”（zombie）。系统进程表是一项有限资源，如果系统进程表被僵尸进程耗尽的话，系统就可能无法创建新的进程。
那么，孤儿进程又是怎么回事呢？
孤儿进程是指这样一类进程：在进程还未退出之前，它的父进程就已经退出了，一个没有了父进程的子进程就是一个孤儿进程（orphan）。既然所有进程都必须在退出之后被wait()或waitpid()以释放其遗留在系统中的一些资源，那么应该由谁来处理孤儿进程的善后事宜呢？这个重任就落到了init进程身上，init进程就好像是一个民政局，专门负责处理孤儿进程的善后工作。每当出现一个孤儿进程的时候，内核就把孤儿进程的父进程设置为init，而init进程会循环地wait()它的已经退出的子进程。这样，当一个孤儿进程“凄凉地”结束了其生命周期的时候，init进程就会代表党和政府出面处理它的一切善后工作。
这样来看，孤儿进程并不会有什么危害，真正会对系统构成威胁的是僵尸进程。
那么，什么情况下僵尸进程会威胁系统的稳定呢？
设想有这样一个父进程：它定期的产生一个子进程，这个子进程需要做的事情很少，做完它该做的事情之后就退出了，因此这个子进程的生命周期很短，但是，父进程只管生成新的子进程，至于子进程退出之后的事情，则一概不闻不问，这样，系统运行上一段时间之后，系统中就会存在很多的僵尸进程，倘若用ps命令查看的话，就会看到很多状态为Z的进程。
严格地来说，僵尸进程并不是问题的根源，罪魁祸首是产生出大量僵尸进程的那个父进程。因此，当我们寻求如何消灭系统中大量的僵尸进程时，答案就是把产生大量僵尸进程的那个元凶枪毙掉（通过kill发送SIGTERM或者SIGKILL信号）。枪毙了元凶进程之后，它产生的僵尸进程就变成了孤儿进程，这些孤儿进程会被init进程接管，init进程会wait()这些孤儿进程，释放它们占用的系统进程表中的资源，这样，这些已经“僵尸”的孤儿进程就能瞑目而去了。

如何避免这种问题
思路很简单。
1、在提交的任务中将异常捕获并处理，不抛给线程池。
2、异常抛给线程池，但是我们要及时处理抛出的异常。

第二种思路中，

  1. 可以继承ThreadPoolExecutor然后复写afterExecute方法。


  2. 利用线程工厂复写线程的UncaughtExceptionHandler


  3. ？？

  4. Future对象get的时候会抛出异常


4.26腾讯实习常规批

审题很重要！！
暴力解法也可以，至少可能有几率通过！！

启发：不懂的话可以暴力

import java.util.Scanner;
import java.util.Stack;

public class Queue {
    private static class Queue1{
        private Stack<Integer> stack1 = new Stack<>();
        private Stack<Integer> stack2 = new Stack<>();

        public void add(Integer num){
            stack1.push(num);
        }

        public Integer peek(){
            if(stack1.size()==0&&stack2.size()==0){
                return null;
            }

            if(stack2.size()==0){
                transfer1to2();
            }

            return stack2.peek();
        }

        public Integer poll(){
            if(stack1.size()==0&&stack2.size()==0){
                return null;
            }

            if(stack2.size()==0){
                transfer1to2();
            }

            return stack2.pop();
        }

        public void transfer1to2(){
            while(stack1.size()!=0) {
                stack2.push(stack1.pop());
            }
        }
    }

    public static void main(String[] args) {
        Queue1 queue = new Queue1();
        Scanner sc = new Scanner(System.in);
        Integer numLines = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < numLines; i++) {
            String line = sc.nextLine();
            String[] splits = line.split("\\s+");
            String op = splits[0].toLowerCase();
            if(op.equals("add")){
                Integer num = Integer.valueOf(splits[1]);
                queue.add(num);
            }else if(op.equals("peek")){
                Integer peek = queue.peek();
                System.out.println(peek);
            }else if(op.equals("poll")){
                queue.poll();
            }
        }
    }
}

import java.util.Scanner;


public class TreeParent {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long numQuery = sc.nextInt();

        for (int i = 0; i < numQuery; i++) {
            long childIndex = sc.nextLong();
            int parentDepth = sc.nextInt();
            System.out.println(getFather(childIndex, parentDepth));
        }
    }

    private static long getFather(long childIndex, int parentDepth){
        int childDepth = depthOf(childIndex);
        if(parentDepth>=childDepth){
            return -1;
        }else{
            int delta = childDepth - parentDepth;
            return childIndex >> delta;
        }
    }

    private static int depthOf(long index){
        int depth = 0;
        while(index>0){
            depth += 1;
            index /= 2;
        }
        return depth;
    }
}

4.29 华为实习面试

        Scanner sc = new Scanner(System.in);
        String M = sc.next();
        int k = sc.nextInt();

        for (int i = 0; i < k; i++) {
            String temp = M.substring(1);
            for (int j = 1; j < M.length(); j++) {
                String s = M.substring(0, j) + M.substring(j + 1);
                if(temp.compareTo(s)>0){
                    temp = s;
                }
            }
            M = temp;
        }

        System.out.println(M);

public class Main2 {
    private static int MAX = 100000000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int K = sc.nextInt(); // coin
        int N = sc.nextInt(); // city
        int R = sc.nextInt(); // road

        int[][] L_Matrix = new int[N][N];
        int[][] T_Matrix = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                L_Matrix[i][j] = 100000000;
            }
        }

        for (int i = 0; i < R; i++) {
            int S = sc.nextInt(); //1~N
            int D = sc.nextInt(); //1~N
            int L = sc.nextInt(); //长度
            int T = sc.nextInt(); //花费

            L_Matrix[S-1][D-1] = L;
            T_Matrix[S-1][D-1] = T;
        }

        smallestRoad(L_Matrix, T_Matrix, N, K);

        System.out.println(L_Matrix[0][N-1]);
    }

    private static void smallestRoad(int[][] L_Matrix, int[][] T_Matrix, int NumOfCity, int cost){
        for (int i = 0; i < NumOfCity; i++) {
            for (int j = 0; j < NumOfCity; j++) {
                for (int k = 0; k < NumOfCity; k++) {
                    if(L_Matrix[j][i]!=MAX&&L_Matrix[i][k]!=MAX){
                        int temp_L = L_Matrix[j][i] + L_Matrix[i][k];
                        int temp_T = T_Matrix[j][i] + T_Matrix[i][k];
                        if(temp_T <= cost){
                            if(L_Matrix[j][k] > temp_L ){
                                L_Matrix[j][k] = temp_L;
                                T_Matrix[j][k] = temp_T;
                            }else if(L_Matrix[j][k] == temp_L&&temp_T < T_Matrix[j][k]) {
                                    L_Matrix[j][k] = temp_L;
                                    T_Matrix[j][k] = temp_T;
                            }
                        }
                    }
                }
            }
        }
    }
}

4.30 哔哩哔哩实习面试

5.17 华为初面

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (getKthNum(nums1, 0, nums2, 0, l) + getKthNum(nums1, 0, nums2, 0, r)) / 2.0;
    }

因此题目转化为求两个有序数组第k排序。

    private static int getKthNum(int[] nums1, int start1, int[] nums2, int start2, int k) {
        if(start1 > nums1.length-1) return nums2[start2 + k - 1];
        if(start2 > nums2.length-1) return nums1[start1 + k - 1];

        if(k == 1) return Math.min(nums1[start1], nums2[start2]);

        // 一定一个数组的可用个数大于k/2的，不管怎么样，我们去掉前面k/2个
        int nums1Mid = start1 + k/2 - 1 < nums1.length ? nums1[start1 + k/2 - 1] : Integer.MAX_VALUE;
        int nums2Mid = start2 + k/2 - 1 < nums2.length ? nums2[start2 + k/2 - 1] : Integer.MAX_VALUE;

        // nums1 前k/2比较小，去掉，并调整k=k-k/2
        if(nums1Mid < nums2Mid)
            return getKthNum(nums1, start1 + k/2, nums2, start2, k-k/2);
        else
            return getKthNum(nums1, start1, nums2, start2 + k/2, k-k/2);
    }

5.24 腾讯正式批面试

  1. 介绍自己和项目

  1. 你用户登录是怎么样做的，如果用户登录只限定30min，怎么做？
    session过期，redis过期，延时队列删除掉对应用户的登录信息。

  2. CSRF攻击和CORS
    是谁控制了

  3. 写一个最熟悉的排序算法
    在面试官面前写代码的诀窍：乱的时候，想清楚思路是比较重要的，不要先动手，把各个细节想清楚在写。我写的时候，连冒泡排序都写错了，一开始马上就写出来两层for循环，然后很乱，不知道外层循环是干什么的，内层循环是干什么的，故在最里层操作的时候自然很难写对。
    冒泡

public class Bubble {
    public static void main(String[] args) {
        int[] array = new int[]{4,3,2,1};
        bubble(array);
        System.out.println(Arrays.toString(array));
    }
    
    static void bubble(int[] array){
        // 趟数
        for (int i = 0; i < array.length; i++) {
            // 每趟比较的次数
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j + 1]){
                    swap(array, j);
                }
            }
        }
    }

    static void swap(int[] array, int i){
        int temp = array[i+1];
        array[i+1] = array[i];
        array[i] = temp;
    }
}

  1. 你说你喜欢看源码，例子？
    应该说下IOC和AOP的，tomcat。

  2. 你还有什么擅长技术是我没有问到的吗？
    创造力，毅力（田径队，电子设计大赛4天3夜）

  3. linux 用过吗？怎么查看CPU占有率？系统调用CPU占用VS用户调用CPU占用？
    top

  4. IOC和AOP解释下

  5. 问问题？
    没问，为啥不问问实习做什么？

  6. 可以实习多久？

上一篇下一篇

猜你喜欢

热点阅读