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.

湾区码工包裹工资系统介绍(Facebook, Google为例)

Cash counting stock equity refreshment for google

这个湾区工资的月经贴看得我头大,还是给大家一个比较系统的介绍吧,有想法来湾区
的,可以根据自己实际情况判断。

我的背景:某湾区独角兽hiring manager,过去几年中接触过各种级别几十个offer,
也在FLAG工作过,朋友众多,熟悉FLAG的情况。经常参加interview和offer decision
,对于面试人的级别以及包裹有足够的insight和一定的决定权。

大家经常所说的包裹,或者年收入,其实包括以下几个部分:

Base salary:每个月的固定工资,通常由级别决定。
Bonus:每年额外的cash bonus,通常由performance决定。
Stock (RSU or Options):股票,一般签offer的时候给个数字,分四年发,通常由级
别决定,要看option会过多久expire,比如有的是6个月,有的是好几年,那么你即使已
经离开公司,只要后来公司上市了,你还是可以在expire 前Exercise.
Stock refresher:类似于Bonus,但是是股票的形式,通常也是每年给一次,分四年发
完。通常由performance决定。

Sign on bonus:一次性的cash bonus,入职的时候给。
经常有公司有所谓的retention bonus,对于high performer在第四年的时候又发一大
笔。至于一般人估计就没有了。

不同的公司,根据公司发展的不同阶段,以上部分在包裹中的比重不同。FLAG大概是一
半一半,或者stock略少,Pre-IPO startup可能股票多于base,很成熟的大公司股票可
能很少,等等等等。

级别在总包裹里起决定性作用。级别和一个人的经验年限,之前的title,有没有
startup经验,有多少别的offer相关。
每个公司对级别的定义也不同,以Google为例(FB和很多startup有相似的级别),正
常的expectation是
fresh grads (under or MS): L3 (入门Junior软工)
fresh grads (PhD/MS) + 1-4 yrs exp: L4 (能正常独立工作的软工)
3-8 yrs exp: L5(senior,或者tech lead)
L5以上就比较wild了,有人十几年经验还是L5,有人很年轻就L7, L8了。L6+开始进入
管理层。

然后,不同公司对于相同的级别的包裹也不同。FLAG这样的土豪给的多,Pre-IPO
startup给的也不错,但是股票有变纸的风险,成熟的大公司给的就少一些。几个例子:
—————————–
以下例子中的数字只是FLAG和少数独角兽,不代表湾区大多数公司!但是所有的
package structure仍然有普遍意义!
—————————–
L5 FB: 16-18w base, 60-80w RSU (4yrs,60-80w分四年发,一年15-20w,不同公司的
vest plan 不一样的,比如AMAZON, 第一年5%, 第二年15%, 40%, 40%。如果攒到
一年给, 税要交到哭死。Uber家三年就fully vested 走人也可以了), 5-8w sign
on bonus, 2-3w bonus, 8-12w stock refresher (4yrs) => $35-40w total cash per
year

L6 GOOG: 20-25w base, 70-120w RSU (4yrs), ?? sign on, ?? bonus, ?? refresher
=> $45-60w total cash per year

L5 Unicorn startup: 16-18w base, ~1M RSU (4yrs), ?? sign on, 0 bonus (
startup穷啊,没cash), ~10w stock refresher (4yrs) => $16-18w total cash per
year,加上股票有可能暴发,有可能是纸…

L5 unicorn startup 的1M 股票,这个unicorn跟FLAG抢人有多desperate… 反正我经
手过L6 $1.6M的offer,同时期L5 $1M也不惊讶了。看你negotiate的能力,60W-1M还是
都有可能的。

当然,大家要记住,这个1M完全可能变纸啊,所以……并木有什么鸟用

L3 Unicorn startup: 10-12w base, ~20-30w RSU (4yrs), ?? sign on, 0 bonus, ~3
-5w stock refresher (4yrs) => ~$12w total cash per year,加上股票有可能暴发
,有可能是纸…

同个级别package上下浮动个十几万,哪怕同一个公司,都是很正常的。

Manager track和同级的IC是一样的(所以完全存在我组里的人比我工资高的状况?_?)

一般到L5就可以开始原地踏步了,self push的人无上限。不是一定努力上进的话,停
在L5 L6是比较常见的range吧。

四年后呢,除了每年发的Stock refresher, 没其他了吗?因为股票refresh以及这几年
科技股大涨, 4年后哪怕不promote收入也会更高,可以升职啊,加薪加股票。而且湾
区这地方四年跳槽一次已经算很久了。

每个half recruiter都会给hiring managers写个report review过去发的offers,还有
给组里的人涨工资的时候也会有业界guideline,我的数据是有统计意义的。

当然,我们统计的对象是同类型的公司,非硬件,非金融,等等等等

苹果家软工也是100% rsu refresher,就是每年refresh rsu 大概是一倍左右base。
senior的base和FLG的L6低端差不多,大概18-20万。苹果家硬工不清楚。

所以苹果家软工跳FLG总觉得有些鸡肋,只有L6差不多能beat,但是FG又不轻易给L6。
。。

以我司的情况来判断,大概就是L3 15-20W,L4 20-30W这个range吧,看你的面试表
现和competing offer的多少
而且今年FB据说招得不多,大概L3 L4会受影响

