01/2018 Big Facebook E4 Package PhD with 1 year experience and competing offer from Google and LinkedIn

Internal Referral: Yes
Education: PhD
Experience: 1-3Year
Facebook Level: E4
Location: Menlo Park, CA
base salary: 160000
Equity部分(RSU/Option Total): 400000
Equity Vesting schedule: 4 years
sign on bonus: 100,000!
Yearly Bonus: 10%+
relocation: no
other offers: google, linkedin

Expected compensation: 305,000+/yr for first 4 years or 400K first year

Analysis: top E4 offer. Competing offer + strong internal referral works magic

01/2018 yelp, salesforce, groupon competing offers master 2 year experience

Has yelp, salesforce, groupon at the same time.

Level: SDE
Education: Master Degree
Location: Bay area
Experience: Bachelor plus 2+years
Competing Offer: yelp, salesforce, groupon
Base: 150K
Bonus: 15%
Equity (over 4 years): 100k stocks / 4 years
Sign on bonus: 50K
Expected income: 210K to 220k/yr

Analysis:
Competing offers help. These 3 companies typically gives 180 to 200k for such candidates. Notice these companies typically pay more base than Facebook/Google but less stock incentives. Some says that these companies has relatively lower workload than F/G.

01/2008 Google T3 offer with 300K stock GSU 1year Experience Master

Google Level: T3
Education: Master Degree
Location: Mountain View
Experience: Bachelor plus 1+years
Competing Offer: NA
Base: 130K
Bonus: 15%
Equity (over 4 years): 300K worth of google stocks / 4 years
Sign on bonus: 50K
Expected income: 237K/yr

Analysis:
No competing offer!

One of the very good offer as a T3 with no competing offer. Almost in T4 lower-mid end range.

Design question: News Feeds

Question

To make it simple, let’s focus on designing news feed system for Facebook since different products have different requirements.

To briefly summarize the feature, when users go to their home pages, they will see updates from their friends based on particular order. Feeds can contain images, videos or just text and a user can have a large number of friends.

So how can you design such news feed system from scratch?

 

Subproblems

If you haven’t thought about this problem, it’s better to solve it by yourself before reading the rest of the post. Although there’s no such a thing as standard answer, you can still learn a lot by comparing your solution with others.

Here we go. As we said before, when facing such large and vague system design question, it’s better to have some high-level ideas by dividing the big problem into subproblem.

For a news feed system, apparently we can divide it into front-end and backend. I’ll skip the front-end as it’s not that common in system design interviews. For backend, three subproblems seem critical to me:

  • Data model. We need some schema to store user and feed object. More importantly, there are lots of trade-offs when we try to optimize the system on read/write. I’ll explain in details next.
  • Feed ranking. Facebook is doing more than ranking chronologically.
  • Feed publishing. Publishing can be trivial when there’re only few hundreds of users. But it can be costly when there are millions or even billions of users. So there’s a scale problem here.

 

Data model

There are two basic objects: user and feed. For user object, we can store userID, name, registration date and so on so forth. And for feed object, there are feedId, feedType, content, metadata etc., which should support images and videos as well.

If we are using a relational database, we also need to model two relations: user-feed relation and friend relation. The former is pretty straightforward. We can create a user-feed table that stores userID and corresponding feedID. For a single user, it can contain multiple entries if he has published many feeds.

For friend relation, adjacency list is one of the most common approaches. If we see all the users as nodes in a giant graph, edges that connect nodes denote friend relation. We can use a friend table that contains two userIDs in each entry to model the edge (friend relation). By doing this, most operations are quite convenient like fetch all friends of a user, check if two people are friends.

 

Data model – continue

In the design above, let’s see what happens when we fetch feeds from all friends of a user.

The system will first get all userIDs of friends from friend table. Then it fetches all feedIDs for each friend from user-feed table. Finally, feed content is fetched based on feedID from feed table. You can see that we need to perform 3 joins, which can affect performance.

A common optimization is to store feed content together with feedID in user-feed table so that we don’t need to join the feed table any more. This approach is called denormalization, which means by adding redundant data, we can optimize the read performance (reducing the number of joins).

