深信服在线笔试-2018.9.22

  还记得上次深信服笔试挺惨的，选择题错一堆是因为计算机系统基础部扎实，编程题是因为没有能够调试的IDE，写的程序都没跑过，但是编写和思路都很快想出来。
  这次总体难度相对于上次降低了很多，由于我个人编程题发挥太垃圾了弄得一塌糊涂GG了，题型相对于上次题型算是改动挺大，不定向选择+填空题+编程题，从毕业到现在都没怎么写过算法题，忙着补充理论基础然后没注重算法题就栽跟头了，之前做畅游笔试信心满满觉得笔试难度大多不难，这次的算法题比上次简单很多，不过我还是GG了。
  经历过这次笔试，对秋招感觉越来越没有把握，有点小绝望，发现秋招群中有很多19届学生比现在的我优秀太多了，后面没机会校招笔试这些公司了，偷懒提前享福，现在都得为这些懒惰负责。
  面试是没机会了，就来记下一些记得的题觉得该写下来或者是没有完成的题目，这次选择题难度还可以，比上次容易了一些，数量也少了一些，而编程题多了些，我觉得编程题可能做过算法竞赛，如ACM或者蓝桥的同学应该会比较熟悉一些，能够更快的理解题目目的，我个人觉得写这种编程题，首先把其样例输入代码给完成，再去完成算法的编写比较方便。

选择题

  （下列序号并不是试卷原先的题号）
1、下面哪个信号是由应用程序捕捉segment fault?
A、SIGSEGV
B、SIGFPE
C、SIGILL
D、SIGBUS
  这道题，我是依靠着写多进程程序的印象，选的A，捕捉段错误，虽然选对了，而我自己记住的信号也就几个，B、C、D没接触过，所以来记录一下。

发出信号的原因很多，这里按发出信号的原因简单分类，以了解各种信号： 　　（1）
与进程终止相关的信号。当进程退出，或者子进程终止时，发出这类信号。 　　（2）
与进程例外事件相关的信号。如进程越界，或企图写一个只读的内存区域（如程序正文区），或执行一个特权指令及其他各种硬件错误。 　　（3）
与在系统调用期间遇到不可恢复条件相关的信号。如执行系统调用exec时，原有资源已经释放，而目前系统资源又已经耗尽。 　　（4）
与执行系统调用时遇到非预测错误条件相关的信号。如执行一个并不存在的系统调用。 　　（5）
在用户态下的进程发出的信号。如进程调用系统调用kill向其他进程发送信号。 　　（6）
与终端交互相关的信号。如用户关闭一个终端，或按下break键等情况。 　　（7） 跟踪进程执行的信号。
　　Linux支持的信号列表如下。很多信号是与机器的体系结构相关的，首先列出的是POSIX.1中列出的信号： 信号 值 处理动作
发出信号的原因

SIGFPE 8 C 浮点异常
SIGBUS 10,7,10 C 总线错误(错误的内存访问)
SIGILL 4 C 非法指令
  可以看到SIGBUS和SIGSEGV似乎都是错误内存访问的类型，而两者的区别就在于，SIGBUS通常是未对齐的数据访问所致，如：
（下面代码在windows下的signal处理一律都是SIGSEGV，即段错误）

char *p=(char*)0x00001111;
*p=1;

  本来上面代码就是非法地址赋值，就会被SIGSEGV捕获，但是如果把char改为int**，就不一样了，可以看下面的汇编代码，异常会在写入p地址值的时候发生，在unix中，第一个是因为访问非法地址而报错，而第二个是因为在写入P的时候，在取指针p的两字位置(地址mod4)出错，0x1111 mod 4 !=0，也就是字节未对齐，就是SIGBUS （看别人的解释，自己大概阐述的）。

char *p = (char*)0x00001111;
01142731 mov dword ptr [p],1111h 
*p = 17;
01142738 mov eax,dword ptr [p] 
0114273B mov byte ptr [eax],11h int *p = (int*)0x00001111;
00AD2731 mov dword ptr [p],1111h 
*p = 17;
00AD2738 mov eax,dword ptr [p] 
00AD273B mov dword ptr [eax],11h 

  
  
