富途 C++客户端 40mins 一面凉经

八股

1、数组和链表的区别

2、Hashmap的实现

3、什么是线程

4、什么是线程安全

5、进程的通信方式

6、什么是死锁，造成死锁的条件

算法

1、删除链表倒数第k个结点（注意边界条件，倒数第一个，第一个）

2、判断括号的合法性

3、多次买卖的股票最大利润

答案

八股

1、数组和链表的区别
1）数组连续空间，链表非连续空间
2）数组查找O(1)，链表查找O(n)
3）数组增删O(n)，链表增删O(1)
4）数组适合多查找少增删，链表适合多增删少查找

2、Hashmap的实现
1）对key作哈希计算，决定存储在哪个数组
2）不同元素会计算到相同的值，造成哈希冲突
3）哈希冲突的解决办法，开链法，随机探寻，再次哈希
4）STL的Hashmap达0.75容量进行2倍扩容

3、什么是线程
1）一个进程有多个线程
2）进程是资源分配的单位，线程是资源调度的单位
3）线程只有很少属于自己的数据结构
4）同个进程的线程通过读写同一块内存空间进行通信

4、什么是线程安全
多个线程对同个内存空间进行读写时，保证内存空间数据的一致性
线程同步的方式：互斥量，条件变量，互斥锁，读写锁

5、进程的通信方式
管道、消息管道、共享内存、信号、信号量、套接字

6、什么是死锁，造成死锁的条件
1）进程无法得到资源而循环等待
2）系统资源不足，分配不当，进程推进顺序不当
3）互斥，请求保持，占有不剥夺，循环等待

7、C++的特性
1）封装——代码模块化
2）继承——代码重用
3）多态——基类指针指向不同子类实现相同函数不同动作

算法

1、删除链表倒数第k个结点（注意边界条件，倒数第一个，第一个）
快慢指针，一个while循环

虚拟头结点防止删除的是头结点
pre slow fast
fast移动到k
fast移动到链表尾部
slow指向删除元素 pre->next=slow->next;

2、判断括号的合法性
左括号入栈，右括号判断是否为空，不为空判断栈顶是否匹配
3、多次买卖的股票最大利润
贪心解决，只要股票升就买

if(prices[i]>prices[i-1]) 
    ans+=prices[i]-prices[i-1]