面(gun)试(cu)

最近面(gun)试(cu)了几家公司……有必要介绍一点人生的经验

因为记不太清楚了所以就凑在一起写吧

算法类

  • 常见的排序算法有哪些(Bogo 冒泡 插入 快排 堆排 BST 内省 桶排(基数))
  • 报一下快排代码(…)
  • 内省排序原理

语言类

  • C++如何zero-initialize一个对象
  • (接上)为什么不能在有string时用memset
  • C++如何实现多态?(静态、动态)
  • 虚函数原理、用途
  • C++的优势、劣势
  • C++ vs Python
  • Golang的优势。协程的优势、应用场景等
  • 会写Java吗……(变化厂专属问题……)

Linux系统类

  • fork+printf问输出多少个\(缓冲区。。。但是这题太捉急了……是未定义行为)
  • login/shell 顺序、区别
  • 物理地址、虚拟地址,线性地址
  • 编译、链接具体做了哪些工作(不太懂……
  • 静态库、动态库
  • Makefile
  • gdb常用命令……如何在输出的时候中断(catch syscall 1)

Redis

  • Redis的内部数据结构、实现原理(刚好看了SET……)
  • 事务 VS 脚本
  • 主从关系

项目相关类

  • LevelDb的底层原理(LSM Tree + SkipList) 为什么采用?
  • 序列化库及原理(不太会……)
  • 提升数据库性能的方法(表拆分。。。)
  • 网络原理(不会。。。GG)
  • Scheme解释器中作用域的实现……递归的实现
  • profile的相关方法……
  • OpenCV了解程度……描述SIFT算法……

并发

  • 进程间同步机制(文件锁、Signal、共享内存……)
  • 线程间同步机制(信号量– >mutex/cond var spinlock spinlock性能一定更好吗……)
  • 无锁队列的实现(只会写入队orz。。。)
  • 为什么要有锁、内存屏障……(内存访问非原子,处理器核缓存,指令重排。。。)
  • CAS问题

杂向

  • 管理团队中最经常碰到的一些问题
  • 文档、测试的重要性
  • 谈谈写代码最重要是什么……(抽象 <-> 性能 之间的平衡……)

CF #345 div.2

打div2和咸鱼有什么区别……

滚粗太久了只能打打div.2了

  • A: DP, 乱搞,注意f(1,1)=0
  • B: 维护一个map<key, cnt>,每次删掉cnt ==0的点,ans += map.size() -1,然后给所有的都-1
  • C: 容斥原理,long long
  • D: 四种情况:全右,全左,右后左,左后右。预处理出到达左边、右边第若干个点的时间,对于1) 2)直接二分查找<=T的最远点。对于3) 4)枚举右边/左边的折返点,然后计算出从出发到回到原点的时间cur,之后二分查找一下另一方向的T – cur。注意最多只能遍历n个点,重复不算。
  • E: 建图,拓扑排序。不需要搞很多边:只要对每一排、列排序一下,把大小相邻的连边就行了