8月11日拼多多笔试

2017-08-12

× 文章目录

1. 一面：技术面
2. 二面：技术面
3. hr面

杭电到浙大玉泉，正午到黄昏，身心都有些疲惫辣。
面试经历记录如下，纪念人生第二次职业面试！

一面：技术面

聊一下项目

华为软件精英挑战赛 （简历上写了，可看我的这篇博客）

手写代码，一道算法题：给一棵二叉树加兄弟指针 。

ppdi1

思路：层次遍历，poll出的节点连向队列头。


public class interview1 {
    public TreeNode addSibling (TreeNode root) {
        if (root == null || (root.left == null && root.right == null))
            return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
            if (queue.isEmpty())
                cur.sibling = null;
            else
                cur.sibling = queue.peek();
        }
        return root;
    }
}

牛客网编程题的问题 ，第一题为什么用了Arrays.sort() 。
- 解释：通过了就没改，现场写了O(n)的做法。
CHROME给每个tab开了进程，为什么？其实就是问 线程与进程区别 ：
- 进程是具有一定独立功能的程序、它是系统进行资源分配和调度的一个独立单位，重点在系统调度和单独的单位，也就是说进程是可以独立运行的一段程序。
- 线程是进程的一个实体，是CPU调度和分派的基本单位，他是比进程更小的能独立运行的基本单位，线程自己基本上不拥有系统资源。在运行时，只是暂用一些计数器、寄存器和栈。
- 调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位。
- 并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可以并发执行。
- 拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源。
- 具体见 Java线程与线程、进程与进程之间通信方式
接着进程线程的问题，问 cpu怎么调度 ：
- 处理器调度总结
tcp、http关系 ：
- TCP协议是传输层协议，主要解决数据如何在网络中传输。而HTTP是应用层协议，主要解决如何包装数据。HTTP是基于TCP协议的。
- 我们在传输数据时，可以只使用传输层（TCP/IP），但是那样的话，由于没有应用层，便无法识别数据内容，如果想要使传输的数据有意义，则必须使用应用层协议，应用层协议很多，有HTTP、FTP、TELNET等等，也可以自己定义应用层协议。WEB使用HTTP作传输层协议，以封装HTTP文本信息，然后使用TCP/IP做传输层协议将它发送到网络上。
数据库事务概念 ：
- 事务是数据库中一个单独的执行单元（unit），它通常由高级数据库操作语言（如SQL）或编程语言（如C++、Java等）书写的用户程序的执行所引起。当在数据库中更改数据成功时，在事务中更改的数据便会提交，不再更改。否则，事务就取消或回滚，更改无效。
- 事务必须满足4个属性，即原子性(atomicity) 、一致性(consistency) 、隔离性(isolation) 、持久性(durability) ，即 ACID 4个属性。
- 具体见数据库常见知识总结

二面：技术面

再次聊项目

手写代码，算法题：给你一个函数rand6()，可以等概率随机产生1~6的数，要求你写一个函数rand7

google经典面试题，一种比较好理解的方法是，我调用rand6()两次，这样就有36种等概率的可能，取其中35种可能等分成7份，若得到第36种可能，则递归rand7()

public class interview2 {
  public int rand7() {
    int[][] n = {
            {1,2,3,4,5,6,1},
            {2,3,4,5,6,1,2},
            {3,4,5,6,1,2,3},
            {4,5,6,1,2,3,4},
            {5,6,1,2,3,4,5},
            {6,1,2,3,4,5,6},
            {1,2,3,4,5,6,8}
    };
    int res = 8;
    while (res == 8) {
      int i = rand6();
      int j = rand6();
      res = vals[i - 1][j - 1];
    }
    return res;
  }
}

算法题，程序安装时有依赖，打印安装顺序。例如1依赖2，2依赖3，则打印321。若有多个正确答案，输出一个即可

有向无环图，拓扑排序。leetcode210题。厅哥写了博文，后悔没看。可以BFS改写。

public int[] findOrder(int num, int[][] prerequisites) {
    if (num == 0) return null;
    // Convert graph presentation from edges to indegree of adjacent list.
    int indegree[] = new int[num];
    order[] = new int[num]
    index = 0;
    for (int i = 0; i < prerequisites.length; i++) // Indegree - how many prerequisites are needed.
        indegree[prerequisites[i][0]]++;    
    Queue<Integer> queue = new LinkedList<Integer>();
    for (int i = 0; i < num; i++)
        if (indegree[i] == 0) {
            // Add the course to the order because it has no prerequisites.
            order[index++] = i;
            queue.offer(i);
        }
    // How many courses don't need prerequisites.
    while (!queue.isEmpty()) {
        int prerequisite = queue.poll(); // Already finished this prerequisite course.
        for (int i = 0; i < prerequisites.length; i++)  {
            if (prerequisites[i][1] == prerequisite) {
                indegree[prerequisites[i][0]]--;
                if (indegree[prerequisites[i][0]] == 0) {
                    // If indegree is zero, then add the course to the order.
                    order[index++] = prerequisites[i][0];
                    queue.offer(prerequisites[i][0]);
                }
            }
        }
    }
    return (index == num) ? order : new int[0];
}

算法题，实现小顶堆插入操作，算法复杂度？

这里用数组表示小顶堆，插入小顶堆尾部，然后不断跟

public void HeapInsert(int[] heap, int n, int num) {
    int i, j;
    heap[n] = num;//num插入堆尾
    i = n;
    j = (n - 1) / 2;//j指向i的父结点
    //注意不要漏掉i!=0的条件。因为必须保证i有父结点j。j>=0并不能保证i!=0。
    //如果没有此条件，当i=0时，j=0,若heap[0]>num,程序就会陷入死循环。
    while (j >= 0 && i != 0)
    {
        if (heap[j] <= num)
            break;
        heap[i] = heap[j];
        i = j;
        j = (i - 1) / 2;
    }
    heap[i] = num;
}

hr面

和hr小姐姐聊得很开心。
最后小姐姐一直问我有什么要问的，我自知技术面表现不好，拼多多offer可能无望，不愿多问什么。
走出曹楼。
向毛爷爷轻诉一声：以后会常来。
告别玉泉。