My CodeTop Practice repo

为什么会有这个repo

暑假实习和秋招的时候好几次因为面试手撕代码写不出来而一面挂，所以痛下决心要好好练面试常见的代码题。

虽然大部分面试代码题都是leetcode原题（或者可以说是全部），但是实际上面试系统并不像leetcode那样只需要写一个函数，其余的输入输出都不需要管，遵守函数规定的输入输出即可。而是需要一个真的可以运行的代码。

所以根据CodeTop网站爆料的一些常见题，在本地模拟一下。根据用到的核心数据结构进行分类.

到目前的一个基本经验是，越是大厂越喜欢考链表的题，可能是因为链表不但能考算法，而且指针操作多，比较考验思维逻辑，而且需要自己定义数据结构。

有的面试官会直接使用面试系统的手撕代码，可以一键运行，需要自己cin数据，这种情况一般是在题库中选择一道题，然后系统自带了验证系统，主要方式就是输入输出ACM模式；而有的面试官会要求打开本地的ide，写一个完整的main函数，自己写数据。（只在腾讯二面遇到过一次）当然，也有的面试官并不要求写main函数，甚至不要求运行，写一个函数能说得通看得懂就行了。（美团一面）

目前遇到过最难的题应该是k个一组反转链表，当时的面试官真看得起我，果然不出意外完全写不出来。LRU问过一次但是没有要求手撕代码，只要求描述一遍（应该是在字节的大数据开发一面，最后因为技术栈不太匹配挂了），感觉灵茶山艾府题解里面的那个比喻挺好用的，一摞书，每次需要就抽出来再放到这摞书的最上面。

文件设定

在每个分类中都会有一个util文件夹存放这类常用的一些基础代码，例如数据结构基本定义、数据结构print函数。

例如，在1-linkList中文件结构如下：

├── xxx.cpp
├── util
│   ├── ListNode.h
    │   ├── struct ListNode{};
    │   ├── void showLinkList(ListNode* root){}

使用设定

• 在命名时使用leetcode中的序号+名字。
• 在编译时使用leetcode中的序号。
• 如无必要，应当尽可能避免使用auto或者其他高级方法，因为有的公司使用的笔试或者面试系统只有C++11标准。
• 多写注释，和一些辅助记忆的口诀。

遇到的手撕

• 京东二面：判断一棵树是不是完全二叉树
  • 其实就是层序遍历，出现nullptr以后不能有非nullptr的节点
• 美团一面：一个实际场景题，比较匹配的最长前缀长度
• 字节一面：Z字型遍历二叉树
• 拼多多一面：LRUCache
• 拼多多二面：
  • 写一个一定会出现死锁的程序，如何避免？WaitGroup的方法没写出来。
  • 实现HashMap的insert操作
    • 拉链法
    • 限定在只能分配大数组（不能new链表节点）
    • 两种方法的复杂度？
• 百度一面：给定长度n，生成合法括号组合
• 滴滴
  • 一面：岛屿数量
  • 二面：三数之和
• 拼多多三面：二叉树中的最大路径和