历程

依图研发工程师面试经历

一面

依图是真的只面算法题，感觉回答的不太好，凉凉。

  • 先自我介绍一下吧
  • 比赛中印象中比较深的题？
  • 快排、归并、堆排那个快？
  • 基环树找环上的一个点（写代码）。
  • 给出两个非负整数 a 和 b ($a, b \le 10^9$)，进行 $10^{18}​$ 次操作，每次操作让小的数变为二倍，并且让大的数变为 a + b - 2 * a (假设 a 为较小的数)。

最后一个题知道解法后很简单，考虑最大的那个数做的变化，就是在 a + b 同余系下的乘二运算。

二面

没想到一面居然过了，之前面试完感觉凉凉，第二个问题疯狂提示才做出来。

  • 算法题

    • N 个数，其中一个只出现一次，其他出现两次，找出出现一次的数。

      异或和。

    • N 个数，其中两个只出现一次，其他出现两次。

      异或和后，按二进制的任意一个非零位划分，然后再求异或和。

  • 从 cache 的角度优化矩阵乘法。

    • 先写个矩阵乘法。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      void mat_mul(float *A, float *B, float *C, int N) {
      	for (int i = 0; i < N; i++) {
         		for (int j = 0; j < N; j++) {
                  C[i * N + j] = 0;
              	for (int k = 0; k < N; k++) {
                      C[i * N + j] += A[i * N + k] * B[k * N + j];
              	}
          	}
      	}
      }

    • 考虑访问 B 数组时，下标不是连续访问，进行优化。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      void mat_mul(float *A, float *B, float *C, int N) {
      	for (int i = 0; i < N; i++) {
          	for (int j = 0; j < N; j++) {
                  C[i * N + j] = 0;
              	for (int k = 0; k < N; k++) {
                      C[i * N + k] += A[i * N + j] * B[j * N + k];
              	}
          	}
      	}
      }

    • 考虑对于每一个 i 每次要遍历整个 B 数组，如果 cache 不能完整存下整个 B 数组时，cache 命中率可能会比较低。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      void mat_mul(float *A, float *B, float *C, int N) {
          for (int jj = 0; jj < N, jj += BLOCK) {
              for (int i = 0; i < N; i++) {
                  for (int j = jj; j < min(jj + BLOCK, N); j++) {
                      C[i * N + j] = 0;
                      for (int k = 0; k < N; k++) {
                          C[i * N + k] += A[i * N + j] * B[j * N + k];
                      }
                  }
              }
          }
      }

      加入分块优化，每次只计算 B 矩阵的 BLOCK 行对答案的贡献。（这里被面试官疯狂提示才理解）

  • 聊下你的项目吧，你选择聊哪一个？

    Web 聊天室，主要用到了多线程，线程间通信，网络编程技术。主要功能是客户端向服务器发送消息，服务器对所有客户端进行广播消息。服务器维护一个消息队列，存储客户端发送的消息，并使用互斥锁保证安全。

    • 你的服务器大概能承载多少用户，如何扩大承载量？

      我认为关键要优化服务器中的消息队列，多个线程对同一个元素进行互斥访问的效率特别差，我们考虑对每一个客户端开一个消息队列进行优化。（面试官提示了为了保证消息的顺序加一个时间戳比较好）

    • 你认为你这个项目中遇到的最难的问题是什么？

      WebSocket 协议的实现，刚开始我以为 WebSocket 协议和 TCP socket 一样，两者可以直接通信，后来才了解到 WebSocket 是一个应用层协议，需要对 TCP 协议进行分组，然后差了许多资料，包括 WebSocket 协议的数据帧，如何从 HTTP 协议升级到 WebSocket 协议等。

  • 我没有问题了，你有问题问我吗？

    • 进入公司后，我大概能学到什么东西，公司有什么培养计划？
    • 依图里是不是有好多 ACM 竞赛选手？