失业的第x天

失业的第1天 打卡
一辞职就开始感冒，生病了几天，正好今天算是第一个不上班的工作日了。接着打卡。
面试：
电话面试了wayfair, 波士顿的在线卖家具的公司。面的是后端物流优化的组，三哥manager面的。介绍了下，后端主要用php + sql 前端用react。本来要面我sql的，我要求改面general coding了。问的two sum的 <= target的两个数。提了sort以后两根指针扫一遍， follow up是如果input 不能sort，我只想到了从target，到target - i 一个个的套hashset的解法。 不知道还有什么别的办法，求大神指点。
刷题：
这几天主要focus 在dfs上面了，因为很多题就算不会相应的解法，比如course schedule需要用拓扑排序，number of island是需要用并查集，但是都可以用dfs来解。

题号	关键点	犯过的错	todo
200 number of islands	遍历二维图上的每一个点进行涂色， static int[] dx = {-1,0,0,1}; static int[] dy = {0,1,-1,0};游走方小技巧		1.bfs和 dfs再写一遍 2.有空的时候再bi并查集
695Max Area of Island	same
394 Decode String	liner scan 然后用stack来控制层	1. 第一次写的时候，试图用一个stack来存储状态，导致很多if else的状态需要考虑 ->一个stack/变量不太方便存储状态 或者把状态存储的比较乱的时候，可以考虑用2个或者多个数据来存储不同的状态，比如说这道题，我要存parent 层的个数和parent层的prefix，用2个stack会清晰很多。另外一个例子是，蓄水问题dp的一种做法是左边扫一遍，然后右边再扫一遍，存2个预处理的数组    2. 扫描的时候，碰到数字之后是把它存在local变量里面，等到碰到[再存到stack里面。同样这样处理也增加了很多额外的if else。当遇到一个数字时，用while把数字的所有位读出来，然后放到stack里面会清楚很多。 同时也是single responsibility的原则。如果用碰到[再存数字到stack， 其实当前做了两件事，一个是处理数字，一个是跳到下一层了。	1. 再多写1-2遍这道题 2.用recursion来写一下这个题
207course-schedule	做法1: 拓扑排序。做法2: dfs dfs就是对于每一节课作为起点做dfs，从当前的课开始把它dependency的课都上完。2个base case： 1. 当前的课已经visited，那么说明有环 2.当前的课没有dependcy，说明当前的课可以上	递归函数的最后忘记把         visited[startIndex] = false;	course-schedule其他相关的题
146LRU cache	Linked list结合hashmap 1. hashmap 里面存的是list里面的节点reference，这样能在o(1)的时间找到要删除/更新的节点 2. linkedlist需要用双向链表，这样方便移除点，其实也可以用单向的链表	1. 在插入一个新的节点时需要更新4跟指针 2. 在put操作的时候其实可以reuse get操作，如果当前的key存在的话，这样node就自动更新到队头/尾了，然后再根据需要更新该node的值 3. 添加了很多if else来处理第一个点，第二个点的特殊情况，其实用2个dummy node，并把值标记为1，这样就不用考虑链表是空或者只有1个node的corner case了。 4. listnode里面不仅要存value，还要存key，因为删除节点的时候，需要同时清除相应hashmap里的点。 5.对链表操作的时候，不要新建linkedlist，然后removeFirst之类调api。而是直接建节点，手动修改节点的指针。对于cache的size，通过hashmap来查询	写单链表版本
140 Word Break II	自顶向下dfs： 用path来存当前的组合，然后遍历每个可以切分的位置的时候，把path往下传。如果切到index = s.length的话，那么说明当前的切分是对的，把当前path加到result里面。这种做法会超时 自底向上的dfs：string 拆分成2部分， current + remains。 把remains扔到递归函数里面，返回对于当前remains valid的拆分，然后在当前层组装起来。 对于这种递归，需要想好：我需要向我的下一层要什么信息就可以解决我当前的问题。下一层给我的这个信息我如何来处理。	Map<string, list> memo = new HashMap<>(); 存当面单词的合理的拆分，避免重复计算	做dp的解法
91. Decode Ways	1. 开一个n+1 size的数组来存当前的结果. 2. dp[i] 取决于 dp[i - 1], dp[i - 2]的状态 3.         dp[1] = (tmp > 0 && tmp < 10) ? 1 : 0;	input： 01的时候 output = 0 也就是说，当两位数的时候，第一位不能为0
44. Wildcard Matching	1.最重要的点在于弄清楚induction rule 当p == * 和p ！= *的时候， 2种情况 2. 3种base case p到尽头了， s到尽头了以及当前组合以及match过了 3. 自底向上的dfs返回是否match
10. Regular Expression Matching	consider a* as a bundle， 如果为'*'，有两种方案 1 '*'不去匹配字符   2.*'重复前面一个字符去匹配s

priority for  tomorrow：
1. 其他的难题和dfs与binary tree结合的题
2. 复习binary tree上游走的相关题目

看了感觉楼主挺理性的，坚持一下，祝好。

LZ加油！

楼主加油！坚持下去一定能尽快上岸的。

不知道说什么 楼主好好加油！不要放弃！

失业的第二天，打卡面试

昨天抱着必死的决心跟wayfair的电话面试manager说这几天感冒，没复习sql，能不能面general的。然后给了two sum。感觉自己这样面试有点作死，哈哈，今天hr电话联系我说可以去onsite了。
不知道理解的对不对，朋友说不喜欢被国人电面，因为国人面国人会assume你刷过很多题，然后是中等难度的起步。上周电话面黑车，国人小姐姐，给了一道中等的和一道难的，第一道写完跑完了，第二道写完没时间跑。感觉bar挺高的。
这次和wayfair的三哥老板聊的比较愉快，虽然是个two sum cloest to target，但是其实考察的更多是沟通和能不能写代码。我把assumption 都ducument好，打印在coing pad上，然后在coding pad上把例子数字和两个指针都画出来，然后让对方明白我的思路。最后基本bug free写完的。

回复了几个猎头/hr，在帮忙找一些la和北加的职位。

刷题
最近这几天喜欢搞搜索，花了些时间吧以前略过的难一点的题目做了。
对于难题的理解：
1. 多种算法/数据结构杂在一起的。比如Word Ladder II 是把bfs和dfs杂在一道题里面了。
2. 基本的解题套路，但是比较难想清楚边界/控制条件。比如median of two sorted arrays。有3种base case，同时还要看怎么传参数给下一层递归
3. 针对该类型的题目有特定的解法， 比如LRU cache. 还是一个对数据结构的熟悉程度，但是这个题刷过就很简单了，没刷过想很快想出来也不容易。
对于 1-2类的题，还是希望自己多练习的，因为一方面更熟练的写代码，另一方面，对于不是特别容易理清楚的问题，可以锻炼思维。
对于3类的题，抄抄答案，学下技巧。

题号	关键	犯过的错	todo
4. Median of two sorted arrays	1.每次可以在两个数组中的某个数组里扔掉k/2个元素来缩小搜索空间 2. 3种base case a. nums1没数字了 b. nums2没数字了  c. 搜索空间缩小到k == 1 3. 对于某一条array没有数字了，可以假象为在两条数字的尾巴上都加了n个无穷大，这样不影响最后结果，同时你也知道，解在另外一条array 上。	1. left1 >= nums1.length 2.         int midValue1 = mid1 >= nums1.length ? Integer.MAX_VALUE : nums1[mid1]; 越界后设为无穷大
121.         Best Time to Buy and Sell Stock	记录个当前卖价的最小值，如果出现了比当前卖价小的更新min.	同时keep了minbuy和maxsell，然后想着somehow 去限制minbuy必须要比maxsell后发生。这样把问题弄复杂了。 其实只要记录着最低的卖价，然后不断和当前扫描到的卖价做比较
122.Best Time to Buy and Sell Stock II	对于任意2个相邻的price，如果第二天比第一天高，那么差值可以+=到总的profit里面去。 和maxsum of sub array 一摸一样	1. 把问题想复杂了again。在考虑如何区分当前一步是卖还是买。
123.Best Time to Buy and Sell Stock III	和昨天总结的，从左往右扫一遍，再从右往左扫一遍的道理一样。 建立这个印象，如果是2次，2个xxx那么是不是能正向做一遍，再反向做一遍。然后再合并结果呢。	1. 最大的错误在于第i天可以作为正向的卖出天和反向的买入天。同一天可以买也可以卖。 2. 注意初始化dp[0]的时候，根据物理意义，第1天，还没有股票可以卖，那么应该为0.
188.Best Time to Buy and Sell Stock IV	有3点很关键的地方： 1. 多了一个k，如何来做状态转移？ ->二维dp， k作为一个新的纬度 2. 对于当天卖没卖，买没买怎么来存dp状态 -> 卖没卖这件事情需要用一个dp数组来存，因为会影响k的纬度。同时还要有个gobalmax的dp数组 3. mustSell[i][j] = Math.max(mustSell[i - 1][j] + diff，...) 因为i点和i - 1 点都sell了，那么就是 i - 1天卖出了，然后马上买了在i的时候卖出。 可以把这两次卖出给合并为1次卖出。所以j不用++。	2个状态转移方程： mustSell[i][j] = Math.max(mustSell[i - 1][j] + diff, gobalMax[i - 1][j - 1] + diff); gobalMax[i][j] = Math.max(gobalMax[i - 1][j], mustSell[i][j]); k >= prices.length / 2 那么说明可以做“无限”次的买卖，退化到122题
309.Best Time to Buy and Sell Stock with Cooldown	//todo 再写一遍
714Best Time to Buy and Sell Stock with Transaction Fee	//todo
Search a 2D Matrix II	每次缩小一行或者一列的搜索空间	1. 重新写了一遍，因为受了第一题的影响，还用一个index来表示位置，然后index % /之类的。其实存个x，y坐标就好了2. 最后终止条件不是缩小到一行/一列，而是缩小到一个点	明天再复习下
301.Remove Invalid Parentheses	1. 对于 (()))来说，需要删掉一个）,对于最后3个）删除掉哪一个都会带来同样的结果，这样如何在答案中去重是个关键问题。和有重复数字的subset一摸一样的思路，对于连续的相同的“数字”，只把第一个的递归树加入结果

附上301的最优解，欢迎小伙伴体验这个题的酸爽。
Key Points:

1. Generate unique answer once and only once, do not rely on Set.
2. Do not need preprocess.
3. Runtime 3 ms.
Explanation:
We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter.
The counter will increase when it is ‘(‘ and decrease when it is ‘)’. Whenever the counter is negative, we have more ‘)’ than ‘(‘ in the prefix.

To make the prefix valid, we need to remove a ‘)’. The problem is: which one? The answer is any one in the prefix. However, if we remove any one, we will generate duplicate results, for example: s = ()), we can remove s[1] or s[2] but the result is the same (). Thus, we restrict ourself to remove the first ) in a series of concecutive )s.