The disadvantages are obvious:

  • Data redundancy. We are storing redundant data, which occupies storage space (classic time-space trade-off).
  • Data consistency. Whenever we update a feed, we need to update both feed table and user-feed table. Otherwise, there is data inconsistency. This increases the complexity of the system.

Remember that there’s no one approach always better than the other (normalization vs denormalization). It’s a matter of whether you want to optimize for read or write.

 

Ranking

The most straightforward way to rank feeds is by the time it was created. Obviously, Facebook is doing more than that. “Important” feeds are ranked on top.

Before jumping to the ranking algorithm, I’d usually like to ask why do we want to change the ranking? How do we evaluate whether the new ranking algorithm is better? It’s definitely impressive if candidates come up with these questions by themselves.

The reason to have better ranking is not that this seems the right thing to do. Instead, everything should happen for a reason. Let’s say there are several core metrics we care about, e.g. users stickiness, retention, ads revenue etc.. A better ranking system can significantly improve these metrics potentially, which also answers how to evaluate if we are making progress.

So back to the question – how should we rank feeds? A common strategy is to calculate a feed score based on various features and rank feeds by its score, which is one of the most common approaches for all ranking problems.

More specifically, we can select several features that are mostly relevant to the importance of the feed, e.g. share/like/comments numbers, time of the update, whether the feed has images/videos etc.. And then, a score can be computed by these features, maybe a linear combination. This is usually enough for a naive ranking system.

 

Design question: POI

FB/Uber likes this one.

A point of interest, or POI, is a specific point location that someone may find useful or interesting.
Read More on wiki

Q1. Given the current location, how to find the most closest k points.
Q2. Given the current location, how to find all the points within k miles. 

A1. Geohash
A2. K-D tree
A3. Space-filling Curve 

intersection of intervals — search points in a range.
intersection of rectangles (using bst)   search overlapped intervals
https://www.youtube.com/watch?v=Igr6yONkpIQ

Integer to English Words

Problem description:
A non-negative Convert integer to its English words representation. Given input is guaranteed to be less than 231 – 1

Examples ,
123 Hundred Twenty – > One Three”
12345 “Twelve Thousand Three Hundred Forty – > Five”
1234567 “One Million Two Hundred Thirty, Four Thousand Five Hundred Sixty Seven”

Analysis:
This problem is the use of the most intuitive, the integer into a string, and then to 3 for the unit will be the string to cut. And then each group was treated separately.
At the beginning I will play as integer processing, can be found later, when 1 000000 should write one million, and if with integer, the output results will for one million thousand, and there seems to be no obvious way to solve.

Code:

import java.util.HashMap;
import java.util.Map;

/** see test {@link _273_IntegerToEnglishWords.SolutionTest } */
public class Solution {
    
    private static final String[] DELIM = { "", " Thousand", " Million", " Billion" };
    
    @SuppressWarnings({ "serial" })
    private static final Map<Integer, String> WORDS = new HashMap<Integer, String>() {{
        put(1, "One");
        put(2, "Two");
        put(3, "Three");
        put(4, "Four");
        put(5, "Five");
        put(6, "Six");
        put(7, "Seven");
        put(8, "Eight");
        put(9, "Nine");
        put(10, "Ten");
        put(11, "Eleven");
        put(12, "Twelve");
        put(13, "Thirteen");
        put(14, "Fourteen");
        put(15, "Fifteen");
        put(16, "Sixteen");
        put(17, "Seventeen");
        put(18, "Eighteen");
        put(19, "Nineteen");
        put(20, "Twenty");
        put(30, "Thirty");
        put(40, "Forty");
        put(50, "Fifty");
        put(60, "Sixty");
        put(70, "Seventy");
        put(80, "Eighty");
        put(90, "Ninety");
        put(100, "Hundred");
    }};
    
    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (num != 0) {
            int partial = num % 1000;
            StringBuilder psb = convert(partial);
            if (psb.length() == 0) {
                i++;
            } else if (sb.length() == 0) {
                sb = psb.append(DELIM[i++]);
            } else {
                sb = psb.append(DELIM[i++]).append(" ").append(sb);
            }
            num = num / 1000;
        }
        return sb.toString();
    }
    
    // convert a number less than 1000
    private StringBuilder convert(int num) {
        if (num == 0) {
            return new StringBuilder();
        } else if (num < 20) { return new StringBuilder(WORDS.get(num)); } else if (num % 100 == 0) { return new StringBuilder(WORDS.get(num / 100) + " Hundred"); } else if (num > 100) {
            return new StringBuilder(WORDS.get(num / 100)  + " Hundred ").append(convert(num % 100));
        } else if (num % 10 == 0) {
            return new StringBuilder(WORDS.get(num));
        } else if (num > 10) {
            return new StringBuilder(WORDS.get(num / 10 * 10) + " " + WORDS.get(num % 10));
        } else {
            return new StringBuilder(); 
        }
    }
}

