Massive Algorithms: Linkedin Interview Misc

http://www.1point3acres.com/bbs/thread-147555-1-1.html
楼主是上周面试的，面试的组是infrastructure，所以考了两轮系统设计，两轮coding，以及最后一轮host manager interview。面试时间是11:30-17:30，中间吃饭一个小时。直接上题吧。
第一轮：系统设计
已知一个函数，输入用户ID，可以返回该用户的所有友好（degree 1 friends），按好友ID从小到大排序。
要求实现函数来输出返回一个用户的所有好友的好友(degree 2 friends), 以及 degree 3 friends。
这里感觉主要是聊天看思路，中间会临时加一些限制条件，来进行时间或者空间的优化。
第二轮： coding
1.implement a class to finish data operation methods: add， delete， random delete
2. repeated DNA sequence (leetcode)
LeetCode 187 - Repeated DNA Sequences Leetcode
是要求按大小顺序输出来着，alphabetical order。我直接用的是int array，没有被要求用bit vector来优化了~
hash函数把结果变成整数，范围是0到4^10 - 1，然后直接用一个这么大的数组来记录结果。之后遍历数组，把找到的结果reverse hash回去~
一共有三种状态吧：0次出现，1次出现，至少两次出现。然后用两个bit来表示这三种状态咯。bit的读取和改变就用and， or之类的bitwise operator来做吧
3. binary tree upside down (leetcode)

第三轮：系统设计
对于key，value pairs，在给定的文件系统中实现 put，get，delete 的方法。其中key比较小，全部key可以放在内存中，value有的会比较大
已知一个文件系统，可以
create files, delete files, sequentially scan file content, read file content randomly, append file content

1. in the main memory, maintain a hashmap, key is each input key appeared, value is the file ptr and line ptr(key-value pair location in the file system)
2. each time when we need to update the value, write a new key value pair at the end of the file, and also update the related key value pairs in the main memory. Then when main memory cracks, we can reconstruct the main memory hashmap from the files content
3. make file modification to save space: scan the file sequentially for each key to find the latest update, then put the latest key-value pairs into another file. After we finished doing this for all the keys in a file, delete that file
4. deal with synchronization: when we do the file modification, put all the newest updates into another file, then replay it
5. each file should have an limited amount of different keys, so that file modification is not that hard

这个也主要是聊天，面试官会不断提到一些他好奇的地方，感觉基本都是暗示吧，有些细节不太记得了，最后面试官也没给评价。。

第四轮：coding
1. 求平方根
2. 双向链表，但是每一个点还可以有up，down pointer，已知一个链表里没有环，要求把这个链表变成标准双向链表，每个点的具体位置排列无所谓。楼主开始反应是递归，写好后面试官说优化一下，，空间要求是constant space，然后尽管面试官一直在提示tail recursion，还是没想出来（据说地里有原题，可惜当时楼主没看到。。。跪了= =！）

一个node本来有prev，next，up，down，最后要up，down都是null，他们自己用prev，next连接。constant time不可能吧，constant space可以用iterative来做，有点two pointer的感觉

第五轮： host manager
主要是在聊简历里面的实习经历和项目经历咯，顺便问问项目相关的技术问题。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=159920&extra=page%3D5%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

