Chapter 50 Linkedin 2016 01-06

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

那我乱讲讲挂后自己的一些想法,你也就乱听听

先按要求做一些math,算一下数据量,流量,需要的机器数目之类的

感觉此类应用应该是用关系型数据库,data可以自己试着设计一下,API可以这些:

query(user, day), insert(user, event), delete(user, event)

scale out的话,因为用户间关联较稀少,所以可以按照用户来shard到不同机器

短时间内notify大量的用户比较麻烦,没想好
---

这题面试官确实是主要考mysql然后加个memcache的.我当时面的说用couchbase,
面试官感觉也不是在一个频道上..

50.1 Reservoir sampling

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

code questions: given a stream of integer, randomly choose k elements from n, ensure each value among k has equal probability.

参考:
https://en.wikipedia.org/wiki/Reservoir_sampling
http://www.geeksforgeeks.org/reservoir-sampling
https://leetcode.com/problems/random-pick-index
https://leetcode.com/problems/linked-list-random-node

50.2 Loop mutlidimentional arrays

Given a mutlidenmentional arrays, compute the sum of all values. Given API getValue(dn, dn-1.... d0), dn = index at denmention n

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

这道题的思想很简单,就是题意容易搞不懂.对多维数组,循环就是了.但是我们不能hardcode这个多重循环,因为数组的维数不是确定的.搞懂这个就简单了.正确的思路是用recusrive function.

输入是MDA的pointer是p, 还有dimension array vector ds:

int getsum(MDA* p, vector<int> ds){
  ...
}

假设ds是{2,3,4}, sum函数必须调用:

get(p,{0,0,0})
get(p,{0,0,1})
get(p,{0,0,2})
get(p,{0,0,3})
get(p,{0,1,0})
get(p,{0,1,1})
get(p,{0,1,2})
get(p,{0,1,3})
get(p,{0,2,0})
get(p,{0,2,1})
get(p,{0,2,2})
get(p,{0,2,3})
...
get(p,{1,2,3})

其实这个题就是combination {{0,1},{0,1,2},{0,1,2,3}}. Pretty much like: https://leetcode.com/problems/letter-combinations-of-a-phone-number ,用DFS解之.

void dfs(MDA* mda, int& sum, VI& p, VI& ds, int idx, int L) {
  if (p.size() == L) {
    sum += getval(mda, p);
    return;
  }
  for (int i = 0; i<ds[idx]; i++) {
    p.push_back(i);
    dfs(mda, sum, p, ds, idx + 1, L);
    p.pop_back();
  }
}

int getsum(MDA* mda, vector<int> ds) {
  int sum = 0;
  int L = ds.size(); // dimension
  vector<int> p;
  dfs(mda, sum, p, ds, 0, L);
  return sum;
}

完整程序见: https://github.com/shadowwalker2718/data_structure_algorithm/blob/master/leetcode_c/MultiDimensionArray.h#L28

technique communcation, describe favorite project

code problems: serialize and deserialize a BST

host manager session: describe the most chanllenging project and how you handle challenges, why choose Linkedin over other companies

system design: design a system to monitors the top exceptions during last hour, last 24 hours