二、请选出尽可能不调整数列上顺序而且算法复杂度为O(NlogN)的稳定排序算法。
A、归并排序
B、快速排序
C、插入排序
D、选择排序
  
  这道题，我没看懂不调整数列上顺序是什么意思，如果按NlogN来选，A、B符合，但是如果顺序很杂乱，是得调整很多次，也就是大的值在前面，而小的值在后面，就得不停的交换，所以我个人觉得可能A、B是正确答案。
  
  
三、（答案不明）

  这道题，我自己最后瞎选的C、D，现在好好想的话觉得应该A、B、C好像都对，暂时找不到答案，知道答案的童鞋可以回复我一下，之前只是大概的了解hash的这几种做法，但并没有去实现以及深入了解，我这几天也来补补hash的知识。
  
  

填空题

1、

  答案是3/1，这道题刚开始看的时候，我是有点懵的，毕竟好久没计算了，概率论也是我的差项，算出来的时候感觉这概率好违和，还以为错了=_=，哈哈…
  这个问题在百度百科上有，即：三门问题，我的解法是，算出他不能得到豪车的概率P(A)，用1-P(A)即可，而他不可能得到豪车的情况是，他第一次选的门就是正确的，第二次选绝对是错误的，因为有两扇门，所以就是P(A)=2/6 * 2=2/3，则他能赢的机率是1/3。
  
  
2、

  这道题我写错了，因为我刚刚写了程序跑了一下，答案是35，而我为什么写6呢，原因我把题目看错了，认为A到B是在方块上移动，而且就这样数，我特么还数错了，现在才知道是在线上的点移动Orz，从数学的角度分析，我们可以看到从A到B，最短路径要一共要经过7个交点，而且必定有3次向下，4次向右，即一共的步骤是7次，所以我们只要计算C7 4或者C7 3就可以，算出在有效次数中，向下或者向右的组合有多少种，就知道一共的数目了。

int findroute(int x, int y) {cout << x << "and " << y << endl;if (x < 0 || y < 0)return 0;if (x == 0 && y == 0) {return 1;}int ret = 0;ret+=findroute(x - 1, y);ret+=findroute(x, y - 1);return ret;
}

编程题

  个人觉得题目难度还是可以的，有些题目很简单，有些题目还是需要动脑思考，主要是阅读理解题目要求你做什么，我把时间都纠结在第一道题以及其网页后台的调试结果，导致后面的题没有编写，以及第一道题没有能够调试成功…
  （2018.9.22更新代码以及编程题）
  （2018.9.23更新第三题的代码，看了题目很久才知道题目要我做什么Orz）
  个人总结：在这笔试之后，我自己花时间重新完成了这几道编程题，我能够确认的是，如果当天我的状态好一些，我能够在我做题做到编程题仅剩的1个小时里完成题目1、2，题目3我没读懂题目意思有点伤，题目4除非再给我40+分钟，我才能够解决，这就是缺乏算法训练，如果是参加ACM或者相关算法竞赛，这些题难度不大，但是对于没有刷题训练的童鞋，我个人觉得会需要很多时间去思考以及实现，就比如我Orz，光理解题目意思就花了很长时间…
  
1、
  由于没截图完整，在这里补充一下题目大概意思吧，输入的第一行是测试的数量，第二行是木板的数量，第三行的数据是每个木板的高度。（上图也是我通过样例的截图，然而提交后显示0%样例通过…）
  木板的意思是，例如2 1 2，就是第一块木板高为2，第二块木板高为1，那么两者之间能够存储1平方米的水量，如果第三块木板为2，那么中间的木板被淹没，则存储的水量为4平方米。
  所以样例输入的木板数量3，高度2 1 3，得到的结果是4。
  图片右上角显示我还有10分钟，我莫名其妙花了大概50分钟在这道题，因为我一直在考虑用什么方法去解决，递归还是依靠栈还是迭代算出来？所以后面的题我也只能翻一翻截个图了，很久没写算法题，怎么去解决问题的思路乱套了，感觉必须得多刷些这样得题才能够去应战，理解题目的意思，然后分析，再去实现，现在的这衰样都是自己懒出来的。
  而我提交的代码存在的问题是，没有考虑周全，只考虑了部分情况，不可能0%样例通过，我自己测了测试用例是通过的，弄得我一直在想问题出在哪不舍得做后面的题，我自己能够测通过得样例，网页上得样例检测也能通过，但是在编辑器页面保存调试就显示0%…
  我的做法：
  首先得知道有哪几种情况出现，高度级别，矮、高、超高，而我自己分析主要分为这三种情况：
  1、高矮高。（高矮超高与其是同一情况）
  2、超高矮高。（我原先的代码忽略了这个情况，已经修改过来了）
  3、矮高矮。

  所以大概的思路就是，符合情况3，就直接累加当前木板与下一个木板的存储值然后移动head与end，否则就遇到1、2情况，就把end指向下一个end，然后比较head和end，而mid负责记录中间的木板数量值。
  head，mid，end，其中head和end就像指针，head指向当前木板，end指向后面的木板，而mid仅仅是一个计数器，sum用于存储值。
  在校招群里我看到有童鞋使用vector和stack之类的搭配，或者与我一样使用递归，而他们好像是完美通过测试，然而我却卡在门外，Orz，我自己的失误的确很多…

