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

晚上打算睡觉前再刷一道题，结果就悲剧地连错了五次😭... 之前一直用Python刷题的我真的是对整数溢出一点概念都没有。还需努力啊！（这是166：分数转小数）

July 第18天 打卡

Linkedlist 连来连去 我要裂开了
Linkedlst Fast/slow Pointer related questions

1.  Linked List Cycle  
2.  Linked List Cycle II  （弗洛伊德算法实在是有点不懂，用unorderd_set做了）
3.  Happy Number (用快慢指针可以optimized O(N) to O(1))
4.  Palindrome Linked List  (快慢指针找到中间，reverse second half the list，需要注意linkedlist 的长度 奇偶性
5.   Reverse Linked List  (Recursion  + Non-Recursion)
6.   Reverse Linked List II
7.   Reorder List  又是一个裂开题，前半部分最后一个node 要记得 把next set成false
8.   Binary Tree Zigzag Level Order Traversal  Deque 可以不用reverse。 zag的时候(Left to right) Push_back + pop_front + (Right->Left) ZIG 的时候 PUSH_FRONT + POP_BACK + LEFT/RIGHT

7月打卡第13天 4道

打卡14天

3道基础题都不难
主要是一些细节需要考虑清楚

7月22日 累计打卡第6天，每天都有新收获
今天三道题，已经累计超过5天了，棱不棱求看官多加几粒米，一定把最扎实的心得给大家分析，55555，谢谢谢谢～～

1.word Ladder I
-BFS
-use an int variable Step to calculate the steps to connect begin word to the end word
-handle the corner case and don't forget to bring the start word itself into consideration

2.word LadderII
-BFS + DFS + HashMap(memoization) + pruning;
-frequently showed up at the interview and I did meet once at wepay onsite at 3.30th 2020

我以为较好的解决方案：
High level:
BFS + DFS with
use memoization & pruning

Details:
首先，过滤掉所有之前已经访问过并且在字典里面的单词，
其次，用一个set-> currentLevel来表示这一层（就是startWord刚好跨一步能够到达的那一层）
所能达到的且在字典里面的单词；并且持续更新这个set（currentLevel）
使用一个boolean variable来判断是不是已经找到最后的goal，如果已经找到，那么只要完成这层建立对应关系即可退出
不然得访问完所有可能性才能终止BFS的循环

然后再用DFS，
base case是: startWord.equals(endWord);
main logic（recursion rule）
具体的说就是用HashMap来记录以s开头的list
然后再用DFS就只在这个s对应的list里面去找
如果找到了就往下探，如果没有找到就在当层的list当中继续找

3. Rotting Orange （leetcode 994）
-BFS
-use HashSet to store the elements that has been successfully traversed in current level;
-one way to improve the space complexity is use a Hashset to store the pair(row, col)
-and @override hashCode + equals

谢谢看官们～～

7/22 打卡第22天， 刷了3道题

225. Implement Stack using Queues
push实现时，先queue.append(x), 然后再queue.append(queue.popleft()) n-1次

232. Implement Queue using Stacks
用了两个stack， stack1 用于push，stack2用于pop，如果stack2空时，把stack1移到stack2

238. Product of Array Except Self
先存左边所有元素的product, 再乘以右边的所有元素

今天还是PayPal的题

day10

7/22/2020 依然是sql 题

1484 Group Sold Products By the Date
这题就是考一个group_concat， 恰好我还不会。。。

1069 Product Sales Analysis II
不懂这题考的点在哪里，难道就一个group by?

1511 Customer Order Frequency
这道题做负责了，用了两个subquery 分别求6，7月的sales, 应该用wild card 做月份 group by 就好了。

抱歉前面的同学，我明天应该就到100分，可以给大家加积分了。

先greedy，要想想
然后dp，要想想
然后dfs，无脑，就需要用一下backtracking