失业的第x天

在亚麻工作2年因为表现不好，需要主动或者被动离职。也没用什么热情继续在亚麻工作，组里所有人都知道我即将要走。新的老板人比较nice，给我留了一些时间让我边工作边找下一份工作。一方面，面对目前的工作实在没有什么热情了，另一方面，因为nice惯了，组员仍然各种指挥，甩锅给我。同时发现自己其实电面一些中等难度的题目，要bug free都挺困难的。所有觉得这样拖下去没有什么意义。我还是离开吧。
当作一个log file，记录每天发生的事情，看看多久能上岸，当然，不排除worse case 2个月都上不了岸。we will see。

失业的第-3天 04/03约老板聊了下离职的事情，他还是有点意外说我会急着要走。大家谈得比较开，确定了timeline，这周五是我最后一天上班。批准了我3周的vocation + 5周的unpaid parental leave。收拾东西，准备撤退。近期走了将近10个组员了，看着他们收拾东西，装箱子的时候觉得还是蛮伤心的。不过大家都是亚麻内部换组，然而我是该滚蛋了。特意找了会议室刷题，等到了11点再收拾。其实坑位上都没有什么属于自己的东西了。要带走的最主要就是这个国旗了。


失业的第-2天 04/03
因为每天晚上刷题要到12点多，早上得8-9点之间起来。
可能真的感觉到压力了吧。早上6:30就睡不着了，毕竟我从亚麻爸爸“辞职”了。
白天去公司打个酱油，然后去会议室刷题好了，明天最后一天因为是sprint planning meeting day，去上班没有什么意义了，就直接wfh了。今天最后一天去公司了，好好“珍惜”下了。
等晚上刷完题，回来打卡。

楼主加油！

失业第三天打卡今天准备把binary search 类别的题目过一遍，以后就基本不用再动binary search了。毕竟简单。
几道值得刷的题目

33. Search in Rotated Sorted Array	关键在于分清楚落在左边和右边的不同情况	忘了最外层if可以判断是在左边还是右边，这样可以把归类弄的简单点	todo明天再写一遍
k-th smallest element in two sorted array	算复习下两个array 找中点	1. 没有想清楚递归的含义。其实应该focus在想清楚当前层是什么意思。 当前层是找在2个array里面的第k个，通过的做法是比较2个array的第k/2个。 2. 当进入当层递归时，某个数组的startindex 以后越界了，那么意味着，所有的k个数都从另外一个数组里面拿。想清楚物理意义，这样代码才不会错。落实到代码： return nums2[start2 + k - 1]; 3. 当前层的第k个数的index 应该是 k - 1. 比如，第一个数的index是0. 代码： mid1 = start1 + k / 2 - 1； 4. 对于当前层应该怎么传数值给下一层递归，还是通过物理意义。当前层从单一一个array里找了k / 2个数字， 所以下一层要找 k - k/2 个数字。而不是k/2。 千万注意！	again：明天再写一遍
k-th element closest to target in array	其实就是找到了target以后，把左半边array 和右半边array分开，做一遍  k-th smallest element in two sorted array	Math.abs(input - target);

对于 33. Search in Rotated Sorted Array，我其实忘了具体的trick是怎么样的了，所以就干脆直接很笨的分类讨论再归纳起来。
Step 1: 分类
mid  >  target
1. both on left -> update right
2. both on right -> update right
3. mid on left, target on right -> update left

mid < target
1. both on left -> update left
2. both on right -> update left
3. mid on right target on left -> update right
step2: 合并
mid  >  target

   mid on left, target on right -> update left

   else  -> update right
mid < target

   mid on right target on left -> update right

   else -> update left
虽然最后代码没有最优的方式优雅，但是锻炼这种能力还是很重要的，毕竟你不能保证你记得所有题的trick或者一眼看穿马甲。

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

失业的第二天，打卡面试

