Chapter 48 Linkedin before 2015

https://github.com/WeizhengZhou/leetcode3/blob/master/src/linkedIn.txt

48.1 Sudoku - Add Two Numbers - Maximum product of a triplet

http://www.mitbbs.com/article_t/JobHunting/33077191.html

最近刚面的, 版上哥们推的,是 SDET的

  1. DEBUG一个class,是解数独的,估计由于是SDET,所以不难,不用考虑3×3的小格 子,只考虑行,列不同就行
    不过是第一轮,并且这个她给的解法,从来没看过.磕磕巴巴在几个HINT的帮助下找来 几个BUG出来.说实在,我发现interview也不太清楚这个解法咋回事,估计是直接题库 拿的.这一轮估计悲剧了

  2. 一个老题目,链表加法. 解法是先反转,再加,再把结果翻转. 写完有个小bug, 改完之后,小印说还有bug,但跑了几个case都能过.就去讨论翻转的func,这个链表 翻转,小印没看懂,一直说有bug,但跑了几个case,还是能过.时间到了,就结束了 .目测也悲剧,因为这种难度题目应该是做两道的.

  3. test plan. 设计一个plan测试一个循环数列

  4. 3道题,第一个是给一个数列,求3个数使其乘积最大. 第二是个简单的same tree. 第三道题交流了10分钟,我还是没搞懂题目意思. 最后面试官给了答案,看了答案发 现是很简单的问题.但我感觉还是问题陈述的不清楚. 问题是给了几个function, 写 一个函数,让两个点相撞.

  5. 传统的behavior面,随便扯了扯

虽然还没给结果,但估计已经挂了.其实L家SDET面试按这个来说,还是相当简单的. 可惜了好久没面试,没习惯白板写算法.犯了不少蠢错误. 还有一个总结是,平时写算法,还是要写能够简单易懂的. 比如翻转链表这种,递归 明显会比迭代看起来顺眼.

48.1.1 36. Valid Sudoku

https://leetcode.com/problems/valid-sudoku/

check: array

48.1.2 37. Sudoku Solver

https://leetcode.com/problems/sudoku-solver/

check: array

48.2 Bipartite - Product of Array Except Self - Intersection of Two Arrays

http://www.mitbbs.com/article_t/JobHunting/33034407.html

  1. recruiter
  2. host manager 老墨? 讲项目,behavior,问了一道 brain storm 所有翻转数组的方法.就是看能想出多少种方法翻转链表,比如两个指针交换,用栈先压进去再弹出来,分治等等
  3. technical communication 两白男,讲项目
  4. lunch 国人小哥,直接中文聊天
  5. coding 一中一印,(1) product with the element except itself, 我先讲了不用除法的方法, 然后是用除法的方法,需要考虑没有0,一个0和多于一个0的情况. 先说了时间O(n)空间O(n),面试官要求时间O(n)空间O(1), 只想到了做除法.一开始写得时候没考虑 0,后来面试官提示有没有 edge case 才加上的.估计减分了.
  1. 判断一个graph 是不是bipartite, 我用了BFS的方法,起始结点标左边,然后相邻标右边,再相邻标左边,如顺利标完则是 bipartite,发现冲突则不是. 用一个哈希表visited保存访问过的节点,另一个哈希表node2color保存节点分在那一侧

  1. system design: tiny URL. 先写了 URL 表示,数据模型.然后聊了后端存储,NoSQL,怎么 partition,怎么判重.然后聊了 cache 和前端的 LB.

  2. coding 同样一中一印,

  1. 找出DNA序列中出现多以一次的长度为10的碱基序列,和面试官讨论最后用bitmap实现. 由于长度为10的碱基序列总状态为\(4^{10}\),可以用长度为\(4^{10}\)的 bitmap 保存是不是遇见过.请问 rolling hash 怎么做?

  2. 两个排序数组找intersection,并要求去重.直接合并完成.

所有的 code 都写完,并且按复杂程度分解成小功能的函数,从宏观到微观写.写code 用了 python,会不会有面试官觉得 python 有些 cheating?
recruiter是三妈,完全不提供feedback,只是说了一些general的原因,觉得都不是很符合.
求分析失败的原因.

48.2.1 238. Product of Array Except Self

Check: array

48.2.3 350. Intersection of Two Arrays II

https://leetcode.com/problems/intersection-of-two-arrays-ii/

Given two arrays, write a function to compute their intersection.

Example:

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

这个题两个解法: 一个是hashtable,一个是two pointer.

https://segmentfault.com/a/1190000005720072

Follow up:

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

  • If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
  • If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read (let’s say) 2G of each into memory and then using the 2 pointer technique, then read 2G more from the array that has been exhausted. Repeat this until no more data to read from disk.

http://www.geeksforgeeks.org/external-sorting/

Keyword: Runs, Fan-in, Page

10月13:

http://www.mitbbs.com/article_t/JobHunting/32802467.html

  1. 层序打印 binary tree
  2. 实现 BlockingQueue 的 take() 和 put()
public interface BlockingQueue<T>{
    /** Retrieve and remove the head of the queue, waiting if no elements
        are present. */
    T take();

    /** Add the given element to the end of the queue, waiting if necessary
        for space to become available. */
    void put (T obj);
}
  1. 实现一共 TwoSum interface
public interface TwoSum {
    /**
     * Stores @param input in an internal data structure.
     */
    void store(int input);

    /**
     * Returns true if there is any pair of numbers in the internal data
       structure which
     * have sum @param val, and false otherwise.
     * For example, if the numbers 1, -2, 3, and 6 had been stored,
     * the method should return true for 4, -1, and 9, but false for 10, 5, and 0
     */
    boolean test(int val);
}

10月14:
Q2: What is a singleton class and how would you design it.
Some threading related things for it.
Q3: Write a parseInt function (Similar to Q1).

10月10:
投的职位Linkedin Test Engineer(Mobile&Web)

背景:cs master +一年test engineer工作经验;

电面一轮+onsite5轮;

电面:什么是singleton,两道算法,printTreeByLevel,字符串含数字求数字和.

