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

刀大匙 新鲜电面

🔗
匿名用户-S1O1O  2021-7-14 05:46:19 |倒序浏览

2021(7-9月) 码农类General 硕士 全职@doordash - 猎头 - 技术电面  | | Other | 在职跳槽

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

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

x
10分钟前的新鲜面经, 一个湾湾小哥面的,在doordash待了三年半了已经。

题目比较有意思,感觉是小哥自己出的题, 有点类似简易版的word ladder II

题目大概就是说, doordash 送餐有几条路线, 让你求出从a 到b的最短路径

给你一个list of tuples
Road fr
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
要自己import library 和写test case。 尽量多和面试官沟通 把test case过一遍就没问题。

顺便再po一下我的代码哈


  1. import java.util.*;

  2. class Solution {
  3.      
  4.      public static void main(String[] args) {
  5.          Solution shortestPath = new Solution();
  6.          Map<Integer, List<Integer>> map = new HashMap<>();
  7.          map.put(0, Arrays.asList(1, 2, 1));
  8.          map.put(1, Arrays.asList(2, 3, 1));
  9.          map.put(2, Arrays.asList(3, 4, 1));
  10.          map.put(3, Arrays.asList(4, 5, 1));
  11.          map.put(4, Arrays.asList(5, 1, 3));
  12.          map.put(5, Arrays.asList(1, 3, 2));
  13.          map.put(6, Arrays.asList(5, 3, 1));
  14.          
  15.          List<Integer> cities = Arrays.asList(1, 2, 3, 4, 5);
  16.          
  17.          boolean[] res = shortestPath.shortestPath(map, cities);
  18.          
  19.          for (boolean used : res) {
  20.             System.out.println(used + ", ");
  21.          }
  22.      }
  23.      
  24.     // given a map of bidrectional routes
  25.     // find a shortest path
  26.     public boolean[] shortestPath(Map<Integer, List<Integer>> map, List<Integer> cities) {
  27.         // 1 (1, 2, 1)
  28.         // 1 -> [2, 1, 1]
  29.         Map<Integer, List<int[]>> graph = new HashMap<>();
  30.         
  31.         for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
  32.             int road = entry.getKey();
  33.             List<Integer> value = entry.getValue();
  34.             int from = value.get(0);
  35.             int to = value.get(1);
  36.             int weight = value.get(2);
  37.             
  38.             graph.computeIfAbsent(from, k -> new ArrayList<>()).add(new int[]{to, weight, road});
  39.             graph.computeIfAbsent(to, k -> new ArrayList<>()).add(new int[]{from, weight, road});
  40.         }
  41.         
  42.         // [city_id, sumOfWeight]
  43.         PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
  44.         Set<Integer> visited = new HashSet<>();
  45.         pq.offer(new int[]{cities.get(0), 0});
  46.         int targetCity = cities.get(cities.size() - 1);
  47.         int lowestWeight = 0;
  48.         
  49.         while (!pq.isEmpty()) {
  50.             int[] entry = pq.poll();
  51.             
  52.             if (entry[0] == targetCity) {
  53.                 lowestWeight = entry[1];
  54.                 break;
  55.             }
  56.             
  57.             visited.add(entry[0]);
  58.             
  59.             for (int[] neis : graph.get(entry[0])) {
  60.                 if (!visited.contains(neis[0])) {
  61.                     pq.offer(new int[]{neis[0], entry[1] + neis[1]});
  62.                 }
  63.             }
  64.         }
  65.         
  66.         boolean[] res = new boolean[map.size()];
  67.         
  68.         dfs(cities.get(0), targetCity, graph, lowestWeight, res, new HashSet<>());
  69.         return res;
  70.     }
  71.    
  72.     private void dfs(int from, int target, Map<Integer, List<int[]>> graph, int weight, boolean[] res, Set<Integer> roads) {
  73.         if (weight < 0) {
  74.             return;      
  75.         }
  76.         
  77.         if (from == target) {
  78.             for (int road : roads) {
  79.                 res[road] = true;
  80.             }
  81.         }
  82.         
  83.         for (int[] neis : graph.get(from)) {
  84.             // add the road
  85.             if (!roads.contains(neis[2])) {
  86.                 roads.add(neis[2]);
  87.                 dfs(neis[0], target, graph, weight - neis[1], res, roads);
  88.                 roads.remove(neis[2]);
  89.             }
  90.         }
  91.     }
  92. }
