虾皮

不难，都是常见问题

• 自我介绍

• 问实习项目

• MySQL索引存储是什么数据结构，如何选择

• Linux用过吗，查看资源利用率有哪些命令，你常用的有哪些命令（用的多的就是cat /proc/cpuinfo| grep xxx，还有top，ps -ef等。常用的主要就是grep，less，vim相关的，感觉如果再会sed和awk就很不错了）

• 输入网站链接到显示发生了什么过程（DNS解析-HTTPS建立连接-三次握手-浏览器解析HTTP报文并渲染-四次挥手，每个阶段都可以扯一堆）

• follow question，HTTP的状态码，四次挥手中的TIME_WAIT

• 平时怎么学习的（这不是hr的问题么哈哈）

• 有刷过题吗（？以前刷过，好久没刷了）

• 算法题：后序遍历+实现一个线程安全的单例模式（用的是双重校验锁的方式，然后讨论了下细节）

腾讯

• 自我介绍

• 说一下Java的垃圾回收

• go了解多少（了解基本语法，协程和锁用的多点）

• 说一下go的协程（开始扯，答得不好）go的协程是操作系统提供的吗

• 说一下项目中数据库的索引是怎么存的（B+树相关），你知道别的存储方式吗（说了MySQL的Memory存储引擎使用Hash存索引）实际上现在比较新的方案不再用B+树存储索引了（可以说一下吗）今天我们就不讨论这个了（补充了下Clickhouse之类的数据库用列式存储）

• 说一下数据量的MVCC（忘了，答得不好，往隔离级别上扯，说了能解决的并发一致性问题，还有MySQL中MVCC不能解决幻读，用了Next-Key锁）

• 长度为n的数组中存放着1-n的数，要么出现一次要么出现两次，不使用额外空间，在O(n)复杂度之内，找到所有的出现两次的数（把第i个数和位置等于它的值的元素交换，不难，但需要注意边界和细节，我最后用set返回）

• 实现LRU

import java.util.*;

public class LRU {
    static class Pair{
        String key;
        int number;

        public Pair(String key, int number) {
            this.key = key;
            this.number = number;
        } @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;

            if (number != pair.number) return false;
            return key != null ? key.equals(pair.key) : pair.key == null;
        } @Override public int hashCode() {
            int result = key != null ? key.hashCode() : 0;
            result = 31 * result + number;
            return result;
        }
    }

    int size;
    HashMap<String, Integer> map;
    //map中可以存指向链表的索引，这里是分开存的
    LinkedList<Pair> list;

    public LRU(int s){
        map = new HashMap<>();
        size = s;
    }

    public int get(String key){
        if (map.containsKey(key)){
            //将linkedlist中的该元素放到尾部
            Pair pair = new Pair(key,map.get(key));
            list.remove(pair);
            list.addLast(pair);
            return map.get(key);
        }
        return -1;
    }

    public void put(String str, int number){

        if (map.containsKey(str)){
            int oldVal = map.get(str);
            map.put(str, number);
            list.remove(new Pair(str,oldVal));
            list.addLast(new Pair(str,number));
        }else {
            if (list.size()<size){
                map.put(str, number);
                list.addLast(new Pair(str, number));
            }else {
                Pair pair = list.removeFirst();
                map.remove(pair.key);
                list.addLast(new Pair(str, number));
                map.put(str,number);
            }
        }

    }

    public static void main(String[] args) {

    }
}

没有问技术问题，全程围绕实习问

关于实习做的项目，怎么做的，解决思路等

实习涉及到k8s，一个pod在k8s中从创建到执行的全过程是什么，k8s的工作机制等

介绍实习项目中用到的算法

算法：求二叉树中两个节点的最近公共祖先，两个节点可能不一定在树中

public class Solution {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode find(TreeNode root, int A, int B){
        if (root==null)
            return null;
        if (isExist(root,A) && isExist(root,B))
            return _find(root, A, B);
        else
            return null;
    }

    private TreeNode _find(TreeNode root, int A, int B){
        if (root==null)
            return null;
        if (root.val==A || root.val==B)
            return root;
//        if (isExist(root.left, A)){
//            if (isExist(root.right, B))
//                return root;
//            else
//                return _find(root.left, A, B);
//        }else {
//            if (isExist(root.right, B))
//                return _find(root.right, A, B);
//            else
//                return root;
//        }
        TreeNode result = _find(root.left,A,B);
        if (result==null)
            return _find(root.right,A,B);
        else
            return result;
    }

