7月缺米的来刷题/Mock interview活动

感谢发起这个活动， 我目前还在继续给六月份的那个加米，没有时间发起新的活动。所以 特别感谢你为版主分担责任！我给你这个贴加了高光和置顶，很棒哦！

今天刷了8道题。。。不过还有一道hard题，从头开始刷，前面的题都快背下来了个p的...

今天刷了四题，继续看trie的feature card

七月第一天。
今天刷了三道题，binary search相关，浪费了很多时间在研究边界和最后退出的判断上面。
有试着去看看别人的解法，但是还没有总结出自己写的习惯的规律。
明天继续binary search。。

7.1 Day 1, 打卡三题

Closest Binary Search Tree Value， O(n)解法：遍历整个二叉树，找到离target最近的数；O(h)解法：h为二叉搜索树的高度，注意到性质：如果target小于root val，那么距离target最近的数一定不再root.right（大于的情况类似），可得到使用二分搜索的解法
Minimum Distance to Type a Word Using Two Fingers，DP题。3D DP很直观。可以进一步优化到2D甚至1D DP，需要注意到性质：两个finger是symmetric的，其中一个finger一定落在word[i-1]（即上一个字符）的位置上
Arranging Coins，二分搜索，注意到可能形成的层数一定在0-sqrt(n)之前，在这个范围内二分搜索，需要注意搜索过程中涉及到乘法的地方要用long

7月第一天

7.1 打卡。3道题。刚开始认真刷leetcode不久，还是略吃力。

3. Longest Substring Without Repeating Characters. 接触到题解里所说的“sliding windows”概念，对以后处理字符串类型的题有启发
441. Arrange Coins. 极其简单的daily challenge
518. Coin Change 2. 开始推错了dp公式，在一时间没头绪的情况下先写了dfs+记忆化搜索，写dfs的过程中受到启发推出了dp公式，于是把两种方法都实现了一下，也算是得到锻炼了。
今天自己给自己埋的最大的坑是edge case和初始化不对，以后要养成自己多想一些edge case的好习惯。

菜鸡七月第二天

1. permutation in strings: 有两个string来看其中一个的permutation是不是另一个的substring，可以用一个array来存第一个string的frequency，
    sliding window每次移动并减掉相应的第二个string里面的frequency，如果某次count array都是0，就说明找到了是permutation的substring，
    不然的话把之前剪掉的再加回去
2. find all anagrams in a string: 写的和前一个差不多，只不过等count array都是零的时候，就把当前index +1 - len1存到result里，因为是anagram
    开始的index
3. minimum index sum of two list: 用一个hashmap，把第一个list里面的string和index存进去，然后存一个minIndex，loop第二个list的时候如果
    map.containsKey(str) 就看可不可以update minIndex，然后根据minIndex update result
4. isomorphic strins: 看可不可以把第一个string里的char map到第二个list里，也可以用一个length 512的array来存每个char最后一次出现的index，
    前256是第一个string的char，后256是存第二个的，如果array[char1] != array[char2+256], 就说明和之前的mapping不一样，不然的话把两个都
    设成index + 1
5. add two numbers II: 这个是用list但从右向左加，可以用两个stack把list element反过来，就和之前add two number 差不多了   

希望明天可以再接再厉

Day2,solve 3 problems, 2 of them are new:

Arranging Coins        LC 441
Rectangle Area        LC 223

1. 计算overlap的面积，用两个右端点的最小值 - 两个左端点的最大值，如果大于0，则有重叠。

2. 第K个小的数，二分答案。最后是先判start >= K，if not return end

感谢组织这个活动！之后有俩onsite，希望能赞点大米看面经。

【打卡第一天】
353. Design Snake Game:
数据结构上好像大家都用的是比较直接的linked list + hashmap的算法来支持O(1) move和hit detection。这道题里面给了生成好的foodlist，不过在其他面经里看到让从头写Snake的时候，如何生成新food position也是一个考点。如果一直随机产生位置直到和snake不重叠，那么在snake size / board size比较大的时候，randomized algorithm有时间可能太长的弊端。后来觉得可以用leetcode 'Random pick with blacklist'的类似做法，用O(snake size)的存储空间来支持deterministic的O(1) generate方法。

378. Kth Smallest Element in a Sorted Matrix：
题目写的medium，但最优解绝对是hard++，想了很久没有答案，看到了StefanPochmann大神po的O(n)算法简直跪了...引用了一个paper
比较popular的解法是当成sort k sorted list做，用minHeap存每一个column的下一个树，这样n + k log(n)的解法只用了row或column sorted性质中的一个。

240. Search a 2D Matrix II
从上一题最优解里引用到的题，很有意思很intuitive，用的是saddleback search的变体，从右上走到坐下。

明天继续！大家一起加油呀