3周前面的，一直没消息，托人找面试官打听了一下，"didn't make it"，应该是被默据了
(L家有onsite 默据传统，mitbbs看来的，lol）其实两轮system design都有面经，但是没翻到过。。。
1. Host Manager，聊简历 + 简历扩展
2. 中国大哥（斯坦福毕业的大牛）+加拿大白人（步步追问，不问出最优设计不甘心）
system design http://www.1point3acres.com/bbs/thread-147555-1-1.html 第三题
3. 俩白人小哥，很幽默。。。气氛轻松活跃 system design
http://www.1point3acres.com/bbs/thread-147555-1-1.html 第一题

4. coding，三哥，判断两个tree是否相同，如何用多线程去解决？（答案：Thread pool，先甩题目，然后问对Java多线程熟不熟，答曰不，就直接换下一题了）
maximum points in a line. 这题答得不好。用的HashMap<Double, Integer>去做的，面试官直接问了这里Double可不可以做hashmap的key，答曰会有斜率误差，然后问了如何不算斜率来做（没想出好的方法），中间还讨论了double可以不可以拿“==”判断的事情，我说C里面一般用 abs(a-b) < epsiplon判断，Java里面我不清楚，直接用“==”没出过啥问题（这里答错了，其实是一样的。。。，会有问题）。最后还是让用HashMap<Double, Integer>去做了。面完完后查了一下用HashMap用Double是没问题的（hashcode已经做过处理了，可以google），但是算斜率可能会出现误差导致不在一条线上的最后到一条线上去了，所以最好还是不要用除法算斜率的方法做
5. coding，小三哥。给定一个abstract class，实现其中的3个function加constructor （题目不难，但是一整个白板都写不下。。。）
用户可以load一个file（给定的函数），这个file里存的是一个1024 block （每个block 大小 1024byte）的数组，完成以下函数：
1.返回一个没用过的block的位置（自己定义位置）
2.写函数：往这个block里写数据
3.delete函数，删除某个位置的block，使其重新可用
用户操作完以后会自动调用finish函数，将数组写入文件。

题目其实很简单，但是开始因为交流问题，一直以为每个block都必须用来存用户写的东西，不可以自己拿一个来用（自己写header记录哪些没用过，哪些用过），所以一直在考虑怎么encoding没用过的block （三哥说没用过的block全是0），绕了好久发现这么做只能扫一遍数组，效率太低。后来给提示说block不一定要给用户用。。。好吧，直接拿一个block来存header就好了，正好一个byte拿0和1存一下，问怎么优化，答曰用bit记录，下面就是实现。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=159620&extra=page%3D5%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
然后编程题，设计一个数据结构，实现add(e), remove(e), removeRand(e), 都是O(1)
复杂度。我提出了用hash+array，并且在remove的时候，把array尾巴和remove的位置
swap，同时更新hash。三哥说这主意不错你写吧。
下面是我的程序。写完后三哥说cool, sounds good，又问了几个followup，说如果数
有重复怎么办。我说那个hash的value要改成list，记录所有相同元素的位置。那你现
在怎么产生随机数呢？我还没怎么想好，三哥就说是不是要看看重复的个数之类的，然
后就跟我瞎聊了。

大家帮我看看，我是哪里不对挂掉的呢？

template <class T>
class element {
public:
element() {}

void add (T e) {
      array.emplace_back(e);
      hash[e] = array.end() - 1;
}

void remvoe (T e) {
      if (count(hash[e]) {
         auto it = hash[e];
         hash.erase(e);
         if (!hash.empty()) {
            auto lastit = array.end() - 1;
            swap(*it, *lastit);
            hash[*lastit] = it;
         }
         array.pop_back();
      }
}

void removeRand() {
      if (!array.empty()) {
         default_random_engine re ((random_device())());
         uniform_int_distribution<int> dis(0, array.size() - 1);
         int index = dis(re);
         T e = array[index];
         remove(e);
      }
}

private:
vector<T> array;
unordered_map<T, vector<T>::iterator> hash;
};
一是int a 是allocate在stack上的，二是我觉得unordered_map存iterator不太对吧，因为vector本身满了要重新分配空间，iterator有可能会被invalidate 掉，不如直接存index

int a 和 int* b[100]都是在stack上的
需要new 才会到heap上去的

Q: virtual memory是如何工作的？优缺点？
A：操作系统一般在内存不够时分配虚拟内存，不够的虚拟空间存硬盘上。优点是内存
不够时还能转，缺点是硬盘读写速度慢
virtual memory和内存够不够应该没什么关系.你的优缺点说的是对的,但是感觉再答全点更好.
Q：如果有两个进程P1和P2，两个进程都分别读取地址0xabc，会发生什么？
A：因为是两个进程，系统会开两个不相干的地址空间，各读各的没有干扰。
这个基本是对的,但是不同进程的虚拟地址也是可以映射到相同的物理地址的,但我觉得他可能没想问这个.
Q: 那这样的读取到底是怎么实现的？P1说我要读0xabc，怎么就知道它能读到自己想要
的内存？
A: （这个我不明确科班的答案），就说操作系统应该有一个进程对page的映射，系统
知道在哪个page里面的地址空间里找。
这个概念上是对的,但是感觉你能答点细节就更好了.
Q: 这样的不同进程分配不同地址空间的做法有什么优缺点？
A: 优点是不同进程之间的地址各不相干，不会干扰；另外多个进程可以在总内存不够的时候仍然能转；缺点是进程间通信比较麻烦。
优点是对的,但是再答全点就更好了,缺点感觉比较牵强.
Q：process和thread的区别
A: process是不共享内存的，thread共享内存。后来网上查了一下，好像主要是这个，
当然也说thread往往是light work，但是我觉得漏掉这个应该没有关系，三哥很快说ok
了。
你这里说的内存到底指什么,是指物理内存还是虚拟内存,是指寻址空间还是什么.这个题感觉你答得很模糊,并且只答了这一个点.

这一几个问题都是关于操作系统知识的,如果我得到你这样的答案我会感觉你是知道这些知识的,但是并不很清楚.
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=159612&extra=page%3D5%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
面试官是一个Hawaiian, 十几年工作经验但是在Linkedin就一年多. 今天在Remote上班, 家里还有狗叫(我也是醉了).

一开始互相讲了下各自的role和working experience, 然后叫我讲了一个在公司最challenging的project, 就blabla...感觉工作一年多口语锻炼得还可以就没什么大碍.
然后剩45分钟开始做题.

第一题:
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);
}

我的回答: (因为是interface, 所以要implements所有的virtual function).
public class TwoSumTest implements TwoSum{
private HashMap<Integer, Integer> map;
private ArrayList<Integer> list;

public TwoSumTest(){
      map = new HashMap<Integer, Integer>();
      list = new ArrayList<Integer>();
}

public void store(int input){
      map.put(input,1);
      list.add(input);
}

public boolean test(int val){
      for (int i=0; i< list.size(); i++){
      int key = list.get(i);
      if (map.containsKey(val-key))
      return true;
      }
      return false;
}
}

/////用了HashMap没用HashSet是怕要follow up说有duplicates, 结果没有, 也算了不影响逻辑.

第二题: follow up, 如果我要实现O(1)的test怎么办?
回答: 那store就不能保证O(1)了,每次存一个新数的时候,map要存前面所有数与这个数的和. 就是把可能的2 sum结果都枚举出来丢到map里

.
public class TwoSumTest2 implements TwoSum{
private HashMap<Integer, Integer> map;
private ArrayList<Integer> list;
int lastIndex;

public TwoSumTest2(){
      map = new HashMap<Integer, Integer>();
      list = new ArrayList<Integer>();
      lastIndex = 0;
}

public void store(int input){
      list.add(input);
      for(int i =1; i<= lastIndex;i++){
      map.put(list.get(i)+input,1);
      }
      lastIndex++;
}

public boolean test(int val){
      if (map.containsKey(val)){
      return true;
      }
      return false;
}
}

//再次声明用的HashMap没用HashSet是因为怕follow up.不过也没问,面试官说也不用改了没关系.

第三题: 老生常谈WordDistance, 我问了, assume WordOne != WordTwo, 那就再简单不过了
/* This class will be given a list of words (such as might be tokenized
* from a paragraph of text), and will provide a method that takes two
* words and returns the shortest distance (in words) between those two
* words in the provided text.
* Example:
* WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
* assert(finder.distance("fox","the") == 3);
* assert(finder.distance("quick", "fox") == 1);
*
* "quick" appears twice in the input. There are two possible distance values for "quick" and "fox":
*    (3 - 1) = 2 and (4 - 3) = 1.
* Since we have to return the shortest distance between the two words we return 1.
*/
public class WordDistanceFinder {
public WordDistanceFinder (List<String> words) {
      // implementation here
}
public int distance (String wordOne, String wordTwo) {
      // implementation here
}
}

我的回答:
public class WordDistanceFinder {
private String[] words2;

public WordDistanceFinder (List<String> words) {
      // implementation here
      words2 = new String[words.size()];
      for(int i = 0; i< words.size()-1; i++){
      words2[i] = words.get(i);
      }
}
public int distance (String wordOne, String wordTwo) {
      // implementation here
      int p =-1, q =-1, min = Integer.MAX_VALUE;
      for (int i =0 ;i< words2.size()-1; i++){
      if (words2[i].equals(wordOne)) p=i;
      if (words2[i].equals(wordsTwo)) q=i;
      if (p >0 && q>0 ){
         min = Math.min(Math.abs(p-q), min);
         }
      }
      return min;
}
}

//感觉第一个constructor可以直接就private List然后把words pass 过去就行..当时就走直觉了..

之后时间差不多了就没继续出题了,问我有没有什么问题要问就blabla...

总体感觉和听几个同事说的, 感觉在职的题目简单一些似乎...完全没有超纲, 全在leetcode上和地里.

不过他们的题的特色就是总是会写一个完整的class, input总是一个个数而不是一整个数组给你, 所以用java的同学们就好好准备下面向对象啰.
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=160166&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1. o(1) add, remove return random: hashmap 解决
2. 类似climbing stairs， recursion -> dp 优化
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=160000&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
然后问C++问题： thread和process，我答的比较细，然后追问了下thread和process分别怎么通信。然后是a==b，什么时候++a != ++b
然后coding问题： valid number不考虑e 和 shortest word distance，并进行优化

http://www.1point3acres.com/bbs/thread-156427-1-1.html
面试官是个中国人，一上来问了点project后，就开始问java的知识，特别细。自己底子不好，招架不住。
之后出coding题，第一道是triangle的，秒过，follow up：1. 输出array能组成triangle的数目。2. 输出所有的能组成的triangle。time complexity，优化等。
1. input array里面所有能够组成的三角形的个数；所有能够组成的三角形。

第二道是新题，给multidimensional array，给一个function，输入这个array以及各个dimension上的index，可以output这个位置上的数字。
2. 第二题的input的dim应该是会给出长度的吧。如果没有给出长度怎么定义index的大小呢

写一个function，input是multidimensional array，以及array的dimensions，只能调用上面给的那个function，输出这个array里面所有的数字的和。
题不难，是我当时脑子懵了，一直在想怎么找这个array的各个dimension上的boundary，其实input就给了。和面试官一直在交流，但我没说好，十几分钟一直在纠结这个问题。
后来面试官举了个例子，立刻反应过来了。但也没有什么时间，就草草的说了下pseudo code，用dfs做所有dimension上的不同index的combination，然后调用那个function求和。
http://www.1point3acres.com/bbs/thread-159875-1-1.html
一共两轮。。。第一轮是三哥三姐，很和蔼，出的题也不难，一个是带字符的valid 括号，另一个是isomofic string，follow up 是3 个的情况。感觉他们都还蛮开心的，最后问问题，他们也很开心的回答了。。题目都是秒过，然后针对test case 解释了挺长时间。。英语渣～没办法。
第二轮下午刚面完，一个是merge array，intersecion of two array, 果断秒过，小插曲：以为说的linkedlist，所以把merge linkedlist也写了一遍。。第二题是longest palindromic string （题目说的 subsequence），但是我想成substring了。。不过事实证明面试官不在乎，你做出来了，并且表达清楚应该就没问题。

linkedin 一面
http://www.1point3acres.com/bbs/thread-159858-1-1.html
system and infrastructure 刚刚面完，全是面经题，都准备到了，求个onsite。。
1. write back/write allocate cache的区别
就是write through/write back... write allocate 是Computer Architecture的另外一个名词。。。
2. suppose a==b, explain when ++a != ++b
第二题是multithreading的情况吧。
我觉得第二题应该是 a 是 int ， b 是 long, 且 a== b == Integer.MAX_VALUE

3. give a string containing 'a' to 'z', sort lexicographically. Example " bbdda" - > "abbdd"
4. get influencer(celebrity)
5. maximum sum subarray, product array 这个就说了一下
http://www.1point3acres.com/bbs/thread-148811-1-1.html
(2) Linkedin: 找人内推，店面Evaluate Reverse Polish Notation, combination sum, binary tree path sum, valid number, positive feedback, onsite在mountain view. Onsite5轮：
第一轮.：word ladder, same tree, edit distance
第二轮：设计题，listview, thumbnail, async request, connection pool
写个listview 奇数行和偶数行显示不同的颜色

第三轮：用android studio现场完成一个 app
第四轮：阿三经理behavior interview, 期间各种刁难
第五轮：设计， restful api
第二轮是设计一个message 小app
http://www.1point3acres.com/bbs/thread-148574-1-1.html
Onsite Round #1 两位中国人。第一题: Given pointers to two nodes in a binary tree, find lowest common ancestor of two nodes (w/ parent pointers)，这道题那就一步到位吧，用了一个O(N) with constant space。变种是不给parent pointer,给你root pointer，那就用DFS吧。第二题: print all permutations of a set of characters。注意重复字母的情况。

