这个repo是关于面试准备的。
掌握数据结构和算法直接的好处就是能写出性能更优的代码。算法是一种解决问题的思路和方法,从长期来看,大脑思考能力是个人最重要的核心竞争力,而算法是为数不多的能够训练大脑思考能力的途径之一。
🍭 学习路线加强巩固数据结构基础知识,主要通过 leetcode 算法题加深对数据结构的理解。在刷Leetcode之前和同时,看Cracking the Coding Interview (CTCI)和在Hackerrank/GeeksForGeeks上练习一些基础会很有帮助。下面的技巧至少练习三遍到滚瓜烂熟:
- 从scratch实现一个ArrayList
- 翻转链表
- 用Array实现Stack和Queue
- 用简单的Hashing function实现一个hashmap
- 用Adjacency Matrix和Adjacency List来实现Graph,然后在此基础上进行BFS和DFS
- Binary Search的迭代和递归
- Merge Sort,Quick Sort,Counting Sort
- 二叉树的DFS(前序,中序,后序的递归写法和迭代写法),BFS(层序)
- 时间空间复杂度分析
可以明确的是,面试时候的算法题目在难度上(尤其是代码难度上)不会吹毛求疵,会倾向于靠擦一些基础的数据结构和算法,对于高级算法和奇技淫巧一般不作考察。
代码题主要考察编程语言的应用是否熟练,基础是否扎实,比如让面试者写出代码完成简单的需求,大约下面的这些内容打好基础就足够了:
Data Structures
- 数组与链表:单/双链表,跳表
- 栈与队列
- 树与图:最近公共祖先,并查集
- 哈希表
- 堆:大根/小根堆,可并堆
- 字符串:前缀树,后缀树
Algorithms
- 排序算法:快排,归并,计数
- 搜索算法:回溯,递归,剪枝技巧
- 图论:最短路径,最小生成树,网络流
- 动态规划:背包问题,最长子序列,计数问题
- 基础技巧:分治,倍增,二分,贪心
贪心 | 分治 | 回溯 | 动态规划 | 递归 | 复杂度分析 |
---|---|---|---|---|---|
️⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐ | ️⭐⭐⭐ | ️⭐⭐⭐ | ⭐⭐⭐ |
Data Structures
- Dynamic Array
- Linked List
- Stack & Queue
- Hash Tables
- Binary Search Tree
- Binary Heaps & Priority Queue
- Graphs
- Trie Algorithms
- Bit Manipulation & Numbers — difference btw Unsigned vs signed numbers
- Stability in Sorting
- Mergesort
- Quicksort
- Heapsort — Sort it in-place to get O(1) space
- Binary Search
- Selections — Kth Smallest Elements (Sort, QuickSelect, Mediums of Mediums) — Implement all three ways
- Permutations
- Subsets
- BFS Graph
- DFS Graph
- Dijkstra’s Algorithm (just learn the idea — no need to implement)
- Tree Traversals — BFS, DFS (in-order, pre-order, post-order): Implement Recursive and Iterative
- External Sort — No implementation; Just know the concept.
- NP-Complete (Video) — Just know the concept
- Topological Sort
- Detect cycle in an undirected graph
- Detect a cycle in a directed graph
- Count connected components in a graph
- Find strongly connected components in a graph
以下列出面试高频出现,以及一些非常经典重要的算法题,点击leetcode的细分类别一定要看,如果想按照类别刷题,可以按照leetcode的分类题目卡片。在线面试工具通常是类似Hackerrank或者codepad或者公司自己的工具。
每道题的时间安排。
第一周
第二周
第三周
第四周
第五周
第六周
第七周
第八周
第九周
第十周
extra
01背包问题 当被问到背包的时候,你第一个想到的是什么?点击查看回溯 + 动态规划两种方式解决背包问题
LRU LRU主要考察你什么?
-
Designing Data Intensive Application 中文版
- 被问到“设计一个支付系统”的思考角度
- 支付平台架构设计的一些思考
- Avoiding Double Payments in a Distributed Payments System
- Paymeng System和API Server如何互相验证1, Paymeng System和API Server如何互相验证2
- Uber支付系统案例
- Design a Chat System (Facebook messenger, Whatsapp)
- Design a Video Streaming Service (YouTube, Netflix)
- Design a Key-value Store
- Design a URL shortener
- Design a Web Crawler
- Design a Shared Cloud Drive (Google Drive, Dropbox)
- Design a News feed System
- Design a Search Autocomplete System
- Design a Notification System
- Design a scalable system that supports millions of users