刷题打卡

zzitaI 发表于 2018-12-9 00:34
behavior question

新人，谢谢~

25天 Goolge onsite 倒计时

12.13 打卡

• 【Longest Common Prefix】find longest common prefix among all input words, sort 或者 trie, O(NklogN) 或者 O(Nk)
• 【Whether a Binary Tree Contains All Chars of a Input String】inorder traversal, 每个节点一个char一个char地check, 17 min
• 【Decoder Iterator】input sequence like [2,4,0,3], it means 2 times of integer 4 and 0 times of integer 3, implement an iterator, 15 min, 多线程则读(hasNext)写(next)锁，两个lock+readCnt
• 【Shortest Path】given an infinite large chess board, start from (0,0) to a destination, some points cannot be visited, 每次跳一个“日”字, shortest path? 双端bfs, 10 min
• 【LC 375 Guess Lower or Higher II】O(N^3) DP, 实际上increasing dq可以达到O(N^2)，下次再写一下这个算法，16 min
• 【Longest String Sequence】given a list of strings, 构成串的条件是当前string比parent多一个字符，并且除去最后这一个字符与parent相同, buildGraph (sort by length, Map: string -> Node) + dfs recursive，O(NlogN), 18 min
• 【LC 3 Longest Substring without Repeating Chars】2 pointers + map, 13 min
• 【Max Value of a Complete Tree】LC原题, O(h^2), 8 min
• 【Minimum Cost for IDs】given a list of pairs, each pair has an id and its cost, find K pairs with minimum cost, also one ID cannot be chosen for more than M times, sort + map, 5 min
• 【LC 777 Transfer one String to the Other】RXX -> XRX, O(N) 12 min
  

Goolge Onsite 23 Days

12.14打卡

• Binary tree leaves sum, requirement space O(1) + time O(N): morris traversal，原本要求的N-ary Tree，这个还不太会
• 【LC 76 Minimum Window SubString】2-pointers + map
• 【LC 399 Evaluation Division】build graph + dfs
• 2 int array, 找出所有相同数字及其下标, map / sort
• Encode String, e.g. aaaabbbcd -> 4Xa3Xbcd, drawback: 有数字需要encode的时候，比如44X133X2可以是44个1+33个2，也可以是44个1+一个3+3个2
• 【LC 252+253 Meeting Rooms】begin/end time sort respectively
• 比较两个sentence中单词是否完全匹配，blacklist中的词skip，不用set可以用trie
• array中每个元素代表多少个coins，index i每次只能取i个coins，少于i则不能取，player1 & player2 in turns take coins, say if player1 wins，sum次数判断奇偶即可
• 【LC 803 Hit Bricks】UnionFind，先把要hit的bricks不算，逆序一个一个添加回来
• given an int array, join all numbers with add/minus/multiply/division, how many results, 每次尝试两个neighbor加减乘除，直到array还剩一个元素，添加到set
  

Google Onsite 23 Days

12.15打卡

• HTML tree, leaves contains string, 给一个string，问有哪些leaves构成，traversal+map
• 有向树多了一条边，找到所有可能多余的
• 【LC 320 Generalized Abbreviation】bit-manipulation,O(2^N)
• 【LC 288 Unique Word Abbreviation】map: abbr -> word，多个相同abbr则更新为abbr -> ""
• 01 matrix各行sort好，找到1最多的行，O(m+n), index pointer从右上到左下
• ABC  -> 123, 问123有多少种字符串可能，dp
• 运算表达式，e.g. 3,3,+,2,1,+,/ => (3+3) / (2+1) = 2, stack
• 【LC 855 Exam Seat】PriorityQueue，首尾interval添加start=-1,end=N，一个人leave遍历pq remove，O(logN) + O(N)