现在应该只有很高级别(L7+)才有可能60w以上股票每年了。Senior director or VP
这样的,没上限,几个米一年的也不少。 反正我级别不够也看不见…

好的时候 股票赶上大涨 本来一年值15万的股票翻两倍三倍光股票就超贫困线了 但不
好的时候 股票变成纸也有可能 而且去flag都是前四年钱多 之后股票跟不上也降
package. 得靠换工作才能保证这个package 值,也很辛苦。关键是湾区房价太高了,
挣这么多先交30,40%的税,再付月供,没剩多少。真的买3,4米房子的都是靠股票买
的,靠工资没戏

另外咱中国人的高管其实并不少,package也是million级的,只是我也不会自讨没趣去
问人家具体数字……这种时候也不是考虑多少钱,而是发展空间,团队前途,甚至是自
己在业界的名誉了。

总结:对于6年以上经验performance好的牛人,单人40-60w的总包裹是完全可能的,不
过光cash估计就20-30w,而且选择很多抢得凶。new grads大概也就是15-20w左右的总
包裹,什么一毕业就40w,要么是超级牛人,要么是去了撞大运的startup(IPO以后股
票暴涨),在成熟稳定公司是不太可能的。

就酱。股票变数太大,所以大家还是按base生活。。。

公司内部各种各样的俱乐部小团体特别多,很多是公司出钱出力sponsor的,不难找到
志同道合的年轻人一起玩,多处处说不定就对上眼了。我家这已婚的还参加了烹饪,攀
岩,骑车,风帆,钢琴,健身等各种小组呢。周围几个公司经常有串场参加活动的。感
觉就和大学里面差不多,单身的男女约会也可以去各食堂。

在FLAG大约20分钟的地方, 租的房子1600尺是6000/月, 如果去城里, 能找到4000
的公寓, FLAG有很多班车, 上班时间灵活, 如果一个人挣28万, 去除40%的税, 还
有17万, 交5万房租的话, 还有12万。 很多其它的地方税前工资就是一个人12万。

湾区双职工一年40-50万确实是普遍存在的,资深双马40岁以上的,70-80万也不少。反
而50岁以上的老人比正当盛年的要拿钱少,工作难找,都在养老公司混着。好在这批人
早就完成了原始积累,倒是也不怕裁。

湾区就是这样的,财富热钱涌入

看看Los Altos现在三百万这个级别的房子都不好买就知道了,我的意思是之前三米还
可以买到房子的,现在至少要四五米了。大家收入越来越高了,Los Altos因为离高大
上公司近嘛,成功码工扎堆,所以才贵, 在大城市要想不commute都是要花大价钱的。
两个人50w的很常见,一个人上50w的不多,但是也有,还有很多看起来工资一般但是进
公司早,股票,ipo各种发了小财的,来看看湾区的房价就知道了,1-2m的房子就是绝
对大部分人可以负担的,在湾区住了很多年了, 真正有钱一掷千金的阶层还是本地old
money和国内来的壕还有做生意的本地人, 这些人才是购买3米以上SFH的主力军。双
码农家庭收入50万是很正常, 可是这种家庭在整个湾区的比例也不能说是普遍啊。更
多是高薪单码农, 老婆是主妇家里蹲还有可能是搬运过来的。何况所谓的股票收入部
分, 不cash out也就是账面上的收入啊。 也别死盯着annual household income 看,
还是disposable income高的人更厉害, 本身家底厚房贷少的, 随意开销大一点, 生
活品质比死挣工资还房贷的更好。 还有做生意的家里的房子都是买地然后自己修,花
一百万搞一个花园,装修都几百万美金。最重要的是 大家保持平常心好吗?天天比来
比去 一定要知道别人赚多少过什么样的生活累不累啊

最后,本人7年经验管理层,离开FLAG来现在的startup也好几年了,如果光看公司
valuation,我自己一年收入轻松beat贫困线。
但是事实是,其中绝大部分是未上市的股票。如果公司挂了,那我的cash收入连FLAG的
L3 L4可能都不如………………………然后就真的是操着卖白粉的心,挣着卖白菜的钱
了……
所以只要公司有点啥负面新闻都会睡不着觉……
然后每天在家跪求老公包养……

如果别的公司的话,行业不同很多。我以前公司,1千多人,公司前十的人工资1百万整
,奖金4百万左右,公司股票(不上市)分红5百多万,招人全靠承诺做得好分股票。

老公手下几十个人,从二三十万到四五十万,都有,包括股票。如果股票涨,年收入会
更高。即使刚毕业的新手,一般也要二十万了,否则根本招不到人。

湾区就是这样,不错的公司都抢人很厉害,特别是特殊红火方向的码工。现在聊最多的
就是如何抢到人。

03/2017 Facebook E6 Experienced Master Offer almost 400K Menlo Park

Facebook Level: E6
Education: Master
Location: Menlo Park

Experience: 5+ Years after Master
Competing Offer: N/A
Base: 200K
Bonus: 20%
Equity (over 4 years): 600K worth of stocks / 4 years
Sign on bonus: N/A
Expected income: 390K/yr

Analysis

E6, RSU CAN be higher if there’s competing offer. But not a bad offer at all!

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.

 

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);
    }
 
};