复制代码

评分

参与人数 11大米 +26 收起 理由
cccrrr + 1 给你点个赞!
zlatanismygod + 1 很有用的信息!
kevinkozj + 2 太赞了 必须给2米!
labour31 + 1 很有用的信息!
zlsc005 + 1 很有用的信息!

查看全部评分


上一篇:TikTok 两轮跪🧎‍♀️
下一篇:FB脸书新鲜VO终面挂经
全局:
好奇楼主 为什么结果有 1 → 5,1 → 2 → 3 → 5, and 1 → 3 → 5
就第一个来说from -> to 里面没有从1直接到5的,难道这个是无向图吗?还是楼主不小心写错了呀
回复

使用道具 举报

推荐
niubuzhi 2021-10-28 07:26:53 | 只看该作者
全局:
Super simple solution using python (please add rice if you like it!!!)
  1. def min_path(self, start, end, edges, n):
  2.         
  3.         from collections import defaultdict
  4.         
  5.         edge_map = defaultdict(list)
  6.         
  7.         for edge in edges:
  8.             parent, child, weight = edge
  9.             edge_map[parent].append((child, weight))
  10.             
  11.         visited = [0] * n
  12.             
  13.         def recur(node):
  14.             if node == end:
  15.                 return 0
  16.             if node not in edge_map:
  17.                 return -1
  18.             childs = edge_map[node]
  19.             
  20.             layer = []
  21.             for child, weight in childs:
  22.                 if visited[child-1]:
  23.                     continue
  24.                 visited[child-1] = 1
  25.                 tmp = recur(child)
  26.                 if tmp >= 0:
  27.                     layer.append(tmp + weight)
  28.             
  29.             if not layer:
  30.                 return -1
  31.             else:
  32.                 return min(layer)
  33.             
  34.         return recur(start)
复制代码

评分

参与人数 1大米 +1 收起 理由
狗狗舔狗 + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

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

使用道具 举报

🔗
l0ganic 2021-7-18 02:41:58 | 只看该作者
全局:
请问楼主DoorDash的电面是AUDIO ONLY吗? 我收到的电面邀请是这个,不知道做题还是就瞎聊?
回复

使用道具 举报

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

使用道具 举报

全局:
道理上的确不难,不过面试写这么多dijkstra + dfs backtracking 还是让人失心疯,尤其写Java的。。555
回复

使用道具 举报

🔗
hgon23 2021-8-24 05:34:23 | 只看该作者
全局:
这题按LeetCode难度应该是hard级别吧....
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-V5N3C  2021-8-30 23:52:51
同意啊,这题好难啊
回复

使用道具 举报

🔗
johnsysu 2021-9-8 06:01:58 | 只看该作者
全局:
今天面了同样的题。。太丧心病狂了。可能和楼主是一个面试官。
回复

使用道具 举报

🔗
vivan_66 2021-9-15 01:47:46 | 只看该作者
全局:
想问一下为什么不用bfs然后create一个专门的node class来存path
回复

使用道具 举报

🔗
jliu 2021-9-15 11:13:12 | 只看该作者
全局:
vivan_66 发表于 2021-9-14 13:47
想问一下为什么不用bfs然后create一个专门的node class来存path

空间占用太大,面试官估计会不满意
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-U77LM  2021-9-15 12:38:03
vivan_66 发表于 2021-9-14 10:47
想问一下为什么不用bfs然后create一个专门的node class来存path

问的好,
我米又限 什么也看不见,为什么不是一个start 和一个end 城市,怎么会是一个城市list?
回复

使用道具 举报

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

本版积分规则

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