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

Keith Mo · 2019年04月14日 · 最后由 Keith Mo 回复于 2019年04月18日 · 2377 次阅读

没错就是这张套路图,据说是 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 题你的做法开发效率要高太多了 😂

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册