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

一面：2021-08-29

1. 自我介绍-提到开源组织，问我贡献，然而我只是学习者，无贡献，就过了~

2. 询问擅长的语言：Java、python、C++

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

4. 手撕一【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

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

   我的思路：

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