System Design

http://horicky.blogspot.com/2010/10/scalable-system-design-patterns.html
http://horicky.blogspot.com/2010/08/designing-algorithmis-for-map-reduce.html
http://horicky.blogspot.com/2009/11/nosql-patterns.html
http://highscalability.com/blog/2014/5/12/4-architecture-issues-when-scaling-web-applications-bottlene.html

OO Design

http://www.quora.com/What-are-good-ways-to-answer-interview-design-questions

facebook

发信人: fbrefer (fbrefer), 信区: JobHunting
标  题: facebook面试准备及内推
关键字: 内推,fb,facebook,refer,面试
发信站: BBS 未名空间站 (Tue Jul 22 11:01:17 2014, 美东)

关于面试流程
社招的话
电面1-2轮，一般就是coding
onsite一般是4轮，2轮coding，1轮design，1轮behavior+coding
校招的话，那轮design也变成coding了



关于准备
1) algo/coding
建议大家刷一下leetcode，基本上cover到了大多数常见面试题，而且有可能碰到原题
。需要注意的是，仅仅解出来，做到bug free可能是不够的。代码的质量和速度也非常
重要。网上有一些别人给出的答案可以参考，尽量做到代码简洁清晰。速度上leetcode
上所有题都做到10分钟以内写完。


2) design
解这种题是个*交流*的过程，或者说是给出方案然后获取反馈的不断循环的过程。
一般的流程：
首先你要问清楚requirement；
然后可以讲一下high level architecture，就是分成哪几个component，互相之间如果
interact，在白板上画一画；
之后面试官可能会让你深入某个component detail讨论；
也有可能变换requirement让你重新设计

另外，f家还喜欢让你估算机器之类的，做一些back-of-envelopme calculation。所以
最好对一些计算机相关的基本常数，fb的用户量等等有个大概的了解。

准备的时候建议看看fb的design高频题。一方面有可能面试的时候刚好碰到这几个
topic，另一方面其实很多design都是相通的。
之前有个帖子讲这个，原帖已经被删了，这儿有个备份http://blog.csdn.net/sigh1988/article/details/9790337

另外补充一点我收集的材料

a) 首先你可以从整体上了解一下facebook的architecture
http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc
http://www.ece.lsu.edu/hpca-18/files/HPCA2012_Facebook_Keynote.
http://www.quora.com/Facebook-Engineering/What-have-been-Facebo
除了下面给出的一些资料，fb engineering page里还有很多不错的内容
https://www.facebook.com/Engineering

b) news feed
这里有个talk
http://www.infoq.com/presentations/Facebook-News-Feed
对应的slides
http://readme.skplanet.com/wp-content/uploads/2012/11/0-3_Faceb
还有一些quora上的讨论
http://www.quora.com/Activity-Streams/What-are-the-scaling-issu
http://www.quora.com/What-are-best-practices-for-building-somet
http://www.quora.com/What-is-the-best-storage-solution-for-buil

c) facebook chat
这里有两个notes，其中第二个里面还有相应的tech talk links
https://www.facebook.com/notes/facebook-engineering/facebook-chat/
14218138919
https://www.facebook.com/notes/facebook-engineering/chat-stability-and-
scalability/51412338919

d) typeahead search & graph search
关于typeahead search的tech talk和notes
https://www.facebook.com/video/video.php?v=432864835468
https://www.facebook.com/note.php?note_id=365915113919
https://www.facebook.com/note.php?note_id=389105248919

关于graph search的paper, tech talk, notes。其中paper很值得一看。
http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p871-cur
https://newsroom.fb.com/Photos-and-B-Roll/4362/Graph-Search-Whiteboard
https://www.facebook.com/note.php?note_id=10151240856103920
https://www.facebook.com/note.php?note_id=10151347573598920
https://www.facebook.com/note.php?note_id=10151361720763920
https://www.facebook.com/note.php?note_id=10151432733048920
https://www.facebook.com/note.php?note_id=10151755593228920

e) facebook messages
两个tech talks
http://www.youtube.com/watch?v=XAuwAHWpzPc
http://www.infoq.com/presentations/HBase-at-Facebook
以及eng notes
https://www.facebook.com/note.php?note_id=10150148835363920
https://www.facebook.com/note.php?note_id=10150162742108920

f) photo storage
相关的papers和notes
https://www.usenix.org/conference/osdi10/finding-needle-haystack-facebooks-
photo-storage
https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Beaver.pdf
https://www.usenix.org/legacy/events/osdi10/tech/slides/beaver.pdf
https://www.facebook.com/note.php?note_id=76191543919

g) social graph data store
相关的note, video, paper
https://www.facebook.com/notes/facebook-engineering/tao-the-power-of-the-
graph/10151525983993920
https://www.usenix.org/conference/atc13/technical-sessions/presentation/
bronson
http://www.cs.cmu.edu/~pavlo/courses/fall2013/static/papers/117

h) tiny URL
这里有一些讨论
http://n00tc0d3r.blogspot.com/2013/09/big-data-tinyurl.html
http://stackoverflow.com/questions/742013/how-to-code-a-url-sho
http://stackoverflow.com/questions/3376163/what-are-the-things-

i) POI
参考这里
http://www.slideshare.net/mmalone/scaling-gis-data-in-nonrelati
http://www.mitbbs.ca/article_t/JobHunting/32476139.html


3) behavior，建议大家了解一下fb的culture，准备一下常见的behavior questions，
面试之前rehearsal一下。

最后面试临近的时候，可以再刷刷面经，找找感觉。像glassdoor, mitbbs/jobhunting
, careercup，这些上面就有很多。

