今天参与了一次某测试工程师技术面试，被问了一个很有意思的问题。
现在趁记忆比较新鲜，记录下来。
虽然这两天才开始学习python，不过由于坚信最好的学习语言的方法就是去使用，于是尝试使用python来解答。
不过似乎对于面试而言，思路会更重要一些，~~毕竟面试时还是有一定心理压力的说，尽管面试官还是很nice的~~。
虽然并没有在现场直接给出完整的代码，不过从思考、解决问题的角度上来说，自觉勉强算及格吧。

问题描述

给定一个数组[n_0,n_1,...,n_k],其中n_i,k都为任意正整数且0<=i<=k,返回相乘每一位n_i所得结果的数字尾部连续0的个数。

例如：

[5,6,7,8]
=>1
# 即相乘结果为5*6*7*8=1680, 尾部共有1个连续的0

[138, 10, 6, 155, 158]
=>2
# 即相乘结果为138*10*6*155*158=202777200，尾部共有2个连续的0

思路

一个直白的思路是，把每一位相乘，接着去数尾巴的0。

乘起来,存到product里：

nums=[...]
product=1
# calculate the product
for i in range(0,len(nums)):
    product*=nums[i]

这样问题就变成了对product数尾巴连续0的问题，解法的话直观上可以：

1-a. 不断地除以10，输出因数10的个数

# divide n by k, return the number of divisor k
# e.g., divide(100,10) => 2
def divide(n,k):
    counter=0
    while n % k == 0 and n!=0:
        n=n//k
        counter+=1
    return counter

print("direct calculation:",divide(product,10))

1-b. 转换成字符串，使用正则表达式截取尾巴所有的0:

_res=0
matchres=re.match(r"(\d*)[^0](0*)$",str(sum))
if (matchres):
    _res=len(matchres.group(2))

print("direct regex:",_res)

不过面试官的意思是可以不用全部乘出来，也可以解，于是我就开始思考:

如果数字尾部为0,那么意味着是10的倍数，同时也意味着有因数2和5。
进一步的，如果数字尾部为00,那么意味着是100的倍数，同时也意味着有因数2,5,2,5。

通过归纳，可以得知，尾部的0的个数与2和5的对数有关。

然而思考到这里我却不断地被我自己的直觉判断所影响，始终挥之不去一个不靠谱的怀疑：这样的方式会不会反而降低效率？

当时我单纯的想法是直白的版本的时间复杂度也就是一个O(n)+O(logn)，而这个算法是O(n)其中对于每个n又有一个最坏O(logk)的处理。
于是我犹豫不前，不断地打消这个念头去尝试寻找新的可能性，不过花了很长时间都没有找到更好的。

可是我应该注意到的是，使用算法2的好处在于可以避免大数的计算，光这一个优势我就应该把它实现出来再说。

但是对于问题的执念，使得到了第二个问题我仍然在脑海中建立了与上一个问题的链接，以至于关于TCP至少三次握手都没能说明清楚。

惭愧惭愧。

不管如何，我还是实现了一下做了下对比，事实证明我当时那个直觉是不正确的，算法2即便在int没有上限的python里仍然有着无可比拟的优势。

five=0
two=0
for i in range(0,len(nums)):
    five+=divide(nums[i],5)
    two+=divide(nums[i],2)

print("tricky one:",min(five,two))

跑了一些随机数据，如下，算法2(tricky one)完胜。

----------------
tricky one: 2449 
in 0.165548589s

direct calculation: 2449 
in 0.398511995s

direct regex: 2449 
in 0.409039028s
----------------

----------------
tricky one: 2392 
in 0.167644693s

direct calculation: 2392 
in 0.383790995s

direct regex: 2392 
in 0.394147758s
----------------

----------------
tricky one: 24404 
in 0.563190995s

direct calculation: 24404 
in 21.995120594s

direct regex: 24404 
in 22.996077246s
----------------

感谢这次面试，让我又学到了很多。

季承成 | CHENGCHENG JI

记一面试题: 数0

问题描述

思路