Microsoft 巨硬 OA 2021 summer sde intern

1月底内推了巨硬，不是说内推的没有OA直接面试吗，我裂开了。
两小时三题A了两题，估计凉凉。

第一题：AC
In one setp, any element of a given array can be either increased or decreased by 1, what is the minimum steps to take that can make all elements in the array equal
Input: [3, 1, 2, 2]
Output: 2
解释：[3, 1, 2, 2] -> [3 - 1, 1, 2, 2] -> [2, 1+1, 2, 2] = [2, 2, 2, 2]
解法：
count = 0
sort array
find medium
for ...
count += abs(medium - array[i])
return count

第二题：AC
给了一个binary tree，找出一个maximum length path，path必须包含root并不能有重复value
解法：
就DFS with memory
path = set()
path.add(root)
stack = [(node, path)]
max_len = 0
while stack:
node, path = stack.pop()
max_len = max(max_len, len(path))
if node.left and node.left not in path: ...
if node.right ....
return max_len

第三题： 爆炸，他给的三个test case过了，剩下的全挂了
find such a path whose product contains the maximum possible number of trailing zeros, path可以转向一次
Input: [[10, 100, 10],
[1, 10, 1],
[1, 10, 1]]
Output: 5
解释：10 * 100 * 10 * 10 有五个0
解法：用recursive，加判断
maxZeros(map, i + 1, j, product * mat[i][j], turned, direction)
...
...
...
max_trailing_zero = max(max_trailing_zero, count_zeros(product))