代码：

//head，mid，end初始值因为0，0，1
void water(int *moodh,size_t moods,int head,int mid,int end,int &sum) {if (end == moods) return;
//这里原先是<符号，因为这个原因碰到情况1会计算错误，现在改成<=if (moodh[head] <= moodh[end]) {sum += mid * moodh[head] + moodh[head];mid = 0;water(moodh, moods, end,mid, end + 1,sum);}else {//我原先编写的没有if(end-head!=1)这段，忘了情况2，现在补充的if (end - head != 1) {int val = moodh[head] > moodh[end] ? moodh[end] : moodh[head];sum += mid * val + val;water(moodh, moods, end, mid, end + 1, sum);return;}//以矮结尾，情况3if (end == moods - 1) {sum += moodh[end];return;}water(moodh, moods, head,mid+1, end + 1,sum);}	
}int main()
{int c, size, sum = 0, cnt = 0;cin >> c;int *cmd = new int[c];while (cnt<c) {cin >> size;int *ary = new int[size];for (int i = 0; i < size; i++) {scanf_s("%d", &ary[i]);}water(ary, size, 0, 0, 1, sum);delete ary;cmd[cnt] = sum;cnt++;sum = 0;}for (int i = 0; i < c; i++) {cout << cmd[i];if (i != c - 1) {cout << endl;}}delete cmd；	return 0;
}

  
  
2、解二元一次方程
  题目过于啰嗦，要求输入是，第一行输入测试数据T组，然后第二行输入处理数据。
  处理数据是 a1，b1，c1，a2，b2，c2，其中a1，b1，c1是一个方程的系数，a2，b2，c2是一组方程的系数，假设a是x的系数，b是y的系数，那么我们输出的结果就是求出x的值和y的值，无解的话输出unknow，其中这些数据都是整数，非整数就是unknow。
  最简单的解法就是消元法，或者用大学里的代数知识，用行列式去计算，因为是二元一次方程组，只要把其中一个元化为0（即化成阶梯型），然后用行列式去判断其有解还是无解。
  因为我们要求的是整数解，所以就可以忽略很多情况了，只需要考虑是否能消元或者化为阶梯矩阵，如果化的过程中无法整除，那么就是无解。
  
  个人还是使用消元法，判断也很简单，我自己用了几个简单得例子测了代码没问题。
代码：

void solution(int *ary,int &ret1,int &ret2) {if (ary == nullptr) {return;}int *p = ary;int *q = ary + 3;int cnt = 1, val1 = *p, val2 = *q;while (cnt < 4) {*p++ = (*p)*val2;*q++ = (*q)*val1;cnt++;}for (int i = 0; i < 3; i++) {ary[i + 3] = ary[i+3] - ary[i];}if (ary[5] % ary[4] != 0) {ret1 = -1;ret2 = -1;}else {ret2 = ary[5] / ary[4];ret1 = (ary[2] - ary[1] * ret2) / ary[0];}
} 
int main()
{int ary[] = { 3,4,7,5,6,11 };int s1,s2;solution(ary, s1, s2);if (s1 == -1) {cout << "unknow unknow" << endl;}else {cout << s1 << " " << s2 << endl;}return 0;
}

  
  
  
3、求最小子序列合最小值
  
  
  这道题目前面的话把我看迷糊了，有用的话也就是我打箭头的那里，也就是求一个序列的子序列合最小值。
  这道题解决方式的话，我是使用类似于第四道编程题的解法，即穷举，毕竟要找到所有的最小值或者最大值，你就得把结果都计算出来。

