全是线上面的，基础知识+文化面并不给安排onsite QAQ
以及答题的时候智商并不在线。

一面

项目 15min

• 判断无向图是否为二叉树。

bool Solve(int n, const vector<vector<int>>& edges) {
  if (n == 0) return true;

  vecotr<vector<int>> G(n);
  for (const auto& x : edges) {
      int& u = x[0], v = x[1];
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  vector<int> pre(n, 0);
  for (int i = 0; i < n; i++) {
      pre[i] = i;
  }

  function<int(int)> find = [&](int x) {
      return x == pre[x] ? x : pre[x] = find(pre[x]);
     };

  function<int(int, int)> unite = [&](int u, int v) {
      u = find(u); v = find(v);
    if (u == v) return 0;
    pre[u] = v;
    return 1;
  };

  bool ok = 1;

  function<void(int, int)> dfs = [&](int u, int p) {
    int tot = 0;
    for (int i = 0; i < G[u].size(); i++) {
        int& v = G[u][i];
      if (v == p) continue;
      if (!unite(u, v)) {
          ok = 0;
        break;
      }
      tot++;
      dfs(v, u);
    }
    if (tot > 2) {
        ok = 0;
    }
  };
  dfs(0, -1);

  int tot = 0;
  for (int i = 0; i < n; i++) {
      if (find(i) == i) tot++;
  }

  return ok && (tot == 1);
}

二面

• n个时间段，让你计算最多多少段时间相互不重叠，证明算法正确性？贪心 10min

int Solve(vector<vector<int>>& seg) {
    int n = seg.size();
  if (n == 0) {
      return 0;
  }
    sort(seg.begin(), seg.end(), [&](const vector<int>& a, const vector<int>& b) {
      if (a[1] == b[1]) return a[0] < b[0];
    return a[1] < b[1];
  });
  int ret = 1;
  int ed = seg[0][1];
  for (int i = 1; i < n; i++) {
      if (seg[i][0] >= ed) {
        ed = seg[i][1];
      ret++;
    }
  }
  return ret;
}

• n个点（1E6） ，给k个点，求这k个点的LCA？提到bitset维护状态，每次返回子树根merge，后来发现没必要维护具体点的出现状态，所以维护在k个点中的点数就可以。 15min

int Solve(int n, int root, const vecotr<vector<int>>& G, const vector<int>& query) {
    // G[i][j] = v: i的第j条边是v。 G: G[i][j] == G[j][i]
  int m = query.size();
  unordered_set<int> qset(query.begin(), query.end());
  int lca = root, ldep = -1;
  function<int(int, int, int)> dfs = [&](int u, int p, int dep) {
    int tot = 0;
      for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
      if (v == p) continue;
      int tmp = dfs(v, u, dep + 1);
      if (ldep != -1) return INT_MAX;
      tot += tmp;
    }
    tot += (qset.find(u) != qset.end());
    if (tot == m && dep > ldep) {
        ldep = dep;
      lca = u;
    }
    return tot;
  };
  dfs(root, -1, 0);
  return lca;
}

• 聊项目：复现的动漫头像生成器，10min

三面

• 聊项目：momenta的驾驶员疲劳监测，Google的MF Indexing 17min

• 一道题：N*M的矩阵，有障碍物。给起点和终点，问从起点到终点最少需要移除多少块障碍物。50min

  对空白缩点，重新建图跑堆优化dijkstra.

  using pii = pair<int, int>;
  
  const int dx[5] = {0, 0, 1, -1};
  const int dy[5] = {1, -1, 0, 0};
  
  int Solve(const vector<vector<int>>& G, int sx, int sy, int ex, int ey) {
      int n = G.size();
    if (n == 0) return 0;
    int m = G[0].size();
    vector<int> pre(n * m + 1, 0);
    int ret = 0;
  
    for (int i = 0; i < n * m; i++) {
        pre[i] = i;
    }
  
    function<int(int, int)> ok = [&](int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    };
  
    function<int(int, int)> id = [&](int x, int y) {
        return x * m + y;
    };
  
    function<pair<int, int>(int)> di = [&](int pos) {
        int x = pos / m;
      int y = pos % m;
      return make_pair(x, y);
    };
  
      function<int(int)> find = [&](int x) {
        return x == pre[x] ? x : pre[x] = find(pre[x]);
    };
  
    function<void(int, int)> unite = [&](int x, int y) {
        pre[find(x)] = find(y);
    };
  
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
        if (G[i][j] == 1) continue;
        for (int k = 0; k < 4; k++) {
          int xx = i + dx[k];
          int yy = j + dy[k];
            if (!ok(xx, yy)) continue;
          if (G[xx][yy] == 0) unite(id(i, j), id(xx, yy));
        }
      }
    }
  
    vector<pii> graph[n * m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
        for (int k = 0; k < 4; k++) {
          int xx = i + dx[k];
          int yy = j + dy[k];
            if (!ok(xx, yy)) continue;
          if (find(id(i, j)) == find(id(xx, yy))) continue;
          graph[id(i, j)].emplace_back(1, id(xx, yy));
          graph[id(xx, yy)].emplace_back(1, id(i, j));
        }
      }
    }
  
      vector<int> dis(n * m, 1E5);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dis[find(id(sx, sy))] = 0;
      pq.emplace(dis[find(id(sx, sy))], id(sx, sy));
      while (!pq.empty()) {
        pii cur = pq.top(); pq.pop();
      int w = cur.first, v = cur.second;
      for (int i = 0; i < graph[v].size(); i++) {
        int u = graph[v][i].second;
          int d = w + graph[v][i].first;
        if (dis[v] + d < dis[u]) {
            dis[u] = dis[v] + d;
          pq.emplace(dis[u], u);
        }
      }
    }
    return dis[find(id(ex, ey))];
  }
  

后面就是基础知识面+文化面了，基础知识面被疯狂问，还考系统设计题。文化面就是唠嗑，发现对面的tech lead在Google Beijing呆过于是枚举了几个G的熟人并八卦了一下在做啥（？）