昨天去知道创宇的面试失败了,很感谢他们能给我这个机会。通过这次面试,我总算迈出了一步,更加明确了自己应该努力的方向。这次面试反映出的一个很严重的问题就是,手太生,学了这么长时间Python,竟然连一些常用的用法,命令都得现查文档。自己反思一下,没有自己动手写多少代码,这个是问题的关键。
面试我的雨哥人非常nice,面对我这么菜的表现没有一点不耐烦,他说的一句话让我印象深刻,“既然是有兴趣,平时就多花点时间,对得起兴趣这两个字”。我会的。
二分法查找
我想这个应该是最容易理解的算法了吧,我差点就在面试的时候完成了,well,almost…
思路很简单,因为给出的列表已经是排好顺序的了,因此直接找到中间的一个记为mid,若是要找的元素,任务完成。若mid比要找的元素大,好的,那么要找的元素肯定在start跟mid之间了,若mid比要找的元素小,那么要找的元素肯定在mid和end之间了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
def binarySearch(lst, element, start, end):
mid = (start + end)/2
if element == lst[mid]:
print 'Found, %d' % mid
elif mid == start:
if element == lst[mid+1]: # 主要处理两个相邻的数的情况,这种情形下mid必然等于start
print 'Found, %d' % (mid+1) # 因此如果end(也就是mid+1)不等于element的话,则没找到
else:
print 'Not found'
elif element > lst[mid]:
return binarySearch(lst, element, mid, end)
elif element < lst[mid]:
return binarySearch(lst, element, start, mid)
def binarySearch2(lst, element, start, end):
mid = (start + end)/2
if element == lst[mid]:
return 'Found, %d' % mid
elif start > end:
return 'Not found'
elif element < lst[mid]:
return binarySearch2(lst, element, start, mid-1)
elif element > lst[mid]:
return binarySearch2(lst, element, mid+1, end)
def binarySearch3(lst, element):
start = 0
end = len(lst) - 1
while (start <= end):
mid = (start + end)/2
if lst[mid] == element:
return 'Found', mid
elif lst[mid] > element:
end = mid - 1
elif lst[mid] < element:
start = mid + 1
return 'Not found'
|
上面的方法一是我自己瞎想的ugly思路,方法三是我在一站式C编程上看到的,方法二是我根据方法三的思路用递归改写的
spreadsheet numeration
这个题目其实我之前在CodeForces上做过的,可惜没有理解它的真谛,虽然当时误打误撞做出来了,还是没有效果,现在遇到还是不会做,面试中雨哥一句话点醒我,“进制转换”,是啊,这个问题实质上就是十进制转换26进制的问题。那进制转换无非就是要做除法、取余。但是也不是这么简单,有一个比较tricky的问题,就是在转换26的倍数的时候,需要做一些特殊处理才行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def numTochar(num):
result = ''
ori = num
while num:
mod = num % 26
if mod == 0:
mod = 26
num = num/26 - 1 # special cases for 'Z'
else:
num /= 26
result = chr(mod + ord('A') - 1) + result
return result,ori
def numTochar2(num):
result = ''
ori = num
while num:
mod = num % 26
if mod == 0:
mod = 26
num -= 1 # a more elegant solution
num /= 26
result = chr(mod + ord('A') - 1) + result
return result,ori
|
方法一是我自己捣鼓的,方法二是我在CodeForces上看到了,效果应该是一样的,都是为了在转换26的倍数的时候能够得出正确的结果,做出的一点特殊处理,不过显然后者更加优雅,每个数在除26之前先减1,这样既对于非26倍数的数没有影响,又能巧妙的处理26的倍数时的特殊情况。