8月刷题/Mock interview接龙活动（缺米刷题的来）

3 minutes ago        Time Based Key-Value Store        Accepted        145 ms        java
18 minutes ago        Reverse Linked List        Accepted        0 ms        java
26 minutes ago        Subarray Sum Equals K        Accepted        13 ms        java
34 minutes ago        Excel Sheet Column Number        Accepted        1 ms        java
40 minutes ago        Decode Ways        Accepted        1 ms        java
1 hour, 10 minutes ago        Permutations        Accepted        1 ms        java
1 hour, 18 minutes ago        Find Permutation        Accepted        6 ms        java

今天早上的DS product sense mock interview，感觉还不错，需要加强的地方：

- User journey的解释放在最前面
- Structure要体现得再清楚一点
- impact size/practical significance的部分可以多描述

Aug 15 打卡


Non-overlapping Intervals         greedy
Wiggle Subsequence         DP时间序列
Paint House         DP 时间序列

昨天刷得题，忘记贴上来了。

8.15 Heapq
#253. Meeting Rooms II
Greedy algorithm + heapq
sort the intervals by start time, and store end time in a heap.
      for sch in intervals:
            if hq and sch[0] >= hq[0]:
                heapq.heappushpop(hq, sch[1])
            else:
                heapq.heappush(hq, sch[1])

#215. Kth Largest Element in an array
k largest -> maintain a min heap, pop out small number and retain big number, return hq[0]

#373. Find k pairs with smallest sums, easy one! Same template

#692. Top k frequent words
A little different, we need to sort by count and alphabetical order. so (-count, word)

#378. Kth Smallest element in a sorted matrix
Solution 1: O(n^2*logk) flatten the matrix, but slow
Solution 2: O(min(n,k) + klogn) = O(klogn) Since rows and columns are both sorted, we can process the matrix diagonally.
        # build a minheap using the first row/column, here I use column, record the idx (i, j ) as well
        # if we look at the matrix diagonally, we can tell that if we do not pop matrix[i][j], we do not need to put on matrix[i][j + 1] and matrix[i + 1][j] since they are bigger
        hq = [(row[0], i, 0) for i, row in enumerate(matrix)]
        heapq.heapify(hq)
        res = 0
        for _ in range(k):
            res, i, j = heapq.heappop(hq)
            if j+1 < len(matrix[0]):
                heapq.heappush(hq, (matrix[i][j+1], i, j+1))
        return res

8/15 三道背包类型的DP
1. Backpack: 0/1背包问题，考虑第i个物品放与不放两种情况。
2. Partition Equal Subset Sum: 将问题转化为从数组中选取元素放入容量为一半总和的背包，判断是否能装满。
3. Backpack II: 除了size，同时考虑item的value

今天的七题

8.15 day15 August LeetCoding Challenge

08.14.2020 打卡第十四天 刷题十四天 刷题8道(6道水题）
第十四天刷题了✌️，加油加油！争取下周能拿到OA

1. ReverseLinkedList(Iterative)
2. ReverseLinkedList(Recursion)
3. Find Middle-快慢指针
4. Check if cycle
-快慢指针
5. Insert in SortedLinkedList
6.MergeTwoSortedLinkedList
-DummyNode
7.Cycle Node in LinkedList
（其实是找到循环开始的第一个元素，如果没有return null）
-assumption:
-这个list里面没有重复的nodes
-这个需要用到一个hashMap
-如果这个HashMap当中任何一个元素出现第一次重复了
-那么该node即为第一个重复的元素

8.Odd even LinkedList
-其实不算个medium题
-算个easy - medium，就算要求O(n) time Complexity-O(1) space complexity
-就是用一个dummy Node帮助串联所有属于even index 的node
-然后再把even Nodes也先接在一起，然后带上之前接好的even nodes

打卡
Search Insert Position
Longest Cycle
Longest Ascending Subsequence
Roman to Integer