面试复盘|8.29~拼多多一面

一面：2021-08-29

自我介绍-提到开源组织，问我贡献，然而我只是学习者，无贡献，就过了~
询问擅长的语言：Java、python、C++
询问Java基础【10min】：Java的八种基本数据类型、装箱和拆箱、何时自动装箱、接口和抽象类的区别、Java多线程是否用过（我说了用过，然后主动说了线程创建的几种方式）、线程和进程的区别、共享资源如何定义、什么是死锁、Java中如何排查死锁（不知道）、如何避免死锁（破坏死锁的四个必要条件）、==和equals的区别、如何排查内存泄漏的问题（不知道）、你平时如何排查代码中的问题（我就说了最近项目中遇到的一个问题和我解决问题的方式）

手撕一【15min-over】：给定0~n这几个数字，和一个整数k，从0开始，删除第k个数字，循环数数并删除，直到数组只剩下一个数字的时候，输出这个数字。

既然是数字绕圈的形式，并且每次操作需要删除元素，我的思路就是用循环链表来处理，but我不熟悉Java中双向链表，emmmm，因此我无法用双向链表来构建循环链表。所以就自己定义了链表结构。考试时只能网页敲，并且网页不能运行，以下代码是我复盘在IDE上复现的当时代码，结果是对的：

class Node {
    int val;
    Node next;

    Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

public class Solution {
    public static void main(String[] args) {
        int n = 6, k = 2;
        // 构建循环链表
        Node head = new Node(0, null);
        Node cur = head;
        for (int i = 1; i < n + 1; i++) {
            cur.next = new Node(i, null);
            cur = cur.next;
        }
        cur.next = head;
        // 删除元素
        cur = head;
        while (cur.next != null) {
            int cnt = 0;
            Node pre = null;
            // 循环k次寻找待删除点
            while (cnt < k && cur.next != null) {
                pre = cur;
                cur = cur.next;
                cnt++;
            }
            // 删除current节点
            if (cur.next != null && cnt == k) {
                System.out.println("delete:" + cur.val);
                pre.next = cur.next;
                cur.next = null;
                cur = pre;
            }
        }
        System.out.println(cur.val);
    }
}

delete:2
delete:4
delete:6
delete:1
delete:5
delete:3
delete:0
0

面试官说不用写注释，直接写代码就可以。but，注释其实是给我自己理清思路看的，不是给他看的，emmmm

手撕二【30min-没写完】：给一个数组nums，顺序不能变；有两个人玩游戏，每一个人可以操作数组，然后会得到自己相应的分数，最后当数组再也无法操作时，游戏结束，输出两人分数之差。其中数组的操作方式：可以从数组的最左侧或最右侧取一个值（该值作为该玩家本轮的分数），或者可以禁掉最左侧/最右侧两个连续的值（本轮则没有得分）（禁掉或者取走都相当于从数组中删除）。甲乙两个人先后执行一个操作。

我的思路：
- 这个涉及到策略问题，甲乙两人相当于都有四种操作方式，每一局需要选择最优的策略，使得最后的总分更高一些。
- 用left、right标记数组当前左右操作的位置
  - 当数组没有剩余数字时，游戏结束，即left>right；
  - 当数组只剩下一个数字时，没必要禁掉，即right-left==0；
  - dfs暴力搜索