南大部分实验室面试比较早，比如WebSoft。发邮件给老师，老师会回邮件让进QQ群，在群内会有学长联系面试。我进的群里，有一个东北大学的同学，有一个哈工大威海的同学。
南大Websoft实验室安排的提前面，是我的第一场面试，个人发挥比较差，未能通过。
由学长负责，腾讯会议开视频与屏幕分享，给出几道编程题目，现场敲代码并提交文件。根据学长所说，大多数面试的同学基本上做到了第二题。
先说题目难度，没有水题，题目整体难度是偏大的，并且对时间复杂度有要求，非常考验算法功底。
首先会被问到，看到题目，有什么解题思路、时间复杂度是多少，之后会被要求优化时间复杂度，直至最佳，之后才开始敲代码。
import java.util.*;
class P {
int x,y;
P(int x,int y) {
this.x=x;
this.y=y;
}
}
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[][] G=new int[n][n];
for(int i=0; i list=new ArrayList<>();
for(int i=0; i=0&&G[i-1][j]==0) {
G[i-1][j]=G[i][j]+1;
list.add(new P(i-1,j));
}
if(i+1=0&&G[i][j-1]==0) {
G[i][j-1]=G[i][j]+1;
list.add(new P(i,j-1));
}
if(j+1
#include
using namespace std;
#define TARGET 24.0
bool judge2(float a,float b) {
return (
a+b==TARGET || a-b==TARGET ||
a/b==TARGET || a*b==TARGET ||
b-a==TARGET || b/a==TARGET
);
}
bool judge3h(float a,float b,float c) {
return (
judge2(a+b,c) || judge2(a-b,c) ||
judge2(a*b,c) || judge2(a/b,c) ||
judge2(b/a,c) || judge2(b-a,c)
);
}
bool judge3(float a,float b,float c) {
return (
judge3h(a,b,c) || judge3h(a,c,b) ||
judge3h(b,c,a)
);
}
bool judge4h(float a,float b,float c,float d) {
return (
judge3(a+b,c,d) || judge3(a-b,c,d) ||
judge3(a*b,c,d) || judge3(a/b,c,d) ||
judge3(b/a,c,d) || judge3(b-a,c,d)
);
}
bool judge4(float a,float b,float c,float d) {
return (
judge4h(a,b,c,d) || judge4h(a,c,b,d) ||
judge4h(a,d,b,c) || judge4h(b,c,a,d) ||
judge4h(b,d,a,c) || judge4h(c,d,a,b)
);
}
int main() {
float a,b,c,d;
cin>>a>>b>>c>>d;
if(judge4(a,b,c,d)) {
cout<<"True";
} else {
cout<<"False";
}
}
第三题：
题目描述：输入两个正整数n和m(0
用例输入：1 100
用例输出：80
用例说明：[1,100]之间不包含4或62的整数个数为80
答题碎碎念：
第一道题目乍看很简答，一个二维数组，算出每个0到1的最短距离就可以。
我一开始想到的是直接遍历数组，每找到一个1，再遍历数组，更新所有的0到它的距离。
这个算法是最笨的，时间复杂度达到了O(N^4)，肯定要进行优化。
一开始有点不在状态，想了很久，最后慢慢向BFS靠拢，想到可以先遍历每一个1，然后向周围更新一步，得到可以一步到达的所有点，更新值为2。再遍历数组，找到所有的2，以此类推。最坏情况下，需要遍历N次数组，因此时间复杂度为O(N^3)。
想到这里，我本认为应该可以了，但是学长说还能再优化。又想了好久，想到用空间换时间，再用一个队列存放每一层遍历的结点，这样可以免去一次次遍历。时间复杂度是O(N^2)，这个时候才开始敲代码。
第二道题目我觉得很简单，不断降维就可以了，注意要用float。因为只有4个数据，所以直接手写代码就行了，不需要每次封装成一个数组再处理。这里不需要优化时间复杂度，因为不存在数据规模的问题。这道题目我很快就解决了，学长说面试的同学里我这道题目写得最快，还问了问我之前是不是做过这道题目。
一般是做到第几个题就给几个题目，所以大多数同学只有两个题目。第三个题目，如果不考虑时间复杂度的话，那么非常简单，判断每一个数字是不是包含4或62就可以了，时间复杂度是O(mlogm)。但是不优化时间复杂度是不可能的，我一开始想到，因为我只需要计算符合条件的整数的个数，并不需要求出是哪些整数，所以可以通过容斥原理去计算。我在这个方向想了很久，尝试能不能通过数学公式算出来从n到m中包括k的数字个数。判断从n到m中所有包括4的数字个数就很已经麻烦了，需要考虑很多情况，比如最低位为4有m个，那么倒数第二位为4就不能再最低位为4。
学长提醒我考虑字符串的前缀。我最后才想到动态规划的做法，dp[i][j]代表以i开头、长度为j的数字中不包括4或62的个数。那么递推公式就是：
dp[i][j]=dp[0][j-1]+ dp[1][j-1]+ ( i==6?(dp[2][j-1]):0 )+ dp[3][j-1]+ dp[5][j-1]+ dp[6][j-1]+ dp[7][j-1]+ dp[8][j-1]+ dp[9][j-1]
只需要考虑从1到m中不包括4或62的数字个数就可以了。关键是怎么样找到小于等于m。这个可以通过从高到低遍历m的每一位实现。时间原因，我只找到了算法，代码还有问题。
面试
用英语介绍一下自己的项目
自己的问题：准备不充分、卡顿很严重
对后面同学的建议：针对于自己简历里的所有项目，准备中文介绍与英文介绍各一份。由于我本科在湖南，但家乡在山东，所以被问到了为什么想要去湖南上大学？以及为什么想要来南大？还报名了其他研究组或者其他学校吗？你的离散数学学了什么？介绍一下闭包的概念？简历里的一个项目的具体信息与流程？具体有几个人，怎样分工？今后的就业打算？
论文汇报
给了一篇论文，要求提前学习、制作PPT、现场汇报。
这篇文章属于知识图谱方向，由于我这方面的经验不多，加上准备时间比较短，所以论文汇报时的发挥比较一般。针对于汇报之后的提问，我也没能回答好。所以在意料之内地，不久后收到了被拒绝的通知。
南大计算机（取得offer）
具体地，分为面试与笔试两个部分。
面试
编译原理中怎样解决二义性问题？
因为我学习过这门课程并且取得了比较不错的成绩，所以被问到了。用英语介绍一下栈溢出 stack overflow？如果下载了一个开源代码，输出语句出错，要怎么去检查？C++程序员动态操作存储空间需要注意什么？什么情况下的溢出是有危害的？什么情况下的溢出是没有危害的？介绍一下KMP算法
笔试
两道读程序选择答案的题目一道反码题目，根据记忆，大概是这个样子：
已知[X]补=X0X1…Xn(n为整数)，则它的模是多少？
当时我并没有做出来。与2n时间复杂度的级别相同的是？
A. n! B. 3n C.2n+1
整体上，南大CS比较看重计算机基础知识。我觉得笔试面试是很客观的，比如笔试，完全是抽取题目。顺利取得了offer。
