推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

Facebook第一次电面 发题攒rp

[复制链接] |试试Instant~ |关注本帖
zhuol 发表于 2015-3-17 00:21:56 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
第一题: 给一个全是数字的数组,随机返回0到当前位置中最大值得坐标
比如【1,2,3,3,3,3,1,2】
在最后一个2的时候有4个3都是最大值,要按1/4的概率返回其中一个3的index
public int findMax(vector<int> &arr){.鐣欏璁哄潧-涓浜-涓夊垎鍦
        int len = arr.length();. more info on 1point3acres.com
        int ret =-1, max = INT_MIN;
        int count=0;. from: 1point3acres.com/bbs
        for(int i=0; i<len; i++){
                if(arr==max){
                        count++;
                        srand(time(NULL));
                        int judge = rand()%count;
                        if(judge==0){
                                ret = i;
                        }
                }. From 1point 3acres bbs
                else if(max==INT_MIN || arr>max){
                        max = arr;. from: 1point3acres.com/bbs
                        ret = i;
                        count=1;
                }
        }
        return ret;. 1point3acres.com/bbs
}. from: 1point3acres.com/bbs


第二题: leetcode原题 decode ways
dp问题
class Solution {
public:
    int check(char a){
        return a=='0'?0:1;
    }

    int check(char a, char b){
        return ((a=='1') || (a=='2' && b<='6'))?1:0;
    }

    int numDecodings(string s) {
        int len=s.length();.鐣欏璁哄潧-涓浜-涓夊垎鍦
        if(len==0)
            return 0;. From 1point 3acres bbs
        if(len==1). 1point 3acres 璁哄潧
            return check(s[0]);
.鐣欏璁哄潧-涓浜-涓夊垎鍦
        vector<int> dp(len, 0);
        dp[0]=check(s[0]);
        dp[1]=(check(s[0])&check(s[1]))+check(s[0], s[1]);

        for(int i=2; i<len; i++){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            if(check(s)==1)
                dp+=dp[i-1];
            if(check(s[i-1], s)==1)
                dp+=dp[i-2];
        }
        return dp[len-1];
    }. 1point3acres.com/bbs
};

. 1point3acres.com/bbs
保佑onsite啊。。


补充内容 (2015-3-17 03:39):
已拿到onsite :)

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
mmliu 发表于 2015-9-14 16:56:00 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
翻了一圈儿其他关于 reservoir sampling 的帖子,可算是明白这题的意思了,留个记录给有需要的同学参考吧。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

randomly return the index of max element in array. 1point 3acres 璁哄潧

最简单的解法当然是跑一遍array,把max elements的index记录到list中,然后random一下list,即可满足题意。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

这样是O(N) time, O(N) space

follow up: 如果要求O(1)space呢?(或者说如果是个infinite array呢)

这时候不能记录 index 了,只能在遍历数组时,记录一个当前遇到的最大值:max,以及最大值的个数:counter
同时维持一个 ret 变量,每次遇到 max 时,以 1/count 的概率更新 ret 为当前位置。

这样最后能保证 ret 是随机的一个max的index么,可以的,比如:

【1,2,3,3,3,3,1,2】
.鐣欏璁哄潧-涓浜-涓夊垎鍦
可以用递推证明,比如遇到第k个max时,假设它被返回的概率是随机的,即1/k,那么第k + 1个max出现的时候,按我们的替换方式,有 k/k+1的可能k + 1不会被选中,也就是第k个max 幸存的概率为 被选中的概率*不被k+1换走的概率 = 1/k * k/(k + 1) = 1/(k + 1)

回复 支持 3 反对 0

使用道具 举报

linmeng44 发表于 2015-3-19 08:30:06 | 显示全部楼层
关注一亩三分地微博:
Warald
谢谢楼主分享. 第一题的思路我觉得用reservior sampling的思路可能更容易理解一点. 恭喜楼主了
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-3-19 14:49:07 | 显示全部楼层
第一题没看懂 可以解释下吗
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-3-19 22:16:02 | 显示全部楼层
ryuichist 发表于 2015-3-19 14:49
第一题没看懂 可以解释下吗

Yes Sir..

就是打比方说你有个数组[1,2,3,3,3,3,3]
然后你就一个个往后扫嘛,扫到某一个的时候要求等概率返回其中一个最大值,比如说扫到[1,2 这里,最大值是2,就他自己一个,就直接返回了,反正是100%的概率, 但是比如扫到了[1,2,3,3,3,3]这里的时候, 最大值3, 并且你现在扫出来了4个3, 于是乎你就要按1/4的概率返回其中的一个3.. 鍥磋鎴戜滑@1point 3 acres

第一次出现的最大值,那就是他自己了, 之后加入出现同样等于最大值的值,就用1/count, count=当前该最大值出现的次数。
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-3-19 22:17:32 | 显示全部楼层
linmeng44 发表于 2015-3-19 08:30
谢谢楼主分享. 第一题的思路我觉得用reservior sampling的思路可能更容易理解一点. 恭喜楼主了

嘻嘻~~就是resevior sampling类似的题~我也是之前刚好看到过类似的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-28 05:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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