腾讯校招面经

【转载请注明:来自微信公众号“数据挖掘机养成记”】


一个月前投了腾讯的TST内推,简历评级S,但一直未收到面试通知,都以为没戏了,终于前几天收到消息了,但是在深圳那边,我说希望是北京的部门,于是又过了几天,在面美团的时候,北京这边打电话过来约面试了,真所谓好事多磨。然而这次面试,却是从我五月份找实习、面试开始,第一场滑铁卢(虽然最终结果没出,但目测跪了)。趁着面经还热乎,赶紧搬上来。


约的下午四点钟,面试前发现面试官手里的简历还是我今年四月找实习投的那个版本。。。腾讯的简历库更新是有多慢/(ㄒoㄒ)/~~上来先是聊简历项目,面试官是个很和气很有耐心的小哥,几乎是逐条项目问过去,并没有提特别刁难的问题(也可能他们组重点不是在机器学习的算法模型策略创新之类,而是工程化实现),感觉比较满意,大概聊了一个小时后,开始手写代码,语言不限。


第一道题: 一个数组,元素可能正可能负,求连续的子数组里,和最大的那个

这个题网上有很多解法,我梳理了其中一种跟我面试时思路最接近的(然而面试时略紧张,没能完成解答),解法很简单,但是补充了自己的理解:

标准解法:首先假设数组元素为a[1:n],最大和子数组为a[i:j],注意最大和子数组有这样的特点

1. 从a[i-1]开始往左(下标减小方向)累加和,和都为负。(因为一旦和为正,这段累加和对应的子数组便可以并入a[i:j]构成更大和)

2. 从a[i]开始往右累加和,在到达a[j]前,和都为正,且累加到a[j]时和最大


我们再来看算法步骤:

s1. 给两个变量,now_sum和max_sum,初始化为0

s2. 从a[1]开始遍历,并把元素值累加给now_sum,一旦now_sum为负数,就清零(基于特点1. 说明目前累加的这些值都在a[i]左边,可以直接废弃)

s3. 在now_sum变化时,max_sum始终保留最大的now_sum(基于特点2.)

s4. 如果都是负数,输出最大的负值

代码(python)

def max_sub(L):

i = 0

j = 0

max_sum = 0

now_sum = 0

max_neg = L[0] # 用来记录最大负数

for idx in xrange(len(L)):

now_sum += L[idx]

if now_sum <= 0:

now_sum = 0

if now_sum > max_sum:

max_sum = now_sum

if L[idx] > max_neg:

max_neg = L[idx]

if max_sum == 0:

return max_neg

else:

return max_sum


L = [-3,5,2,1,7,-9,5,3,23,-111,3,7]

print max_sub(L)


第二道题:手写快速排序的代码

鉴于我上题没答好,面试官最后就随便出了道简单的题,这题太基本,就不贴代码了。几个点:1.有递归和非递归两种方式 2.尽量别额外开数组

本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院