首页 > [已意向] pony.ai 2020秋招 五轮技术面面试记录
头像
业余选手キライ!
编辑于 2020-10-28 18:26
+ 关注

[已意向] pony.ai 2020秋招 五轮技术面面试记录

全是线上面的,基础知识+文化面并不给安排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的熟人并八卦了一下在做啥(?)

更多模拟面试

全部评论

(15) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