面试题汇总

最近参加了数十个公司的后台开发岗位面试，有些面试官问到了一些有意思的题目，个人觉得有必要记录下来，方便以后面试复习。

1. 任务系统复杂度体现在哪里？

   1. 配置规模大，2300 多行，66 列的配置
   2. 玩家实际接取的任务数量多，超过 500 多个任务。
   3. 代码量多，15000 行左右的代码，
   4. 支持任务目标多，超过 100 多种不同的任务目标
   5. 大量被其他系统所引用，超过 90 个代码文件里面引用了任务系统

2. lua metatable 的用处

3. C++ 多态 虚函数机制介绍

4. 二叉树遍历

   • 按遍历顺序分为：前序，中序，后序
   • 按实现方式：递归，循环+栈数据结构，Morris Traversal

5. stl shuffle的实现

    template< class RandomIt >
    void random_shuffle( RandomIt first, RandomIt last )
    {
        typename std::iterator_traits<RandomIt>::difference_type i, n;
        n = last - first;
        for (i = n-1; i > 0; --i) {
            std::swap(first[i], first[std::rand() % (i+1)]);
        }
    }
    //来自 <https://en.cppreference.com/w/cpp/algorithm/random_shuffle> 

6. 多线程开发需要注意的点？

   • 能不用就不用。单线程程序易写易调易维护。如果决定采用多线程，想清楚收益，最好能预估
   • 尽量不共享数据
   • 如果要共享数据，Go 不要以共享内存的方式来通信，相反，要通过通信来共享内存
   • 如果要共享数据
     • 如果只是一些简单数据共享，还可以使用原子类型。（如计算变量之类的）
     • 如果一定需要自定义临界区，尽量使用互斥锁 mutex, 多读少写的情况下使用读写锁，理顺锁的顺序避免死锁发生

7. 如何避免死锁？

   • 线程之间交错执行
     • 解决：以固定的顺序加锁
   • 执行某方法时就需要持有锁，且不释放
     • 解决：缩减同步代码块范围，最好仅操作共享变量时才加锁
   • 永久等待
     • 解决：使用 tryLock()定时锁，超过时限则返回错误信息

8. 出现死锁怎么检测？

   • 检测有向图是否存在环，从一个节点出发深度优化搜索，对访问过的节点进行标记，如果访问了已标记的节点，就表示有向图存在环。

9. 条件变量用来干什么的

   • 条件变量是线程可用的一种同步机制，条件变量给多个线程提供一个回合的场所。条件变量与互斥量一次使用，允许线程以无竞争的方式等待一个特定的条件发生。

10. redis 基础数据结构介绍？

11. 红黑树和跳跃表比较

    1. 时间复杂度差不多，跳跃表实现简单，方便调试和 review
    2. 跳跃表范围查找更方便（因为有 next 指针）
    3. 跳跃表并发支持更好，红黑树插入删除有 rebalance 的过程，会涉及到比较多的节点，而跳跃表因为是链表结构，并发加锁的粒度就会小一些，并发支持就更友好一些。

12. 自己的优势？

    • 肯专研，喜欢去看源码
    • 喜欢去接触新的技术，或者是提高工作效率的东西

13. 自己的劣势？ *比较好说话了，不够强势。

14. 挑战最大的事情？怎么解决的？

15. 缓存一致性

16. 扩容

17. 缩容

18. 单点

19. 故障自愈

20. 并发量大处理不过来怎么办？

21. epoll 与 select 区别

22. 进程与线程调度区别？

23. 大数相乘的实现

24. 格子最短路径数统计

25. 背包问题

26. 排行榜服务器实现 （上榜、下榜逻辑）

27. 好友服务器实现 （添加好友、删除好友逻辑）

28. 匹配服务器实现，以及如何选战斗服务器（ds)

29. 有序数组去除重复元素

30. 链表，将倒数 K 个节点，移到链表前面