Python

一共两道题，一道是class的基本用法纯属送分题，第二道考如下

Dominant cell

count the number of Dominant cell (the cell that strictly greater than its neighbor value) in a 2D array

比如说如下2D Array:

a = [[6, 2, 3],
     [5, 2, 6],
     [3, 6, 9]]

就存在2个dominant cell: 6, 9 因为 6 > 2, 2, 5 以及 9 > 6, 2, 6

这道题难点就在于得讨论 edge case，但其实实现起来也不是很复杂，代码如下：

    c = 0
    height = len(grid)
    width = len(grid[0])

    for h in range(0, height):
        for w in range(0, width):
            num = grid[h][w]
            u = h if h - 1 < 0 else h - 1
            d = h if h + 1 >= height else h + 1
            l = w if w - 1 < 0 else w - 1
            r = w if w + 1 >= width else w + 1
            
            result_u = u == h or num > grid[u][w]
            result_d = d == h or num > grid[d][w]
            result_l = l == w or num > grid[h][l]
            result_r = r == w or num > grid[h][r]
            result_ul = u == h or l == w or num > grid[u][l]
            result_dl = d == h or l == w or num > grid[d][l]
            result_ur = u == h or r == w or num > grid[u][r]
            result_dr = d == h or r == w or num > grid[d][r]
            
            c = c + 1 if result_u and result_d and result_l and result_r and \
            result_ul and  result_dl and result_ur and result_dr else c
        
    return c

Problem Solving

这一部分也有两道题，虽然题目看着比较友好，但因为test case有runtime限制写起来比Python那两道题难了114514倍，题目如下

Subarray Sum

q1
q1

如果使用普通方法两个循环嵌套的话会导致超时，所以我的思路是建立两个斐波那契数列zeros和sums来避免重复的求和

def findSum(numbers, queries):
    r = []
    sums = [0]
    zeros = [0]
    
    for i in range(1, len(numbers) + 1):
        sums.append(sums[i - 1] + numbers[i - 1])
        id_z = 1 if numbers[i - 1] == 0 else 0
        zeros.append(zeros[i - 1] + id_z)

    for c in range(len(queries)):
        non_z = sums[queries[c][2]] - sums[queries[c][0] - 1]
        z_s = (zeros[queries[c][3]] - zeros[queries[c][0] - 1]) * queries[c][2]
        r.append(non_z + z_s)
    return r

Similar Rectangle

q2
q2

这道题就要简单一些了，难点是如何要找到是什么因素影响了pairs的数量，题目里的pairs，其实就是对n个similar rectangle进行排列 (Arrangment)，所以，每当 n+1，pairs就会增加n+1种可能性
$$\sum_i^{n+1}i-\sum_i^{n}i=n+1$$

def nearlySimilarRectangles(sides):
    c = 0
    f = {}
    for i in range(len(sides)):
        val = sides[i][0] / sides[i][1]
        if not val in f.keys():
            f[val] = 0
            continue
        c += f[val] + 1
        f[val] += 1
    return c