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

2013-04-12 16:37:55 +08:00
 justfly
我是今年的应届毕业生,求职某个工程师文化挺浓的公司,给了两个笔试题如下:

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.统计出所有以上用户所访问的路径中每天都出现两次以上的路径列表

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

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

代码正确与否不知道
这样的注释嘛(#否则) 不要也罢
另外写英文的注释
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
2013-04-12 17:35:27 +08:00
01背包
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
2013-04-12 17:46:12 +08:00
@mingzhi 错了 ((n-5)%6+5)*(2^((n-(n-5)%6+5)/6))吧
binux
2013-04-12 17:55:30 +08:00
第一题,python一行流:
F = lambda n: max([F(n-2-k)*k for k in range(1, n)]+[n, ]) if n > 0 else 0

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

这样子更多吧。。
nkliwenjian
2013-04-12 18:13:06 +08:00
暂时没有详细研究,但是先提出来一个很严重的问题,就是单纯的(全选,拷贝,粘贴)的组合行为,实际上数量是完全没有增加的,因为粘贴的动作会覆盖掉原来的选择,并且光标会移动到最后,至少再粘贴一次才有效果。
wuma
2013-04-12 18:22:46 +08:00
第一个是个动态规划问题吧。第二个是正则+awk+sort。
awsx
2013-04-12 18:22:51 +08:00
现场笔的还是网络上提交?
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
2013-04-12 18:32:46 +08:00
ctrl是可以一直按住的
全选的情况下是可以被覆盖的
hfeeki
2013-04-12 18:34:32 +08:00
第一个题目描述得太简单了,是不是只有出题人自己才能看懂呢?ctrl + A到底是算一个键呢?还是算是组合键?如果是组合键,那加上另两个组合键,全部的键的数目就是:A, C, V, ctrl。希望先讲清楚出题人到底啥意图
justfly
2013-04-12 19:23:33 +08:00
@mingzhi
@hfeeki
题目就是他给的邮件,题目这样写很容易想到组合键和A一样算一次,如果算两次他应该说有A CTRL C V 这几个键
justfly
2013-04-12 19:23:52 +08:00
@awsx 网上提交的
justfly
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)

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/65710

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX