一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1458|回复: 5
收起左侧

Facebook第一次电面 发题攒rp

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

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

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

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

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();
        int ret =-1, max = INT_MIN;
        int count=0;
        for(int i=0; i<len; i++){. 鍥磋鎴戜滑@1point 3 acres
                if(arr==max){
                        count++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        srand(time(NULL));
                        int judge = rand()%count;. visit 1point3acres.com for more.
                        if(judge==0){. more info on 1point3acres.com
                                ret = i;
                        }
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                else if(max==INT_MIN || arr>max){
                        max = arr;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        ret = i;
                        count=1;
                }
        }
        return ret;. 鍥磋鎴戜滑@1point 3 acres
}


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

    int check(char a, char b){
-google 1point3acres        return ((a=='1') || (a=='2' && b<='6'))?1:0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }

    int numDecodings(string s) {
        int len=s.length();
        if(len==0). more info on 1point3acres.com
            return 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if(len==1). 1point3acres.com/bbs
            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];. 1point 3acres 璁哄潧
        }
        return dp[len-1];
    }
};


保佑onsite啊。。


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

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
mmliu 发表于 2015-9-14 16:56:00 | 显示全部楼层
翻了一圈儿其他关于 reservoir sampling 的帖子,可算是明白这题的意思了,留个记录给有需要的同学参考吧。

randomly return the index of max element in array

最简单的解法当然是跑一遍array,把max elements的index记录到list中,然后random一下list,即可满足题意。

这样是O(N) time, O(N) space. 鍥磋鎴戜滑@1point 3 acres
. visit 1point3acres.com for more.
follow up: 如果要求O(1)space呢?(或者说如果是个infinite array呢)

. 鍥磋鎴戜滑@1point 3 acres这时候不能记录 index 了,只能在遍历数组时,记录一个当前遇到的最大值:max,以及最大值的个数:counter
同时维持一个 ret 变量,每次遇到 max 时,以 1/count 的概率更新 ret 为当前位置。
.1point3acres缃
这样最后能保证 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 | 显示全部楼层
谢谢楼主分享. 第一题的思路我觉得用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.
. visit 1point3acres.com for more.
第一次出现的最大值,那就是他自己了, 之后加入出现同样等于最大值的值,就用1/count, count=当前该最大值出现的次数。
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-3-19 22:17:32 | 显示全部楼层
linmeng44 发表于 2015-3-19 08:30
谢谢楼主分享. 第一题的思路我觉得用reservior sampling的思路可能更容易理解一点. 恭喜楼主了
. Waral 鍗氬鏈夋洿澶氭枃绔,
嘻嘻~~就是resevior sampling类似的题~我也是之前刚好看到过类似的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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