📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

到大时 interview

🔗
匿名用户-DSTDZ  2021-9-16 10:12:34 |倒序浏览

2021(7-9月) 码农类General 硕士 全职@doordash - 猎头 - Onsite  | 😃 Positive 😣 Hard | WaitList | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
都是高频面经题
幸亏之前过了一遍地里的帖子,虽然米不够看不全 还是有帮助,基本都cover 住了
share一下 希望有助于后面面的同胞, 如果有帮助请加米


第一轮俩题
第一题 选3个距离某个餐馆最近的k个dasher
用min heap 秒过


第二题 就是 最短距离的点  类似力扣 药七七旧   

   A number of cities are arranged on a graph that has been divided up like an ordinary Cartesian plane.
   Each city is located at an integral (x, y) coordinate intersection.
   City names and locations are given in the form of three arrays: c, x, and y, which are aligned by the index to provide the city name (c[i]), and its coordinates, (x[i], y[i]).

   Determine the name of the nearest city that
    - shares either an x or a y coordinate with the queried city.
    - If no other cities share an x or y coordinate, return 'NONE'.
    - If two cities have the same distance to the queried city, q[i], consider the one with first lexicographically order name (i.e. 'ab' < 'aba' < 'abb') as the closest choice.

   The distance is the Manhattan distance, the absolute difference in x plus the absolute difference in y.

我能作到O(NlogK+M*N)

地里有人提过这个题 我实现作了功课 所以很快就做完了
  public List<String> closestStraightCity(String[] citys, int[] xs, int[] ys, String[] queryCitys) {
    Map<String, int[]> cs = new HashMap<>(); // city name: (x,y)
    Map<Integer, TreeMap<Integer, String>> X = new HashMap<>();
    // x line:  y1: city2 name( < city1name)  y3: city3 name
    Map<Integer, TreeMap<Integer, String>> Y = new HashMap<>();
    // y line:  x1: city1 name, x2: city2 name

    int N = citys.length;
    for (int i = 0; i < N; i++) {
      int x = xs[i], y = ys[i];
      String name = citys[i];
      X.computeIfAbsent(x, k -> new TreeMap<>());
      if (!X.get(x).containsKey(y) || name.compareTo(X.get(x).get(y)) < 0) {
        X.get(x).put(y, name); // lexicographically order name
      }

      Y.computeIfAbsent(y, k -> new TreeMap<>());
      if (!Y.get(y).containsKey(x) || name.compareTo(Y.get(y).get(x)) < 0) {
        Y.get(y).put(x, name); // lexicographically order name
      }
      cs.put(name, new int[] {x, y});
    }

    Lis
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
  d(4, T) e(5, T)      g(7, T)

       New Menu sent by the Merchant:

                  a(1, T)
                /           \
            b(2, T)         c(3, T)
         /    |    \           \
      d(4, T) e(5, T) f(6, T)    g(7, F)

      Expected Answer: 2
      Explanation: Node f is a newly-added node.
                   Node g changed from Active to inactive

public int f(Node n1, Node n2) {
    int r = 0;
    if (n1 == null && n2 == null) return r;
    if (n1 == null || n2 == null || !equals(n2, n1)) r++;
    Map<String, Node> child1 = mapChildren(n1);
    Map<String, Node> child2 = mapChildren(n2);
    for (String k : child1.keySet()) {
      r += f(child1.get(k), child2.getOrDefault(k, null));
    }
    for (String k : child2.keySet()) {
      if (!child1.containsKey(k)) {
        r += f(null, child2.get(k));
      }
    }
    return r;
  }

  private static Map<String, Node> mapChildren(Node n) {
    Map<String, Node> map = new HashMap<>();
    if (n == null) return map;
    for (Node c : n.children) map.put(c.key, c);
    return map;
  }

  public boolean equals(Node n1, Node n2) {
    return n2.key.equals(n1.key) && n2.value == n1.value && n2.active == n1.active;
  }


花了很多时间讨论corner cases 和 什么叫diff
没时间作完第二道,第二道是   Patching Array 力扣原题

总的来说 题库不大,但是需要尽快些,还需要解决compile error  hackranker  真不习惯
如果事先没见过  当时思考的时间肯定不够, 确认理解问题就会花很多时间。
所以还是事先好好看看地里的帖子。
估计黄了
希望对后边的能有帮助  过关斩将
求米









评分

参与人数 9大米 +33 收起 理由
CASCAS + 1 给你点个赞!
HOMIE + 1 很有用的信息!
alphayan + 1 good
krystalHappy + 1 很有用的信息!
lestrois + 1 谢谢分享!

查看全部评分


上一篇:DRW OA
下一篇:申请面试推迟,然后hr说没有面试hc了?

本帖被以下淘专辑推荐:

推荐
guiguia 2021-11-6 04:47:50 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

地里匿名用户
推荐
匿名用户-DSTDZ  2021-9-16 13:24:10
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-FYKCU  2021-9-16 12:45:11
没面设计?
回复

使用道具 举报

🔗
jerrytan 2021-9-17 00:40:15 | 只看该作者
全局:
本帖最后由 jerrytan 于 2021-9-16 09:45 编辑

多谢分享! 被隐藏的部分不够米看。
有点好奇,所以楼主onsite是四轮里3轮coding,每轮coding 2道题,然后bh + sd压缩在一轮里?
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-DSTDZ  2021-9-17 09:22:19
jerrytan 发表于 2021-9-16 09:40
多谢分享! 被隐藏的部分不够米看。
有点好奇,所以楼主onsite是四轮里3轮coding,每轮coding 2道题,然后 ...

不知道怎么去掉米的限制,不同职位面试轮数应该不一样,面试内容和面试官有关,所以不用太关注这些,核心还是算法。
回复

使用道具 举报

🔗
Znedison 2021-9-22 10:41:00 | 只看该作者
全局:
第一轮第二题为啥有logk呀?最差应该就是mn吧
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-RTHAK  2021-10-18 03:10:42
最近city那题可以考虑用DP,能做到O(N)
回复

使用道具 举报

🔗
liyoulu 2021-10-21 02:35:07 | 只看该作者
全局:
匿名者 发表于 2021-10-17 11:10
最近city那题可以考虑用DP,能做到O(N)

具体怎么dp?
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-5PWE5  2021-10-31 15:40:25
第二题稍微改一下Dijkstra应该可以不需要dfs(如果都是positive的话), 每一层维护一个访问过的path, 只考虑到达n的最短路径就行.
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-JAKEN  2021-11-4 11:37:24
楼主收到offer了吗?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表