Implement regular expression matching with support for ‘.’ and ‘*’

这题很多人都被问过,很多人都背了答案,但是很重要的事要知道算法复杂度。很多人洋洋洒洒写出来后被拒还不知道为什么。

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Analysis:

Note that this problem is NOT the same as Wildcard Matching.
The major difference is the meaning of  “*” in the string.
Here, “*” means 0 or more preceding element. For example, the last test case in the problem description:
isMatch(“aab”,””c*a*b”)
The pattern :  “c*a*b” means,  there can be 0 or more ‘c’, 0 or more ‘a’ and one b.
e.g., “ccaab”, “aab”, “ccb”, “b” are all valid strings for this pattern, thus the correct answer for this test case is also true (0 ‘c’, 2 ‘a’ and 1 ‘b’).

How to solve this question?  DFS!
Since we don’t know how many “* element ” is needed to get a match, one way is to search every possibilities. However in this problem, it is not complex because there are many restrictions, which seems even easier than the wildcard matching problem.

First of all, let’s define “{x}” means 0 or more ‘x’ can be here in the string.
Using the above example, the problem can be rewritten as:
                             isMatch(“aab” “{c}{a}b”)

Then we can do the matching from the start of the two strings. The condition of a match between two elements s[i] and p[j] are:
(1) s[i]==p[j]
(2) s[i]!=p[j] but p[j]==’.’
Otherwise, 2 strings cannot have a match.

In the first case (s[i]==p[j]),
If p[j] is not a { }, (not followed by a *), we can just go to the next element (i++, j++).
If p[j] is a { } (followed by a *), zero or more p[j]s might be here.

How many time we need here to have multiple p[j]s?
Let’s consider this problem in another way.
If it is zero p[j], then just search the next j (j++,i).
Otherwise, no matter how many we need, for the next element s[i+1], s[i+1] only knows it is now matching with {p[j]}. So, we can just search the current j with next i (j, i++).

For the end of the pattern, if all the remaining elements are { }, then it can all be empty so it is a match. Otherwise it is a false match.

To reduce the number of recursion, we know that, if p[j]==p[j+1] and they both are “{ }”, then they can be considered as only one element with “{ }”. Without this condition, your code might not pass the last test case in the OJ.

Code:

 

class Solution {
public:
 
    bool emp(int pm, vector &vali){ //check if the remaining pattern can be empty or not
        if (pm==vali.size()){return true;}
        else{return vali[pm];}
    }
 
    bool match(string s,int sm, string p, int pm, vector &stars, vector &vali){
        if (sm<s.size() && pm==p.size()){ // if string is not ended but pattern is ended, it is a false return false; } if (sm>=s.size()){  //if the string is ended
            if (emp(pm,vali)){return true;} // if remaining pattern can be empty, it is a match
            else{return false;}
        }else{
            if (s[sm]!=p[pm] && p[pm]!='.'){ //if current elements not equal
                if (stars[pm]){ //if there can be zero p[pm].
                    return match(s,sm,p,pm+1,stars,vali); //search the next element
                }else{
                    return false;
                }
            }
            if (s[sm]==p[pm]||p[pm]=='.'){ //if current elements equal
                if (stars[pm]==1){ //if there can be 0 or more p[pm]
                    if(p[pm]==p[pm+1] && stars[pm+1]==1){ //if the next element is the same and also followed by *
                        return match(s,sm+1,p,pm+1,stars,vali);
                    }else{
                        ////////////////////search zero or more p[pm]///////////////////////
                        return match(s,sm,p,pm+1,stars,vali)||match(s,sm+1,p,pm,stars,vali); 
                        ////////////////////////////////////////////////////////////////////
                    }
                }else{
                    return match(s,sm+1,p,pm+1,stars,vali);
                }
            }
        }
    }
 
    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string str_s(s);
        string str_p(p);
        vector stars;
        int i=0;
        while (i<=str_p.size()){  //rewrite the pattern string, store the elements followed with "*"
            if (str_p[i+1]=='*'){
                str_p.erase(i+1,1);
                stars.push_back(1);
            }else{
                stars.push_back(0);
            }
            i++;
        }
         
