一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 4942|回复: 27
收起左侧

Facebook Onsite

[复制链接] |试试Instant~ |关注本帖
fatfrog 发表于 2015-10-12 12:38:08 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Facebook - 猎头 - Onsite |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x

1.
a.Binary tree print all pathes from root to leaf
                                  A
                  B                       C. From 1point 3acres bbs
           D            E                     F
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
ABD
ABE
ACF

Computation complexity (space/time)
Follow up: Print the based on column

--A, _B, D
__A,_B,__E. 1point3acres.com/bbs

Space and time complexity (worst case)-google 1point3acres

b.1 , 2,  5, 8, 9 , "+" "-" "" target 50
Print all possible way to reach 50
How to Prune

2.
Behavior, why FB, which facebook feature do you  like best, how to improve it.1point3acres缃
Your work, challenges, bugs.
10 mins left Stock1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

3.
Status update and search system design:
Status example: I eat a pie, I bouth a car
Search eat and pie  return I eat a pie
Search a or bought return  only search in  last N day
Start with the architecture, based on the given number of users, number of status each day
Estimate QPS, the storage, DB schema
  
Invert Index data structure for search How to implement invert index, data structure 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Index update function how to update retire the expired data
Data is too large to fit into memory, how to handle,
DHT, How to hash the data( hash the words or id) , pro, con

4.
Read4 multi times
Print a Binary Tree in Vertical Order. From 1point 3acres bbs



补充内容 (2015-10-12 12:51):
已跪. 第四轮被一个三哥用下流的手段黑(真的挺下流的),我当然还是相信不是所有阿三都黑老中,不过这次碰到的是我见过最黑的一个。可惜没当天complain, 不过我还是在悲剧后写了信complain不能让丫再害人

评分

2

查看全部评分

本帖被以下淘专辑推荐:

tellmarbray 发表于 2015-10-18 06:18:43 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
分享vertical oder 不用MAP (使用vector), 一次循环O(N)解法.鐣欏璁哄潧-涓浜-涓夊垎鍦
===========================================
void insertNode(Node *root, vector<vector<Node *>> &level, int d)
-google 1point3acres{ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    if (d == level.size()). more info on 1point3acres.com
    {
        vector<Node *> one_level;. 1point3acres.com/bbs
        one_level.push_back(root);
        level.push_back(one_level);
    }
    else. 1point 3acres 璁哄潧
    {
        level[d].push_back(root);
    }
}

void genVertical(Node *root, vector<vector<Node *>> &pos, vector<vector<Node *>> &neg, int dis)
{
   
    if (!root) return;

    if (dis >= 0).1point3acres缃
        insertNode(root, pos, dis);
    else
        insertNode(root, neg, (-dis) - 1);

    genVertical(root->left, pos, neg, dis-1);
    genVertical(root->right, pos, neg, dis+1);
}

void printVerticalOrder(Node* root)
{
    vector<vector<Node *>> pos, neg;
    genVertical(root, pos, neg, 0);
.鏈枃鍘熷垱鑷1point3acres璁哄潧
    for (int i = neg.size()-1; i >= 0; i--)
    {
        for (auto a : neg[i])
            cout << a->key << ",";
        cout << endl;. more info on 1point3acres.com
    }
. 1point3acres.com/bbs
    for (auto p : pos)
. 1point3acres.com/bbs    {
        for (auto a : p)
            cout << a->key << ",";
        cout << endl;
    }. 1point 3acres 璁哄潧
}
回复 支持 2 反对 0

使用道具 举报

 楼主| fatfrog 发表于 2015-10-19 04:31:38 | 显示全部楼层
关注一亩三分地微博:
Warald
sonicgu 发表于 2015-10-18 23:19
lz实力还是挺好的,试试其他家,肯定有机会!顺便问下,那道加+,-号的题,如何剪枝呢,想了想,似乎没有很 ...
. 鍥磋鎴戜滑@1point 3 acres
我当时就是被问了一下没让implement剪枝,
1 , 2,  5, 8, 9 +,-,""
                  1
            +    -     ""
把问题看成个树,number是节点,每个节点下面有三个branch, +,-,""  。 我当时就说先算‘+’下面的子树可以算出一个range, 最大可组成的数字和最小可组成的数字, 然后在计算‘-’ 下面的子树是可以通过这个range剪枝。也没被追问。
回复 支持 1 反对 0

使用道具 举报

cjlm007 发表于 2015-10-12 12:42:45 | 显示全部楼层
赞,祝offer。楼主什么背景?
回复 支持 反对

使用道具 举报

 楼主| fatfrog 发表于 2015-10-12 12:53:11 | 显示全部楼层
cjlm007 发表于 2015-10-12 12:42
赞,祝offer。楼主什么背景?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢了! 可惜已跪,背景不好,EE转行, 继续努力
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

wyx63953 发表于 2015-10-12 13:03:49 | 显示全部楼层
赞,祝楼主offer。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-10-12 13:15:21 | 显示全部楼层
lz说说怎么个下流法。。。
回复 支持 反对

使用道具 举报

hylldxm 发表于 2015-10-12 13:32:56 | 显示全部楼层
据说最近f家都不招fresh了,楼主走到onsite已经和棒了,以你的能力肯定能找到不错的,不过老印确实太可恶!
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-10-12 13:50:13 | 显示全部楼层
可以解释第一题follow up什么意思吗