    private boolean isExist(TreeNode root, int nodeVal){
        if (root==null)
            return false;
        if (root.val==nodeVal)
            return true;
        else
            return isExist(root.left, nodeVal) && isExist(root.right, nodeVal);
    }
}

小米金融（天星金融） 用户增长部

一面

• 自我介绍

• 已经有这个实习经验了，为什么还要找实习（技术栈不匹配）

• Spring用过吗（本科用过，现在好久没用忘得差不多了）Spring的AOP知道吗（说了大概）

• 假如现在让你设计一个缓存，你有什么思路（答了用Redis，但面试官想知道如何用AOP来完成，之后引导了我半天才回答到点上）

• 那如果缓存里面的元素比较复杂呢，比如包括多种元素（可以转成Json存到Redis。。。）

• 知不知道Swift RPC（不知道，没用过RPC，说了下对RPC的理解）

• 那假如考虑到RPC，刚才的缓存你会怎么设计（开始扯，序列化，或者传回来一些元素在用户端组合（这个我都不知道对不对），都想往CDN上扯）

• 考虑刚才的AOP，如果我要用它来实现一个缓存，应该怎么做（说了用AOP可以在方法的执行前后输出日志，并不知道怎么做）你说可以在方法执行前后执行一些逻辑，那么缓存可以怎么设计（幡然醒悟，可以在方法执行之前先在缓存中查看有无数据）那如果没数据呢（在方法执行之后把结果返回，并在缓存中放一份）

• 实习的时候用的是什么系统（Linux，CentOS）我们也是，那么如果查看日志用什么命令（用的最多的是查看K8s组件的日志：kubectl logs -n xxnamespace xxpod，如果查看其他的文件日志的话，量比较小可以用cat，比较多可以用tail，流式输出可以用tail -f）那么如果对不断写入的日志中查看和error相关的日志，怎么做（可以用管道在tail后加上grep，但我不知道这样行不行，因为我一般是两个分开用的）是可以一起用的，那么你对grep的高级用法看起来不是特别熟（是的，一般就用了-i忽略大小写和-e正则表达式）如果想查看查找的内容的前几行或后几行日志用什么（不知道）用-a看之后的，after，用-b看之前的，before，用-c同时看前后的，可以了解下（好的）

• 那么问题来了，现在请编程实现一个grep -c的功能。

grep -C5 “ERROR”
编程实现
public void grepC(List<String>content, int n, String keyword)

--------

import java.util.*;
public class Main {

    public void grep(List<String>content, int n, String keyword){
        if(content.size()<1){
            return;
        }
        ArrayList<Integer> lines = new ArrayList<>();
        for(int i=0;i<content.size();i++){
            if(content.get(i).contains(keyword)){
                lines.add(i);
            }
        }

        System.out.println(lines);
        int cur = 0;
        int start = 0;
        for(int i=0;i<lines.size();i++){
            if(lines.get(i)-n<cur){
                start = cur;
            }else{
                start = lines.get(i)-n;
            }
            for(int j=start;j<n+lines.get(i);j++){
                if(j<content.size()){
                    System.out.println(content.get(j));
                    cur++;
                }else
                    return;
            }
        }
    }

    public static void main(String[] args) {
        List<String>content = new ArrayList<>();
//        content.add("hello");
//        content.add("hello");
//        content.add("he world llo");
//        content.add("hello");
//        content.add("hello");
        content.add("hello");
        content.add("he world llo");
        content.add("he wd llo");
        content.add("hel world lo");
        content.add("hello");
        new Main().grep(content,1,"world");
    }
}

• 最后一个小问题，MySQL中索引可以包括多个字段吗（可以，这就是联合索引）它们的顺序不同会有区别吗（有，说了最左匹配）

