V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
justfly
V2EX  ›  Python

python 笔试题被刷 求大牛指导!

  •  
  •   justfly · 2013-04-12 16:37:55 +08:00 · 12935 次点击
    这是一个创建于 4245 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我是今年的应届毕业生,求职某个工程师文化挺浓的公司,给了两个笔试题如下:

    1.假设你的键盘只有以下键:
    A
    Ctrl + A
    Ctrl + C
    Ctrl + V
    这里Ctrl+A,Ctrl+C,Ctrl+V分别代表"全选",“复制”,“粘贴”。

    如果你只能按键盘N次,请写一个程序可以产生最多数量的A。也就是说输入是N(你按键盘的次数), 输出是M(产生的A的个数)。

    加分项:
    打印出中间你按下的那些键。


    2.假设给你一个月的日志,格式如下:

    [I 130403 17:26:40] 1 200 GET /question/123 (8.8.9.9) 200.39ms
    [I 130403 17:26:90] 1 200 GET /topic/456 (8.8.9.9) 300.85ms
    [I 130403 17:26:90] 1 200 POST /answer/789 (8.8.9.9) 300.85ms
    ...

    方括号中依次是:级别,日期,时间,后面依次是用户id,返回码,访问方式,访问路径,用户ip,响应时间

    日志文件名格式为:年-月-日-小时.log,如:2013-01-01-18.log,共30*24个文件。

    写个程序,算出一个用户列表和一个路径列表符合以下要求:
    1.这些用户每天都会访问(GET)/topic/***这个路径两次以上(*代表数字)
    2.这些用户每天访问(GET)的/topic/***路径中,至少会包含两个不同的路径(后面的数字不一样)
    3.统计出所有以上用户所访问的路径中每天都出现两次以上的路径列表

    下面我给出了实现,然后**无情被拒绝**了,求指点我做的不好的地方在哪里

    36 条回复    1970-01-01 08:00:00 +08:00
    0bit
        1
    0bit  
       2013-04-12 16:43:59 +08:00
    实现在哪里?
    justfly
        2
    justfly  
    OP
       2013-04-12 16:46:50 +08:00
    @0bit 我贴了gist啊
    如果看不到的话 访问这里:
    https://gist.github.com/imjustfly/5370526
    longxi
        3
    longxi  
       2013-04-12 17:12:02 +08:00
    wenbinwu
        4
    wenbinwu  
       2013-04-12 17:25:03 +08:00
    第一题就是考虑一开始那几种情况吧,剩下的ctrl a + ctrl c + ctrl v三个键效率肯定比aaa高,最后考虑下剩下1个或者2个键的情况

    代码正确与否不知道
    这样的注释嘛(#否则) 不要也罢
    另外写英文的注释
    binux
        5
    binux  
       2013-04-12 17:29:19 +08:00
    第一题这样暴力做肯定是不对的,假设之前已经输入了a个A了,那么再经过2+k次粘贴可以得到k*a个A
    假设: M = F(n)
    有:
    F(n) = max([F(n-2-k)*k for k in range(1, N)]+[n, ])

    当n<=0时: F(n) = 0
    lddhbu
        6
    lddhbu  
       2013-04-12 17:35:27 +08:00
    01背包
    mingzhi
        7
    mingzhi  
       2013-04-12 17:43:44 +08:00
    我觉得楼主的第一题好像是看错题目了吧。
    Ctrl + a 这样 算2次吧
    然后
    n<=11 次 就是直接按a

    n>11 算 ((n-5)%6+5)^((n-(n-5)%6+5)/6)
    不知道有没有错了。。
    mingzhi
        8
    mingzhi  
       2013-04-12 17:46:12 +08:00
    @mingzhi 错了 ((n-5)%6+5)*(2^((n-(n-5)%6+5)/6))吧
    binux
        9
    binux  
       2013-04-12 17:55:30 +08:00   ❤️ 1
    第一题,python一行流:
    F = lambda n: max([F(n-2-k)*k for k in range(1, n)]+[n, ]) if n > 0 else 0

    后面的就懒得看了
    lddhbu
        10
    lddhbu  
       2013-04-12 17:58:22 +08:00
    好像比背包要简单,因为如果有“复制粘贴”,“复制粘贴”操作肯定是最后一步。
    而如果N大于6,肯定会有“复制粘贴”,然后就可以递归了。
    mingzhi
        11
    mingzhi  
       2013-04-12 18:06:06 +08:00
    @mingzhi 我又觉得我错了
    全选 复制 粘帖 再粘帖 再粘帖 再粘帖 再粘帖
    再全选 复制 粘帖 再粘帖 再粘帖 再粘帖 再粘帖

    这样子更多吧。。
    nkliwenjian
        12
    nkliwenjian  
       2013-04-12 18:13:06 +08:00
    暂时没有详细研究,但是先提出来一个很严重的问题,就是单纯的(全选,拷贝,粘贴)的组合行为,实际上数量是完全没有增加的,因为粘贴的动作会覆盖掉原来的选择,并且光标会移动到最后,至少再粘贴一次才有效果。
    wuma
        13
    wuma  
       2013-04-12 18:22:46 +08:00   ❤️ 1
    第一个是个动态规划问题吧。第二个是正则+awk+sort。
    awsx
        14
    awsx  
       2013-04-12 18:22:51 +08:00
    现场笔的还是网络上提交?
    wuma
        15
    wuma  
       2013-04-12 18:24:11 +08:00
    n <=6 -> m=n
    n>6 -> m(n) = Max (m(n-1)+p, m(n-2)+2p , m(n-3)*2)
    csx162
        16
    csx162  
       2013-04-12 18:32:46 +08:00
    ctrl是可以一直按住的
    全选的情况下是可以被覆盖的
    hfeeki
        17
    hfeeki  
       2013-04-12 18:34:32 +08:00
    第一个题目描述得太简单了,是不是只有出题人自己才能看懂呢?ctrl + A到底是算一个键呢?还是算是组合键?如果是组合键,那加上另两个组合键,全部的键的数目就是:A, C, V, ctrl。希望先讲清楚出题人到底啥意图
    justfly
        18
    justfly  
    OP
       2013-04-12 19:23:33 +08:00
    @mingzhi
    @hfeeki
    题目就是他给的邮件,题目这样写很容易想到组合键和A一样算一次,如果算两次他应该说有A CTRL C V 这几个键
    justfly
        19
    justfly  
    OP
       2013-04-12 19:23:52 +08:00
    @awsx 网上提交的
    justfly
        20
    justfly  
    OP
       2013-04-12 19:28:51 +08:00
    @lddhbu 没这么简单
    比如十次按键:
    AAAA CTRL+A CTRL+C CTRL+V CTRL+V CTRL+V CTRL+V (20个A)
    AAAA CTRL+A CTRL+C CTRL+V CTRL+A CTRL+C CTRL+V(16个A)
    Muninn
        21
    Muninn  
       2013-04-12 19:29:36 +08:00
    哈哈 看来最难的是怎么理解第一题
    nkliwenjian
        22
    nkliwenjian  
       2013-04-12 19:41:52 +08:00
    动态规划我是没有学过了,但是很多时候一眼看上去的东西会有点误差。我简单的手算了一下,过程如下:
    f(n + (a,c,v,v)) = f(n) * 2
    f(n + (a,c,v,v,v)) = f(n) * 3
    f(n + (a,c,v,v,v,v)) = f(n) * 4
    f(n + (a,c,v,v,v,v,v)) = f(n) * 5
    ......

    f(n+4) = f(n) * 2
    f(n+5) = f(n) * 3
    f(n+6) = f(n) * 4
    f(n+7) = f(n) * 5
    f(n+k) = f(n) * (k - 2)

    f(n+8) = f(n) * 6, f(n+4+4) = f(n) * 2 * 2
    f(n+9) = f(n) * 7, f(n+5+4) = f(n) * 3 * 2
    f(n+10) = f(n) * 8, f(n+6+4) = f(n) * 4 * 2, f(n+5+5) = f(n) * 3 * 3
    f(n+11) = f(n) * 9, f(n+7+4) = f(n) * 5 * 2, f(n+6+5) = f(n) * 4 * 3
    f(n+12) = f(n) * 10, f(n+8+4) = f(n) * 6 * 2, f(n+6*6) = f(n) * 4 * 4, f(n+4+4+4) = f(n) * 2 * 2 * 2
    f(n+16) = f(n) * 14, f(n+12+4) = f(n) * 10 * 2, f(n+8+8) = f(n) * 6 * 6, f(n+4+4+4+4) = f(n) * 2 * 2 * 2 * 2

    我们知道指数函数是增长速度最快的函数,所以到此其实大概能得出结论,如果我们把k进行不同的组合拆分的话,大概会是这样的一个结果:

    2 ^ (k / 4) = 2 ^ (0.25 * k)
    3 ^ (k / 5) = 2 ^ (0.317 * k)
    4 ^ (k / 6) = 2 ^ (0.333 * k)
    5 ^ (k / 7) = 2 ^ (0.332 * k)
    6 ^ (k / 8) = 2 ^ (0.323 * k)

    k / 6的时候取得最大值,有兴趣可以算一下验证一下,基本上就是底下的公式变形推导:
    a ^ (k / (a + 2)) = 2 ^ (lg(a) / lg(2)) ^ (k / (a + 2))
    2 ^ (k / lg(2) * (lg(a) / (a + 2))

    所以,当n足够大时,尽量多的按照这个a+c+v+v+v+v的组合来操作,结果是最大的。剩下的部分就是n从多少开始满足这个规则,以及6的组合余下的余数放哪,这个就不推算了。

    有错误莫怪哦。
    qdcanyun
        23
    qdcanyun  
       2013-04-12 21:22:19 +08:00
    第一题 很简单的动态规划
    分为3个原子操作:
    “A”
    “Press Ctrl+A;Press Ctrl+C;Press Ctrl+V;Press Ctrl+V;”
    "Press Ctrl+V;"

    当前敲击按键x的次数的最大值为(list[x-1]+1, list[x-4] * 2, list[x-1]+copy_clipboard_num)里的最大值

    当 list[x-4] * 2 与 list[x-1]+copy_clipboard_num 相等时
    优先使用 list[x-4] * 2 ,这样在步数相同的情况下可以扩大clipboard

    其实分析一下就可以看出PressA这种情况在第8次敲键盘之后不会出现, 也可以初始化前八次按键的状态, 然后只采用2种原子操作

    代码
    http://gist.github.com/5371878
    qdcanyun
        24
    qdcanyun  
       2013-04-12 21:23:42 +08:00
    输出步骤的时候从后往前找出来就行
    MayLava
        25
    MayLava  
       2013-04-12 21:42:07 +08:00
    研究了半天状态,结果还是用5分钟写个搜索……orz……
    效率不高,n=46时约用时1s
    简单的三种操作,1、按A;2、按C-v;3、按C-a,C-c,C-v,C-v
    简单的剪枝:如果Clipboard大于1则不按A;反之则按A。
    http://gist.github.com/MayLava/5372068
    MayLava
        26
    MayLava  
       2013-04-12 21:48:10 +08:00
    nkliwenjian
        27
    nkliwenjian  
       2013-04-12 23:07:43 +08:00
    @justfly 1秒钟之内循环1到49毫无压力。注意我前面说的,全选复制粘贴是不会变多的,至少粘贴两次才会多出来一次,所以结果会跟你的不一样。当n=11的时候,m=20。而不是n=10。

    SELECT_ALL = 'CTRL+A'
    COPY = 'CTRL+C'
    PASTE = 'CTRL+V'
    PRESS_GROUP = [SELECT_ALL, COPY, PASTE, PASTE, PASTE, PASTE]
    A4 = ['A', 'A', 'A', 'A']

    def f(n):
    press_left = n
    press_keys = []
    total = 0
    group_count = 0

    if n <= 7:
    return (n, ['A'] * n)
    elif n == 8:
    return (9, [['A', 'A', 'A'], [SELECT_ALL, COPY, PASTE, PASTE, PASTE]])
    elif n == 9:
    return (12, [['A', 'A', 'A', 'A'], [SELECT_ALL, COPY, PASTE, PASTE, PASTE]])
    else:
    press_a4(press_keys)
    press_left = press_left - 4
    group_count = press_group(press_left, press_keys)
    press_left = press_left - 6 * group_count
    allot_left(press_left, press_keys)
    total = calculate_total(press_keys)
    return (total, press_keys)

    def press_a4(press_keys):
    press_keys.append(A4)

    def press_group(press_left, press_keys):
    group_count = press_left / 6
    for i in range(group_count):
    press_keys.append(PRESS_GROUP)
    return group_count

    def allot_left(press_left, press_keys):
    if len(press_keys) == 2:
    a_count = press_left / 2
    v_count = press_left - a_count
    for i in range(a_count):
    press_keys[0].append('A')
    for i in range(v_count):
    press_keys[1].append(PASTE)
    else:
    left = press_left
    index = len(press_keys) - 1
    while left > 0:
    left = left - 1
    press_keys[index].append(PASTE)
    index = index - 1
    if index == 0:
    index = len(press_keys) - 1

    def calculate_total(press_keys):
    total = len(press_keys[0])
    for l in press_keys[1:]:
    total = total * (len(l) - 2)
    return total

    def main():
    for i in range(1, 50):
    print 'n=%d, m=%d' % (i, f(i)[0])

    if __name__ == "__main__":
    main()
    nkliwenjian
        28
    nkliwenjian  
       2013-04-12 23:28:00 +08:00
    @justfly 一点小bug,请把press_keys.append(A4)改成press_keys.append(copy.copy(A4)),把press_keys.append(PRESS_GROUP)改成press_keys.append(copy.copy(PRESS_GROUP))
    jesse_luo
        29
    jesse_luo  
       2013-04-14 01:40:50 +08:00
    第一题是动态规划吧……归纳下可以得出递推式:
    m=f(x)=
    1(x=1)
    f(x-1)+1
    f(x-3)*2
    f(x-1)+Clickboard
    jesse_luo
        30
    jesse_luo  
       2013-04-14 01:51:20 +08:00
    基本就是同@qdcanyun 的解答那样的啦……

    第二题得算算有用信息可能的大小。不知道一天的访问量是多大……
    dndx
        31
    dndx  
       2013-04-14 02:01:45 +08:00
    歪下楼

    [I 130403 17:26:40] 1 200 GET /question/123 (8.8.9.9) 200.39ms
    [I 130403 17:26:90] 1 200 GET /topic/456 (8.8.9.9) 300.85ms
    [I 130403 17:26:90] 1 200 POST /answer/789 (8.8.9.9) 300.85ms

    公司是知乎,鉴定完毕。
    sethverlo
        32
    sethverlo  
       2013-04-24 13:25:18 +08:00
    第二题写了个解题报告,欢迎拍砖。

    感谢好基友 MayLava 帮忙修改

    https://gist.github.com/TheLoverZ/5449825
    rrfeng
        33
    rrfeng  
       2013-04-24 14:13:00 +08:00
    第二题题意不是很明确……
    不过用 awk 直接实现很容易的呀。用三个键计数:
    1. awk '/GET \/topic/{id[$4]++;topic[$7]++;it[$4" "$7]++}'

    2. END 里面判断:
    {for(x in id){if(id[x]>2)print x}} 访问 /topic 大于2次的用户列表
    {for(y in it){if(it[y]>2)print y}} 同一个用户访问了2次以上不同 /topic 地址的列表 id /topic/***

    真的没看懂题目的要求
    [用户列表] :访问了 2个不同的 /topic 并且这几个topic 均重复访问了 2次?

    不过三个哈希组合判断足够了,awk 后面直接跟所有文件的列表一次搞定~~
    rrfeng
        34
    rrfeng  
       2013-04-24 14:13:40 +08:00
    python 的话……好长。
    sailxjx
        35
    sailxjx  
       2013-04-24 16:23:45 +08:00
    怎么又开始挖坟了
    搭车贴gist
    https://gist.github.com/sailxjx/5388648
    zhangxi1989
        36
    zhangxi1989  
       2013-04-25 15:58:21 +08:00
    这个结果对不对?
    /*
    括号里表示一开始输入几个0
    0:0(0)
    1:1(1)
    2:2(2)
    3:3(3)
    4:4(4)
    5:5(5)
    6:6(6)
    7:9(3)
    8:12(3)
    9:16(4)
    10:20(4)
    11:25(5)
    12:36(3)
    13:48(3)
    14:64(4)
    15:80(4)
    16:100(5)
    17:144(3)
    18:192(3)
    19:256(4)
    20:320(4)
    21:400(5)
    22:576(3)
    23:768(3)
    24:1024(4)
    25:1280(4)
    26:1600(5)
    2304(3)
    3072(3)
    4096(4)
    */
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3234 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 13:11 · PVG 21:11 · LAX 05:11 · JFK 08:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.