After the removal, the prefix is then valid. We then call the function recursively to solve the rest of the string. However, we need to keep another information: the last removal position. If we do not have this position, we will generate duplicate by removing two ‘)’ in two steps only with a different order.
For this, we keep tracking the last removal position and only remove ‘)’ after that.

Now one may ask. What about ‘(‘? What if s = ‘(()(()’ in which we need remove ‘(‘?
The answer is: do the same from right to left.
However a cleverer idea is: reverse the string and reuse the code!
Here is the final implement in Java.

private static final char[] PAR = new char[]{'(', ')'};
private static final char[] REV_PAR = new char[]{ ')', '('};
private void remove(String s, List<String>ans, int last_i, int last_j, char[] par){
    int stack = 0, i = last_i, j = last_j;
    for(; i < s.length(); ++i){
        if(s.charAt(i) == par[0]) stack++;
        if(s.charAt(i) == par[1]) stack--;
        if(stack >= 0) continue;
        for(; j <= i; ++j){
            if(s.charAt(j) != par[1]) continue;
            if(j == last_j || s.charAt(j - 1) != par[1]) remove(s.substring(0, j) + s.substring(j + 1), ans, i, j, par);
        }
        return;
    }
    String reversed = new StringBuilder(s).reverse().toString();
    if(par[0] == PAR[0]) remove(reversed, ans, 0, 0, REV_PAR);
    else ans.add(reversed);
}

public List<String> removeInvalidParentheses(String s) {
    List<String> ans = new ArrayList<>();
    remove(s, ans, 0, 0, PAR);
    return ans;
}

楼主的打卡非常认真，我也要学习。楼主加油，给你点个赞。

给楼主点个赞，楼主加油。现在有工作的小伙伴也要居安思危才行

zjccpmh 发表于 2019-4-5 13:16
parental leave，他没权力不批啊， 进了pivot就拿钱走吧，免费的三个月工资不也挺好的么

楼主是不是可以先用完pto，再请unpaid/parental leave，最后再拿三个月pip package走人？