我的一面
烙印+国人，烙印主面
上来自我介绍，然后问操作系统的一些概念，page,physical page,virtual page, page faullt, 为什么要有virtual page
2题
1.sorted char array, char key
找strictly大于key的元素，如果没有return array[0]
binary search，然后又一堆test cases要一个一个验证给他看
follow up， 如果这个数组很大，那这一行要怎么改 “int mid=(start+end)/2;”
我开始问是不是不能load到memory，他说可以load，然后问我java max integer是多少，我说大概2^31-1,他说那这个数组的size是3／4个Integer.MAX_VALUE. 然后我就知道是考overflow， 改成
if even mid=start+len/2-1;
if odd mid=start+len/2;
2.nestedinteger, 我第一遍居然忘了乘depth也是蠢。。。
然后随便问了问题

---

网上搜到的

汇总整理 1.public int distance (List words, String wordOne, String wordTwo).
2.输入是一个array stream，在任何时候call你的method，给一个input value，让返回之前输入过的数字有没有两个加起来等于这个value的（2sum稍稍变形）。follow up: store 多的时候怎么设计，test多得时候怎么设计
3.pow(x,n), check boundaries, O(log(n))
4.rotated binary search (leetcode)
5.hashcode() of a String in Java
6.Kth closest point to point P on a plane with N points (heap, comparator).
7.ArrayList impl without importing ArrayList。
8.IsSameTree (leetcode)
9.Word Ladder II (leetcode)
10.Text Justification (leetcode)
11.permutation II ，Permutation Sequence
12.Insert interval 变种给你一个接口两个函数
insert(int from, int to)
int getLen() 给出所有interval cover 的length
13. 给一个array A, return一个新的array B，B[i]是A中所有元素乘积但不包括A[i]
14.valid number
15. word distance, what if this method is called frequently
16. square root
17. print a binary tree node in level order
18. find a balance point in an array, array不是sorted的，里面可能有负数. balance是左边的和等于右边
19. boolean canIWin(int maxNum, int target)，从1,2…maxNum的数组里两个玩家轮流选数，第一个达到sum>=target的玩家获胜，问如何判断先选的玩家能获胜。
20. Implement a (Java) Iterable object that iterates lines one by one from a text file.
public class TextFile implements Iterable
{
public TextFile(String fileName) {
/* Begin reading the file, line by line. The returned Iterator.next() will return a line. /
@Override
public Iterator iterator() { 实现这个
21.max sum subarray, 连续的。 max product subarray，连续的
22.实现一个可跳过元素的Iterator, 比如输入是1 2 3 4 5 6 7 8 hopValue = 2，输出: 2 4 6 8
构造函数是这样的，需要实现hasNext 和next 方法
public void HopIterator(Iterator itr, int hopValue)
23.内容排序好的iterator的几个操作，union, intersect
Iterable XXX(Iterator a, Iterator b)
24.Iterable mergeKSortedIterators(Iterators[] iters)
25.设计一个类实现下面的接口.
interface List{
public void add(T o);//add to the last
public T get(int index); //get the index object
public int size();//return the size
public boolean remove(T o);//remove the first o and return true; if not exist, return false.
} 26.设计hashtable，考虑线程安全，数据增加的时候怎么办
27.implement Arrays.sort(Object[] a);
28.最小的k个数：max heap,快排的partition
29.common ancestor
30.reverse polish notation
31.merge intervals
32.L家最爱考的面试题之一就是nested integer了，还爱考各种iterator的implementation，这题是把两个最爱合在一起了。。。。感觉很有可能出，但网上没找到满意的答案.
题目是这样的
eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6
这个data structure的interface是这样的 public interface Data { // Does this Data hold a collection? public boolean isCollection(); // Returns the collection contained by this Data, or null if it is a single element public Collection> getCollection(); // Returns the single element contained by this Data, or null if it is a collection public T getElement(); }

1. public interface PointsOnAPlane { /* Stores a given point in an internal data structure / void addPoint(Point point); /* * For given ‘center’ point returns a subset of ‘m’ stored points that are * closer to the center than others. * * E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) * * findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3) */ Collection findNearest(Point center, int m);}
   heap+comparator
2. public interface InfluencerFinder {
   /**
   
   • Given a matrix of following between N LinkedIn users (with ids from 0 to N-1)
   • followingMatrix[i][j] == true iff user i is following user j
   • thus followingMatrix[i][j] doesn’t imply followingMatrix[j][i].
   • Let’s also agree that followingMatrix[i][i] == false
     *
   • Influencer is a user who is:
   • – followed by everyone else and
   • – not following anyone himself
     *
   • This method should find an Influencer by a given matrix of following,
   • or return -1 if there is no Influencer in this group.
     */
     int getInfluencer(boolean[][] followingMatrix)
3. bounded queue(consumer， producer )
   还问了一些基本概念，virtual memeory, thread, process 区别等。
4. merge two sorted inked list(从大到小)
5. 一个文件，有很多行string, 从里面提取所以valid的Ip address. (我当时用C++写的，有点麻烦，面试官最后给我看了，python代码，就两行，哎！)
6. 给一个二叉树，返回它的镜像
7. 实现一个 thread-safe blocking queue
8. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
   嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
   似树遍历一样的方法

design
11.how to get top 10 Exceptions for the past 24 hours in 400 machines and update every 5 minutes. General idea: Kafka + Storm. Uses sliding window, hashTable, heap. (这道题pinterest也问了） behavior
12.Tell me in depth about the project you’re most proud of (45 mins).
13.How would you improve LinkedIn Influencer to enter international market. Round 1
System design
问有很多host上面都跑着不同或者相同的service, 如果这些service有抛出exception都会被写到log里。请设计一个service能够返回过去24小时以内出现频率最高的K个exception。
solution
service所在机器维持一个24h的window(queue or linkedlist)和max heap，hashmap(exception, count)，收集exception的机器上维持5min的window。没5min新的exception发到service得机器，更新window, hashmap, heap Round 2
Coding.
DNA问题 leetcode187
加了点小变形，问的是repeated长度为10的substring，然后以大小输出所有它们 Round 3
午饭，瞎扯 Round 4
Tech communication
基本就是描述自己之前的做的一个project
interviewer会问他们感兴趣的问题
这里分享个小trick，一般都会问“如果让你重新做，你会怎么改进”。对于这类问题，只要你在一开始描述的时候故意说点可以被优化的东西，然后后面被问起的时候再补充就好了。这样就不用真的去想到底要怎么改进了。 Round 5
Coding
longest palindromic subsequence
实现一个class提供以下操作：
1. addInterval(int start, int end) - 加入一段interval
2. getTotalCoverage() - 返回总共能够cover的时间.
非常类似leetcode57，不同就在于要自己排序
这题因为时间关系没来得完全写完，但是给interviewer解释了思路 Round 6
Hosting manager
上来也是问了之前做的project.
接着问了一个design的问题，问如何设计一个linkedin profile page能够支持rich media，诸如视频，图片，音频等等 Linkedin：.
1. Word distance.
2. 2 sum
3.
/**
* Given a nested list of integers, returns the sum of all integers in the list weighted by their depth
* For example, given the 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)
*/
4. permutation
5. reverse word in string (in place)
6. system design 类似这个
http://www.shuatiblog.com/blog/2 … ta-real-time-top-k/.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
7. 问project。把我问跪了。他们问的非常非常详细。我只准备了architecture，明显不够用。一些具体logic也得准备。.1point3acres缃�
8. minimum window substring
9. sqrt int + double版.

---

1.
第一题：
public boolean canPlaceFlowers(List flowerbed, int numberToPlace).
如果flowerbed当中为true，说明已经栽过花了，附近两个不能再栽花。numberToPlace代表想再栽多少花到flowerbed里。让return是不是还能栽那么多谢花进去。
第二题：
public int distance (List words, String wordOne, String wordTwo).
给一个string list，可能存在重复，给两个word，让return这两个word在list中的最短距离： 可以用bfs
第三题：
输入是一个array stream，在任何时候call你的method，给一个input value，让返回之前输入过的数字有没有两个加起来等于这个value的（2sum稍稍变形）： hashmap 2.LinkedIn题目
电话
1. pow(x,n), check boundaries, O(log(n))
2. rotated binary search (leetcode)
3. hashcode() of a String in Java
solution s[0]*31^(n-1)+s[1]*31^(n-2)+…+s[n-1]
选31是因为是prime所以知道31*n可以很容易算出n，而且容易算 (i<<5)-1, 而且bitmap不能太短以免collision太多
4. Kth closest point to point P on a plane with N points (heap, comparator).
5. ArrayList impl without importing ArrayList。 扩容，copy 原数组到新的2倍大的数组
Onsite
1. IsSameTree (leetcode)
2. Word Ladder II (leetcode)
3. Text Justification (leetcode)
4. how to get top 10 Exceptions for the past 24 hours in 400 machines and update every 5 minutes. General idea: Kafka + Storm. Uses sliding window, hashTable, heap. (这道题pinterest也问了）
5. Tell me in depth about the project you’re most proud of (45 mins).
6. How would you improve LinkedIn Influencer to enter international market. 这道题正中下怀，我口若悬河谈天说地，从GFW到Akamai到蓝汛ChinaCache，从比尔盖茨到李开复，从11年的茉莉花事件LinkedIn主站被墙到如何有效censorship，从网页设计一致性到本土化，和面试官一拍即合，看他当时满面红光我就知道自己有戏啦，果然隔了一天就收到Offer。 3.linkedin经典题
3道题全是nestedinteger
1. 计算sum = sum(value * level). private int getSum(List input, int level) { int sum = 0; for(int i = 0 ; i < input.size(); i++) { if(input.get(i).isInteger()) sum += level * input.get(i).getInteger(); else sum += getSum(input.get(i).getList(), level + 1); } return sum; } public int depthSum (List input) { //Implement this function return getSum(input, 1); } /** * This is the interface that allows for creating nested lists. You should not implement it, or speculate about its implementation */ public interface NestedInteger { // Returns true if this NestedInteger holds a single integer, rather than a nested list public boolean isInteger(); // Returns the single integer that this NestedInteger holds, if it holds a single integer // Returns null if this NestedInteger holds a nested list public Integer getInteger(); // Returns the nested list that this NestedInteger holds, if it holds a nested list // Returns null if this NestedInteger holds a single integer public List getList(); }

1. reverse sum. 第一题的第一层level是1，此题第一题的level是最大level，然后每层递减。
2. level 遍历输出。。。跟二叉树的levelOrderOutput一样。

4.一面：word distance (what if this method will be called frequently)，如果word重复出现可以hash预处理?
二面：square root (given an integer, decide whether it has an integer square root), binary search (sorted array has been rotated) 5.两个人面试的一个中国人一个烙印.
先介绍下他们的背景让你介绍下自己，然后两道题目
permutation II 你要问考官有没有重复元素。去重的代码跟考官讨论了下。
Insert interval 变种给你一个接口两个函数
insert(int from, int to) . more info on 1point3acres.com
int getLen() 给出所有interval cover 的length
ex Insert(1, 2), insert(1, 3)
getLen() 3 - 1 = 2 6. /* Implement a method which takes an integer array and returns an integer array (of equal size) in * which each element is the product of every number in the input array with the exception of the. From 1point 3acres bbs * number at that index. * * Example: * [3, 1, 4, 2] => [8, 24, 6, 12]. */ public int[] selfExcludingProduct(int[] input) { // implementation... } . 1point3acres.com/bbs 第二题 lc validnumber solution 和lc 2次交易得stock思路一样. 从左到右，d1[i]=0到i－1的乘积。从右到左，d2[i]=n到i+1的乘积。
不能用除法，因为1总乘积会溢出，2有0的情况无法处理 7.
1， print a binary tree node in level order, 是leetcode原题，大家可以自己去搜一下
2， find a balance point in an array, array不是sorted的，里面可能有负数。
解法也是从两边往中间搞，用两个数组left和right存原数组从左向右和从右向左的元素和。然后按index来比较left和right两个数组里的元素，有相等的就是balance point.
第二轮电面：.
1，给一个array，生产一个新的array，新array中的每个元素都是上一个array中除了这个位置之外其他的元素的乘积。
原题链接：http://www.geeksforgeeks.org/a-product-array-puzzle/
这个题从原始array的两边往中间搞，把乘的结果存起来，然后新的array利用左右的结果相乘得出，时间复杂度O(n).
2, Find the shortest distance between two words in a string, 好像也是leetcode原题，记不清了
input: {“you”, “he”, “she”,”her”, “you”}， “you”, “her”.
outpu:t you和her的最短距离是1.
这题为了节省空间复杂度，可以用两个flag, 一个用来指示之前发现的有用元素是input的中指定的哪个，另一个用来存之前发现元素的index。
时间复杂度O(n), 空间复杂度：O(1) 8.pow,
construct a string using another string ( String A 和B, 能否用A的字符拼出B)
permutation
面的感觉不错，因为题很简单，而且面之前我还正好复习了一边permutation的解法。。但是同样因为太简单了，感觉不确定性很大。 9.
boolean canIWin(int maxNum, int target)，从1,2…maxNum的数组里两个玩家轮流选数，第一个达到sum>=target的玩家获胜，问如何判断先选的玩家能获胜。 10.
1.Implement a (Java) Iterable object that iterates lines one by one from a text file.-google 1point3acres
* A reference to a file. /
public class TextFile implements Iterable
{
public TextFile(String fileName) { // please implement this.
/* Begin reading the file, line by line. The returned Iterator.next() will return a line. /
@Override
public Iterator iterator() { // please implement this
solution
br=new BufferedReader(new FileReader(file))
line=br.readLine() 存到arraylist, 直到line=null
然后在arraylsit上写iterator
follow up是文件特别大无法全部load进内存。
方法是一次读一部分，如果iterator到了arraylist的末尾，把另一部分覆盖进来： 文件offset的实现依靠RandomAccessFile 类。
RandomAccessFile rf=new …
rf.seek( rf.getFilePointer() )//设定当前指针为下一次read开始的位置
rf.readline()
2.Print binary tree by level 11.
全LC
valid number
max sum subarray, 连续的
max product subarray，连续的
word distance 12.
实现一个可跳过元素的Iterator, 比如输入是1 2 3 4 5 6 7 8 hopValue = 2，输出: 2 4 6 8
构造函数是这样的，需要实现hasNext 和next 方法
public void HopIterator(Iterator itr, int hopValue) 13.
1. Valid Number
2. Print tree in level ordering, follow up: zigzag.
3. Text Justification
1. 内容排序好的iterator的几个操作，union, intersect
Iterable XXX(Iterator a, Iterator b)
2. Iterable mergeKSortedIterators(Iterators[] iters)
问了面试官一些他们组的开源项目。 14.
设计一个类实现下面的接口.
interface List{
public void add(T o);//add to the last
public T get(int index); //get the index object
public int size();//return the size
public boolean remove(T o);//remove the first o and return true; if not exist, return false.
}
Permutation Sequence, 印象中是差不多的题，非常简单。 15.
2sum.
follow up: store 多的时候怎么设计，test多得时候怎么设计
solution
store(int newInt)使用多： 可以考虑开个list来cash下最近的new ints，超过一定的time threshold或者size threshold才往hashtable里flush。这样减少对hashtable的写操作，否则过多lock性能不佳，也可能block test操作。 test(int targetInt）使用多：考虑对hashtable做多个copy，也就是search system常用的replica设计，让test操作assign到10个、100个hashtable instances上去跑，每个再对应一个thread。 16.第一题
设计hashtable，考虑线程安全，数据增加的时候怎么办，不用写代码只要说就行了
大概用了十分钟
**solution**array of linkedlist, 给hashtable上lock，granularity是linkedlist而非整表。如果数据量增加导致collision过多，需要rehash
concurrenthashmap的实现是加了一层hash，叫segment。element->segment->hashentry. 而且rehash可以再segment级别上而非整表
第二题
implement Arrays.sort(Object[] a);
//1. Mutate input or return your own array
//2. I value run time over memory usage. Ideally both should be as minimal
as possible, but I prefer faster runtime.
//3. You can assume that all the objects in the array ‘a’ all implement the
comparable interface. 17.
binary tree按行打印
最小的k个数：max heap 18
common ancestor
max points on a line 19
reverse polish notation
sqrt
word distance finder 20.
1) lowest common ancestor; merge intervals
2) find the smallest character that is strictly larger than the search
character; minimal distance between two words 21.
L家最爱考的面试题之一就是nested integer了，
还爱考各种iterator的implementation
这题是把两个最爱合在一起了。。。。感觉很有可能出，但网上没找到满意的答案. 题目是这样的
eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6 这个data structure的interface是这样的
public interface Data {
// Does this Data hold a collection?
public boolean isCollection();
// Returns the collection contained by this Data, or null if it is a
single element
public Collection public class H2O { static final Lock LOCK = new ReentrantLock(); static final Condition ENOUGH_H = LOCK.newCondition(); static final Condition ENOUGH_O = LOCK.newCondition(); static int H = 0; static int O = 0; static void check() { if (H >= 2 && O >= 1) { ENOUGH_H.signal(); ENOUGH_H.signal(); ENOUGH_O.signal(); H -= 2; O -= 1; } } public static void h() { LOCK.lock(); try { check(); ++H; ENOUGH_H.awaitUninterruptibly(); } finally { LOCK.unlock(); } } public static void o() { LOCK.lock(); try { check(); ++O; ENOUGH_O.awaitUninterruptibly(); } finally { LOCK.unlock(); } } }` 2.
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) 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.. 1.设计题：Design: monitor systesm. 1.k-way sort given a stream iterator, vector,
2.product of other elements
3.把一个数，比如24，写成factor的乘积组合， 2*12， 2*2*3… 1.找n所有factor
1) While n is divisible by 2, print 2 and divide n by 2.
2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.
3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.