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

11月水卢狗昂赛

🔗
匿名用户-NYFU9  2019-11-18 10:25:16 |倒序浏览

2020(1-3月) 码农类General 硕士 全职@google - 网上海投 - Onsite  | | Other | 应届毕业生

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

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

x
4轮tech,1轮bq,有轮tech面的很差,很桑心,算是自行move on了。发个面经,求个大米,求接下来找工好运,早日上岸。我比较小白,今年第一个onsite,也求路过大神点评下这算是什么难度,先谢过了。

一轮刷题网84散, 一轮
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
选一个离所有种设施的距离最近的社区。这里距离不是距离和,是离当前街区最远的设施的距离。要求时间复杂度是街区个数乘设施种类数。

评分

参与人数 6大米 +16 收起 理由
adayxiang + 2 欢迎分享你知道的情况,会给更多积分奖励!
StupidCorn + 1 给你点个赞!
good-luck + 2 欢迎来一亩三分地论坛!
匿名用户-RSUGP + 7
yiliaobailiao + 3 给你点个赞!

查看全部评分


上一篇:亚麻BQ详解--BQ怎么问,到底在问什么?
下一篇:Peloton电面
推荐
hook5760 2019-11-22 07:00:26 | 只看该作者
全局:
最後一輪:
我的解讀是在2D matrix中,找出一點P(i, j),使得該點距離最遠的設施之距離和最小
P(i, j) is not unique, 可能有複數個點值相等, 不過回傳一個大概就可以了
min( SUM( max( dist( P(i, j) -  facility[f]  )  )  )  )

設施:f = 1, 2, 3, 4,....etc
0: available
1: restaurant
2: Gym
3: ....
4: .....etc
-1: blocked

mat = [
[1,0,0,0,0,0,1,0],
[2,0,0,0,0,0,0,0],
[0,0,0,-1,0,0,2,0],
[0,0,4,-1,0,0,0,0],
[0,0,0,-1,0,0,0,0],
[0,0,0,-1,0,0,0,0],
[0,0,3,-1,0,0,0,0],
[0,0,0,0,0,0,3,0]
]
# output: dist = 20, position = [1 3]
"""
[
[0, 28, 24, 22, 24, 28, 0, 38],
[0, 26, 22, 20, 22, 26, 30, 34],
[30, 26, 24, 0, 24, 28, 0, 36],
[30, 26, 0, 0, 26, 30, 34, 38],
[32, 28, 30, 0, 28, 32, 36, 40],
[34, 30, 32, 0, 30, 34, 38, 42],
[36, 32, 0, 0, 32, 36, 40, 44],
[36, 32, 30, 29, 32, 36, 0, 48]]
"""
import collections
def minMaxDistance(mat):
        m = len(mat)
        n = len(mat[0])
        shift = [-1, 0, 1, 0, -1]
        buildingNum = 0
        buildingFind = False
        dist = [[0 for _ in range(n)] for _ in range(m)]
        reach = [[0 for _ in range(n)] for _ in range(m)]
        d = collections.defaultdict(list)
        for i in range(m):
                for j in range(n):
                        if mat[i][j] != 0 and mat[i][j] != -1:
                                d[mat[i][j]].append([i, j])

        for key, val in d.items():
                maxDist = [[0 for _ in range(n)] for _ in range(m)]
                for i, j in val:
                        queue = collections.deque()
                        queue.append((i, j))
                        visited = [[0 for _ in range(n)] for _ in range(m)]
                        level = 1
                        while queue:
                                size = len(queue)
                                for _ in range(size):
                                        r, c = queue.popleft()
                                        for k in range(len(shift) - 1):
                                                nr = r + shift[k]
                                                nc = c + shift[k + 1]
                                                if 0 <= nr < m and 0 <= nc < n and mat[nr][nc] == 0 and not visited[nr][nc]:
                                                        queue.append((nr, nc))                                                       
                                                        maxDist[nr][nc] = max(maxDist[nr][nc], level)
                                                        reach[nr][nc] += key
                                                        visited[nr][nc] = 1
                                level += 1
                dist = [[dist[i][j] + maxDist[i][j] for j in range(n)] for i in range(m)]

        reachBuildingSum = 0
        for key, val in d.items():
                for i, j in val:
                        reachBuildingSum += key

        shortestDist = float("inf")
        pos = [0, 0]
        for i in range(m):
                for j in range(n):
                        if mat[i][j] == 0 and reach[i][j] == reachBuildingSum:
                                if dist[i][j] <= shortestDist:
                                        shortestDist = dist[i][j]
                                        pos = [i, j]

        return [shortestDist, pos]

