WXG 后台开发2面面经

First interview

program

1. 给定一个有序的双向环形链表，插入一个新节点，使得插入后依然有序（head指针指向最小的节点）

2. 给定一个数组，有正数，负数，求和最大的连续子序列（子序列大小>=0）

• 详细问的时候要我改求和为 -> 连续子序列的的 index

system design

实时输出最近一个小时内访问频率最高的10个IP，要求：

实时输出

从当前时间向前数的1个小时

QPS可能会达到10W/s

public class Node {

    int val;

    Node next = null;

    Node pre = null;

    Node(int val) {

        this.val = val;

    }

}

public class One {

    public Node insert(Node head, int num) {

        Node node = new Node(num);

        if (head == null) {

            node.next = node;

            node.pre = node;

            return node;

        }

        Node p = head;

        if (num <= head.val) {

            Node tmp = p.pre;

            node.next = head;

            node.pre = tmp;

            tmp.next = node;

            head.pre = node;

            return node;

        }

        Node c = head.next;

        while (c.val > head.val && c.val < num) {

            p = c;

            c = c.next;

        }

        p.next = node;

        c.pre = node;

        node.pre = p;

        node.next = c;

        return head;

    }

}

public class Two {

    public int findMaxSum(int[] arr) {

        if (arr == null || arr.length < 1) return 0;

        int max = Integer.**MIN_VALUE**;

        int cur = 0;

        for (int i : arr) {

            if (cur <= 0) {

                cur = i;

            } else {

                cur += i;

            }

            if (max < cur) {

                max = cur;

            }

        }

        return max;

    }

}

*/***

 ** 第三题*

 ** top k -> 用count建堆*

 ** 淘汰问题 -> 每过one s就要淘汰one hour前的one s，每秒 减去一小时前1s的count*

 **          核心问题：怎么维护与时间有关的这个特点*

 **          3600 s*

 **          以秒为粒度，如果用数组模拟Hash节约空间，内存不太够用*

 **          qps \* second_sum \* arr_byte \* count*

 **          如果粒度更小，内存所需更大，不太可行。*

 **          要使其可行的话，减小时间粒度*

 **          为了节约空间，每秒改用前缀树//不行，前缀树应该没有数组更节约空间*

 ** 10W/s -> 360000000 one hour*

 ** 在线查询 -> 返回堆的前10个*

 **/*

• 问了raft
  • 讲了raft状态机
  • 讲了日志同步一块的问题
• 讲了学校项目中缓存不一致的解决办法
• TCP状态机
• 输入URL
  • HTTPS
  • DNS
  • IP -> OSPF / BBR / BGP
  • ARP
  • NAT地址转换
  • DHCP

Second Interview

题目面试官封了

40分钟4题

具体4道A了3道

前两道是lc原题

• 回文链表

• 大数乘法

• 还有个啥忘了

• 趣题：N个小伙伴过桥 cost is A[i]，最多2个人过，cost为max(A[i],A[j])，过桥需要手电筒，只有一个，过岸后手电筒必要有人带回

Specific

• 问6.828 -> 问了点后，觉得这个是完形填空，就没问了
• 问了些Linux比较细节的问题，具体记不清了
• Raft是几阶段提交 -> 肯定不是2PC，答曰3PC，其实都不是

挂