刷题记录帖

1. coding：一个类似线段树的题。一棵树叶子节点上有单词，所有的字母从左向右看，index从0递增。实现一个方法返回index对应的字符。follow up是实现一个方法返回start, end之间的字符。

2. coding: 很裸的拓扑排序。Makefile里面的build target有dependency，输出build的顺序。follow up是怎么设计一个系统，加速build的过程，就是纯说。最后剩了10多分钟就纯聊天了。

午饭是一个中国大兄弟，很逗的，刚入职google不久，问啥都回答不知道

3. coding: 上来先跟我聊了15分钟，然后说我们开始做题吧，要不然做不完了。让我实现一个音乐播放列表的随机播放功能，要保证每首歌概率一致，给个window，代表同一首歌不能在这个window中被重复播放。
               我一直没有get到这轮要考察什么，写了很简单的代码，然后一直在问我API design和OOD相关的问题，然后问我为啥工作用java，面试用python，还有python的语法特性之类的问题。

4. bq: 这轮bq问的相比亚麻来说毫无灵魂，感觉就是照着checklist读，每个问题也不会去扣很深，不知道是狗家的风格还是面试官对我做的东西不感兴趣。

5. coding: 给一个array of TreeNode，每个TreeNode中只有一个id(没有left, right指针)，这个id代表这个node的parent在array中的index，如果id==index，这个node就是root。
               实现一个方法，input是array中的一个TreeNode，output是删除掉以这个TreeNode为root的子树之后的array。最开始给了assumption，array中只有一棵树。
               follow up: input是多个TreeNode，output要求不变
               follow up: 如果array中有多棵树，代码还work吗
               这一轮面试官人不错，给了我很多hint

https://www.1point3acres.com/bbs ... 6orderby%3Ddateline

recursion 跑test case方法

250. Count Univalue Subtrees
687. Longest Univalue Path

done

568. Maximum Vacation Days
165. Compare Version Numbers
812. Largest Triangle Area
246. Strobogrammatic Number
1056. Confusing Number
iterator
https://www.1point3acres.com/bbs ... 6orderby%3Ddateline

OODtimu

design的题目全部做掉
Google软件测试之道 下载一下

阅读test书， test plan risk analysis

Chrome OS Test Plan
what is Chrome OS?
ACC
what is sync, web centric, plugin, power management,

to be continued, dive into detail.
what is RAM and irm.

146. LRU Cache
380. Insert Delete GetRandom O(1)
prc tomor
class ListNode{
    int val;
    ListNode next;
    public ListNode(int x){
       val= x;
    }
}

LinkedList

707. Design Linked List
1206. Design Skiplist


plan tmr, get up at 8, arrive at 9.
practice code

and study.
go to bed at 11:00

707. Design Linked List

没有 debug出来

design for single linked list and double linked list.

pay attention

141. Linked List Cycle
142. Linked List Cycle II
202. Happy Number
160. Intersection of Two Linked Lists
19. Remove Nth Node From End of List
study this tmr
206. Reverse Linked List
203. Remove Linked List Elements
328. Odd Even Linked List
234. Palindrome Linked List

2. Add Two Numbers
21. Merge Two Sorted Lists
61. Rotate List

430. Flatten a Multilevel Doubly Linked List
study tmr
708. Insert into a Sorted Circular Linked List
138. Copy List with Random Pointer


One advantage of double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.

146. LRU Cache
done

297. Serialize and Deserialize Binary Tree

they create automation for user scenarios
how？

47. Permutations II
debug yixia


trick
31. Next Permutation
122. Best Time to Buy and Sell Stock II
121. Best Time to Buy and Sell Stock

return type
203. Remove Linked List Elements
sentinel node
keep record of prev node
after deletion, head still point to head next but it is not in the list

debug a linkedList code
what will it return
the link betwen node

328. Odd Even Linked List
termination condition

whilte board


ListNode 要注意的点：
1 是否需要设置dummy head and tail
2, print 顺序，怎样来设置print 的顺序。
3. node.next.next 的使用
4 base case 的条件设置。
node != null &&(||) node.next != null
5 when you iterate to the end and still want to use head, initialize a node to store the head.
6 two pointer technique

234. Palindrome Linked List

// because we are comparing Integer, not int.
            if (!vals.get(front).equals(vals.get(back))) {

Approach 3: Reverse Second Half In-place

double linked list
study about it.

380. Insert Delete GetRandom O(1)
done
pay attention to sequence
usually operate then delete.
Random.nextInt() in Java

// Print next int value
        // Returns number between 0-9
        int nxt = ran.nextInt(10);
  

remove(int index) : Accept index of object to be removed.

The set() method of java.util.ArrayList class is used to replace the element at the specified position in this list with the specified element.

public E set(int index, E element)