03/2017 Snapchat Senior Offer San Francisco 340K After IPO

Snap Level: Senior
Education: Master
Location: San Franciso

Experience:Master + 5 years
Competing Offer: Facebook
Base: 160K
Bonus: 15% ~ 20%
Equity (over 4 years): 600K worth
Sign on bonus: N/A
Expected income: 340K+/yr

Analysis

Facebook offer is very good for competing. Snap has the potential to be another big target.

03/2017 Google T3 Entry Level Master Offer 170K Mountain View

Google Level: T3
Education: Master
Location: MTV

Experience:Master (intern but no full time experience)
Competing Offer: Amazon
Base: 120K
Bonus: 15%
Equity (over 4 years): 135  shares = 820*135 / 4 years
Sign on bonus: 20K
Expected income: 170K/yr

Analysis

Amazon offer (especially benefits) doesn’t even come close to Google or Facebook. Not a very effective competing offer.

Ivy League, other top colleges, top US corporations are biased against Asian, using race-based quotas or caps to keep down the number of Asians

It’s known Asian immigrants are model minority. They value education, work hard; they obey the law, their families have strong bonds. A special group of people are afraid, they are trying everything to diminish Asian’s opportunity to achieve higher. In my company (internet computer software), their are special hire quota called “diversity hire”. People from non-Asian background got hired to the company, in a few years they are promoted to “senior engineer” with code output far less than average junior Asian software engineer. More astonishing, they have systematically created a network that makes it very hard for Asian students to get into the higher education. Here is just a tip of the iceberg of this kind of system:

 

Princeton is scrambling to prevent the release of a trove of its most sensitive admissions documents, including individual student files and information about how the school judges and selects its freshman class.

The data was provided to the Education Department as part of a years-long investigation, making it subject to Freedom of Information Act requests. If those requests are successful and the documents are made public, it could upend the world of Ivy League college admissions, shining an uncomfortable light on what is usually a clandestine process. It would also have the potential to deal a serious blow to affirmative action efforts by elite colleges.

The group pushing to obtain the information is Students for Fair Admissions, an anti-affirmative action group whose founder and president, Edward Blum, has worked for decades to dismantle laws based on race and ethnicity, bringing several successful cases to the Supreme Court.

More from Buzzfeed:
Trump’s Critics Are Letting The Bigger Russia Story Slide
Planned Parenthood’s President Says Ivanka’s Silence On Republican Health Care Bill Is “Deafening”
A Fight Over A Bison Herd In Montana Sets Retired Rangers Against Tribes

Students for Fair Admissions hopes the information will reveal what it has long alleged: that Ivy League and other top colleges are biased against Asian applicants, using race-based quotas or caps to keep down the number of Asians they admit to their tiny, highly selective classes each year.

The cache of “highly sensitive data about applicants,” as Princeton calls it, now sits in the hands of the Education Department, which collected the information over the course of almost seven years as part of an internal compliance review within its Office of Civil Rights. Princeton is suing to prevent the Department from releasing it.

“The fact that Princeton has sued suggests that Princeton has something very revealing it wants to hide about its admissions,” Blum said.

The university insists the government promised to keep much of the information confidential when it was first turned over, and has taken the highly unusual step of filing a “reverse FOIA” — a request for information not to be released. It says the admissions data violates the Trade Secrets Act and, if released, would seriously damage its image.

Princeton is one of several elite colleges embroiled in battles with Students for Fair Admissions, which has filed a slew of lawsuits and complaints against schools like Harvard, the University of North Carolina-Chapel Hill, Yale, Dartmouth, and Brown. The complaints allege that the schools unfairly discriminate on the basis of race in their admissions process — particularly against Asian-Americans.

The Education Department did its own investigation into the allegations against Princeton, the lawsuit says, and concluded the university didn’t discriminate on the basis of race.

But even if it isn’t incriminating, the data collected for that investigation is likely to be extremely controversial in the obsessive world of elite college admissions.

“Everyone want to see what goes on behind the curtain,” said Mimi Doe, the president of Top Tier Admissions, a college admissions advising company. While it is generally known that top schools give applicants numeric grades and rankings, Doe said, “We haven’t seen the qualitative piece of this — the unspoken quotas. What will probably come out is that, for years, colleges have been — just as they did in the 1940s with Jews — saying, ‘we don’t want this person, because this is a stereotypical Asian applicant.’ These kids are penalized because of their race.”

The admissions data, Doe says, has serious potential to lay bare some of the Ivy League’s other unsavory admissions practices, too, like the preference given to children of alumni and celebrities, or the way that even privileged applicants can be given preference based on race or their status as first-generation students.

“It won’t play well for Princeton when that comes out,” Doe said. “But it’s not illegal.”