Follow up: Print the based on column

--A, _B, D. visit 1point3acres.com for more.
__A,_B,__E.鏈枃鍘熷垱鑷1point3acres璁哄潧

Space and time complexity (worst case)

回复 支持 反对

使用道具 举报

 楼主| fatfrog 发表于 2015-10-12 13:53:11 | 显示全部楼层
blactangeri 发表于 2015-10-12 13:15
lz说说怎么个下流法。。。

简单说来就是:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. 上来故意不说清楚要multi-time readN, 当然我也大意没澄清以为会引申,但是在我先说readN算法后后他说好, 你可以写了,等我写完让我run case, 时间耗差不多了突然说你这个不对,读multi-time你的不work,尼玛,你之前也没说multi-time,我写之前给你讲了一遍你当时怎么不说不work,很深沉的故意浪费时间,写完 readN Multi time 还剩15分钟
2. 第二题我一看挺熟说5分钟就能写完,他坚持说不用,就让我说算法我先说. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1:hashmap 存 http://www.geeksforgeeks.org/pri ... rtical-order-set-2/
刚说道hashmap 他就打断,不许用hashmap,我说你要不要听我说完?丫直接一句不用我懂.1point3acres缃
然后我说
2: http://www.geeksforgeeks.org/print-binary-tree-vertical-order/  iterate一遍找到最大最小column, 丫马上有还没说完就打断就一遍iterate 不能找最大最小column. 1point3acres.com/bbs
就是我会的都不能用,然后我就跟他说怎么maintain一个array中间插入对应的column. 实在不知道还有啥别的办法了,丫到最后很满意的说,没时间了,算了吧! 感觉就是想要废你,用容易的题一样可以废你
回复 支持 反对

使用道具 举报

JimLuo 发表于 2015-10-12 13:53:37 | 显示全部楼层
多谢楼主分享,楼主能onsite还是很厉害的
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-10-12 13:58:08 | 显示全部楼层
b.1 , 2,  5, 8, 9 , "+" "-" "" target 50
Print all possible way to reach 50. 1point3acres.com/bbs
How to Prune

如果有了减号  "-" 那不是有无数种可能吗 100个1减50个1 ,1000个1减950个1 。。。
回复 支持 反对

使用道具 举报

 楼主| fatfrog 发表于 2015-10-12 14:01:19 | 显示全部楼层
LifeGoesOn 发表于 2015-10-12 13:50
可以解释第一题follow up什么意思吗

Follow up: Print the based on column

表达能力不是很好,多包涵. 1point3acres.com/bbs
就是如果按列看树
例子里, A在column3, B在column2, D在column1, 打印时在A前加两个space, B前一个space, D前面0个space
注意的是E和A属于同一column.
回复 支持 反对

使用道具 举报

 楼主| fatfrog 发表于 2015-10-12 14:03:36 | 显示全部楼层
LifeGoesOn 发表于 2015-10-12 13:58
b.1 , 2,  5, 8, 9 , "+" "-" "" target 50.鐣欏璁哄潧-涓浜-涓夊垎鍦
Print all possible way to reach 50. 1point3acres.com/bbs. visit 1point3acres.com for more.
...

没说清楚,. more info on 1point3acres.com
和这题一样,就是没有 *
. from: 1point3acres.com/bbs https://leetcode.com/problems/expression-add-operators/
回复 支持 反对

使用道具 举报

calalia 发表于 2015-10-18 06:57:40 | 显示全部楼层
fatfrog 发表于 2015-10-11 23:53
简单说来就是:
1. 上来故意不说清楚要multi-time readN, 当然我也大意没澄清以为会引申,但是在我先说r ...

太可怕啦~~超喜欢Hashmap~ 能用的都不让用 这是要多边边角角的方法啊~~
╮(╯▽╰)╭ 我觉得用复杂度低的方法优化啦就可以了嘛嘛嘛嘛嘛嘛
回复 支持 反对

使用道具 举报

 楼主| fatfrog 发表于 2015-10-18 07:14:21 | 显示全部楼层
tellmarbray 发表于 2015-10-18 06:18
分享vertical oder 不用MAP (使用vector), 一次循环O(N)解法
========================================== ...

谢谢!当时没想到用两个vector分别存左边和右边,陷入思维定式了。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-10-18 09:41:53 | 显示全部楼层
fatfrog 发表于 2015-10-12 13:53
简单说来就是:
1. 上来故意不说清楚要multi-time readN, 当然我也大意没澄清以为会引申,但是在我先说r ...

不能忍。。。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-18 10:31:33 | 显示全部楼层
楼主, 第一题follow up 怎么做的  Follow up: Print the based on column
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-10-18 23:19:51 | 显示全部楼层
lz实力还是挺好的,试试其他家,肯定有机会!顺便问下,那道加+,-号的题,如何剪枝呢,想了想,似乎没有很好的做法
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-10-19 02:06:37 | 显示全部楼层
阿三上来就能感到或多或少的恶意,小/老白和国人一般都会给点提示,如果你在思考也不会随意打断你。阿三基本所有的都是不给提示,有的会顺着你的错误思路跟你讨论把你引到坑里然后填土埋好,还有的不断质问你,对你保持强大的心理压力
回复 支持 反对

使用道具 举报

fromemories1 发表于 2015-10-19 02:23:55 | 显示全部楼层
订~~~~~~~~~~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-2-24 03:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表