• 你有什么问题吗

  • 所在部门及业务（见标题）

  • 技术栈（Java，HBase，数据库就是MySQL，Redis，RPC框架就是之前说的Swift RPC）

  • 您的一天是怎么度过的（这个问题绝了，本来问完前面两个标准问题就可以结束了，但我想着大胆一把就问了，然后面试官沉吟两秒，说我们这边一般九点上班，晚上六点就差不多下班了，加班的情况还好...我连忙打住，说，那个，我指的是你们部门项目上线的大概工作流程之类的 :P 面试官说就是正常的开发，然后邮件通知可以上线，然后会看一些监控数据之类的。）

二面

• 自我介绍

• 聊项目

• Linux会哪些命令

• 算法：多个有序链表的合并 public Node merge(List<Node> nodeList)

//思路：简单粗暴地全放到优先队列中，然后出队直到空
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {
    static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node() {
        }
    }
    //多个有序链表的合并
    public Node merge(List<Node> nodeList){
        Node dummyNode = new Node();
        Node ptr = dummyNode;
        PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() { @Override public int compare(Node o1, Node o2) {
                return o1.value-o2.value;
            }
        });
        for (int i = 0; i < nodeList.size(); i++) {
            Node node = nodeList.get(i);
            while (node!=null){
                queue.add(node);
                node = node.next;
            }
        }
        while (!queue.isEmpty()){
            Node newNode = queue.poll();
            ptr.next = newNode;
            ptr = ptr.next;
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(3);
        Node n3 = new Node(5);
        Node n4 = new Node(2);
        Node n5 = new Node(4);
        Node n6 = new Node(6);
        n1.next = n2;
        n2.next = n3;
        n4.next = n5;
        n5.next = n6;
        List<Node> list = new ArrayList<>();
        list.add(n1);
        list.add(n4);
        Node result = new Solution().merge(list);
        while (result!=null){
            System.out.print(result.value+"->");
            result = result.next;
        }
        System.out.println("NULL");
    }
}

• follow question：时间复杂度是多少？（O(NlogN)，其实我也不确定...）

• 一个数组有序存放着1-n，现在对数组中的数进行操作如下：若能被2整除，则除2；若不能，则置为0。问经过若干***作后，最后一个非0的值是多少？说思路（开始想到按n的奇偶情况分类，后来想到二叉树就知道了，比如深度为4的满二叉树，叶子节点数目为8，经过一***作后，深度变成3，第四层叶子节点中的右子树晋升成第三层的叶子结点，以此类推。也就是说如果n是2的整数次幂（也就是说logn为整数），那么最后一个非0的值就是最后一个元素。如果不是2的整数次幂，就只考虑前2的整数次幂的元素即可，因为可以想象一下深度为5的完全二叉树，第5层的节点数目为10，一***作后，右叶子结点晋升到第4层，继续操作，当晋升到第3层的时候，第4层的最后一个节点，也就是5，因为属于左侧节点，所以被淘汰。因此只需考虑前2的整数次幂的元素。综上所述，经过的操作次数为logN向下取整次，也就是⌊logN⌋，那么根据满二叉树的高度和叶子结点数目的关系，答案就是2^⌊logN⌋-1次。）

• 反问

字节跳动海外电商

一面

• 自我介绍

• 实习相关，做了哪些事情，是什么思路，做的东西上线了么（上线了一部分）

• MySQL会不会，索引是怎么存储的（B+）为什么是B+

• 来写个SQL，一个图书馆里有很多书，有读者来看书，每个读者可以给任何一本书打标签。指定一本书的ID，求这本书最热门的10个标签。（先讨论了下表结构，可以是|readers|bookid|tag|，然后就是select tag from table where bookid=“xxx” group by tag order by xxx desc limit 10，写得有点问题，面试官说没事，大概思路对就行）

  正确写法：

SELECT
	tag,
	count(tag)
FROM
	readertagtable
WHERE
	bookid = 1
GROUP BY
	tag
ORDER BY
	count(tag) DESC
LIMIT 10

• 数组a，先递增再递减，输出数组中不同元素个数。要求O(1)空间复杂度，尽可能小的时间复杂度，不能改变原数组。比如1 2 4 6 3 2 2 输出 5

