首页 > 微软苏州 三面(LEAD面)
头像
无人可超
编辑于 2020-10-30 19:27
+ 关注

微软苏州 三面(LEAD面)

10月30日 11点至12点 约1小时
首先英语自我介绍,听到我提到了C++、java和Python,
觉得我是不是对于C++熟悉,所以准备问C++,我及时拦住了
我英文说了自己工程一般用java,C++仅限于写算法,Python用来写小东西
他继续英语提问:那你说一下Python和java的异同吧
实话说,中文我能说的很好,英语就很多词到嘴边说不出_(:з」∠)_
说了比如java需要JVM,但是Python不需要,虽然Python也可以跑在JVM里面
然后两者都是OOP,但是我忘记了P是指什么【实菜,害】
java在业内用于高性能已经被实践了,比如阿里、字节等公司都用java做后端
Python相对简单,同时有很多工具【因为库不会翻,所以用了tool和function,实菜,害】
大致英语说了这些
然后照例做题,本地IDE

首先有两个函数,第一个作为初始化函数,无返回值,调用次数是一次
第二个是需要计算返回一个和,调用次数可能是成千上万次
第一个函数的参数是一个二维矩阵,你可以对矩阵做处理或者想办法做一些预处理,为第二个函数的计算求和做准备
第二个函数的参数是两个点的坐标,根据这两个点,可以围成一个矩形,求在这个矩形里所有数字的和。
我提出的第一个设计是用map来存两个点坐标,然后对应的结果就能留下来,
对应的时间复杂度虽然在后几次会只有O(1)但是空间复杂度因为需要存m*n个点两两组合的,所以空间复杂度O((m*n)^2),太大了
第二种设计,考虑到需要求和,那么可以利用每一行前缀和来加速求和的过程,这时空间复杂度就是跟一开始初始化传入的参数大小一样,也就是m*n,
时间复杂度是根据两个点坐标的上下差决定的,所以也可以等价的看做O(n)即上下差n行
把前缀和写了一点之后,我发现可以利用这个思路是求出每一块的前缀和,然后加速求和过程
所以在这之后,辅助空间就成了计算当前点到左上角所有数字的和,
然后利用它上方和左方的和,减去左上角的和就可以了(然后我一开始漏了加上自身的值,被面试官提醒才发现的)
然后第二个函数是操作就是O(1)常数级别的计算了,
首先判断坐标是不是在矩阵里的,然后如果不是我直接返回了0(面试官后来提醒,这里本身的值可能就是0,如何区分?我说那可能可以抛个异常)
因为平时C++都是写算法, 然后不考虑这种抛异常,就考虑题目中的特殊情况,所以抛异常写不来【实菜,害】
然后考虑两个点是否是矩形的左上右下,如果是左下右上需要做处理,然后口头和面试官说了这一点,然后他说那咱们就算写过了
下一步计算就不用说了,求出右下角节点的值,然后减去上方,左方,再加上重复减去的值,OK了

好了,看在这么详细的份上,求一份offer_(:з」∠)_四面希望是多唠嗑,
求求了求求了,救救孩子吧,学了仨月面试的东西了QAQ快崩溃了

更多模拟面试

全部评论

(6) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