Hulu 软件开发准备 9.16笔试

2020往年题

Hulu往届校招编程测试真题 2020

1

2021往年题

Hulu往年校招编程真题 2021

面经

1

1：给n个三元组[Li,Ri,Vi]表示n个程序，第i个程序在[Li,Ri]时间区间里消耗内存为Vi，问在n个程序运行过程中内存消耗的峰值是多少。 2 : n个数，有两种操作方式 一种是将其中一个数除以二（向下取整），第二种是将一个数翻倍。问最少用多少次操作能使得这n个数相等。

2

设计一个短网址，在线写一个n进制转换函数

LeetCode

907. Sum of Subarray Minimums （Medium）

https://leetcode.com/problems/sum-of-subarray-minimums/
Monotonous stack 单调栈
https://zhuanlan.zhihu.com/p/103562972

暴力法
遍历所有区间，然后对于每个区间找出最小值求和。这种方法时间复杂度是 [公式] ，显然不可行。

暴力法优化
对于区间左端点 i ，遍历所有的右端点 j ，然后维护最小值，时间复杂度可以降到 [公式] ，但还是太高了。

单调栈
既然我们不能先遍历区间，然后找最小值，那么我们不如顺序倒过来，对于每个值，我们找有多少区间里面，它是最小值。

909. Snakes and Ladders (Medium)

• 从格子1开始，每次只能从当前格子 i 到，i+1 or i+2 or i+3 or i+4 or i+5 or i+6 (模仿掷色子走大富翁)
• 如果当前格子存在ladder或者snakeboard[r][c] != -1，可以直接到那个链接的格子，一次移动只能用一次ladder/snake（）不能连续走。
  返回走到格子N*N的最少步数，不能，返回-1 （返回至少掷几次骰子）

class Solution:def snakesAndLadders(self, board: List[List[int]]) -> int:n = len(board)# get  index in matirx by input value of this current griddef label2position(label):r, c = divmod(label-1, n)if r % 2 == 0:  # columns 从左往右return n-1-r, celse:           # colums 从右往左return n-1-r, n-1-cseen = set()queue = collections.deque()queue.append((1, 0))    # start grid, # of stepwhile queue:label, step = queue.popleft()r, c = label2position(label)if board[r][c] != -1:   # There is ladder: renew the label to the destinationlabel = board[r][c] if label == n*n:        # Finishedreturn stepfor x in range(1, 7):   # roll the dice (all 6 possoblities)new_label =label + x# still in the board && no loop: never go back tp the previous bfsif new_label <= n*n and new_label not in seen:seen.add(new_label)queue.append((new_label, step+1))return -1