//用碰撞指针做
public int findDiffNum(int[] numbers){
        if (numbers.length<2){
            return numbers.length;
        }
        int left = 0;
        int right = numbers.length-1;
        int result = 1;

        while (left<right){
            if (numbers[left]<numbers[right]){
                result++;
                left++;
            }else if (numbers[left]>numbers[right]){
                result++;
                right--;
            }else {
                int temp = numbers[left];
                while (left<right && numbers[left]==temp){
                    left++;
                }
                while (left<right && temp==numbers[right]){
                    right--;
                }
                if (numbers[left]!=numbers[right]){
                    result++;
                }
            }
        }
        return result;
    }

• 反问：部门什么业务，答抖音海外电商，问可以再详细点么，答涉及的方面很多，来的话会被分到更加具体的部门

• 让我等一下，联系二面面试官继续面试，加快速度

• 自我介绍

• 操作系统中的进程是怎么切换的（脑子一片空白，操作系统不熟。。。答保存上下文，还有线程用到的信息，比如加载的类信息，局部变量，执行到哪里之类的，扯到了jvm内存区域，然后被问为什么局部变量不在堆中保存而在jvm栈中，之前应该答错了，然后含糊答了一通）

• 什么是中断

• CPU只知道执行，怎么知道运行哪个进程（操作系统调度，时间片轮转，fifo，先来先调度，lru之类的）

• 说一下ARP攻击（不太会，但是知道ARP是根据ip找到mac的，所以或许可以通过这种方式来窃取mac地址）

• HTTP请求报文的结构（忘了）首部都有哪些字段？（忘了，憋出来一两个）

• Linux命令，一个文件中有记录着若干用户登录的ID，不同用户可能登录多次，如何统计每个ID的次数？（说用wc，然后写不出来。后来查了下，要想用wc做到这一点，可能需要用shell脚本，先获取所有id，然后grep+wc逐一查找。这样比较麻烦，可以使用sort user.log|uniq -c来统计。如果要按次数排序就是sort user.log|uniq -c|sort -rn。（sort -n可以识别每行开头的数字，并按其大小对文本行进行排序。默认是按升序排列，如果想要按降序要加-r选项 。另外为什么uniq要和sort配合使用，因为uniq命名用于比较相邻的行并去掉重复的行，对不相邻的行无效。所以如果输入文件中的id是乱序的，uniq是无效的）也可用awk，更简洁难度也更大些。参考：https://blog.csdn.net/cy413026/article/details/91490714）

• 一个岛上有红黄蓝三种颜色的兔子，数目分别为abc，任意两种不同颜色的兔子，碰撞后可以变成两只另一种颜色的兔子，请问abc满足什么条件时，经过若干次碰撞以后只剩下一种颜色的兔子？（回答得不全，分了3个case：假设a>b，那么ab变成c之后，三种颜色兔子数目为a-b，0，2b+c，case1：a-b=0 => a=b；case2：2b+c=0，=> b=c=0，case3：a-b=2b+c => a=3b+c。面试官指出case2包含于case1，并且1 4 2的数目组合并不满足case3。分析了一波是因为这种情况没有全部碰撞4和2，而是只碰撞了一次然后又进行别的碰撞。然而还是没有答出来正确做法。）

  （正确答案：通过某些变换，可以达到3k条a1变色龙，n+k条a3变色龙，就说明条件满足。参考：https://developer.aliyun.com/article/466252）

• 乱序数组，任意选出一个数x删除，同时删掉值为x-1和x+1的元素，这样可以得到x分。重复此操作直到删完数组，问最多能有多少分。比如1 3 3 4 4 5 5，先删除1个5，此时4没有了；再删除1个5；再删除1个3，再删除1个3，最后删除1，总分就是17分。（没思路，刚开始答先排序后，从后往前进行贪心删除，被面试官举例否了，又说每次删除前遍历一次找到最高得分的数删除，也不对，后来面试官说动态规划，然而刷题少了还是不会，面试官提示写出状态转移方程，刚开始状态方程写了3个参数，后来面试官说一维的就可以，写出了下面的，但还是有问题，时间关系就先结束了）

if num[n+1]==num[n]:
	dp(0,n+1)=dp(0,n)+num[n+1]
if num[n+1]==num[n]+1:
	dp(0,n+1)=dp(0,n)+1
if num[n+1]>num[n]:
	dp(0,n+1)=dp(0,n)+num[n+1]

• 反问：对于我接下来的学习有没有什么建议？（和你接触不太多，没法给出建议）