一亩三分地论坛

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

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

youtube 电话面试 刚刚面完

[复制链接] |试试Instant~ |关注本帖
zhanglin6261 发表于 2015-1-22 06:05:18 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other

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

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

x
刚刚面完,发出来攒攒人品。和2-sum等等各种sum很像,只不过要求<=某个值,然后返回符合要求的pair数。在google doc上写的,木有缩进很蛋疼,直接上题了。代码是我当时写的,最后一个k-tuple的感觉没什么时间了写的比较慌,也不知道对不对
[7, 2, 5, 1, 6, 3], X=5

Count the number of distinct pairs such that their sum is <= X? 3

int pairs(vector<int> num, int x){
        int count = 0;
        for(int i=0;i<num.size();i++){
        for(int j=i+1;j<num.size();j++){
                if(num+num[j] <= x){
        count++;
}
}
}
return count;
}

[1, 2, 3, 5, 6, 7]
i        j            
i=0, j=2: 2
i=1

int pair(vector<int> num, int x){
        sort(num.begin(),num.end());
        int i = 0;
        int j = num.size()-1;
        int count = 0;
        while(i<j){
                if(num+num[j] > x){
        j--;
}
else if(num+num[j] <= x){
        count += j-i;
        i++;
}

}
return count;
}


(a,b,c) -> a+b+c<=X
a+b <= X
a+b <= X-c

int pair(vector<int> num, int x){
        sort(num.begin(),num.end());
        int k = 0;

        int count = 0;
        if(num.size()<3){
        return count;
}
while(k<num.size()-2){
        int target = x - num[k];
        int i = k+1;
                int j = num.size()-1;
                while(i<j){
                        if(num+num[j] > target){
                j--;
}
else if(num+num[j] <= target){
                count += j-i;
                i++;
}
}
k++;
}
       
return count;
}

k-tuples?
int k, l, m;
int i, j;

int count = 0;
int pair(int k, vector<int> num, int x, int s){
        int count = 0;
if(k == 2){
                int i = s;
                int j = num.size()-1;
                int c = 0;
while(i<j){
                        if(num+num[j] > x){
                j--;
}
else if(num+num[j] <= x){
                c += j-i;
                i++;
}

}

        return c;
}
        else{
        for(int i=s;i<num.size()-k+1;i++){
count +=pair(k-1, num, x-num, i+1);
}
}
return count;
}






评分

1

查看全部评分

cjlm007 发表于 2015-1-22 06:16:36 | 显示全部楼层
bless, 感谢分享!
回复 支持 反对

使用道具 举报

shiningfree 发表于 2015-8-21 15:37:54 | 显示全部楼层
贴一个我的解法:

int XSumHelper(unordered_map<int, int> &table, int target,int X, const vector<int> &nums, int start ){
        if(start>=nums.size())
                return 0;
        -google 1point3acres
        if(X==0 && target >=0)
                return 1;
                . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        if(target < 0)
                return 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
       
        int total = 0;. visit 1point3acres.com for more.
        if(table[nums[start]]>0){
                table[nums[start]]--;
                total = XSumHelper(table, target-nums[start],X-1,nums, start+1);
        }
        total += XSumHelper(table, target, X, nums, start+1);. 鍥磋鎴戜滑@1point 3 acres
        return total;
}
. 1point 3acres 璁哄潧
int XSum(const vector<int> &nums, int target, int X){

        unordered_map<int, int> table;
        for(int n : nums){
                table[n] += 1;
        }
       
        return XSumHelper(table, target, X, nums, 0);
       
         
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 22:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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