48.3 415. Add Strings

https://leetcode.com/problems/add-strings/

Onsite,第一轮manager面(女阿三),基本都是 behavior questions, 聊下文化和做的项目;第二轮(国女)问的都是用selenium解决一些实际问题(automation),比如在google search然后返回search结果的数目,怎么判断页面加载完毕等;第三轮吃饭;第四轮(国男+印女),test strategy 给一个linkedin的feature,写一个完整的test plan.最后一轮俩阿三,一男一女,问了一下做的项目,然后两道coding,这轮答得不好,题目很简单,但是阿三表述一直不太清楚,感觉花了很久才明白到底问什么;一个leetcode原题(fibonacci 数列的一个),还有一个实现stack的push和pop,但要求每次返回middle number,主要是考察一些基本data structure.因为linkedin主要是test在web和mobile,用的工具是selenium和appium,所以面试官也比较喜欢问这方面.
http://www.mitbbs.com/article_t/JobHunting/32800519.html

48.4 34. Search for a Range

https://leetcode.com/problems/search-for-a-range/

更多解释参考binary search一章.

10月7日:
Print a tree like reading a book, left to right.

如果是binary tree,就是in order traversal.

phone 1:
1. Search for a Range (leetcode)
2. Decide whether a target is covered by a list of intervals (类似merge intervals)

Interval Tree?

第二题答的不好,感谢国人大哥大姐放水!

phone 2:

  1. permutations (leetcode)
  2. permutations II (leetcode)
  3. 设计一个iterator class处理文件line by line

三哥看不懂2的solution,纠结了好几十分钟,最后3基本没时间写,悲剧了

http://www.mitbbs.com/article_t/JobHunting/32800503.html

intern 两个leetcode题目:

Maximum Product Subarray

Check: array

9月17: 1. valid number. LeetCode 原题,但是没写过,讨论了半天edge case,结果还是没考虑“-.”的情况,最后经过提示算是勉强写出来了,但是code不是很clean.

  1. Nested integer weighted sum. 一个list, 元素可能是list,也可能是Integer, 但是每个元素都包装在NestedInteger类里面了,求weighted sum. 例子是{2, {4, {6}}}. 应该返回2×1 + 4×2 + 6×3. 我可能该开始就省题不清,写成了 (((6x3) + 4)x2 + 1)x1. 经过面试官提醒,改了一个小地方就对了.感觉自己代码还算简洁,总共15行左右.

http://www.mitbbs.com/article_t1/JobHunting/32784787_0_2.html

  • 实现stack的push和pop,返回middle number就是http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation

Check: linkedin-2016-11

9月15
http://www.mitbbs.com/article_t/JobHunting/32783387.html

48.5 Design RESTFUL Server

9月6
http://www.mitbbs.com/article_t/JobHunting/32776417.html

设计题: a restful server with 4GB (memory),
given a request such as: http://seq=4?len=60?xxxxdata, the system will store the binary data with that sequence number. given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.

9月5:
http://www.mitbbs.com/article_t/JobHunting/32775405.html
http://www.mitbbs.com/article_t/JobHunting/32763769.html

  1. 2D matrix, sorted on each row, first element of next row is larger(or equal) to the last element of previous row, now giving a target number, returning the position that the target locates within the matrix

  2. Given a binary tree where all the right nodes are leaf nodes, flip it upside down * and turn it into a tree with left leaf nodes.

http://www.meetqun.com/thread-2083-1-1.html

8月29:
- How to find if nodes in graph are exactly 1/2/3 edges apart. how would you distribute graph across machines.
- Given set of characters and a string, find smallest substring which contains all characters.
- Implement a delayed scheduler for jobs using pthread apis(mutex/condition_var)
- You have bunch of numbers coming in, and a given a window size, how would you save numbers so that you can return number if present in window and provide average for current window.
- Manager round: You are given bunch of machines with services running on them, how would you improve things. very vague design talk.
- Reverse words in a string.
- Implement decimal to roman and vice versa.

48.6 Deadlock + Constant Time Add-Remove Data Structure

48.6.2 Data structure: insert, remove, contains, get random element, all at O(1)

http://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1

O(1) lookup implies a hashed data structure.

By comparison:

  • O(1) insert/delete with O(N) lookup implies a linked list.
  • O(1) insert, O(N) delete, and O(N) lookup implies an array-backed list
  • O(logN) insert/delete/lookup implies a tree or heap.

http://blog.csdn.net/whuwangyi/article/details/18897387

48.7 Line Iterator of Text File

8月26:
店面的,应该是挂了,完全不知道要做什么
就让实现一个file class的iterator
然后已经有一个method可以读取文件每一行.
需要返回一个iterator, 返回文件的下一行.
也可能题目我没理解明白,刚开始我打算写读取文件,他又说文件很大,不能一次读入

http://www.mitbbs.com/article_t/JobHunting/32767815.html

ifstream::open does not read the file into memory. an ifstreram will only load a small buffer into memory at any one time.

http://www.cplusplus.com/forum/general/57790/
http://stackoverflow.com/questions/12997131/stdfstream-buffering-vs-manual-buffering-why-10x-gain-with-manual-buffering

8月20: 1.查找2个单词的距离

/*
* Example:
*   WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
"quick", "brown", "fox", "quick"));
*   assert(finder.distance("fox","the") == 3);
*   assert(finder.distance("quick", "fox") == 1);
*/
  1. 洗牌 要求in-place
    第二面:老印和abc,中间abc一直没有吭声过…貌似这个题很常见,我另外2个朋友电面都碰到了,原题,大家好好准备,其实不难,就是edge容易忽略
  • Return the smallest character that is strictly larger than the search character,
    ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'

http://www.mitbbs.com/article_t/JobHunting/32763769.html

http://www.careercup.com/question?id=5726366532108288

8月11:
两个面试官,master是中国人(WW),另一个是烙印.两题在网上都有一个是Nested Sum,第二个在sorted 的integer中找到给定的数的range.

http://www.mitbbs.com/article_t/JobHunting/32763427.html

7月10:
http://www.mitbbs.com/article_t/JobHunting/32733769.html

48.8 Bidirection BFS + Design Hashtable

  1. 给定一个undirected graph和一个s节点和一个d节点,判断s和d的距离是否<=3.距离定义为s和d之间最短路径上link的数目.如果d是s的邻居,则距离为1.

注意,这个undirected graph使用adjacent array来表示一个节点的所有neighbors,并且每个节点最多有n个neighbors.每个节点都有一个Idx,并且每个节点的adjacent array都是sorted.例如1有邻居2和3,那么1的adjacent array是[2,3] (sorted)

直接的BSF解法时间复杂度是O(n^3). 要求设计Solution是时间 O(n^2).

  1. 设计一个hash table,实现set(int key,int val)和get(int key)

  2. 给定一个整数array A (长度为n),求出另外一个array B,使得B[i] = A[0]A[1]…A[i - 1]A[i + 1]…A[n - 1] (i.e., A[i] is missing from B[i])

如果不可以用除法,如何解?要求solution是时间O(n)

  1. 给出n个点,求最多点的数目(这些点在一条直线), leetcode原题

48.9 Convert a Binary Tree into its Mirror Tree

6月23:
L家 - 挂了:

电面1: 白人,HM.
Chat 5 min.
Basic Question: 10 min: TCP vs UDP, Virtual Memory, Page fault, etc…

Question 1: Mirror a Tree
http://www.geeksforgeeks.org/write-an-efficient-c-function-to-convert-a-tree-into-its-mirror-tree/

Question 2: Implement a data structure supporting: insert, delete and random get

http://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1

电面2: 国人
Question: Java Blocking Queue

http://www.practice.geeksforgeeks.org/problem-page.php?pid=700155

48.10 getTotalCoveredLength

6月22:

  1. Return if two strings are isomorphic. (character 1-1 match)
"zoo" -> "fee"  ( z->f, o->e)               true
"zoo" -> "dui"  ( z->d, o->u, o-> )        false
"dui" -> "zoo" (d->z, u->o, i-> )         false

Use two hashmaps

  1. K nearest points (solution see below) Time: O(nlgk)

  2. Search in rotated sorted array

2. public interface Intervals {
    /**
     * Adds an interval [from, to) into internal structure.
     */
    void addInterval(int from, int to);
    /**
     * Returns a total length covered by intervals.
     * If several intervals intersect, intersection should be
     * counted only once.
     * Example:
     *
     * addInterval(3, 6)
     * addInterval(8, 9)
     * addInterval(1, 5)
     *
     getTotalCoveredLength() -> 6
     i.e. [1,5) and [3,6) intersect and give a total covered
     interval [1,6). [1,6) and [8,9) don't intersect so total
     covered length is a sum for both intervals, that is 6.
     *
     * 0  1    2    3    4    5   6   7    8    9    10
     */
    int getTotalCoveredLength();
}

Interval Tree主要拿来找重叠的interval,所以这里用不上.

48.10.1 Algo 1. Add - \(O(1)\), getTotalCoveredLength - \(O(NLogN)\)

遇到起始点count加1,结束点count减1. count等于0的时候把结束点 - 起始点的差累加入结果.

Trick: 如果所有的数字都为正,可以用正数代表起始点,负数代表终止点, then we don’t have to use the bool.

因为用了sort所以复杂度是\(O(NLogN)\). 上面的算法用在add被调用很多次但是getTotalCoveredLength被调用的次数很少的时候.

Simliar problems:

如果add调用的次数少,getTotalCoveredLength要调用很多很多次的话,如何改进上面的算法?

48.10.2 Algo 2: List of Ordered Intervals

Add: \(O(K)\) Len: \(O(1)\) - 总interval个数是N,互不重叠的interval有K个(K<=N).

Very similar to Insert Interval

这个办法是面试最优解.

  • For b4’s case, line 19 and 27 neutralize each other, so sz doesn’t change.

  • Why reduce sz at line 19?

Because we call addInterval many times. For example, for the first call, we have added the first range size into sz; for the second, if there is a merge, we need to subtract the first range size, which is (it->second - it->first).

Compared with 57. Insert Interval(Given a set of non-overlapping intervals(initially sorted according to their start times), insert a new interval into the intervals (merge if necessary)), the setup are the same, but this question requires to maintain a total covered length.

List insert with iterator is to insert before the iterator: http://en.cppreference.com/w/cpp/container/list/insert

这里采用的数据结构是List. 通常来说在循环里面删除container里面的元素很危险. 但是对list来说可以这么干.

循环的时候erase List item最好用while loop.

注意it=l.erase(it)其实也可以用l.erase(it++)代替. 参见: https://goo.gl/gqhnT

不用担心在continue之前没有it++,这不是bug. l.erase(it) 返回的就是删除之后的下一个iterator.

Follow up: Google Rain Drop(Coupon Collector’s Problem)

48.11 Count possible triangles + Implement Linked List

  1. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number

http://www.practice.geeksforgeeks.org/problem-page.php?pid=358

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles.

For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).

三角形三边条件: 任意两边之和大于第三边. 所以我们只需要把数组排序,如果两个小的数的和大于大的数那么这三个数就可以组成一个三角形.

https://repl.it/FYqz/1

请问上面算法的时间复杂度是多少? 如何改进?

上面的算法是\(O(N^3)\),找K的时候如果用Binary search可以改进到\(O(LogN*N^2)\).

但这还不是最优,最优的算法是\(O(N^2)\).代码如下:

如果第10行不加那个if condition,就通不过这个case: [0,0,1,1]. 当然如果输入没有重复数字,可以不加.

为什么这里三个loop复杂度却是\(O(N^2)\)呢? 参考: http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers

This definitely is \(O(n^2)\)! Please read carefully “An Introduction of Algorithms” by Thomas H. Cormen chapter about Amortized Analysis (17.2 in second edition). Finding complexity by counting nested loops is completely wrong sometimes. Here I try to explain it as simple as I could. Let’s fix i variable. Then for that i we must iterate j from i to n (it means O(n) operation) and internal while loop iterate k from i to n (it also means O(n) operation). Note: I don’t start while loop from the beginning for each j. We also need to do it for each i from 0 to n. So it gives us \(n * (O(n) + O(n)) = O(n^2)\).

这道题跟2 sum II 非常类似. 因为我们要找的是三个元素A[x],A[y],A[z]满足,
A[x]+A[y] > A[z]
A[x]+A[z] > A[y]
A[y]+A[z] > A[x]
就可以了. 那么怎么样实现呢?朴素的解放是o(n^3)的, 那么怎么样优化时间复杂度呢?我们可以先把数组排序, 然后如果默认x< y < z的话,可以推出,A[x] < A[y] < A[z] 所以上面条件里面2,3 一定成立. 那么接下来我们要做的就是对于每一个z我们要找x,y 使得A[x]+A[y]>A[z] , 其实这样我们可以枚举所有的z, 然后固定z了后, 不就是找有多少个x和y的组合,使得他们的和大于 A[z] 这就是2 sum II 的问题, 我们可以借鉴2 sum II的方式来做, 最后的时间复杂度就是O(n^2)的时间复杂度.KSum

https://www.jiuzhang.com/qa/808/ 这个分析提供了另外一个思路,就是固定最大值,然后移动较小值inwards.

这道题技巧性很强.其实还有个坑:如果说输入里面有重复数字的话,而且重复数字无区别的话,应该把重复数字用counter记录下来单独处理.比如[1,2,2,3,4],先转化成[1,2,3,4]+counter[2->2],如果重复次数等于3,这三个重复数字可以形成一个triangle,如果重复数字大于三就无所谓了.

还有个变化就是求所有的这些triangles,而不是仅仅返回个数,这个时候除了上面的方法外,也可以用DFS来解.stackframe depth is equal to 3. 同时记录cumulative sum,如果大于第三个数就cherry pick.

一个类似的例子是BUILD-MAX-HEAP(A) at CLRS P157.复杂度是\(O(N)\).但是子函数MAX-HEAPIFY(A,i)是\(O(logN)\). Why?

BUILD-MAX-HEAP(A)
  A.heap-size = A.size()
  for i from floor(A.size()/2) downto 1
    MAX-HEAPIFY(A,i)

首先这个BUILD-MAX-HEAP(A) 里面的循环是bottom up,而且是从中间floor(A.size()/2)开始; 其次MAX-HEAPIFY复杂度是\(O(h=logN)\). 所以最后的式子是对一个integrating and differentiating series(CLRS P1147)求和.得出的结果是\(O(2N)\),或者说O(N). 参见CLRS P159.

Find triangle sides in an unsorted array

  1. 给一数组,让判断是否有三个数可以组成一个三角形.三个数代表三角形三边长,三角形的定义是仍和两边长相加要大于第三边.此题类似3sum和sliding window的组合,只要考虑清楚了也是容易得到线性解.

http://www.geeksforgeeks.org/possible-form-triangle-array-values/

这道题的关键在于如果A+B>C,那么就一定可以组成一个三角形,所以我们可以将所有的数先sort,然后按顺序扫,只需要扫相邻的ABC三个数就可以,因为我们可以保证C+B>A和C+A>B

http://www.1point3acres.com/bbs/thread-156387-1-1.html
https://github.com/richzw/CodeHome/blob/master/Questions.txt#L211

6月20:
一面: 国人大哥和美国妹妹,妹妹是shadow.
第一题: search in rotated sorted array,(with or without duplicates)
第二题: Given an array of integers, find out a triple of integers such that they form a triangle. i.e. given a,b,c from the array, a+b >c, b+c >a, a+c >b, 返回任何三个就可以了.

大哥给了很积极的评价,一天后通知二面

昨天下午二面: 希腊士大夫工程师,加印度大哥
第一题:print binary tree level by level, 外加c++ vector内部怎么实现以及复杂度等细节
第二题: print factors of a given integer
example: 12 可以表示为:

12 ＊1
6 ＊2 ＊1
4 ＊3 ＊1
3 ＊2 ＊2 ＊1

要求走几个例子,写出完整的递归的stack trace
题目差不多都做出来了
http://www.mitbbs.com/article_t/JobHunting/32721825.html

5月27:
L phone interview:
1. Implement Linked list.
2. nested integer list, 求weighted sum. weight 就是嵌套的层数.
3. Find a number in rotated sorted array, leet code 原题

L onsite:
1. Senior manager 谈PhD 项目,出了个关于ads monetize 的粗浅问题.聊的很愉快.
2. Senior software engineer 谈之前工作中得项目和系统.考察communiation, 水过.
3. Design question, tiny url service.
4. Coding: text justification. 考查Implementation, leetcode 原题.不难,就是繁琐.
5. Coding: same tree, calculate product of an array without the number itself, sort

48.12 Text Justification

google-2016-11.html#text-justification-1

48.14 Implement a blocking bounded queue

Check concurrency

3月28:
电面1:印度 + 老毛
1. rotated binary search
2. 给你一个BST的pre-order traverse的结果,让你返回in-order traverse的结果.

http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

sort pre-order to get in order of BST

电面2:国人大哥 +　老毛(结果老毛没来)
1. double power(a,b)
2. binary tree level traversal,然后追加了要打印出来他所需要的格式.
比如,给你:

           3
          / \
         2   5
        /   / \
       1   4   6

打印出来的格式要是:

           3
         2   5
        1   4  6

on-site:

  1. 跟经理聊天,介绍自己的背景,behavior interview.经理看起来是个ABC,刚开始有点严肃,我也有点拘谨.到后来比较nice.

  2. 详细介绍自己所做的项目,面试官还比较nice,人也很聪明,提的问题有时候一针见血.stanford小印,全程比较严肃.

  3. Lunch interview,就是一起吃饭

  4. 题目是tiny URL那题,问的很细.

  5. Coding : Implement a blocking bounded queue

  6. Coding: 题目有点忘记了,大概好像就是:比如要安装gcc 2.1 这个程序,会有一些dependency,让你写个程序,让你返回安装一个程序所需的所有dependency.

  • topological sort/khan algorithm

48.15 Sqrt

sqrt 有两个版本,一个输入输出是integer,一个输入输出是double.

48.15.2 Sqrt(double)

  • 二分法

这道题用二分法解其实难点是: 1. 确定tail. 2.零点定理:若f(x)在(a,b)连续,且f(a)f(b)<0,则f(0)在(a, b)内有零点.

我们知道如果x大于1,sqrt(x)肯定小于x; 但是如果x小于1, sqrt(x)就大于x.

我们的tail必须大于sqrt(x),二分的时候才能找到解.So we need to solve the 不等式 equation:

\(\sqrt{x} \le x + k\)

let \(t=\sqrt{x}\), we have \(t \le t^2 +k\), then \(t^2 - t + k \ge 0\), then \((t-1/2)^2 + (k-1/4) \ge 0\).

so when \(K\ge1/4\), we have \(x+k\) greater than \(\sqrt{x}\).

因为我们选x+0.25为tail的初始值. 代码如下:

完整代码参见: https://repl.it/FZhm/1

  • 牛顿迭代法

经过(\(x_i, f(x_i)\))这个点的切线方程为\(f(x) = f(x_i) + f'(x_i)(x - x_i)\),其中\(f'(x)\)为\(f(x)\)的导数,本题中为\(2x\).令切线方程等于0,即可求出\(x_{i+1}=x_i - f(x_i) / f'(x_i)\).

继续化简, \[x_{i+1} = x_i - (x_i^2 - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2\]

为了求sqrt(n),就是求:\(f(x) = x^2 - n\)当\(f(x) = 0\)的解.

完整代码参见: https://repl.it/FZhm/1

  • 割线法

Check this animation

http://blog.csdn.net/xusiwei1236/article/details/25657611

3月18:
1: sqrt(double) with double 精度,
2: Whether one list is merged into given lists.
http://www.mitbbs.com/article_t/JobHunting/32640521.html

3月5:
Parse the IP in a file, actually, it is not difficult View Answers (2)

48.16 Flatten a multilevel linked list

Pretty much like orthogonal list.

3月:
一个双向链表,带头尾指针,每个节点可能都有父节点和子节点,每个父子节点又是一个链表.要求把它拍扁,顺序随意.

http://www.geeksforgeeks.org/flatten-a-linked-list-with-next-and-child-pointers/

这个方法是go through to the next and then go to immeidate child. 还有一个方法是先走immediate child,在往左走一步.参见: http://www.geeksforgeeks.org/flatten-a-multi-level-linked-list-set-2-depth-wise/

If there is cycle:

We can add all appended nodes into set<node*> appendedNodes. Before appending a child, check if it is already in the set. If it is, skip it and break the child link/relation.

linkedin-2017-01.html#flatten-a-multilevel-linked-list-2

48.17 Design Thread-Safe Hashmap + Celebrity

2月25: http://www.mitbbs.com/article_t/JobHunting/32634315.html

个人背景:master 三年,frontend 和 backend都做过,frontend多一些. 面的是application team, 总共onsite 5轮,2轮算法,1轮聊项目,1轮设计,1轮 manager面.算法都不是很难,感觉是跪在中间两轮,hr的反馈是说经验不够.

r1 1白男+1小印,题目是实现hashmap,写完后继续要求要考虑multi-thread.总体算还行,但是第一轮有点紧张,出了几个小错误.

r2 印度人, 三题,

1 实现sqrt,就是考察binary search.

2 给一个数组,返回一个数组其中每个数是除了之前数组这个index的数以外所有数的乘积,主要就考虑有0的情况.

3 linkedin 有两类用户,普通user和influencer,数据量都很大,写一个类,要求O(1)的type get(user), set(user, type), getAllInfluencer(). 我一开始用两个hashset,问我有没更好的办法,后来问明白他其实就是想要bitset, 写出搞定.

r3 两senior,其中一国人一印度女.就是问做过的project,但是之前做过的project 确实没有很大的user base,我做的也是偏前端的模块,聊不出太多scalable的东西. 所以我说的challenge的问题他们有些也不了解或者不感兴趣,感觉十八九悲剧在这轮.

r4 国人senior,设计一个web calendar,从interface到后台数据结构,因为没有标准答案,面完也不知道算好算坏,有些地方他认为重要的我一开始没想到,有些地方我提出了好的想法他也会做record.

r5 白人manager,基本在聊天,从大学毕业到现在的历程过了一遍,一个设计题是linkedin要launch和大学合作认证课程的feature,让我想想要怎么去做,但问着问着感觉变成了怎么向用户推广这个新feature… 然后他之前在amazon做了6年而我已经拿了amazon的offer最后十多分钟就变成了他向我吐槽amazon…

http://www.geeksforgeeks.org/the-celebrity-problem/

2月24:
LinkedIn
一面
1’ Level order tree traversal. (Leetcode)
2’ Find the distance between two words in a list. The words can repeat.

二面
1’ pow(x, n), where x is a double, n is an integer (Leetcode)
2’ Number factorization

2月11:
JAVA part:
1 interface 和 abstract class 区别

http://blog.csdn.net/b271737818/article/details/3950245

2 multithread, thread safe
3 equals 和 == 区别 : == 比较地址, equals: object, == basic

1 get 和 post 区别
2 http 和 https 区别

Algorithm:

1 NestedInteger 如 {2, 4, {6, {8}}} calculate weighted sum. weight is the depth.
http://www.mitbbs.com/article_t/JobHunting/32613585.html

2 Two sum

linkedin
http://www.mitbbs.com/article_t/JobHunting/32619609.html
电面1:
第一题:给一个words list, 输入两个单词,找出这两个单词在list中的最近距离(先写了一个没有预处理的,又写了一个预处理建index的)

['green', 'blue', 'orange', 'purple', 'green']  f.distance(list, 'blue', 'green') # output 1

第二题:类似binary search的一题,要注意boundary case

电面2:
binary tree level order traversal, 写了三种方法…(BFS用arraylist,类似DFS,BFS用queue)

48.18 149. Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line/

若干注意事项:
1. 垂直曲线, 即斜率无穷大(INFINITY is a valid float).
2. 重复节点.

如果把上面的unordered_map改成map, [[0,0],[1,1],[1,-1]] will make it fail.

这是我知道的map和unordered_map的唯一除了效率在使用上的不同哦.

map不可以处理INFINITY和NAN,因为map是用比较来的red-black tree.
unordered_map可以正确的处理INFINITY,它使用hash,INFINITY和NAN的hash值是不同的.

如果想把上面的unordered_map改成map,可以把NAN和INFINITY改成INT_MIN, INT_MAX.

其实上面的解法还是有问题的,最靠谱的解法在这里: google-2015.html#max-points-on-a-line

http://www.mitbbs.com/article_t/JobHunting/32633911.html

2月24:
1. given the list {{1,1},2,{1,1}},返回10……因为,(four 1’s at depth 2, one 2 at depth 1). 给定 {1,{4,{6}}} ,返回27……因为, (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3)
2. leetcode: traversal binary tree level by level
3. 给2个string,判断是否可以map. say (foo, abb) 这2个string是可以map的, f->a, o->b. say (foo, sdf),是不可以map的……返回bool值
4. 给一个string,每10个letter一组,输出所有出现次数超过一次的strings with length of 10. 一定要用rolling hashing做
5. 给一个数组,输出连续元素的最大和.
6. 判断2个linkedlist是否在某一点会重合. O(1) space.
7. leetcode: Max Points on a Line
8. string reverse. 输入 “Hello, word”, 输出 “word Hello,”.
9. 给一个数组,输出连续元素的最大乘积.
10. leetcode: permutations
11. 给一个数组,a(10, 2, 5)……输出一个数组, b(10, 50, 20)……b[i]是除了a[i]以外剩下a中所有元素的乘积……不准用除法.

L家是有题库的,把版上的面经都看一遍就差不多了……design是设计amazon product page的后端

http://www.mitbbs.com/article_t/JobHunting/32580833.html

2月24:
Write a method implementing a given interface to merge two streams of numbers. Answer Question

2月18:
a) Find the nearest K point given a set of N point.
b) Print a tree level-by level.
c) Given a dictionary find and set of two words find path from one word to another such that all the intermediate words are also from dictionary.
Example: GOD -> GID -> DID -> DIG -> DOG.
At each time we are allowed only one character change.
d) Design an Hangman. { They expect MVC architecture. }

2月16:
2) Return true if there are any users who are not following any other user but been followed by every other user. View Answer

Find celebrity

2月15:
http://www.mitbbs.com/article_t/JobHunting/32626981.html

  1. 阿三经理 80年代IIT毕业,口音没问题
  1. 问项目经验
  2. 分布式相关问题,没深入细节,包括2pc, paxos, zookeeper的实现等
  1. 波兰小伙
    有点害羞,但人非常好.
  1. message{msgId,byte}.大量message持续的input,要支持Message getAll(msgId),问怎么存储message.

48.19 Distributed Inverted Index Design

  1. 阿根廷帅哥 专做搜索的,长的好像诺维斯基…
    问题:如何设计分布式倒排索引,如何进行query.

https://www.coursera.org/learn/text-retrieval/lecture/PgzsP/lesson-2-5-system-implementation-inverted-index-construction

48.20 isThirdDegree

  1. 阿三 小印,口音重,发了篇SIGMOD,不过第一作者是国人:)
  1. 假设有函数int getConnection(memberID),结果是有序的,要求实现:
isFirstDegree(member1,member2)
isSecondDegree(member1,member2)
isThirdDegree(member1,member2)

就是判断一度,二度,三度好友关系,是系统设计题,伪代码即可.
follow up:分布式下怎么做

  • Algo
  1. STL find; 2. Two pointers; 3. BFS + swap + set
  1. tinyurl
    follow up:问如何scala-out
  1. 埃塞俄比亚小伙 悲剧的一轮,小伙人很好,但英语比阿三还难懂,有史以表现最差的一次.

  1. 给一个矩阵,followMatrix[i][j]==true,表示j影响了i.求influencer,即影响所有人,且不被任何人影响

  2. 三角形问题,输入一些线段的长度,找出能形成三角形的三条线段

  1. 老美 表现最好的一轮,有相似的项目经验,聊的比较投机
  1. max points on a line
  2. 给int a,求int result. 其中result[i]=a1*a2...*ai-1*ai+1*...an, follow up:不能用除法

6轮下来,5表现非常不好,2也不太理想(都没有进入follow up分布式的情况),所以基本是跪了.

2月11:
两星期前onsite, 面了一个 Web-based hangman design 跪在这上了 其他都是老题比如 integer to roman, roman to integer, 他们家貌似喜欢考这种messy的编程题

http://www.mitbbs.com/article_t/JobHunting/32613585.html

48.22 12. Integer to Roman

https://leetcode.com/problems/integer-to-roman/

这题需要一些背景知识,首先要知道罗马数字是怎么表示的:

http://en.wikipedia.org/wiki/Roman_numerals

I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000

字母可以重复,但不超过三次,当需要超过三次时,用与下一位的组合表示:

I: 1, II: 2, III: 3, IV: 4; C: 100, CC: 200, CCC: 300, CD: 400

Algo Example:

s = 3978
3978/1000 = 3: MMM
978>(1000-100), 978/900 = 1: CM
78<(100-10), 78/50 = 1 :L
28<(50-10), 28/10 = XX
8<(10-1), 8/5 = 1: V
3<(5-1), 3/1 = 3: III

So ret = MMMCMLXXVIII

所以可以将单个罗马字符扩展成组合形式,来避免需要额外处理类似IX这种特殊情况.

I: 1, IV: 4, V: 5, IX: 9, X: 10, XL: 40, L: 50, XC: 90, C: 100, CD: 400, D: 500, CM: 900, M: 1000

Code:

今天看到一个更简单粗暴的方法,对这种题目就记住这个就行了:

https://discuss.leetcode.com/topic/8057/two-lines-can-do-the-job

48.23 Edit Distance (Levenshtein distance)

https://leetcode.com/problems/edit-distance/

onsite: 1. romanToInt, intToRoman,
N points, m nearst ones
2. 双向链表,每个node可能都有父节点和子节点,每个父子节点又是一个链表.把它拍扁,顺序随意,O(1)空间复杂度
edit distance
3. system deisign: design amazon product page
4. project presentation
5. group fit

2月8:
PS1:
senior staff engineer,老美,70年代大学毕业.
1. 聊简历和技术背景
2. 子数组最大和,我说见过,说了O(n)的方案,没coding
3. Search in rotated sorted array.开始没考虑重复元素,后来修正了.但面试官似乎不知道重复元素的影响,举了几个例子验证后,说OK.最后,我问了一些linkedin infra的问题,解答很详细,并推荐了rest.li,后来和同事研究了下,在服务发现这块设计的很赞

PS2:
国人主面,老外shadow
1. 聊项目经验,问的很仔细,英文水平有限,又没法画图,解释的不太好
2. Java和OS相关概念
3. coding,序列化和反序列二叉树.用了leetcode的表示法.春节期间没练习,手生,结果有逻辑bug,当时感觉完全没信心了,提问阶段只问了一个就不想说了.

Refer to: binary-search-1.html#search-in-rotated-sorted-array

2月2日:
Final round was kind of unexcited, was asked to write out all the combination of factors of one number. another was about implementing hash table. Answer Question

48.24 Write-through and Write-back Cache + MM File

1月:
http://www.mitbbs.com/article_t/JobHunting/32607193.html
L:
问答题
Write-through cache vs write-back cache
what’s memory mapped file

算法题,都是老题
1) 给一个nested的int array, 返回sum of int weight by its depth
2) 写一个支持removeRandom的hashtable
3) 一串字符串,返回有多少个substring符合某些pattern,这些pattern都是10char的长度,所以逐个比较就可以了
4) tree lowest ancestor( tree node have parent pointer)

2013年12月:
Given a sorted array with duplicates and a number, find the range in the form of (startIndex, endIndex) of that number. For example:

find_range({0 2 3 3 3 10 10}, 3) should return (2,4).
find_range({0 2 3 3 3 10 10}, 6) should return (-1,-1).

The array and the number of duplicates can be large.

2013年12月:

已从L onsite面的有设计挺经典的O(1) insert/remove/random pick数据结构, distributed topk exception, 扯amazon.com如何设计, 版上似乎都有原题 代码不一定是bug free 我觉得挺看思路也就是overall approach的 http://www.mitbbs.com/article_t/JobHunting/32595845.html

2013年12月:
第1题:Leetcode原题:由一个binary tree的inorder及preorder traversal结果,重构原binary tree.
第2题:Leetcode原题:一个已排序的数组中查找某给定element重复的个数.
Search for range的变形

Round 2:tech电面2.国人大哥.
第1题:level sum,算是deep iterator的变种.一个多重nested array,例如{a,{b,c},{{d},e}},返回level sum = a + 2 * (b + c) + 3 * d + 2 * e.
第2题:First Common Ancestor with parent pointer.What if the parent pointer is not available?

2013年8月:
Consider an X x Y array of 1’s and 0s. The X axis represents “influences” meaning that X influences Y. So, for example, if array[3,7] is 1 that means that 3 influences 7.

An “influencer” is someone who influences every other person, but is not influenced by any other member.

Given such an array, write a function to determine whether or not an “influencer” exists in the array. View Answers (7)

题目:
1.Resume
2.LCA(with parent pointer)
3.Lower and upper bound of target number index in a sorted array

2013年4月20:
http://www.mitbbs.com/article_t/JobHunting/32411325.html
LinkedIn:2轮电面,5轮onsite见9个人.2天后offer.每一个遇到的人都很nice,onsite的时候会给准备零食放在会议室,会打印出InMap,手写卡片等,非常sweet收拢人心.

电面1-2 请搜索版内面经,基本重复.
onsite 1: behavior questions with their director, 最后讲了讲如果设计一个系统(和我master研究相关)可能会存在的问题.
onsite 2:介绍我现在的工作,考察technical communication skills
onsite 3: justify text, leetcode上原题
onsite 4:minimize the cost of painting K houses, each house has different costs to paint in different colors, 2 houses (next to each other) cannot be painted in the same color. DP 问题很简单,忽略.
onsite 5:设计题,涉及到分布式系统,缓存算法,缓存更新,读取速度优化

2013年6月:
code a text justification routine (Given a line length insert white space so text is uniformly displayed within the given length).

48.25 Memory Copy + BST Insert and Delete + Making Water

48.25.1 Memory Copy

先看下标准memcpy()的解释:

注意下面的注释,对于地址重叠的情况,该函数的行为是未定义的.另外,标准库也提供了地址重叠时的内存拷贝函数:memmove(),那么为什么还要考虑重写memcpy()函数呢? 因为memmove()函数的实现效率问题,该函数把源字符串拷贝到临时buf里,然后再从临时buf里写到目的地址,增加了一次不必要的开销.

解决方案是从后向前拷贝:

http://www.codingtree.com/c/c-string-library-copying-functions.html

48.25.2 BST Deletion

根据教科书,删除的时候三种情况:

没有子节点
有一个子节点
有两个子节点

两种方法Recursive和Iterative

Recursive比较简单. 递归的解法,首先判断根节点是否为空.由于BST的左<根<右的性质,使得我们可以快速定位到要删除的节点,我们对于当前节点值不等于key的情况,根据大小关系对其左右子节点分别调用递归函数.若当前节点就是要删除的节点,我们首先判断是否有一个子节点不存在,那么我们就将root指向另一个节点,如果左右子节点都不存在,那么root就赋值为空了,也正确.