        vector vali(str_p.size(),0); //if the remaining pattern are all with *, then vali[i]=1, otherwise 0
        i=str_p.size()-1;
        while(i>=0){
            if (stars[i]==1){vali[i--]=1;}
            else{break;}
        }
         
        return match(str_s,0,str_p,0,stars,vali);
    }
 
};

Print A Binary Tree in Vertical Order Path

Objec­tive: Given a binary tree, print it in ver­ti­cal order path.

What is Ver­ti­cal Order

Vertical-Order-Print-Example

Vertical-Order-Print-Example

as you can see in the exam­ple above, [4],[2], [1,5,6],[3],[7] are the ver­i­cal order of the given binary tree.

Approach:

  • Its a tricky solution.
  • Do the inorder traversal.
  • Take a vari­able called level, when ever you go left, do level++ AND when ever you go right do level–.
  • With step above we have sep­a­rated out the lev­els vertically.
  • Now you need to store the ele­ments of each level, so cre­ate a TreeMap and the (key,value) pair will be (level,elements at that level).
  • At the end iter­ate through the TreeMap and print the results.

Vertical-Order-Sum-Implementation

Code:

import java.util.ArrayList;
import java.util.Set;
import java.util.TreeMap;

public class VerticalOrder {
	public static TreeMap<Integer, ArrayList> ht = new TreeMap<>();;
	public static int level;
	public ArrayList<Integer> al;

	public Node vertical(Node root, int level) {
		if (root == null) {
			return null;
		}
		Node y = vertical(root.left, --level);
		if (y == null) {
			level++;
		}
		if (ht.get(level) != null) {
			ArrayList x = ht.get(level);
			x.add(root.data);
			ht.put(level, x);
		} else {
			al = new ArrayList<>();
			al.add(root.data);
			ht.put(level, al);
		}
		return vertical(root.right, ++level);
	}

	public void printResult(TreeMap ht) {
		Set<Integer> i = ht.keySet();
		for (int keys : i) {
			System.out.println(ht.get(keys));
		}
	}

	public static void main(String args[]) {
		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(3);
		root.left.left = new Node(4);
		root.left.right = new Node(5);
		root.right.left = new Node(6);
		root.right.right = new Node(7);

		VerticalOrder p = new VerticalOrder();
		p.vertical(root, 0);
		p.printResult(ht);

	}
}

class Node {
	int data;
	Node left;
	Node right;

	public Node(int data) {
		this.data = data;
		left = null;
		right = null;
	}
}

class ListNode {
	int data;
	ListNode next;

	public ListNode(int data) {
		this.data = data;
		next = null;
	}
}

Out­put:

[4]
[2]
[5, 1, 6]
[3]
[7]

又跪了,Facebook跳到各大公司的offer包裹(Uber,Google,Snapchat,Dropox)

人比人气死人啊,算了什么都不说了,直接上数据吧
背景:CS Master 5.5年

地点:湾区

现在在Facebook

最近拿了几个offer, 请大家看看给个建议
大概annual pkg 情况如下

Google T5 : 350k
(Master + 5.5年 拿到 G T5 感觉挺满意的了, 知道不少朋友没要到T5,最后从了高端
T4)

Uber Senior: 410k
(60B的估值不知道啥时候revenue才能justify, 短期看不到套现的可能???)

Snapchat: 420k (注意了,vest plan其实是10%,20%,30%,40%, 这里按每年25%算的,有
点坑!)
(Vest plan有点坑,会不会干到第三年就被fire了???)

Dropbox: 430k
(2017年IPO?? http://www.bloomberg.com/news/articles/2016-08-15/dropbox-said-to-discuss-possible-2017-ipo-in-talks-with-advisers)

都已经negotiate过了(except snapchat, no bargain at all)