int findMinSum(int *ary,int start,int size) {if (start == size - 1) {return ary[start];}int minv = 0, sum = 0;for (int i = start; i < size; i++) {sum += ary[i];if (minv > sum) {minv = sum;}}minv = min(findMinSum(ary, start + 1, size), minv);return minv;
}
int main()
{int ary[] = { 2,-3,-4,1,-3,2,-1 };int ret=findMinSum(ary, 0, 7);cout << ret;return 0;
}

  
4、求最优值
  这道题的题目前面的废话太多，就截图该部分。


  很简单的一道题目，就是介绍的字很多，大概意思就是求出不同列不同行的组合最大值。
  原先以为简单而打算找个时间随便写个代码就能运行，现在有点打脸了，写的时候眉头一皱发现事情并没想得那么简单，实际写还是有点复杂的，主要问题是如果列数一多，怎么去判断是否同行同列，也就涉及到了该用怎样的数据结构去保存点的信息。
  而完成这道题，我花了近一小时的时间，包括我思考怎样去求解以及实现与调试，我第一时间所想到的求解方法就是写各种循环，嵌套进去从而达到穷举，然后发现需要保存许多状态值，如是否同行同列，然后又存储各种状态的求和值，就感觉我自己用一般的循环是行不通的（在写这一般的循环嵌套花了挺长时间Orz），于是就想到了借用stack，达到保存值，于是就有了下面的代码。

  情况的话分为两种：
  1、人数=<岗位
  2、人数>岗位
  情况这样分是根据我自己的写的算法设计的，第一种情况，我是通过岗位去遍历人数，从而存储不同搭配得到的值，而第二种情况还使用第一种情况的话，会存在有一些人数与岗位搭配没算进去，这是和我写的程序相关的，所以第二种情况就是使用人数去遍历岗位，具体实现如下。

代码：

struct Node {int raw;int col;int val;Node(int x = 0, int y = 0,int v=0) :raw(x), col(y) ,val(v){};
};int findMaxSum(int **ary,int row,int col) {int max = -1, val = 0, cnt = 0;//记录岗位是否被占用int *statcol = new int[col]();int realr, realc;//pary是用于判断是哪种情况的数组int **pary;stack<Node*> mlist;//如果row>col，将矩阵转置if (row > col) {realr = col, realc = row;pary = new int*[col];for (int i = 0; i < col; i++) {pary[i] = new int[row];}for (int i = 0; i < col; i++) {for (int j = 0; j < row; j++) {pary[i][j] = ary[j][i];}}for (int i = 0; i < row; i++) {delete[] ary[i];}delete[]ary;}else {realr = row, realc = col;pary = ary;}//初始化for (int i = 0; i < realc; i++) {int flag = realc - 1 - i;auto tmp = new Node(0,flag,pary[0][flag]);mlist.push(tmp);}while (!mlist.empty()) {auto cur = mlist.top();auto curraw = cur->raw, curcol = cur->col, curval = cur->val;mlist.pop();//重置statcolif (curraw == 0) {for (int i = 0; i < realc; i++)statcol[i] = 0;}if (curraw == realr - 1) {max = curval > max ? curval : max;statcol[curcol] = 0;continue;}if (statcol[curcol] == 1) {continue;}statcol[curcol] = 1;for (int i = 0; i < realc; i++) {int flag = realc - 1 - i;if (statcol[flag] != 1) {auto tmp = new Node(curraw + 1, flag, curval + pary[curraw + 1][flag]);mlist.push(tmp);}}delete cur;}for (int i = 0; i < realr; i++) {delete[] pary[i];}delete[]pary;return max;
}
int main()
{
//测试用例是3行，2列const int r = 3;const int c = 2;//ary在findMaxSum中deleteint **ary = new int*[r];for (int i = 0; i < r; i++) {ary[i] = new int[c];}for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {cin >> ary[i][j];}}int ret = findMaxSum(ary, r, c);cout << ret;return 0;
}

  
结果图：