Onsite Round #2 一个美国人。System Design: Design a web word game that user can bet money on it。具体答题方向在web server, data base, load ballancer, master-slave db, shardling, denormolization, caching。后来面试官说想聊一聊如何用第三方（facebook，google，wechat）做登录，正好我做过就给他讲了讲。

Onsite Round #3 一个中国人。这场是我整个面试最不顺利的一场。第一题: Given two linked list, find whether the two overlap。这道题可以用O(N) with constant space解，分为三种情况：两个都没cycle，只有一个有，两个都有cycle。再加上找到overlap的起始点。我每说出一个假设，小哥就让我数学证明，问的还是十分详细的。最后出来的解法有一点麻烦，小哥说其实已经很好了，但是可以找个地方把cycle切掉，这样做更decent。好吧，确实没有想到。第二题是word ladder。有一个优化就是可以把之前的结果cache起来，用于提升下次Query的效率。

http://www.40jy.com/archives/96

第一轮一上来是行为问题，把我简历上的边边角角都问的非常仔细，包括我为什么做，怎么做，如果再来一次会怎么改进，将来有什么计划，甚至还来了一个场景题。。。这在以技术见长的公司里面还是比较少见的

第二轮是一个系统设计，上来先问了三个跟图有关的关联度问题的解法，比如如何判断两个人是不是同一个人的好友之类的。然后问复杂度，然后改进，一直改进到两位面试官们满意，这是已经过去好久了。接着又问如何扩展到多个机器，如何划分这个图的信息，等等。乱答之，完全是混过去。事后得知面试官也觉得我这部分答得不太好，但是一开始的解题还是可以的。基于我的经验不够，这样的表现还算是可以谅解。

第四轮coding，LC的原题两题，秒杀咯，到此终于略微舒了一口气，也为下一轮被虐到渣也不剩埋下了伏笔。。。写完之后有稍微讨论了一下复杂度和扩展到多个机器就放我过了。

第五轮系统设计，跟内存有关的一个设计。。。内存。。。不可以用已有的任何STL容器，因为这些容器需要分配多少内存空间是不太确定的，而且分配的内存地址也很可能不连续，所以要自己设计一个用且只用给定大小内存的信息读写系统。。。当然，内存的声明，使用，回收，寻址都要自己来设计啦。。。一上来毫无头绪，面试官大人也不屑于给我提点，只能挤牙膏一般这边挤一点，那边挤一点，顺便观察人家脸色，看到对路就继续往下猜，居然最后也七七八八混了个大概样子出来，不过卡在了寻址那里。面试官大人高抬贵手放我一马，接着问了问同步和锁的问题就算结束了。

一上来就是讨论TCP的滑动窗口。我搜肠刮肚把以前还给老师的知识都一一抢回来才勉强通过，接着有讨论如何用这个滑动窗口实现可靠的多播，最后还问怎么用这玩意儿实现事务一致性

0. 最最重要的一点：一场成功的面试有两个重要的因素： 1. 快速解决问题并且可以做出相应优化 2. 快速完成没有任何错误的代码。

1.关于运气：我认为面试是50%运气加上50%实力。四个公司面下来我觉得能过两个。最后过了四个只是运气很好。如果真的面了我不会的题目我也一点办法也没有。. visit

2.关于刷题：我Leetcode只刷了一遍，每道题亲自写代码保证AC（这点很重要！），写完之后看看讨论有没有更优化的解法用来举一反三，或是有没有更简洁更美观的代码。没有就自己发一个。从来不用IDE，点Submit就要保证不出Syntax Error，过基本的testcase。这样我感觉才是正确的刷题之道。

3. 关于面试题：这几家大公司都是最为常规的面试题目。Google难度大概在Top Coder Division 1 250 分左右， Hackerrank rated contest 题目里面简单和中等之间。

4. 关于面试表现：保持自信！保持微笑！微笑是实力的体现。面试更像是一场交流，你不会的多想一想，他不会的你给他讲一讲。

5. Experience Beats Everything。刷题其实是快速积累经验的一种方法，但是如果只靠刷题就能困难的面试，你让我们这些科班出身的情何以堪。所以还是推荐大家刷题的同时循序渐进，多掌握一些算法以外的东西，多做做有意思的项目，加深对计算机科学的理解。

Linkedin Interview Misc

Labels

Popular Posts