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

20200714:
3: 0050, 0508, 0530(0783), 0536
4: 0120, 0250
5:

打卡第一天 六道题（期待各位看官走过路过别忘记高抬贵手～～）
其实7月份天天都在刷题，每天都会写一个长总结，虽然题目不多，但是感觉收获很大，今天开始来地里继续开始打7月的卡了，加油干！

1.Check if Decimal
-注意上来手写5个boolean
-然后从左到右逐个依次进行检查
-最后通过validNumber && numberAfterPoint && numberAfterE来判断到底是不是decimal

2.reverse polish expression
-考察对于数据结构stack的应用
-需要检查开始的时候有咩有两个Integer，然后运算的过程当中如果一次拿不到2个intergers也是要丢异常
-值得注意的是除数如果是0那就要丢算术异常

1.2 两道题可以混在一起考察

3. Merge Two SortedLinkedList
-用两个dummy node
-whoever smaller choose whom
-最后记得断尾
4. Add two number
-想清楚terminal condition
-用int val记录一下当前的数，用取余数的方法新建node然后塞进新的list里面去
-然后每次通过 val /= 10来更新 val自己
5.LRU implementation

High level:
what kind of operations should I implement
what kind of DSs should I use;
what is LRU(least recently used)

Details:
Use a doubly LinkedList and a hashMap

Firstly, initialize the head and tail node;
initialize the treeMap;
and the hashMap take <key, Node> as <key, value> pair;

set(K key, V value)
check if hashMap contains this key,
case 1: already exist remove it from the cache and unlinked key Node in the doubly Linked List, then add the new One just right behind the head, and add the new <Key,Node> pair to the cache.
case 2: not exist
check the size of the cache and if it already full(cache.size() == capacity) then remove the earliest element we set, and unlink that node in the Doubly Linked List, finally create a new ListNode just right behind the head and put it into the cache. If it is not full just add the new Key-value pair into the cache and add the new Node right behind the head node

get(K key) -> return null if key does not exist in the hashMap

6. Max Stack
-虽然可以用两个stacks做，但是这样在用popMax的时候时间复杂度可能会直逼O(N)

-所以仍然采用Doubly‘linkedList + HashMap（treeMap）来做 只是参数会变化一些

High level:
my approach: use doubly-linked List and a treeMap
instead of using two stacks so I can make sure the popMax() operation can quicker than O(n) -> O(logN)

Details:
Firstly, set up the head and tail doubly-linked list node and initialize an empty treeMap;
push(): every time got an element, create a new ListNode and put it just behind the head, also to check if the element has already existed in the treeMap then update the <key, List<Node>> pair

pop(): unlinked the node just behind the head; and remove the node in the treeMap, if there is only one exist in the <key, List<Node>> pair, remove the pair;

top(): return the value of the node right behind the head;

peekMax(): use treeMap.LastKey() just return the value;

popMax(): use treeMap.Lastkey() not only return the value but remove the node in the Doubly linked List, also remove the node in the treeMap, if there is only one exists in the <key, List<Node>> pair, remove the pair;

TimLee 发表于 2020-7-18 06:49
July 13天打卡
今天有点刷不动了 0 0 求鼓励
Top K Frequent Elements         MinHeap （ ...

刷题很累，一起坚持！加油加油！

Jun 17 打卡第16天，复习13道题
426. Convert Binary Search Tree to Sorted Doubly Linked List, 注意dummy node，prev指针和helper方法不断更新当前连接；

day12
dp题目
decode ways是经典两种情况取一个，1d array就行
combination sum4和coin change基本差不多，有一种用hashmap的做法让我想到了brick wall但是这两题完全不一样
jump game早该做了，一直不会，解法有很多。dp的逻辑还算可以。greedy想出来果然很难啊

Day3 Doubly Linked list

连续刷题第5天
6. ZigZag Conversion 这是一道medium题，关键是想明白采用哪种算法，一种是类似仿真，同步build每一行的string,另外一种是直接计算出每一行的string.然后要处理第一行和最后一行的corner case. 另外我个人漏了考虑输入长度为1的特殊情况。
20        Valid Parentheses  
21        Merge Two Sorted Lists   

今天做了validate BST, insert into a BST, Delete Node in a BST，都是tree的题。

Day 5:
Smallest Range Covering Elements from K Lists: hard 题目，用到heap
Count Unique Characters of All Substrings of a Given String: hard 题目，每一次iteration根据上一次iter的结果算一下以当前char结尾的array里的unique char数量
Subarrays with K Different Integers： hard题目，将题目转化成atmost k intergers - at most k-1 integers, subquestion用two pointer解决
**number of contiguous subarray in a array (length n) = (n+1)n/2

Day 7

347. Top K Frequent Elements, 常规做法 counter + heap 同时solution中提到还有两个比较高级的解法：quick select 和 median of medians
1153. String Transforms Into Another String, string 题 还是要特别注意corner case
249. Group Shifted Strings, 也是string题，相对简单 主要是考ord函数