print(minMaxDistance(mat))

补充内容 (2019-11-22 08:03):
time complexity: O(f * (traverse all elements in 2D) * (BFS)) = O(f * mn * mn) = O(f * m^2*n^2)
where f: category set of facilities
回复

使用道具 举报

推荐
novasu 2019-11-19 05:22:45 | 只看该作者
全局:
匿名者 发表于 2019-11-19 04:27
这个题不能dp,必须把所有可能路径都算出来,求个最小的。。

是这样的吗:
  1. class Solution {
  2.     int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  3.     int min = Integer.MAX_VALUE;
  4.     public int minPathSum(int[][] grid) {
  5.         boolean[][] visited = new boolean[grid.length][grid[0].length];
  6.         visited[0][0] = true;
  7.         dfs(0, 0, grid, visited, grid[0][0]);
  8.         return min;
  9.     }
  10.    
  11.     private void dfs(int i, int j, int[][] grid, boolean[][] visited, int distance) {
  12.         if (i == grid.length - 1 && j == grid[0].length - 1) {
  13.             min = Math.min(min, distance);
  14.         }
  15.         
  16.         for (int k = 0; k < 4; k++) {
  17.             int newX = i + dir[k][0];
  18.             int newY = j + dir[k][1];
  19.             if (isValid(newX, newY, grid, visited)) {
  20.                 visited[newX][newY] = true;
  21.                 dfs(newX, newY, grid, visited, distance + grid[newX][newY]);
  22.                 visited[newX][newY] = false;
  23.             }
  24.         }
  25.     }
  26.    
  27.     private boolean isValid(int i, int j, int[][] grid, boolean[][] visited) {
  28.         return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && visited[i][j] == false;
  29.     }
  30. }[/i]
  31. [i]
复制代码
[/i]
回复

使用道具 举报

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

使用道具 举报

🔗
小猴子 2019-11-18 12:19:36 | 只看该作者
全局:
加油呀! 顺便问楼主实在Sunnyvle吗
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NYFU9  2019-11-18 14:42:28
小猴子 发表于 2019-11-18 12:19
加油呀! 顺便问楼主实在Sunnyvle吗

不是呢 加拿大水卢
回复

使用道具 举报

🔗
novasu 2019-11-18 22:12:12 | 只看该作者
全局:
楼主能说一下第一轮面试官想要的答案吗,每一次两层for loop 找最少miss的单词吗?还有你建议直接说这个答案还是先说naive的那个。
楼主不要先放弃,感觉总体应该做的还不错还是很有机会的,感觉就算没做到最好的时间复杂度如果交流好的话也还行
回复

使用道具 举报

🔗
novasu 2019-11-18 22:15:42 | 只看该作者
全局:
还有楼主能讲一下第三轮什么思路,应该怎么写,因为上下左右都能走的话是不是不好用dp了
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NYFU9  2019-11-19 04:27:01
novasu 发表于 2019-11-18 22:15
还有楼主能讲一下第三轮什么思路,应该怎么写,因为上下左右都能走的话是不是不好用dp了

这个题不能dp,必须把所有可能路径都算出来,求个最小的。。
回复

使用道具 举报

🔗
novasu 2019-11-19 04:37:04 | 只看该作者
全局:
匿名者 发表于 2019-11-19 04:27
这个题不能dp,必须把所有可能路径都算出来,求个最小的。。

所以是直接dfs遍历所有路径吗?感觉时间复杂度很高啊,面试官有说需要更加efficient的方法吗还是直接说挺好的,会不会用bellman ford?
回复

使用道具 举报

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

使用道具 举报

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

本版积分规则

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