In 2015, BuzzFeed News reported that a group of Stanford students had found what was essentially a loophole in federal law allowing students to view their own college admissions files.

Elite schools were flooded with requests from curious students desperate to find out what admissions officers had said about them — an onslaught that forced schools like Yale to begin purging their admissions archives, hoping to protect any more files from being released.

The original post is titled

Princeton is scrambling to block its admissions records from being released

and published here:

http://www.cnbc.com/2017/03/24/princeton-is-scrambling-to-block-release-of-admission-records.html

 

转自:飞洋在线

常春藤学校一直以来对公众隐瞒他们的大学新生录取标准,特别是在接收亚裔学生过程
中是否存在歧视,但这个秘密有可能要被公之于众。

在一项历时7年的调查中,普林斯顿大学被迫把大批新生录取资料提交给教育部。根据
“公开信息法案”,媒体和公众有权要求查看这些资料。如果这样的话,普林斯顿和其
他藤校近乎黑箱操作的新生录取标准就会被曝光。

众所周知,亚裔学生进入顶尖大学要比其他学生困难得多。各方面出类拔萃的亚裔常常
被藤校拒绝,而成绩和社会活动远不如自己的其他族裔却没有问题。很多人认为这是大
学暗中采取的种族配额标准(Race-Based Quota),但是多年来常春藤学校一直否认。
如果普林斯顿的资料曝光的话,所有的指责和辩解可以瞬间真相大白。这对大学录取时
的AA政策(区别对待各族裔录取)也会带来致命一击。

虽然有AA保护,大学录取依然不允许种族配额。最高法院1978年的判决明确了这一点,
2013年和2016年两次Fisher案再次表明,只有当 “既有的,合理的,无关种族的录取
标准” 无法满足有限的多元化目标时,才能在严格监管的情况下适当考虑种族,但是
设定种族配额依然是违宪的。

普林斯顿大学已经提交诉讼要求教育部不要公开这些信息。

反AA的“公平入学”组织创始人和主席Edward Blum几十年来一直要求法律废除基于种
族的AA,他有好几起诉讼案打到了高院。公平入学组织希望曝光常春藤学校对亚裔申请
者的歧视,他们近年来起诉了普林斯顿等大学。其他被告的大学包括:哈佛,耶鲁,布
朗, 达特茅斯,北卡。

Blum说:“普林斯顿状告教育部,这本身就说明他们试图掩藏什么。”

奥巴马治下的教育部经过调查,得到的结论是没有歧视,但是公众并不认可。奥巴马总
统和民主党政客支持AA,这点是公开的。但是新任教育部长Betsy DeVos反对AA,她如
何对待普林斯顿的材料倒是值得期待。

Mimi Doe,一家从事大学申请的公司总裁说:“每个人都想知道幕后的故事。众所周知
,很多顶级大学都给申请者排名打分,但是我们从来没见过确切的内容 – 那个不言而
喻的配额。很有可能,就像40年代大学对待犹太人那样,仅仅因为种族因素,就不录取
某个亚裔孩子。”

数据分析
2005年,普林斯顿大学社会学教授Thomas J. Espenshade 和 Chang Y. Chung发表了一
份调查结果,以SAT (大学入学考试,旧版1600分)成绩为例,比较了各族裔在大学录
取中被区别对待的情况:

白人 (非体育特招或校友子女): 0 (基准)
黑人: +230
西裔: +185
亚裔: –50
运动员: +200
校友子女: +160
2009年,Espenshade与人合作出版了一本书,再次发表数据:如果一个亚裔孩子进入某
个顶级私立大学需要SAT 1550分的话,白人只需1410,而黑人只需1100。综合考虑成绩
,背景和体育特长等因素,作者发现和亚裔孩子相比,白人,西裔和非裔进入同一个大
学的机会分别是亚裔孩子的3倍,6倍,和15倍。

美国医科大学协会发布了如下数据,比较各族裔在各个成绩段中被医学院录取的比例。
不出所料亚裔录取率远远低于其他族裔。也就是说,一个亚裔孩子想进入医学院要比其
他族裔多付出太多。这不是政治,也不是文艺,更不是社交,这是要上手术台救死扶伤
的,不应该择优录取吗?假如有一天你需要做心脏手术,你希望主刀的大夫是一路靠AA
才勉强过关的吗?

诚然,大学录取不应该唯成绩论,但是一个亚裔,仅仅因为他的肤色,就要多付出数倍
的心血,这本身就是一种歧视。加州的SCA-5和最近的亚裔细分法案让很多华人醒悟,
原来民主党一直标榜的“人人平等”是如此的不堪一击。这也是很多华人和亚裔转而支
持共和党的一个重要原因。2016年共和党大获全胜,但是维权之路并不平坦。与大家共
勉。

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.

 

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