昨天抱着必死的决心跟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[j] = Math.max(mustSell[i - 1][j] + diff，...) 因为i点和i - 1 点都sell了，那么就是 i - 1天卖出了，然后马上买了在i的时候卖出。 可以把这两次卖出给合并为1次卖出。所以j不用++。	2个状态转移方程： mustSell[j] = Math.max(mustSell[i - 1][j] + diff, gobalMax[i - 1][j - 1] + diff); gobalMax[j] = Math.max(gobalMax[i - 1][j], mustSell[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一摸一样的思路，对于连续的相同的“数字”，只把第一个的递归树加入结果

失业的第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 取决于 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上游走的相关题目

楼主加油，亚麻的工作还挺有价值，要跳应该不难，你一定可以找到下一个工作的

楼主能说下具体原因吗？工作2年/表现不好？是工作内容难？没意思？团队不好？还是什么的？

manager真的是很够意思了感觉。。LZ加油刷题，来得及的

期待LZ可以和我们大家说说你自己的经历，虽然你走了，但是你的经历都是有价值的！！

Cpangwork 发表于 2019-4-5 06:44
期待LZ可以和我们大家说说你自己的经历，虽然你走了，但是你的经历都是有价值的！！

https://www.1point3acres.com/bbs ... D325%26sortid%3D325
经历 拿去～

你老板不错， 给5周unpaid, 一般只肯给2周交接， 也不肯换4周unpaid, 加油啊， 兄弟， 可以加我微信聊一下， 我也是最近进了pivot

831128 发表于 2019-4-5 12:35
你老板不错， 给5周unpaid, 一般只肯给2周交接， 也不肯换4周unpaid, 加油啊， 兄弟， 可以加我微信聊一下 ...

parental leave，他没权力不批啊， 进了pivot就拿钱走吧，免费的三个月工资不也挺好的么

失业的第-2天 打卡
把手上的任务基本做完了，tech debt的code扔出去了一个cr，等着明天看看能不能apprive了。
昨晚把箱子收拾好，扔车里了。今天把书包带走，工位上除了显示器就啥都没了。过去一年送走了 3-4个同事了，今天轮到中国同事把我送出大楼里，还是有点伤感的。

晚上开始刷题：

题号	关键点	备注
309. Best Time to Buy and Sell Stock with Cooldown	1. 动态规划general的思想，后一个状态取决于前面的一个或者几个状态。这个题也不例外，但是induction rule不是特别明显。 2. 涉及到的状态太多，比如我是买还是卖，什么时候买卖，我当前的状态是否需要cool down之类的。用一个一维数组，if else的情况太多很难想清楚。 -> 关键点 a. 一个数组表示之前的状态太复杂，考虑开2个数组，分别记录买的时候的最大利润和卖的时候的最大利润。开2个数组来存dp的状态是很多题目通用的技巧，比如一些string的题，从左往右扫一遍，然后从右往左再扫一遍。 > 关键点b. 动态规划考虑当前问题和小1号问题之间的联系。所以buy取决于buy[i - 1] 和 sell[i - 2] (因为有冷冻期)。 想清楚induction rule 当前问题和小一号问题之间的关系是整个题目的关键	//todo: 把股票相关的问题过一遍
jump game1 && 2	1. 贪心法涂色是最优解法 2. 判断dp 的状态的时候，需要遍历左侧所有的点，不能只从右往左找到第一个点，因为可能会漏掉最优解
221. Maximal Square	induction rule是这道题的关键： dp[x][ y] = min(dp[x- 1][ y -1], dp[x- 1][y], dp[x][y - 1]) + 1 首先别忘了+ 1， 其次理解为什么是选三者的最小，可以自己画画图，结果是这三个正方形的overlapping的区域。
279. Perfect Squares	关键点： 1. dp[x]的物理意义， 组成x大的数最少需要多少个square number 2. 类似于jump game： 要在dp[x] 左侧所有点都过一遍去找最小的可能的解。找到所有的而不是一个 3. for (int j = 1; i - j * j >= 0; j++) {         dp = Math.min(dp, dp[i - j * j] + 1); }  注意理解这个循环控制条件 以及>=
Search a 2D Matrix II	关键点： 1. 还是二分法的思想，但是重点在于如何缩小搜索空间，或者说扔掉一半 2. 不是像search 2d matrix 1 一样，每次能找到个中间的点，扔掉一半，目前是从左到右，从上到下是sort的。这样的话，如果选了中间的点，无法更新搜索空间。关键点是，选取角落上的点，每次将搜索空间缩小一行或者一列。其实还是根据它sort的性质来缩小搜索空间，但是不是死板的选择一个中点来扔一半。	//todo 明天写一遍

快要入职亚麻了（不过不是语音助手组） 关注一波楼主 楼主加油！