灌水 这几天很火的套路招聘图片……

Keith Mo · April 14, 2019 · Last by Keith Mo replied at April 18, 2019 · 2389 hits

没错就是这张套路图,据说是 segment fault 的招聘?无聊刷一下题,抛砖引玉。(知乎那边也回了贴,话说破乎的编辑器还真不适合贴代码……)


正好最近在出招聘测试的笔试题,在网上看到跟第 1 题类似的,数字比这个大 10 倍有多。自己做了一下发现如果之前没刷过类似的,要在限时内在纸上写出优化过的代码并不容易,就放弃把它收进题库了……

现成的贴上来:

import time
import math


def is_prime(x):
if x <= 1:
return False

if x == 2:
return True

for i in range(3, int(math.sqrt(x)) + 1, 2):
if x % i == 0:
return False

return True


def prime_factorization(x):
for i in range(2, int(math.sqrt(x)) + 1):
if x % i == 0 and is_prime(i):
quotient = x // i

if is_prime(quotient):
print(i, quotient)


if __name__ == '__main__':
t1 = time.time()
prime_factorization(707829217)
t2 = time.time()

print(f'ms: {t2 * 1000 - t1 * 1000}')

输出:

8171 86627
ms: 3.166015625

我能想到的优化点有 3 个:

  • 1、n 的最小质因数(能整除给定正整数的质数)<= √n(因为如果 √n 是整数,n 一定是合数)。因此没必要循环到 n,√n + 1 就够了。
    • 优化后时间复杂度从 O(n) 降到 O(log(n)) 。
    • 我找到的题里的数字是 7140229933,开根号后约 84500,少循环了 7140145433 次!本来要跑几分钟,优化后 230ms 左右出结果。
  • 2、解一定是整数,如果不能整除某个数 a,也就没必要判断 a 是不是质数了。
    • 调整判断条件的次序,优化后 14ms 左右出结果。
  • 3、除了 2,其他质数都是奇数,循环时可以跳过偶数,减少一半判断。
    • 本来对于判断是否质数来说这个优化点很重要,但在这里贡献几乎忽略不计,做了第二点优化之后已经没剩几次需要判断的了。

第二题:

没有用典型的 DP 模板(因为我想了半天都套不上……),题目条件太简单,用了取巧的办法硬是磨出来了,目测反而会比 DFS 快不少。

def get_answer(n):
"""
这题有个取巧的方法,十位以上是 3 的时候,奇数的个数是 10^i / 2。例如 300-400 之间有 10^2 / 2 = 50 个奇数,如此类推。
用记忆化搜索的思路把结果缓存起来,然后注意一下最后每位数字的限制,就能直接推出最终结果。

速度极快,哪怕是 333333333333333333333333333333333333333 这种大数字也就 1ms 左右。

题中 866278171 这个数字其实不是好例子,因为所有位都不是 3。
下面注释那几处地方假如没注意,就连 N = 3 都出 bug 的情况下这个数也能得到正确结果……

测试:1 3 4 9 10 13 29 31 33 39 41 43 100 299 301 303 333 399 400 1000
1224 1234 1244 10000 33333 1234567 12345678
"""

count = 0
nums = []
results = []

x = n
while x > 0:
# nums 存储 N 的各位数字,个位在前,最高位在最后
nums.append(x % 10)
# results 是二维数组,行数为 N 的位数,11 列分别代表 0-9 开头的数字 和总计
# 把每一位各数字开头的 3 的总数存起来
results.append([0] * 11)
x //= 10

digits = len(nums)

# 个位特殊处理
results[0][3] = 1
results[0][-1] = 1
if nums[0] >= 3: # 注意这里
count += 1

for i in range(1, digits):
for j in range(9 + 1):
results[i][j] += results[i - 1][-1]

if j == 3:
results[i][j] += 10 ** i // 2

results[i][-1] += results[i][j]

# 注意加的时候只能小于 N 在这一位的数字,否则会超出。
# 如果这一位为 0 就跳过(在下一位或下几位会包含进去)。
if j < nums[i]:
count += results[i][j]

# 补上 N 十位以上为 3 开头时漏统计的情况(因为不能读缓存)
if nums[i] == 3:
count += (sum(nums[j] * 10 ** j for j in range(i)) + 1) // 2

return count

输出:(没错就是这么快)

441684627
ms: 0.07421875

上面的方法不太好验证正确性,可以配合穷举和 1234567 之类较小的数字做测试:

def brute_force(n):
"""
如果是现场做笔试题,想不出 DP 至少写上这个凑数……
效率很低,算个 12345678 都要 7 秒左右,据说算完题中的数要 7-10 分钟。
"""

count = 0

i = 1
while i <= n:
x = i
while x > 0:
if x % 10 == 3:
count += 1
x //= 10

i += 2

return count
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
共收到 5 条回复 时间 点赞

那么问题来了,你见到女神了么😂

张全蛋 回复

已鉴定为hr。。

厉害厉害,第一题我是从1开始除。。一直除到707829217,运气很好,总共就两组数,一下就看出来了,速度的话,大概3秒😂 ,第二题是先循环,偶数就continue,奇数就转string,再转char数组,循环数有多少个3,49秒。

Ikaros灬 回复

厉害,第2题你的做法开发效率要高太多了 😂

需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up