INTERVIEW #0

一、造成网络延迟的可能原因

1，WiFi所有用户上下行流量共用一个信道，当用户太多或者有人在下载大的资源时带宽不够，丢包；

2，线路质量不佳导致信噪比太低，比如光纤损耗太大等。

二、IPv6优势

1，IPv4地址不够用，IPv6有$2^{128}$个地址；

2，使用更小的路由表，转发速度更快；

3，扩充了DHCP协议，支持自动配置；安全性更高，有更好的头部格式，允许扩容......

三、找到单向无环链表的中间元素，若结点总数为偶数，返回第二个元素。

https://leetcode.com/problems/middle-of-the-linked-list/

只扫描一遍的做法：设两个指针，初始指向头结点，p1每次走两步，p2每次走一步，p1到达链尾，p2到达中间。假设链表带有头结点。

/*单链表定义*/
struct ListNode{
	int val;
	ListNode* next;
	ListNode(int x) :val(x), next(NULL) {};
};

class Solution {
public:
	ListNode * middle(ListNode* head)
	{
		if (head == NULL)
			return NULL;
		ListNode* fast = head;
		ListNode* slow = head;
		while (fast && fast->next)
		{
			fast = fast->next->next;
			slow = slow->next;
		}
		return slow;
	}
};

四、给出四个点坐标，判断是否是凸四边形

不妨扩展下该问题，给出任意n个点，判断是否凸多边形。

http://acm.hdu.edu.cn/showproblem.php?pid=2108

凸多边形就是所有内角均小于180°，方法有好几种，这里利用定点凹凸性判断：

设当前三个连续的顶点$P_0, P_1, P_2$，计算向量$P_0P_1$, $P_1P_2$的叉积，若结果为正，表示多边形顶点逆时针转；若结果为负，两向量夹角大于180°，则为凹多边形。

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include <cstdio>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 struct point {
 9     int x, y;
10 }p[600000];
11 
12 int cross_p(point a, point b,point c)
13 {
14     return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
15 }
16 
17 bool isConvex(int n)
18 {
19     for (int i = 0; i < n; i++)
20     {
21         //叉积量值
22         if (cross_p(p[i], p[(i + 1) % n], p[(i + 2) % n]) < 0)
23             return false;
24     }
25     return true;
26 }
27 
28 int main()
29 {
30     int n;
31     
32     while (scanf("%d", &n) && n)
33     {
34         for (int i = 0; i < n; i++)
35         {
36             scanf("%d%d", &p[i].x, &p[i].y);
37         }
38         if (isConvex(n))
39             printf("convex
");
40         else
41             printf("concave
");
42     }
43     
44     return 0;
45 }

五、两个位数在10万位以内的数乘法

https://leetcode.com/problems/multiply-strings/

高精度乘法，模仿我们笔算的过程。每一位$res[i + j]$的构成：$res[i + j] + carry + a[i] * b[j]$，注意去掉结果的前导0。

 1 class Solution {
 2 public:
 3     string multiply(string num1, string num2) {
 4         int a[120], b[120], res[250];
 5         memset(a, 0, sizeof(a));
 6         memset(b, 0, sizeof(b));
 7         memset(res, 0, sizeof(res));
 8 
 9         int lena = num1.size(), lenb = num2.size();
10         for (int i = 0; i < lena; i++)
11             a[i] = num1[lena - i - 1] - '0';
12         for (int i = 0; i < lenb; i++)
13             b[i] = num2[lenb - i - 1] - '0';
14 
15         for (int i = 0; i < lenb; i++)
16         {
17             int carry = 0;
18             for (int j = 0; j < lena; j++)
19             {
20                 res[i + j] = res[i + j] + a[j] * b[i] + carry;
21                 carry = res[i + j] / 10;
22                 res[i + j] %= 10;
23             }
24             res[i + lena] = carry;
25         }
26 
27         int len_res = lena + lenb;
28         //去掉结果的前导0,若结果为0，保留一个0
29         while (res[len_res - 1] == 0 && len_res > 1)
30         {
31             len_res--;
32         }
33         
　　　　　　　//使用字符串流将整数转为字符串
34         stringstream ans;
35         for (int i = len_res - 1; i >= 0; i--)
36         {
37             ans << res[i];
38         }
39         return ans.str();
40     }
41 };

六、其它

1，操作系统：CPU调度，用户态&内核态，IPC，各种锁，实时系统；

2，数据结构：判断有向图是否存在回路（拓扑排序、求最短路、关键路径、BFS），排序（快排、冒泡、选择、插入），链表是否有环；

3，计网：ARP、TCP/UDP、NAT、802.11ac协议，ping过程；

4，C++多态。