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

SQL

1142  User Activity for the past 30 days ii
1350 students with invalid departments
608 tree node
597 friend requests i: overall acceptance rate

最近打算一口气把sql刷完。

7.12 zszszszszszszszszs

7.12 打卡第四天

刷题第七天
第一题是一道面试基础题 考的是hashmap和基础sliding windows
第二题考的是dp与二分查找
第三题考是backtrace

今天做了Two Sum II, Delete Node in a Linked List, Remove Linked List Elements。

Day 2
190. Reverse Bits bit operation 还是有些不熟练
1515. Best Position for a Service Centre 求Geometric median，和Center of mass不同的是没有公式解，但是因为优化的目标函数是convex的，所以可以用迭代逼近，一开始尝试求导然后用gradient decent，但是可能因为converge太慢而TLE。然后用Weiszfeld's algorithm可以过，本质是固定前一次解后，通过一阶导数算local minimum来算新的解，直到converge。感觉值得去了解下如何证明下后者converge速度的上届。
99. Recover Binary Search Tree Naive的solution是 in-order-traversal 然后在sorted list里面找有问题的值，值得注意下如何用stack来些in-order-traversal。另一种constant space但是花更多时间的方法是morris traversal，本质上是把bst变成只有右子树，要注意下因为会过程中会修改原本的树，所以不能提前退出。

菜鸡七月第十三天

今天做了一些merge interval的题
1. merge intervals:  先把intervals根据start sort一遍，然后从第一个interval看起，如果有overlap ie.当前start小于current end，
    就把end延长，如果没有overlap就把当前interval当作current interval加到list里面
2. interval list intersection： 用两个pointer分别scan两个list，每次取两个interval的start的最大值和end的最小值，如果最小值
    小于等于最大值，说明有overlap，不然根据interval结束的大小移相应的index
3. nonoverlapping interval: greedy一点，每次找结束最早的，sort的时候也是根据interval的end time sort，如果有overlap就把
    count加一，没有就继续往前看
4. teemo attacking: 这道题看懂了很简单，每次只要取两次时间间隔和duration的最小值加上就可以，最后因为不会被打断加上duration
5. partition labels：先用array存每个字母最后出现的index，然后用两个index存当前partition的start和end，如果current index是
    当前letter最后出现的index，就把interval length加到list里面，同时start = ind + 1是新的partition的开始

来加入了！
今日刷了三道有关双指针的题~也可以用哈希表做~都是比较经典的题了

三道 linkedlist经典题

注意的就是null判断

0712 Day11 打卡四题

Maximum Points You Can Obtain from Cards，Sliding Window，遍历所有长度为n-k的sub-array，总点数最小的对应sub-array对应的complement即为答案
Friends Of Appropriate Ages，统计各个年龄段的人数，遍历所有年龄二元组合
Word Ladder II，BFS+DFS，BFS构建Graph，DFS寻找所有路径
Reverse Bits，bit operation