古狗新鲜VO挂经

新鲜的挂经 T_T
第一轮bq

第二轮: https://leetcode.com/discuss/int ... ate-Total-Wait-Time
用正常的方式写完之后,follow up了一下以数学题的角度来说怎么解决, 最小公倍数之类的.

第三轮: 给一个计算机屏幕, 比如左上角是(0,0), 右下角是(1920, 1080).
这其中有一些窗口, 给的也是这些窗口的左上角和右下角坐标(都是长方形), 比如 A:[(10,10), (50,50), 3], 最后那个参数3 是指这个窗口的相对位置,

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

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

了一下思路, code没有完全写完.

LZ比较菜, 这一波面下来整个人崩溃了, 感觉好难, 欢迎大家留言讨论一下这些题的做法和思路T_T....尤其是第3,4题..

祝大家面试成功!!  加油加油!! 另求一些大米! 感激不尽!~~

第三題想了一下, 應該算 LC 2158 的變種吧 , 2D 的 2158
2158 有一種解法是用 把每一個區間的點當成 key, 然後 end 的點存成 value, 這樣就可以避免重複
->
class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        ans = []
        seen = {}
        for start, end in paint:
            cnt = 0
            while start < end:
                if start in seen:
                    start = seen[start]
                else:
                    seen[start] = end
                    cnt += 1
                    start += 1
            ans.append(cnt)
        return ans

所以應該只要把每一個 row 當成一個 2158 的 1D array,  然後 sort window array, 讓 size 數字越大的越先處理, 這樣應該可以更簡化一些 ?
def findAllSquare(self, squares: list, windows: List[List[int]]):
    # each item in squares is like [(startx, starty), (endx, endy), size]
    record = defaultdict(int)
    squares.sort(key=lambda x: -x[2])
    counter = defaultdict(int)
    for i, s in enumerate(squares):
        endy = s[1][1]
        j = s[0][1]
        for i in range(s[0][0], s[1][0]+1):
            while j <= s[1][1]:
                if (i, j) in record: # 已經有更大的size 直接跳到 結束的點
                    j = record[(i,j)]
                else:
                    windows[i][j] = s[2] # 還沒有更大的size, record當前的size
                    record[(i,j)] = endy+1
    for i in range(len(windows)):
        for j in range(len(windows[0])):
            counter[windows[i][j]] += 1
    return counter

提供一个第三题的思路，不知道有没有bug。

因为计算机屏幕的总面积是固定的（1920*1080）， 所以可以直接iterate所有点然后找每个点所在的window。对于每一个y来说，windows相当于一个list of 1d intervals。所以找window可以sort windows by x然后用two pointer。Priority queue用来优先选level更高的window。时间复杂度O(1920*1080*log(n)).


def calculateAreas(windows):
    windows.sort(key=lambda window: window[0][0])
    areas = [0] * len(windows)
    for y in range(1080):
        x, i = 0, 0
        pq = []
        while x < 1920 and (pq or i < len(windows)):
            while i < len(windows) and windows[0][0] <= x:
                heapq.heappush(pq, (-windows\[i\][2], windows\[i\], i))
                i += 1
            while pq and not contains(pq[0][1], x, y):
                heapq.heappop(pq)
            if pq:
                areas[pq[0][2]] += 1
            x += 1
    return areas

def contains(window, x, y):
    '''
    Return True if window contains the coordinate (x, y)
    '''
    leftBot, topRight, _ = window
    return leftBot[0] <= x <= topRight[0] and leftBot[1] <= y <= topRight[1]

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

第一轮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没有完全写完.

确实感觉这波好难啊，看来狗家coding确实看运气。。。这个就感觉很简单 https://www.1point3acres.com/bbs/thread-891486-1-1.html
请问lz你走新的hiring process了吗？是组里面人面的你吗？ 谢谢

第三题应该是从index 最高的 长方形开始找吧（clarify index 是唯一的吗 like 有可能多个长方形有同一个index ） brute force 的应该就是 maintain 2d[][] array 然后 对每个window 从左上角一直搜索到右下角 找没有被cover的点 如果有大神能用merge interval能给个解法那就太感谢了 二维的interval merge有点难想
第四题看了下原题的解法是segment tree 难道真的要现场手写segment tree 吗。。。
顺便问一句楼主target level是多少？ 这面试有点难

楼主面完recruiter直接通知挂了吗？没有过hc或者尝试先match再过hc吗？谢谢

大佬哪天面的。。

匿名者 发表于 2022-5-4 00:05
确实感觉这波好难啊，看来狗家coding确实看运气。。。这个就感觉很简单 https://www.1point3acres.com/bbs/ ...

不是新的process, 还是打散了随机找人面的

SSGEZREAL 发表于 2022-5-4 00:06
第三题应该是从index 最高的 长方形开始找吧（clarify index 是唯一的吗 like 有可能多个长方形有同一个ind ...

第三题上来就说了brute force, 给我的答复是万一有很多长方形呢? 让我优化T_T

第四题是segment tree..就得写出来吧大概

这个是L4

太难了，只能加个米安慰下

匿名用户 发表于 2022-05-04 10:26:01
第三题上来就说了brute force, 给我的答复是万一有很多长方形呢? 让我优化T_T

第四题是segment tree..就得写出来吧大概

继续第三题 我想了一下其实这就是个二维版的painting area every day 对于某一行或者某一列来说用maintain jump line 就可以了？ 比如对一个window 是（25,25) (50,50) 那么标记它中间所有的点直接跳转到51  这样应该可以？
现场写segment tree 也太残暴了 楼主是hc通知挂了吗