古狗新鲜VO挂经

第三題, 同 level 的 window 會有重疊嗎 ?如果沒有, 而且 level <= 31 的話, 我覺得可以用 bitmasking 來做

楼主可以把题目发在回复里面一遍，照顾我们这些没有米看帖，又心急找工作的人不？谢谢谢谢！

把题再发一遍,可能有些小伙伴没米看不了..不太清楚我没设置等级呀..

第一轮bq
第二轮: https://link.1point3acres.com/?u ... ate-Total-Wait-Time
用正常的方式写完之后,follow up了一下以数学题的角度来说怎么解决, 最小公倍数之类的.
第三轮: 给一个计算机屏幕, 比如左上角是(0,0), 右下角是(1920, 1080).
这其中有一些窗口, 给的也是这些窗口的左上角和右下角坐标(都是长方形), 比如 A:[(10,10), (50,50), 3], 最后那个参数3 是指这个窗口的相对位置, 也就是说数字越大代表这个窗口在更靠前的位置. 比如 B:[(25,25), (100,100), 4]. B这个长方形盖在A的上方.
求每一个window露出来的面积是多少.
第四轮: 类似蠡口 叁亿伍, 但是反过来找, count the smaller element before self.
第五轮: 类似蠡口 儿医义乌, 但是输入输出的格式全需要我自己问, 这个美国大哥给我的感觉不是很好,问三句回一句. 纠结了比较久的输入输出格式, 最后只是讲了一下思路, code没有完全写完.

danielff7 发表于 2022-5-4 15:44
第三題, 同 level 的 window 會有重疊嗎 ?如果沒有, 而且 level

同level理论上不会有重叠, 一旦重叠了, level肯定不一样的. 倒是没规定level<=31...

pususu2001 发表于 2022-5-4 11:46
提供一个第三题的思路，不知道有没有bug。

因为计算机屏幕的总面积是固定的（1920*1080）， 所以可以直 ...

同样面积为4, 正方形内只有9个grid points,L型有10个,从你算的点数不好计算面积

laplacecrame 发表于 2022-5-4 22:26
同样面积为4, 正方形内只有9个grid points,L型有10个,从你算的点数不好计算面积

哦对 那就不是iterate points而是iterate每个1x1的格子，总共1919*1079个格子，判断格子在哪个window里然后window面积+1. 思路应该是一样的。

pususu2001 发表于 2022-5-4 22:58
哦对 那就不是iterate points而是iterate每个1x1的格子，总共1919*1079个格子，判断格子在哪个window里然 ...

还有你的复杂度是 nlog(n)吧? 我觉得离谱的点在于brute force就是nlog(n)感觉并不能再优化了. 暴力解法应该就是把window按level sort了,然后按level从上到下过一遍,标记已覆盖的点

laplacecrame 发表于 2022-05-04 22:01:23
还有你的复杂度是 nlog(n)吧? 我觉得离谱的点在于brute force就是nlog(n)感觉并不能再优化了. 暴力解法应该就是把window按level sort了,然后按level从上到下过

hmmm好像确实是。。。

补充内容 (2022-05-05 23:44 +8:00):
其实稍微有点区别。brute force是O(1920*1080*n+nlogn), 我的解法是O(1080*nlogn). 理论情况1080  > logn所以右边会略优。实际情况如果窗口分散且面积偏小就是brute force更优。面试的时候如果想不到更优解就只能这样讨论一下trade off。

第一题n比较大的时候用binary search会比heap快

匿名者 发表于 2022-5-5 09:38
同level理论上不会有重叠, 一旦重叠了, level肯定不一样的. 倒是没规定level

發個我的 bitmasking 思路, 如果 同 level 會有不只一個 window , 那 record = defaultdict(list(tuple)) <- 必須確認所有同 level 的 end position

record 去紀錄 每個 window 的 end 座標, 用來判定當前的 i, j 是否需要 |= 這個 level

基本上就是每個 Matrix[x][y] 有被 cover 到的 就 |= (1 << level) 來表示 status (check Matrix[i-1][j] and Matrix[j-1]), 然後取最高位的表示當前的 位置是哪一個 window 的

def findAllVolume(query: list, Matrix: List[List[int]]):
    n = len(query)
    record = defaultdict(tuple)
    m, k = len(Matrix), len(Matrix[0])
    ans = {}
    for i, q in enumerate(query):
        Matrix[q[0][0]][q[0][1]] |= 1 << q[2]
        record[q[2]] = q[1]
    def update(status: int, i, j):
        cnt = 0
        for i in range(31, -1, -1):
            if (status & 1 << i) != 0:
                if i <= record[0] and j <= record[i][1]:
                    cnt |= 1 << i
        return cnt
    def findMaxCover(status: int) -> int:
        for i in range(31, -1, -1):
            if (status & 1 << i) != 0:
                return i
        return -1

    for i in range(m):
        for j in range(k):
            res= 0
            if i > 0:
                res |= update(Matrix[i-1][j], i, j)
            if j > 0:
                res |= update(Matrix[i][j-1], i, j)
            Matrix[i][j] |= res
            idx = findMaxCover(Matrix[i][j])
            if idx >= 0:
                ans[idx] += 1
    return ans[/i][/i][/i][/i]