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) 回帖