一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 4138|回复: 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
           D            E                     F.鐣欏璁哄潧-涓浜-涓夊垎鍦

ABD. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
ABE
ACF

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

. Waral 鍗氬鏈夋洿澶氭枃绔,--A, _B, D. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
__A,_B,__E

Space and time complexity (worst case)

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
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,
-google 1point3acresDHT, 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 | 显示全部楼层
分享vertical oder 不用MAP (使用vector), 一次循环O(N)解法
===========================================
void insertNode(Node *root, vector<vector<Node *>> &level, int d)
{
    if (d == level.size())
    {
        vector<Node *> one_level;
        one_level.push_back(root);
        level.push_back(one_level);
    }
    else
    {
        level[d].push_back(root);
    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

void genVertical(Node *root, vector<vector<Node *>> &pos, vector<vector<Node *>> &neg, int dis)
{
    . From 1point 3acres bbs
    if (!root) return;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    if (dis >= 0)
        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);

    for (int i = neg.size()-1; i >= 0; i--)
    {
        for (auto a : neg[i])
            cout << a->key << ",";
        cout << endl;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }-google 1point3acres

    for (auto p : pos)
    {
        for (auto a : p). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            cout << a->key << ",";
        cout << endl;
    }
}
回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

 楼主| fatfrog 发表于 2015-10-12 12:53:11 | 显示全部楼层
cjlm007 发表于 2015-10-12 12:42
赞,祝offer。楼主什么背景?

谢谢了! 可惜已跪,背景不好,EE转行, 继续努力
回复 支持 反对

使用道具 举报

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什么意思吗. more info on 1point3acres.com

Follow up: Print the based on column
. from: 1point3acres.com/bbs
--A, _B, D. visit 1point3acres.com for more.
__A,_B,__E

Space and time complexity (worst case). visit 1point3acres.com for more.

回复 支持 反对

使用道具 举报

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

简单说来就是:
1. 上来故意不说清楚要multi-time readN, 当然我也大意没澄清以为会引申,但是在我先说readN算法后后他说好, 你可以写了,等我写完让我run case, 时间耗差不多了突然说你这个不对,读multi-time你的不work,尼玛,你之前也没说multi-time,我写之前给你讲了一遍你当时怎么不说不work,很深沉的故意浪费时间,写完 readN Multi time 还剩15分钟
2. 第二题我一看挺熟说5分钟就能写完,他坚持说不用,就让我说算法我先说. 1point3acres.com/bbs
1:hashmap 存 http://www.geeksforgeeks.org/pri ... rtical-order-set-2/
刚说道hashmap 他就打断,不许用hashmap,我说你要不要听我说完?丫直接一句不用我懂
然后我说
2: http://www.geeksforgeeks.org/print-binary-tree-vertical-order/  iterate一遍找到最大最小column, 丫马上有还没说完就打断就一遍iterate 不能找最大最小column
就是我会的都不能用,然后我就跟他说怎么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. 1point3acres.com/bbs
可以解释第一题follow up什么意思吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Follow up: Print the based on column

表达能力不是很好,多包涵. 1point 3acres 璁哄潧
就是如果按列看树
例子里, 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
...
. From 1point 3acres bbs
没说清楚,
和这题一样,就是没有 *. 1point 3acres 璁哄潧
https://leetcode.com/problems/expression-add-operators/
回复 支持 反对

使用道具 举报

calalia 发表于 2015-10-18 06:57:40 | 显示全部楼层
fatfrog 发表于 2015-10-11 23:53. Waral 鍗氬鏈夋洿澶氭枃绔,
简单说来就是:
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, 2016-12-11 06:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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