🐶🐶 昂塞特

上周去面的，趁还不知道结果有心情还是发个面筋攒个人品吧：一共五轮，前四轮技术面，最后一轮论文discussion

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

总体来说第一轮有点懵反应很慢，中东小哥有点不懂他什么套路，要跪应该就这两轮了，希望能过吧....


补充内容 (2019-4-10 00:28):
多谢大佬指点，大伙儿走过路过赏点米啊~~

以LC 363为基础写了个第二题

1. #第二个阿三小哥，先问了问有什么interesting research的话题可以分享，然后开始做题：
   
2. # 又是一个二维矩阵代表cost，然后有个地产商要买地，他有一个budget limit，
   
3. # 求 < budget能买到的面积最大的rectangle，讨论了15min怎么做怎么优化，
   
4. # 15min写code，然后花了10min回答我的问题
   
5. 
   
6. def max_area_within_budget(mat, budget):
   
7.     if not mat: return 0
   
8.     m, n = len(mat), len(mat[0])
   
9. 
   
10.     res = 0
    
11.     for up in range(m):
    
12.         sumarr = [0] * n
    
13.         for down in range(up, m):
    
14.             for j in range(n):
    
15.                 sumarr[j] += mat[down][j]
    
16.             height = down - up + 1
    
17.             width = find_max_width(sumarr, budget)
    
18.             res = max(res, width * height)
    
19.     return res
    
20.    
    
21. def find_max_width(arr, k):
    
22.     res = 0
    
23.     curr = start = end = 0
    
24.     while end < len(arr):
    
25.         curr += arr[end]
    
26.         end += 1
    
27.         while curr > k:
    
28.             curr -= arr[start]
    
29.             start += 1
    
30.         res =  max(res, end - start)
    
31.     return res
    
32. 
    
33. import unittest
    
34. 
    
35. class TestMaxAreaWithinBudget(unittest.TestCase):
    
36. 
    
37.     def test_1(self):
    
38.         mat = [[1, 1, 3, 6], [2, 4, 10, 3], [1, 1, 9, 6]]
    
39.         k = 10
    
40.         print(max_area_within_budget(mat, k))
    
41.         assert max_area_within_budget(mat, k) == 6
    
42.         k = 4
    
43.         print(max_area_within_budget(mat, k))
    
44.         assert max_area_within_budget(mat, k) == 3
    
45. 
    
46.     def test_2(self):
    
47.         mat = [
    
48.             [10, 10, 10, 10],
    
49.             [11, 1, 2, 3],
    
50.             [21, 2, 3, 4],
    
51.             [40, 1, 9, 9]
    
52.         ]
    
53.         k = 4
    
54.         print(max_area_within_budget(mat, k))
    
55.         assert max_area_within_budget(mat, k) == 3
    
56.         k = 8
    
57.         print(max_area_within_budget(mat, k))
    
58.         assert max_area_within_budget(mat, k) == 4
    
59.         k = 15
    
60.         print(max_area_within_budget(mat, k))
    
61.         assert max_area_within_budget(mat, k) == 6
    
62.         k = 34
    
63.         print(max_area_within_budget(mat, k))
    
64.         assert max_area_within_budget(mat, k) == 9
    
65.         k = 10000
    
66.         print(max_area_within_budget(mat, k))
    
67.         assert max_area_within_budget(mat, k) == 16
    
68. 
    
69. unittest.main()

复制代码

第二题： 每一列从上到下 presum， 然后 每一行，双指针，扫描。 <target 的个数 * 深度 ， 就是面积。
              然后再从下到上 presum， 一样的再做一遍。
              就能找到最大面积。

第三题是不是利口maze兔bfs找最短？

第三个是类似滑冰那种，除非遇到障碍物，否则必须一直前进，遇到障碍物可以选择左拐或者右拐，或者说类似CTSC 2000冰原探险那种题目么= =...那道题的话是BFS找最短路

第二题怎么做的呢

第三题用分层图好了，第一层只能横走，第二层只能竖着走，转向的话就是两层之间跳。再加个BFS就行了。

楼主讲讲Q4?
另外Q1 did you clarify lake overflow? (WallWallRain312, from 3 can flow over 1 /2 to edge?)
Q2 range sum
Q3 if fail, should be double BFS look for joint set, each turn a step
Q4 ?

第3题是用MST来优化？

kaipeng21 发表于 2019-4-9 04:26
第二题怎么做的呢

LC 363

Gary.W 发表于 2019/04/09 07:40:22


LC 363

我竟然没做过。。。