南京大学计算机学院面试准备

该内容是我面试南京大学计算机学院保研的时候的准备题目，最后是面试的时候问到的问题。

1. 自我介绍

​ Good afternoon, professors. It is my great honor to attend the interview myself here. I’m LiangYuanshao from Hunnan University, majoring in software engineering. Today I will introduce myself from three aspects: education background, Scientific research experience and my future plan.
​ First of all, I ranked 12th among 131 students and have received Scholarship twice . During my spare time, I devote myself to learning Web crawlers and data analysis, So I am good at them.
​ Next, in addition to professional knowledge learning, I also actively participated in various competitions, which not only exercised my hard skills such as programming and document writing, but also exercised my soft skills of cooperation with others and innovative thinking.
​ Finally, my future plan. I have made decision to apply for master degree and focus on my favorite field: Big Data. In addition, going further study in XiAnJiaoTong University has always been my dream. I sincerely hope that I can get this opportunity to make my dream come true here.
Thank you for your time and attention！

2. 进程和线程的区别

1. 进程是资源分配最小单位，线程是程序执行的最小单位
2. 进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈段和数据段，线程没有独立的地址空间，它使用相同的地址空间共享数据
3. CPU切换一个线程比切换进程花费小
4. 创建一个线程比进程开销小
5. 线程之间通信更方便，同一个进程下，线程共享全局变量，静态变量等数据，进程之间的通信需要以通信的方式（PIC）进行；（但多线程程序处理好同步与互斥是个难点）
6. 多进程程序更安全，生命力更强，一个进程死掉不会对另一个进程造成影响（源于有独立的地址空间），多线程程序更不易维护，一个线程死掉，整个进程就死掉了（因为共享地址空间）

3. 循环引用

循环引用指两个对象相互强引用了对方，从而导致两个对象都无法被释放，引发了内存泄漏现象，互相引用变量的引用计数都为1，本质上是引用计数的原因。

只靠强引用计数方式，会存在循环引用的问题，导致对象永远无法被释放，弱引用就是专门用来解决循环引用问题的：

「若 A 强引用了 B，那 B 引用 A 时就需使用弱引用，当判断是否为无用对象时仅考虑强引用计数是否为 0，不关心弱引用计数的数量」

这样就解决了循环引用导致对象无法释放的问题，但这会引发野指针问题：当 B 要通过弱指针访问 A 时，A 可能已经被销毁了，那指向 A 的这个弱指针就变成野指针了。在这种情况下，就表示 A 确实已经不存在了，需要进行重新创建等其他操作

4. 操作系统怎么利用多核？

现在CPU是多核的，不依赖PIC，而是依赖APIC。（Advanced Programmable Interrupt Controller）
每个核都有LAPIC，处理内部的定时芯片产生的定时中断，进行调度
https://www.bilibili.com/video/BV1VT4y1v7o9

5. 英文介绍二叉搜索树

Binary search tree It is either an empty tree or a binary tree with the following property: if its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node; If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are also binary sort trees respectively

6. 英文介绍二叉搜索树的时间复杂度

closely related to the tree shape.

left and right subtrees of each node in the tree are roughly the same height, the tree height is logN. the average search time complexity is on the order of O(logN)

if the inserted keywords are in order, the BST degenerates into a single tree structure. the average search time complexity is on the order of O(n).

7. 介绍 stackover flow

Stack overflow is due to the fact that the C language family has no built-in checks to ensure that data copied to the buffer is not larger than the size of the buffer, so when the data is large enough, the buffer will overflow.

8. 什么是函数服务

开始是云计算里面三种计算模式，基础设施即服务(IaaS)、平台即服务(PaaS)、软件即服务(SaaS)。Faas是一种新的运算模式

云计算里面的是对函数服务的高度抽象，给它一个输入，就给返回给你一个输出。

9. Java和C++的区别

1. Java源码会先经过一次编译，成为中间码，中间码再被解释器解释成机器码。对于Java而言，中间码就是字节码(.class)，而解释器在JVM中内置了。C++源码一次编译，直接在编译的过程中链接了，形成了机器码。
2. C++比Java执行速度快，但是Java可以利用JVM跨平台。
3. C++中有指针，Java中没有，但是有引用。
4. C++支持多继承，Java中类都是单继承的。但是继承都有传递性，同时Java中的接口是多继承，类对接口的实现也是多实现。
5. C++运算符可以重载，但是Java中不可以。
6. 同时C++中支持强制自动转型，Java中不行，会出现ClassCastException（类型不匹配）。
7. C++中，开发需要自己去管理内存，但是Java中JVM有自己的GC机制，虽然有自己的GC机制，但是也会出现OOM和内存泄漏的问题。C++中有析构函数，Java中Object的finalize方法。
8. Java是纯面向对象的语言，所有代码（包括函数、变量）都必须在类中定义。而C++中还有面向过程的东西，比如是全局变量和全局函数。

10. new和malloc的区别

1. new是C++里面的操作符，由编译器支持。malloc是函数，是由头文件支持

2. new无需指定内存大小，编译器会根据类型信息自行计算，malloc需要指定

new之间返回生成对象的指针，是安全操作。malloc只是分配的内存，返回是void* ，需要强制转型，不安全

new可以重载

new失败就抛出异常，malloc失败就返回null

new可以检测内存泄漏到具体哪一行

11. topK问题

https://blog.csdn.net/zjwreal/article/details/90674978
快排的partition函数和最小堆

12. 判断图是否有环

dfs，拓扑排序，并查集

我们可以使用并查集来判断一个图中是否存在环：

对于无向图来说，在遍历边（u-v）时，如果结点 u 和结点 v 的“父亲”相同，那么结点 u 和结点 v 在同一个环中。

对于有向图来说，在遍历边（u->v）时，如果结点 u 的“父亲”是结点 v，那么结点 u 和结点 v 在同一个环中。

11. 给你一个长度为 n 的数组，其中只有一个数字出现了奇数次，其他均出现偶数次，问如何使用优秀的时空复杂度快速找到这个数字
    进行遍历异或

12. 给你一个长度为 n 的数组，其中只有一个数字出现了大于等于 n/2 次，问如何使用优秀的 时空复杂度快速找到这个数字

    public int find(int[] nums) {int count = 1;int result = nums[0];for (int i = 1; i < nums.length; i++) {count = result == nums[i] ? ++count : --count;if (count == 0) {result = nums[i + 1];}}return result;
    }

    13. 动态分配的注意事项

    https://blog.csdn.net/qq_36698189/article/details/114989965

当我面试后具体问题到的问题

1. Krustra算法英文介绍
2. Krustra算法的数据结构？几个优化过程？
3. np和p问题了解吗？我说我不了解，常用是java语言。问我，java类加载机制是什么?
4. 离散数学你最清楚什么内容？我说是最短路径，说一下Dijkstra算法和Bellman-fold算法的区别？为什么Bellman-fold算法能够解决负权？
5. 并发和并行？
6. Cpu的数据哪里来？？？Cache相关的问题，我没了解老师意思
7. 最后问我我的特长和缺点