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

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

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

[0bit]

实现在哪里？

[justfly]

@0bit 我贴了gist啊
如果看不到的话 访问这里：
https://gist.github.com/imjustfly/5370526

[longxi]

第一题以前看过
http://www.matrix67.com/blog/archives/4092

[wenbinwu]

第一题就是考虑一开始那几种情况吧，剩下的ctrl a + ctrl c + ctrl v三个键效率肯定比aaa高，最后考虑下剩下1个或者2个键的情况

代码正确与否不知道
这样的注释嘛（#否则） 不要也罢
另外写英文的注释

[binux]

第一题这样暴力做肯定是不对的，假设之前已经输入了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]

01背包

[mingzhi]

我觉得楼主的第一题好像是看错题目了吧。
Ctrl + a 这样 算2次吧
然后
n<=11 次 就是直接按a

n>11 算 ((n-5)%6+5)^((n-(n-5)%6+5)/6)
不知道有没有错了。。

[mingzhi]

@mingzhi 错了 ((n-5)%6+5)*(2^((n-(n-5)%6+5)/6))吧

[binux]

第一题，python一行流：
F = lambda n: max([F(n-2-k)*k for k in range(1, n)]+[n, ]) if n > 0 else 0

后面的就懒得看了

[lddhbu]

好像比背包要简单，因为如果有“复制粘贴”，“复制粘贴”操作肯定是最后一步。
而如果N大于6，肯定会有“复制粘贴”，然后就可以递归了。

[mingzhi]

@mingzhi 我又觉得我错了
全选 复制 粘帖 再粘帖 再粘帖 再粘帖 再粘帖
再全选 复制 粘帖 再粘帖 再粘帖 再粘帖 再粘帖

这样子更多吧。。

[nkliwenjian]

暂时没有详细研究，但是先提出来一个很严重的问题，就是单纯的(全选，拷贝，粘贴)的组合行为，实际上数量是完全没有增加的，因为粘贴的动作会覆盖掉原来的选择，并且光标会移动到最后，至少再粘贴一次才有效果。

[wuma]

第一个是个动态规划问题吧。第二个是正则+awk+sort。

[awsx]

现场笔的还是网络上提交？

[wuma]

n <=6 -> m=n
n>6 -> m(n) = Max (m(n-1)+p, m(n-2)+2p , m(n-3)*2)

[csx162]

ctrl是可以一直按住的
全选的情况下是可以被覆盖的

[hfeeki]

第一个题目描述得太简单了，是不是只有出题人自己才能看懂呢？ctrl + A到底是算一个键呢？还是算是组合键？如果是组合键，那加上另两个组合键，全部的键的数目就是：A, C, V, ctrl。希望先讲清楚出题人到底啥意图

[justfly]

@mingzhi
@hfeeki
题目就是他给的邮件，题目这样写很容易想到组合键和A一样算一次，如果算两次他应该说有A CTRL C V 这几个键

[justfly]

@awsx 网上提交的

[justfly]

@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]

哈哈 看来最难的是怎么理解第一题

[nkliwenjian]

动态规划我是没有学过了，但是很多时候一眼看上去的东西会有点误差。我简单的手算了一下，过程如下：
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]

第一题 很简单的动态规划
分为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]

输出步骤的时候从后往前找出来就行

[MayLava]

研究了半天状态，结果还是用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]

https://gist.github.com/MayLava/5372068

[nkliwenjian]

@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]

@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]

第一题是动态规划吧……归纳下可以得出递推式：
m=f(x)=
1(x=1)
f(x-1)+1
f(x-3)*2
f(x-1)+Clickboard

[jesse_luo]

基本就是同@qdcanyun 的解答那样的啦……

第二题得算算有用信息可能的大小。不知道一天的访问量是多大……

[dndx]

歪下楼

[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]

第二题写了个解题报告，欢迎拍砖。

感谢好基友 MayLava 帮忙修改

https://gist.github.com/TheLoverZ/5449825

[rrfeng]

第二题题意不是很明确……
不过用 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]

python 的话……好长。

[sailxjx]

怎么又开始挖坟了
搭车贴gist
https://gist.github.com/sailxjx/5388648

[zhangxi1989]

这个结果对不对？
/*
括号里表示一开始输入几个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)
*/