Python技术迷

某候选人:我不是做奴隶的料,你找错人了

刚刷到这个,真给我看清醒了。

HR上来就把条件摊开:一周干六天,平时晚上基本要耗到九点,忙起来可能还要倒夜班。加班费是有,但听着就不是“偶尔忙一下”,更像是把人直接按在工位上榨。

结果候选人也没绕弯子,直接说不行,这种强度自己不接,找别人吧。

Image

我还挺佩服这哥们的。很多人面试时明明心里已经骂街了,嘴上还得装成“我可以适应”“我抗压能力强”。他倒好,现场把话说明白:我来找工作,不是来把命抵押给公司的。

其实最尴尬的不是他拒绝,是这种岗位条件已经能被HR平静说出来了。六天制、晚九点、夜班,包装一下就成“发展机会”。打工人看完血压都上来了。

今日算法题

用户行为日志里只有三种动作:show、answer、skip。

这题我第一眼不会急着写除法。 因为“回答率最高”这几个字看着简单,线上真落到日志里,最容易错在两个地方:一个是把 skip 也算进分母,一个是 show 次数为 0 时直接炸掉。

题目一般是这种数据:

logs = [
    {"user_id": 1, "question_id": 10, "action": "show"},
    {"user_id": 1, "question_id": 10, "action": "answer"},
    {"user_id": 2, "question_id": 10, "action": "show"},
    {"user_id": 2, "question_id": 10, "action": "skip"},

    {"user_id": 3, "question_id": 20, "action": "show"},
    {"user_id": 3, "question_id": 20, "action": "answer"},
]

问题 10 展示了 2 次,回答了 1 次,回答率是 1 / 2。 问题 20 展示了 1 次,回答了 1 次,回答率是 1 / 1。

所以最后应该返回 20。

这题的核心不是多复杂的算法,就是把每个问题的 show 和 answer 分开统计。别看到日志表就乱算 total,skip 只是用户跳过,它不应该增加回答数,但它通常已经伴随着一次 show 了,别重复算。

我一般会这么写:

from collections import defaultdict

deffind_best_question(logs):
    stat = defaultdict(lambda: {"show": 0, "answer": 0})

for row in logs:
        qid = row["question_id"]
        action = row["action"]

if action == "show":
            stat[qid]["show"] += 1
elif action == "answer":
            stat[qid]["answer"] += 1

    best_qid = None
    best_answer = 0
    best_show = 1

for qid, item in stat.items():
        show = item["show"]
        answer = item["answer"]

if show == 0:
continue

if best_qid isNone:
            best_qid = qid
            best_answer = answer
            best_show = show
continue

# 不直接用 answer / show,比浮点数稳一点
        left = answer * best_show
        right = best_answer * show

if left > right:
            best_qid = qid
            best_answer = answer
            best_show = show
elif left == right and qid < best_qid:
            best_qid = qid
            best_answer = answer
            best_show = show

return best_qid

这里有个小细节,我没用:

answer / show

不是不能用,小数据当然没问题。但这种题如果放到真实统计里,我更习惯用交叉相乘:

answer * best_show > best_answer * show

这样不用关心浮点数精度,也不用写一堆小数比较。

跑一下:

print(find_best_question(logs))

输出:

20

如果题目要求回答率相同返回最小的 question_id,上面这段也处理了:

elif left == right and qid < best_qid:

这行别漏。很多人前面统计都写对了,最后就栽在并列条件上。

这题时间复杂度是 O(n),日志扫一遍,问题集合再扫一遍。空间复杂度是 O(m),m 是不同问题的数量。

真要落到数据库里,也是同一个思路:先按 question_id 分组,再分别数 show 和 answer,最后按回答率倒序排。换成 Python,本质就是手写一次 group by。