缺大米的请参加这个刷题/Mock interview活动

1. Reverse a sentence
Mindset:
If the given string is null, we do not need to do anything.
use two pointers, left and right as reverse helper function
distinguished it from a character with space

2. Right shift a given string by n characters.

Assumptions
The given string is not null.
n >= 0

MindSet:
just find the index of n - 1 and reverse the whole sentence then reverse the rest two parts

3. Find all occurrence of anagrams of a given string s in a given string l.
Return the list of starting indices.

//Mindset
use a HashMap to store the s with character and its repeated frequency;
use int variable match and check about the current match status
don't forget to handle the case: if the element comes over the s.length(), we should put previously matched back to map
return a result list.

我要參加

9 题, 包括 biweekly + weekly

2020.06.14
参加了周赛


找kAncestor当时已经想到建立shortcut，但是还是抱着侥幸心里用每次查询都需要线性的思路去做的，果然tle。

打卡第八天， weekly contest 只做对了一半，⛽️1Running Sum of 1d Array 难度1星，preSum处理
2 Least Number of Unique Integers after K Removals 要点是排序+ hashmap
3 Minimum Number of Days to Make m Bouquets 没有看出来要用Binary Search来做。 难点在于设计mid判断条件
4 Kth Ancestor of a Tree Node 预处理 + 动态规划 dp[i][j] means the (2^j)th ancestor of node i, 思路巧妙，利用exponential来快速查找到已预处理的parent的node

06/13/2020 打卡第14天

今天完成5道
#201 Bitwise AND of Numbers Range - medium 好用的Brian Kernighan's Algorithm: n & (n - 1)
#208 Implement Trie (Prefix Tree) - medium
#211 Add and Search Word - medium 这两道和Trie是照答案打的。万事开头难。
#5453 Running Sum of 1d Array - easy 自己写的不是O（1）space的写法，学习了。
#5454 Least Number of Unique Integers after K Removals - medium 这个是和大家写的差不多的。用到PriorityQueue 和 map 结构
#5455 Minimum Number of Days to Make m Bouquets  真想不到居然是binary search。

All My SubmissionsTime Submitted        Question        Status        Runtime        Language
3 hours, 41 minutes ago        Kth Ancestor of a Tree Node        Wrong Answer        N/A        java
4 hours, 21 minutes ago        Least Number of Unique Integers after K Removals        Accepted        1135 ms        java
4 hours, 24 minutes ago        Least Number of Unique Integers after K Removals        Wrong Answer        N/A        java
4 hours, 28 minutes ago        Least Number of Unique Integers after K Removals        Wrong Answer        N/A        java
4 hours, 45 minutes ago        Running Sum of 1d Array        Accepted        0 ms        java
8 hours, 25 minutes ago        Add and Search Word - Data structure design        Accepted        75 ms        java
9 hours, 35 minutes ago        Implement Trie (Prefix Tree)        Accepted        50 ms        java
10 hours, 25 minutes ago        Bitwise AND of Numbers Range        Accepted        5 ms        java

day 5 打卡四题
今天做了周赛 第一第二题还需要更快 第三题没想到好思路只能brute force 没想到正解是用binary search

坚持的第11天，
做了**3道**
完成了heap和stack的章节
开始DP的章节
今日总结：
1. LRU的概念还不是很理解，多做做类似的题目
2. 有些DP的题目也可以用divideandconquer来做，虽然时间BigO有可能差不多，但空间会消耗更多
3. 正如DPS, 在写helper function的时候，出了table memo， 还要仔细考虑还需要什么其他parameter（目前的弱点）

06/13 Day 9: 六道题

2020年6月13日，第十二天发帖，今天刷了5道题（不算今天做的微软OTS）：

229. Majority Element II。这个是朋友帮我做的mock interview第一题。看到条件我说可以用map实现O(N)/O(N)或者用排序实现O(NlogN)/O(1)，然后他问我有没有听说过Boyer-Moore算法，我说没有，于是便让我去google一下。虽然现场学到了这个算法，不过这个题目还是不会做，于是他又给了个hint说可以用两个counter分别计数两个target。然后思路便全都理顺了。当然这要是在面试我挂定了。
1401. Circle and Rectangle Overlapping。这个是朋友帮我做的mock interview第二题。我自己整理了三点思路（1. 勾股定理分析长方形四个角到圆心的距离是否小于等于圆半径的距离 2. 圆心是否在长方形内部 3. 圆心在长方形外但是否和长方形某条边相切或相割），虽然他让我先去写，于是自己写出来了好几个非常长的if statement。于是朋友提示可以考虑计算长方形上离圆心最近的一点到圆心的距离的平方，勾股定理和圆半径的平方进行比较。这个思路确实把之前二十几行的代码变得非常清晰。
1252. Cells with Odd Values in a Matrix。这个题目乍一看是要创建m×n的数组的，不过直觉告诉我相信应该有不用那么大量的memory的方法。于是发现了我只需要知道有多少行及有多少列变成了奇数就可以了，把空间复杂度从O(mn)降到O(m + n)。
962. Maximum Width Ramp。这个题目让我直觉地回想起了单调栈，不过自己做过的单调栈是用来找最近的更大/更小的元素的，但这里我们要找的是最远的。于是大脑就想不出来该怎么做了，但是我确实觉得可以借助栈来实现这个做法。看答案后确实是栈，而且在某种程度上也是一种单调栈。有点被定势思维套住了。
592. Fraction Addition and Subtraction。这道题和我在OA上挂了的题目很像。为了完成自己之前没有彻底完成的代码，我又把考场上现场写的OOD又重写了一遍，发现了一些之前漏掉的细节。如果OA之前做过这道题就好了，哎。

总结一下：
0. 今天学习到了Boyer-Moore 算法，复习了最大公约数的写法和单调栈的用法。
1. 单调栈即可以on-the-fly来跟踪最近的更大/更小的元素，还可以先行iterate一遍做precompute来跟踪最远的更大/更小的元素。
2. 对于跟圆和任何多边形相关的几何题目，都可以转化为point-in-polygon问题：https://en.wikipedia.org/wiki/Point_in_polygon

action-item:
1. 继续做一些需要boyer-moore算法的题目；
2. 继续做一些单调栈类的题目；