Just want to push myself to practice coding
Readme 里面并没有列出所有的题目的解法，只列出一些比较经典的
| # | Title | Solution | Basic idea (One line) |
|---|---|---|---|
| n sum | |||
| 1 | Two Sum | Java | 1. HashMap O(n) and O(n) space. 2. Sort with two points O(nlogn) and O(1) space. |
| 167 | Two Sum II - Input Array is sorted | Java | 1. two pointers O(n) 2. binary search O(log(n!)) |
| 170 | Two Sum III - Data Structure Design | Java | Use HashMap to store numbers. Maintain a list with distinct elements. |
| 653 | Two Sum IV - Input is a BST | Java | 1. DFS + HashSet Time: O(n), Space: O(n). 2. Inorder traversal + two pointers Time: O(n), Space: O(n) 3. BST iterator + stack Time: O(n), Space: O(logn) |
| 15 | 3 sum | Java | for loop + two sum(pay attention to duplicates) Time: O(n^2) |
| fb 4sum | 4 sum FB面经 | //TODO: 如果target是0的话可以用n^2来做 | |
| two pointers, sliding window algorithm | |||
| 3 | Longest Substring without Repeating Characters | Java | two pointers, sliding window algorithm |
| 76 | Minimum Window Substring | Java | two pointers, sliding window algorithm |
| 159 | Longest Substring with At Most Two Distinct Characters | Java | two pointers, sliding window algorithm |
| 340 | Longest Substring with At Most k Distinct Characters | Java | two pointers, sliding window algorighm |
| 438 | Find All Anagrams in a String | Java | 1. sliding window 固定窗口，比较两格hashmap -> 比较两个array -> 维护一个array 2. two pointers + sliding window 活动窗口 |
| 567 | Permutation in String | Java | sliding window 固定窗口，比较两格hashmap -> 比较两个array -> 维护一个array |
| 395 | Longest Substring with At Least K Repeating Characters | ||
| 42 | Trapping Rain Water | Java | 1.two pointer: left, right. 同时用maxLeft, maxRight 维护boundary高度. 从短边注水 2.变形：如果有-1，漏水怎么办。 instead of summing up water each bin. we sum up water each container |
| 992 | Subarrays with K Different Integers | Java | 这道题巧妙的地方在于！写个sliding window algorithm: get the number of subarrays with at most Kdistinct elements. Then, f(exactly K) = f(atMost K) - f(atMost K-1) |
| binary search | |||
| 278 | First Bad Version | Java | Binary Search Time: O(logN) Space: O(1) |
| 35 | Search Insert Position | Java | Binary Search, 注意边界条件 |
| 852 | Peak Index in a Mountain Array | Java | 1. Binary Search iterative Time: O(logN) Space: O(1) 2. Binary Search recursive Time: O(logN) Space: O(logN) 3. for loop .. |
| 162 | Find Peak Element | Java | same as 852 山峰数组，关键找出判断二分的条件 |
| 153 | Find Minimum in Rotated Sorted Array | Java | Binary Search 跟nums[right]比较 |
| 154 | Find Minimum in Rotated Sorted Array II | Java | 包含duplicates,还是Binary Search 当nums[mid]和nums[right]相等时，right--。但是时间复杂度变O(n), worst case: 11101111 |
| 33 | Search in Rotated Sorted Array | Java | 两次二分法，先找出rotate的点，再在一边进行normal binary search |
| 74 | Search a 2D metrix | Java | 把2Dmetric看成一个sorted array，还是binary search Time: O(log(m*n)) = O(log(m)+log(n)) |
| 240 | Search a 2D metrix II | Java | 1. binary search tree model. Time: O(m+n) 2. binary search Time:O(m*log(n)) |
| 825 | Friends Of Appropriate Age | Java | 1. 如果没有年龄限制 binary search 2.如果有年龄限制可简化，用 counts[] sum[] |
| [在sorted有duplicats array里面，找targe 左右边界] | Java | 找left most和right most只需要改一行代码就好啦 | |
| back tracking | |||
| 78 | Subsets | Java | back tracking 两种方法构造recursion tree 剪枝的那个TREE更容易处理remove duplicates的问题 |
| 90 | SubsetsII | Java | 有duplicates应该怎样处理(对于每个node，剪掉相同的branches) |
| 77 | Combinations | Java | 自己稍微改动一下，练习了一下应对duplicates的情况。Time: O(C(n,k)/C(K)) ~ O(n!) |
| 39 | Combination Sum | Java | 1. 引入index来确定有多少branches 2。去重问题 T:exponential |
| 40 | Combination Sum II | Java | 相同的recursion tree,不同的限制条件 |
| 216 | Combination Sum III | Java | 相同的recursion tree,不同的限制条件 |
| 46 | Permutations | Java | 1. remove/add elements from arraylist 2. use a boolean array |
| 47 | PermutationsII | Java | For each node, remove duplicate branches |
| 20 | Valid Parentheses | Java | valid parentheses: 每当我们放一个右括号的时候，已经放的左括号要比右括号的数量多 |
| 22 | Generate Parentheses | Java | backtracking的经典题目，对于每一个position（Node）,有两个branches：（ 或 ） |
| 401 | Binary Watch | Java | 把num分成两个数num1，num2。分别对hours和minutes求combination sum。 9.5 notes: 这几天系统刷backtracking的题。发现这道题的子问题其实就是combination sum |
| 17 | Letter Combinations of a Phone Number | Java | 非常经典直接，多少层：按了多少键 每个NODE多少branches：每个键课代表多少数字 |
| 681 | Next Closet Time | Java | Approach1: simulate the clock and move forward by one minute. Chech whether 4 digits are allowed. Time: O(2460) Approach2: 用已经存在的digits做DFS排列组合，看那种最closest time：O(4444 = 256) |
| 79 | Word Search | Java | Time complexity: time O(mn*4^k) where k is the length of the string |
| 51 | N Queens | Java | n层，每个node n个branch if delta(col, row) equals, same diagnol1; if sum(col, row) equals, same diagnal2. |
| 52 | N Queens II | Java | 一个是返回count，一个是返回paths。注意 new ArrayList<>(path) !! |
| 139 | Word Break | Java | memorized dfs：如果直接用DFS的话，时间复杂度：O(N!)。因为很多相同的substring算了很多遍。用map记录下distinct substring的解->O(N^2)。因为用n*(n-1)/2个substring |
| 140 | Word Break II | Java | 1. true or false: boolean DP[] 2.all paths: LinkedList [] DP, 每个value是一个list of string |
| 394 | Decode String | Java | 1. use stack Time: O(n) Space: O(n) 2. use recursion Time:O(n)我觉得O(n) 因为string的每个元素只走了一遍 Space:O(1) |
| LC外 | FangFang goes home | Java | 自己出着玩的题目. 一个棋盘，从左上角到右下角一共：C(m+n, m) 或 C(m+n, n)种 |
| BFS | |||
| 909 | Snakes and Ladders | Java | 经典BFS,求最短路径。别忘了用visited防止TLE |
| Tree | |||
| 297 | Serialize and Deserialize Binary Tree | Java | 我把它写在了tree的第一个是因为之后都要用它来构建tree了。总结了两种方法，熟练掌握。 1. use queue to traverse/construct the tree level by level 2. recursively pre-order traverse/construct the tree |
| 449 | Serialize and Deserialize BST | Java | 1. preorder traverse. Take advantage of BST, 不需要全局变量，就可以判断string里面哪边是左树，哪边是右树 2. use a queue, level order traverse |
| 428 | Serialize and Deserialize N-ary Tree | Java | serialize: "preorder" traverse: root [children] deserialize: 结合了297和calculator的一些技巧。结合括号的recursion。 |
| 431 | Encode N-ary tree to Binary Tree | Java | 思路：每一层最左边的child作为新root encode: 对于跟自己同一层的nodes，构成其right substree. 自己本身的children，构成其left substree. decode: recursion返回 list,左边返回的list是自己的children，右边返回的是自己的partners |
| 652 | Find Duplicate Subtrees | Java | 关键是利用积累的serialize tree的技巧 |
| 863 | All Nodes Distance K in Binary Tree | Java | 这道题太好了 建造了一个新的含有parent的node，clone一遍tree，然后dfs/bfs |
| 742 | Closet Leaf in a Binary Tree | Java | step1: dfs traverse the tree to find the target node and build parent hashmap step2: bfs traverse the graph, find the closest leaf 注意细节比如是add 进queue里面的时候标记为visited |
| 834 | Sum of Distances in Tree | Java | 从n^2 简化至 n, 关键是理解： When we move our root from one node to its connected node, one part of nodes get closer, one the other part get further. |
| inorder, preorder, poster | 相关运用，变形关键是要融会贯通 | ||
| 94 | Binary Tree Inorder Traversal | Java | 方法1：recursively inorder traverse the tree into a list. T:O(n) S:O(h) 方法2：iteratively inorder traverse the tree, use a stack(在stack pop的时候值放进res里面) T:O(n) S:O(n) |
| 144 | Binary Tree Preorder Traversal | Java | 两种iterative的方法： 1.use a stack(在push node into stack的时候, add val into res) T:O(n) S:O(n) 2.用一个stack,对于一个Node的children，从右往左push，那么pop的时候就是从左往右(这种方法很适合推广到n-ary) |
| 145 | Binary Tree Postorder Traversal | Java | iterative方法，观察postorder: 左 右 root, 其实就是preorder 左右翻转版再倒过来 |
| 589 | N-ary Tree Preorder Traversal | Java | 关键也是iterative. 也是两种方法，从preorder binary tree 的两种方法中衍生出来 |
| 590 | N-ary Tree Postorder Traversal | Java | preorder 左右翻转版再倒过来 |
| 105 | Construct Binary Tree from Preorder and Inorder Traversal | Java | 关键是找到root,哪一部分是left tree, 哪一部分是right tree |
| 106 | Construct Binary Tree from Postorder and Inorder Traversal | Java | postorder就是左右相反的preorder再reverse。注意细节 |
| 889 | Construct Binary Tree from Preorder and Postorder Traversal | Java | |
| 285 | Inorder Successor in BST | Java | method 1 : take advantage of BST time: O(h) method 2: 用stack, 适用于general binary tree |
| 255 | Verify Preorder Sequence in BST | Java | divide and conquer: O(nlogn) |
| 272 | Closet BST Value ii | Java | Got inspired by 285(inorder successor)。Time: O(klog(n) |
| 701 | Insert into a Binary Search Tree | Java | Got inspired by 285(inorder successor) 关键在于找到该val对应的successor |
| 173 | BST Iterator | Java | 需要非常熟练掌握。average time: O(1) 虽然next()有时候会是O(h),但是总体来说每个Node被visited了2次，一共call了N次 |
| 98 | Valid Binary Search Tree | Java | 1:recursively inorder traverse the tree into a list. T:O(n) S:O(n) 2.iteratively inorder traverse the tree using a stack. T:O(n) S:O(n) 3.recursively inorder traverse the tree using two boundary values: min, max T:O(n) S:O(1) 考虑integer overflow：long pre = Long.MIN_VALUE; |
| 971 | Flip Binary Tree To Match Preorder Traversal | Java | 关于"flip"的理解：一开始preorder是中，左，右。flip就是中，右，左 |
| bfs dfs | top down, bottom up | ||
| 623 | Add One Row To Tree | Java | 一道经典BFS的题，注意corner case |
| 450 | Delete Node in a BST | Java | 1. search for a node to remove 2. If the node is found, delete the node |
| 865 | Smallest Substree with all the Deepest Nodes | Java | method 1: BFS + Lowest Common Ancestor method 2: dfs (discuss 里面大佬说的) 学习一下 |
| 894 | All Possible Full Binary Trees | Java | 警醒一下recursion: 转化成subproblem, 然后call 自己 solution |
| 559 | Maximum Depth of N-ary Tree | Java | bottom to up 超时了，可以考虑top down dfs 或者 bfs |
| 298 | Binary Tree Longest Consecutive Sequence | Java | top down dfs + 打擂台 |
| 549 | Binary Tree Longest Consecutive Sequence II | Java | top down then bottom up dfs + 打擂台 |
| 337 | House Robber III | Java | dfs all the nodes of the tree, each node return two number, int[] num, num[0] is the max value while rob this node, num[1] is max value while not rob this value. |
| convert tree to list | 相关问题 | ||
| 109 | Convert Sorted List into Binary Search Tree | Java | Divide and Conquer |
| 897 | Increasing Order Search Tree | Java | 还是用那个技巧：用一个全局变量prev |
| 156 | Binary Tree Upside Down | Java | two methods: 1. recursive 2. iterative(三步：store, change, update) 其思路有点像reverse linked list |
| DP, Palindrome(Substring, Subsequence, Subarray..) | |||
| LC外 | Longest Common Substring | Java | DP: O(n*m) if(s(i) == t(j)): DP(i)(j) = DP(i-1)(j-1)+1 |
| LC外 | Longest Common Subsequence | Java | DP: O(n*m) if(s(i) == t(j)): DP(i)(j) = DP(i-1)(j-1)+1 if(s(i)!=t(j)): DP(i)(j) = Math.mDP(i-1)(j-1) |
| 5 | Longest Palindromic Substring | Java | Approach 1. DP: boolean DP(i)(j) = (DP(i+1)(j-1) && (s(i) == s(j))即当两边的字符一样且substring也是palindrome。 二维boolean DP矩阵，从对角线往斜上方走。T:O(n^2) S:O(n^2) Approach 2: expand function T:O(n^2) S:O(1) |
| 647 | Palindromic Substrings | Java | use expand helper function T:O(n^2) S:O(1) |
| 516 | Longest Palindromic Subsequence | Java | DP: dp(i)(k): the longest palindromic subsequence's length of substring(i, j) dp(i)(j) = dp(i+1)(j-1) + 2 if s.charAt(i) == s.charAt(j) otherwise, dp(i)(j) = Math.max(dp(i+1)(j), dp(i)(j-1)) |
| 647 | Longest Continuous Increasing Subsequence | Java | O(N)思路 |
| 300 | Longest Increasing Subsequence | Java | O(N^2)思路 |
| 32 | Longest Valid Parentheses | Java | O(N)思路 |
| 44 | Wild Card Matching | Java | |
| 10 | Regular Expression Matching | Java | |
| 322 | Coin Change | Java | 经典DP题目 |
| 518 | Coin Change 2 | Java | 1. DFS -> memorized DFS, 注意map的key要用list不要用int[] (存在map里的是reference) 2. DP!!! 从最基本的subproblem开始：只用coin1，加上coin2 .. coin5 |
| 983 | Min Cost for Tickets | Java | 思路来源于coin change这道题 |
| 152 | Maximum Product Subarray | Java | 因为有负数，所以我们不仅要keep track of imax 还要keep track of imin. 乘负数的时候，小的会变成大的，大的会变成小的 |
| 325 | Maximum Size Subarray Sum Equals K | Java | presum + hashmap(presum : index) pay attention: map.put(0,-1); |
| 560 | Subarray Sum Equals K | Java | presum + hashmap (presum : frequency) follow up: if all elements >= 0 (space O(1)). Two pointers |
| 926 | Flip String to Monotone Increasing | Java | 养成手感了，挺有意思一道题 |
| 975 | Odd Even Jump | Java | 1. DP ideal, 从后往头走 2. 学会多熟练运用treemap的ceilingEntry and floorEntry |
| 312 | Burst Balloons | Java | |
| 1000 | Minimum Cost To Merge Stones | Java | |
| Union Find | 并查集算法介绍 | ||
| 200 | Number of Islands | Java | 这种解法是用的quick union的方法，即使用parent-link |
| 305 | Number of Islands 2 | Java | Weighted Union Find. 相比于1，多了weighted步骤，即争取保持树的平衡性 |
| Linked List | |||
| lc外 | Generate Linked List | Java | 自己写的class用来快速构建linked list 1.generate 2. show |
| 206 | Reverse Linked List | Java | 经典题目 关键在于next指向previous node同时，不能丢掉后面linked list的头 1. iterative method 2. recursive method |
| 92 | Reverse Linked List II | Java | 慢慢深入到写出来大致分了三步： 1.完全理解从头到尾 reverse linked list 2.从头到第N个 reverse 3.从第M个到第N个 reverse |
| 24 | Swap Nodes in Pairs | Java | 这道题有很多种解法来做： 1.把92作为helper function，把swap two nodes 看成reverse nodes in 2 group 2.自己比较straightforward的解法 3.recursive |
| 25 | Reverse Nodes in K Group | Java | 1. 把92作为helper function 2.recursive方法 |
| 876 | Middle of the Linked List | Java | 快慢指针 |
| 237 | Delete Node in a linked list | Java | 这道题很有意思，只给了要删除node的reference. (面试的时候最好问清) |
| 83 | Remove duplicates from Sorted List | Java | 1.return a new linked list 2. operate in place 3. recursive method |
| 203 | Remove Linked List Elements | Java | 1.return a new linked list 2. operate in place 最大的感受是，假如remove个多个重复元素，可以一个一个remove（ head.next = head.next.next;），不需要一下就找到头 |
| 21 | Merge two sorted lists | Java | 分清什么时候把L1放进去，什么时候把L2放进去 |
| 23 | Merge k sorted lists | Java | 1. priority queue, compare head of each linked list T:N*LOGK S:K 2. divide and conquer(with merge 2 linked lists) |
| 143 | Reorder List | Java | 三道经典例题的结合 1. find the middle of the linked list 2. reverse the second part 3. merge in-place |
| 328 | Odd Even Linked List | Java | split it into two linked lists then connect them。注意先对ODD操作。 |
| 141 | Linked List Circle | Java | 1. 老生常谈的slow/fast pointers 2 hastset方法，store visited nodes' reference into a set. 我觉得非常straightforward |
| 142 | Linked List Circle ii | Java | 对于上一道题，返回环开始的地方。用slow/fast pointers方法就需要数学证明了 |
| 708 | Insert into a Cyclic Sorted List | Java | do...while loop, pay attention to corner cases: 1. in the middle 2. between head and tail 3. duplicates |
| 801 | Linked List Connected Components | Java | 自己的直观solution：一个hashset, 一个boolean值 |
| 61 | Rotate List | Java | 1. Get the length 2. move to the (length - n%length) node 3. do the rotation |
| 86 | Partition List | Java | iterate 两遍，非常strightforward |
| 117 | Populating Next Right Pointers in Each Node I,II | Java | 1. 如果没有space要求，用一个queue BFS就行 2. O(1) space. Make use of next pointer |
| 138 | Copy List with Random Pointer | Java | method 1: use a hashmap 1. copy all nodes 2. assign next and random pointer method 2: space O(1) 把每个node duplicated 一下, 放在后面 |
| Math | |||
| 7 | Reverse Integer | Java | 这道题的关键是处理overflow的问题Integer.MAX_VALUE:2147483647 Integer.MIN_VALUE:-2147483648 1.Pop and Push Digits & Check before Overflow 2. 作弊方法catch exception |
| 9 | Palindrome Number | Java | 1. contert to string 2. 重点掌握 思路有些像上面的reverse integer，但是只用reverse 一半，有效防止over flow |
| 50 | Pow(x,n) | Java | recursive method: T(logn) S(logn) 1. n < 0 2. n == 0 3. n % 2 == 0 4. n % 2 == 1 |
| 65 | Valid Number | Java | a general pattern: "-xx.xxe-xx" |
| Priority Queue | (Top K 问题 quick select, treeset) intervals | ||
| 346 | Top K Frequent Elements | Java | 1. use PriorityQueue Time: n + k*log(n) 2.bucket sort T:O(n) List[] bucket = new List[nums.length+1]; |
| 215 | Kth Largest Element in an Array | Java | Quick Select (注意partition function里面用two pointers swap的模版) |
| 295 | Find Median from Data Stream | Java | two heaps: minheap to store the larger part, maxheap to store the smaller part |
| Pin面经 | get Top K Rating | Java | 有一个app,要实现两个方法：updateRating()和getTopKRating()，要求getTopK()的时间复杂度O(1) 后怕，发现了自己的知识盲区 |
| 759 | Employee Free Time | Java | Priority Queue solution based on merging intervals |
| Stack,Queue | |||
| 394 | Decode String | Java | 1. use stack Time: O(n) Space: O(n) 2. use recursion Time:O(n)我觉得O(n) 因为string的每个元素只走了一遍 Space:O(1) |
| 402 | Remove K Digits | Java | 非常好的一道题从straightforward solution到optimized solution(USE A STACK) 思考 如果是remove k digits 边最大呢？ |
| Graph | |||
| 261 | Graph Valid Tree | Java | 判断一个(无向)graph是不是valid tree: 1. 不能有cycles 2. 所有node都要connected 有环：1. DFS:一直往下走的path会回到某个已经被visited的点 2. BFS queue里面会有重复的点 |
| 323 | Number of Connected Components in an Undirected Graph | Java | 跟number of islands差不多, graph + dfs |
| 399 | Evaluate Division | Java | 1. edge 有weight 2. dfs + graph |
| 785 | Is Graph Bipartite | Java | 经典 1. 从一个没有染色的node开始，BFS把所有与之构成graph的node染色 2. 继续从另一个没有染色的node开始，直到所有的node都染色了 |
| 886 | Possible Bipartition | Java | 同是bipartite graph问题.不过这个我们需要自己建造一个graph. |
| 928 | Minimize Malware Spread II | Java | 还是要多练习图的遍历 BFS图的遍历，注意细节：add into queue的时候标记为visited |
| 207 | Course Schedule | Java | 经典的拓扑排序问题 能想到的需要熟练掌握的子问题: 1.构建directed graph 需要好好思考是 child:parents 还是 parent:children 2. 判断有向图里面有没有环 3.打印拓扑排序 |
| 269 | Alien Dictionary | Java | 很好的一道题 step 1: build directed graph step 2: topological sort 还要理解lexicographical order的正确意思来build正确的tree |
| 301 | Minimum Height Trees | Java | 类似于拓扑排序，但是这是一个无向图 详细解释 又是那些细节：什么时候标记为visited。add的时候标记visited是防止queue里面有重复元素，remove的时候标记visited，是标记已经被expanded的node |
| Trie | |||
| 208 | Implement Trie(Prefix Tree) | Java | Trie 相关题目的基础，需要知道它是如何实现的 |
| 211 | Add and Search Word | Java | 一道经典的trie与dfs结合的题 |
| 676 | Implement Magic Dictionary | Java | 1. 用trie做，找到第一个不同的char，看char之后的substring 能否在当前的子树里面找到。 2. 非常巧妙的hashmap做法 <childstring: [index, char]> |
| 720 | Longest Word in Dictionary | Java | 1.很tricy的sort方法 2. trie + dfs (Build a trie in the normal way, then do a dfs to find the longest continuous downward path from the root.) |
| 642 | Design Search Autocomplete System | Java | 相对于normal trienode，加了一个set strings. 表示有多少string的prefix是当前prefix.最关键的一点是：每insert一个word,就在经过的node加上这个word |
| 648 | Replace Words | Java | 一道很直观的trie的题目，对于每个word,找包含的最短的prefix |
| 677 | Map Sum | Java | 还是那关键的一步：相对于normal trienode，加了一个set strings. 表示有多少string的prefix是当前prefix |
| 472 | Concatenated Words | Java | 1. for loop + word break解法 2. Trie + dfs 对当前string进行dfs, 找到一个存在的prefix之后，再对之后的substring进行dfs（for loop） |
| 212 | Word Search II | Java | word search I for loop 版本，但是会tle，用trie优化 |
| 425 | Word Squares | Java | Trie + DFS 结合 Explanation |
| P面经 | 打印log | Java | 1.根据题意建立trie tree 2.DFS打印trie tree 根据不同情况给trie node赋予不同property children, count, list of words等等 |
| Design | |||
| 146 | LRU | Java | 经典题目LRU，hashmap + doubly linkedlist dll head:most recent used, tail:least recent used |
| 460 | LFU | Java | LRU加强版 Map<Integer, Integer> vals; Map<Integer, Integer> counts; Map<Integer, LinkedHashSet> lists; min什么时候变换？ |
| 622 | Design Circular Queue | Java | 用array，和巧妙的头尾指针 |
| 103 | Design Hit Counter | Java1Java2 | 1.用一个简单的queue做(当重复在一个timestampt hit很多次就会很costring) 2.用circular array（推荐） |
| 981 | Time Based Key-Value Store | Java Java2 | 1. 建造一个Pair class，然后binary search 2. treemap 直接用 floorKey() 这个method |
| board 相关题目 | |||
| 939 | Minimum Area Rectangle | Java | 跟google面试题一样，所有point存在hashmap里面，通过看对角线来看是否构成矩形 |
| 一些神奇的算法 | |||
| 287 | Find the Duplicate Number | Java | 这道题一开始就有很多constraints,但是我觉得面试中不可能一开始就有这么多constrains 1. instinct method: use hashmap 2.（虽然modify了array）因为n+1 长度，但是数字只在1-n之间，用swap把它们放到了对应的位置上 3. 很精妙的binary search算法 （但是判断语句跟平常不太一样） |
| 一些OA | |||
| G | Group Email | Java | 简单字符串处理 |
| L | Shift String | Java | 三步翻转法 |
| L | Max Different | Java | 挺简单的，我好像用了个PQ |
| L | Can U Sort | Java | bucket sort |
| 百度 | 有多少不上升/不下降序列 | Java | dfs -> memorized dfs -> 感觉DP可以做还没想出来 |
| Google 面经 | |||
| 1 | Concatenated String | Java | 1、BFS 2. DP，类似于word break，但是要存储所有的valid combination |
| 2 (lc 890) | Find and Replace Pattern | Java | 1. lc这道题是要求双向映射都要有唯一性 2.google面经说可以存在 a->b, c->b情况。 follow up: 字符变换是否需要中间变量->hashmap映射是否有环 |
| Karat 面经 | |||
| 1 | 有向图三小问 | Java | 1. 第一问是只有0个parents和只有1个parent的节点 2. 第二问是 两个指定的点有没有公共祖先 3.第三问是就一个点的最远祖先 |
| 2.(lc 227) | Basic Calculator | Java | 只含有+,-,/,* 和空格。用stack |
| 3.(lc 224) | Basic Calculator II | Java | 只含有+，-, (, ), 和空格。面对有括号的情况，我必将倾向于用recursive的方法，因为括号里面是subproblem。 优化recursive方法，把index设置成全局，或者存在int[] index里面 |
| 4 | [Basic Calculator III] | Java | 含有+, -, *, /, (, )等情况 |
| 5 | [Basic Calculator IV] | Java | 含有+，-，（，）和 变量名 |
| 6 | Task By Level | Java | 一道经典的topological sort题目（indegree + BFS。但是这里构造graph是用的map: parent : list of children |
| 7 | Security System | Java | 1.找到mismatched person。关键是用0:屋外, 1:屋内。表示状态。 2.关键是two pointer的helper function |
| 8 | 矩阵 | Java | 1.只有一个矩阵 2.有多个矩阵，互相不重叠 3.不再是矩阵而是形状不规则的区域(有点像number of islands)万事无他唯手熟尔 |
| 9 | Domain问题 | Java | 1. 返回domain和所有sub domain被click的总次数 2.找出两个user之间的longest continuous common history（Longest Common Substring）问题啊！ |
| 10 | 设计一个sparse vector class | Java | 实现 add, dot, cosine 操作 |