难点就在于处理左右子节点都存在的情况, 有两种方法可行.

  1. 在右子树找到最小值,即右子树中最左下方的节点,然后将该最小值赋值给root,然后再在右子树中调用递归函数来删除这个值最小的节点,参见代码如下:

注意删除完点之后返回新树的root.

  1. 找左子树中的最大值代替root,然后在左子树中删除该最大值.

相应的代码是:

Iterative需要track父节点.就是按照教科书上的方法来做.

48.26 Making Water

2013年2月20日:
电面:
给一个二叉树,返回它的镜像
实现一个 thread-safe blocking queue
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element. 就是类似树遍历一样的方法

Onsite:
第一个: 给两个单词, 比如head, tail: 找到一个最短的转换,从head到tail,每次只能变一个字母,path上的word都必须是有效的英文单词,我用的Graph shortest path

48.27 Word Ladder 1.5

Return one path (Bi-BFS+DFS)

第二个: memcpy: 源区域和目标区域可能有重叠

BST 插入和删除操作实现
BST iterator 实现

3: 实现两个函数: H() and O(), 这两个函数会被多线程调用.当一个线程调用H或O时,如果当前已经有至少两个线程call H和一个线程call O.那么让两个call H和一个call O的线程返回(产生一个水分子),其他的都block.

https://see.stanford.edu/materials/icsppcs107/23-Concurrency-Examples.pdf

Search making water

4: Given a social graph, find if there is a path between two persons with at most 2 steps (3rd level connection), how to handle it in distributed way (large graph stored at a large number of nodes, minimize cross-communication)

48.28 3rd Degree Friends and Distributed Graph

Bi-BFS, Kernighan–Lin Algorithm

Even a simplified version with two partitions (the “minimum bisection problem”) can be proven to be NP-hard.

https://code.facebook.com/posts/274771932683700/large-scale-graph-partitioning-with-apache-giraph/

Vertex-centric systems
> The representative vertex-centric systems include Pregel, Giraph (an open source implementation of Pregel) and GraphLab.

https://minjianblog.wordpress.com/2015/10/08/vertex-centric-and-neighbourhood-centric-systems/

Precisely here: https://www.youtube.com/watch?v=JF-ttZyNa84&feature=youtu.be&t=14m54s

https://arxiv.org/pdf/1601.00289.pdf

5: 设计题: a restful server with 4GB

given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.

multiple clients calling simutaneous
what data structure, concurrency, locking, etc..

参见讨论: http://www.mitbbs.com/article_t/JobHunting/32331973.html

2012年:
Phone Interview
都是老题.先问LinkedIn最喜欢的:double pow(double a, int b)

我的Algorithm Project里有这个题,当时很想直接贴答案.后来忍住了.这是个中等难度的题,里面很多细节,如果贴的话,他一问,我没有过脑子,有可能被问住,那个印象就太差了.如果自己解的,哪怕有错,思考过之后,我很快会有相应的回答.不管多简单的题,我都会错,但我会补得很快.

想清楚,开始写.尽管很小心,最后还是在边界条件错了,就是第一句:
if (b < 0) return pow(a, -b);
我少写了1.0/pow(a, -b);

但我不后悔,如果他因为这个把我毙了,那我也只能认倒霉.

接着给Amazon的favorite, 2-sum to fixed number, 我不喜欢写这个题.就直接告诉他:两种答案,hashtable, 2个指针,我都写过,你要哪种?他挺理解,说,既然你写过,给我讲一下性能差别,然后就放过了.

接着第三题,算逆波兰表达式.又是一个细节题,我知道会写错.小心翼翼地写,一边写一边解释,最后还是有小错.

48.29 Place Flowers

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

https://leetcode.com/problems/can-place-flowers

http://www.1point3acres.com/bbs/thread-129336-1-1.html

第一轮电面:
1.function replace(string orig, string find, string repl)
- replaces every instances of string find with string repl
- returned the modified string
2. double pow(double,int)
第二轮电面:
1. Maximum Depth of Binary Tree
2./**
* Given a nested listof integers, returns the sum of all integers in the list weighted by theirdepth
* For example, giventhe list {{1,1},2,{1,1}} the function should return 10 (four 1’s at depth 2,one 2 at depth 1)
* Given the list{1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2,and one 6 at depth 3)
/
int depthSum (const list &input){
//Implementationhere
}
/** This is theinterface that allows for creating nested lists. You should not implement it,or speculate about its implementation*/
class NestedInteger{
public:
// Returns true ifthis NestedInteger holds a single integer, rather than a nested list
virtual boolisInteger() const = 0;
// Returns thesingle integer that this NestedInteger holds, if it holds a single integer
virtual intgetInteger() const = 0;
// Returns thenested list that this NestedInteger holds, if it holds a nested list
virtual constlist &getList() const = 0;
}
第三轮电面:
// Suppose you have a long flowerbed in which some of the plots are planted and some are not.
// However, flowers cannot be planted in adjacent plots -they would compete for water and both would die.
// Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers
// can be planted in it without violating the no-adjacent-flowers rule.
// 0 0 0 0 0 0
// canPlaceFlowers(1) == true; canPlaceFlowers(2) == true; canPlaceFlowers(3)== true
// canPlaceFlowers(4)
// 1 0 1 1 1 0
// canPlaceFlowers(1) == false;
// 1 0 0 0 1
// canPlaceFlowers(1) == true; canPlaceFlowers(2) == false;

Followup: what if no random access to the list is permitted

http://www.1point3acres.com/bbs/thread-112464-1-1.html

Greedy approach: check from the first possible plot to the last, store the current and next plots each time you iterate on a plot, which will separately become the previous and current plots when you iterate on the next plot.
T: \(O(N)\)

如果输入是vector,可以比较方便的求解.

如果允许更改原vector,可以这样:

否则,如图所示, status:-1 表示在两头的情况, status:0表示中间的情况.注意edge case没有1的情况[0,0,0]=> can place 2 flowers.

如果输入是forward_list,那么就比较麻烦了,用i做loop,然后p表示previous node的情况,pp 表示previous previous.
0 : empty plot; 1 : plot with flower; -1 : 初始状态,不是plot