如果有其它疑问，欢迎回复或者PM我。

Snapchat

http://www.2cto.com/kf/201205/131442.html
http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/
http://www.cgorbit.itkm.ru/docs/unix-way/Programming%20Pearls%20%282nd%20Ed%202000%29%20-%20Jon%20Bentley%20ADDISON%20WESLEY.pdf

http://www.1point3acres.com/bbs/thread-108837-1-1.html
http://www.1point3acres.com/bbs/thread-125921-1-1.html
http://zhedahht.blog.163.com/
http://ac.jobdu.com/hhtproblems.php
http://baozitraining.org/blog/2014-star-startup-interview-snapchat/


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

电面：
非常简单的两道题：
find the shift position in the rotated sorted array
like windows paint, draw the color of triangle, square, or circle

class color {
  private:
    int R;
    int G;
    int B;
};
class point {
public:
  int x;
  int y;
};
class paint_tool {
  private:
    vector<vector<int>> canvas;
    int index[] = {-1, 1}
  public:
    void piant(point p, int color) {
      queue<point> que;
      que.push(p);
      vector<vector<bool>> marker;
      for(int i = 0; i < canvas.size(); i++) {
        for (int j = 0; j < canvas[0].size(); j++) {
          marker[i][j] = false;
        }
      }
      canvas[p.y][p.x] = color;
      marker[p.y][p.x] = true;
      while (!que.empty()) {
        point cur = que.front();
        que.pop();
        for (int j = -1; j <= 1; j++) {
          for (int i = -1; i <= 1; i++) {
            if (i == 0 && j == 0) {
              continue;
            } else {
              point neighbor(cur.x + j, cur.y + i);
              if (validBoundary(color, neighbor) && marker[neighbor.y][neighbor.x] == false) {
                que.push(neighbor);
              }
            }
          }
        }
        //paint the point
        canvas[p.y][p.x] = color;
        marker[p.y][p.x] = true;
      }    
    }
    bool validBoundary(int color, point &p2) {
      if (color != canvas[p2.y][p2.x]) {
        return true;
      } else {
        return false;
      }
    }
};

Maximum Subarray III

Maximum Subarray III

Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

Note

The subarray should contain at least one number

Example

Given [-1,4,-2,3,-2,3],k=2, return 8

------------------------ thinking --------------------------------
http://www.cnblogs.com/lishiblog/p/4183917.html
-----------------------  codes ----------------------------------
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    int maxSubArray(vector<int> nums, int k) {
        // write your code here
        //dp[j][i] means the max of j elements with i subarrays
        int dp[nums.size() + 1][k+1];
        for (int i = 0; i <= nums.size(); i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= k; i++) {
            for (int j = i; j <= nums.size(); j++) {
                dp[j][i] = INT_MIN;
                int max = INT_MIN;
                int end_max = -1;
// BUG here -> the edge number should be carefully set
                for (int p = j-1; p >= i-1; p--) {
                    end_max = end_max < 0?nums[p]: end_max+nums[p];
                    max = max > end_max?max:end_max;
                    int val = dp[p][i-1] + max;
                    dp[j][i] = dp[j][i] > val?dp[j][i]:val;
                }
            }
        }
        return dp[nums.size()][k];
    }
};

Kth Prime Number

Kth Prime Number

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

The eligible numbers are like 3, 5, 7, 9, 15 ...

Example

If k=4, return 9.

Challenge

O(n log n) or O(n) time

-------------------------- thinking --------------------------------
https://tianrunhe.wordpress.com/2012/04/03/find-the-kth-number-with-prime-factors-3-5-and-7/
-------------------------- codes --------------------------------
class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    long long kthPrimeNumber(int k) {
        // write your code here
        queue<long long> Q3;
        queue<long long> Q5;
        queue<long long> Q7;
        Q3.push(3);
        Q5.push(5);
        Q7.push(7);
        int out_cnt = 0;
        long long result;
        while (out_cnt < k) {
            out_cnt++;
            if (Q3.front() < Q5.front() && Q3.front() < Q7.front()) {
                result = Q3.front();
                Q3.pop();
                    Q3.push(result * 3);
                    Q5.push(result * 5);
                    Q7.push(result * 7);
            } else if (Q5.front() < Q3.front() && Q5.front() < Q7.front()) {
                result = Q5.front();
                Q5.pop();
                    Q5.push(result * 5);
                    Q7.push(result * 7);

            } else {
                result = Q7.front();
                Q7.pop();
                Q7.push(result * 7);
            }
        }
        return result;
    }
};

Wood Cut

Wood Cut

Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

Note

You couldn't cut wood into float length.

Example

For L=[232, 124, 456], k=7, return 114.

Challenge

O(n log Len), where Len is the longest length of the wood.

---------------------------- thinking ---------------------------------------

---------------------------- codes -----------------------------------------
class Solution {
public:
    /**
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    int woodCut(vector<int> L, int k) {
        // write your code here
        if (L.size() == 0) return 0;
        if (L.size() == 1) return (L[0]/k);
        int max = 0;
        for (int i = 0; i < L.size(); i++) {
            if (max < L[i]) {
                max = L[i];
            }
        }
       // max = max/L.size();
        int start = 0;
        int end = max;
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            int cnt = 0;
            if (mid == 0) {
                cnt = INT_MAX;
            } else {
                for (int i = 0; i < L.size(); i++) {
                    cnt += L[i]/mid;
                }
                if (cnt >= k) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < L.size(); i++) {
            cnt += L[i]/end;
        }
        if (cnt >= k) {
            return end;
        } else {
            return start;
        }
    }
};