10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3133|回复: 2
收起左侧

youtube 电话面试 刚刚面完

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

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

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

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

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

Count the number of distinct pairs such that their sum is <= X? 3
.1point3acres缃
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;
}





. From 1point 3acres bbs

评分

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()). visit 1point3acres.com for more.
                return 0;
       
        if(X==0 && target >=0)
                return 1;
               
        if(target < 0)
                return 0;. From 1point 3acres bbs
       
        int total = 0;
        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);
        return total;. Waral 鍗氬鏈夋洿澶氭枃绔,
}

int XSum(const vector<int> &nums, int target, int X){

        unordered_map<int, int> table;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        for(int n : nums){. 鍥磋鎴戜滑@1point 3 acres
                table[n] += 1;
        }
       
        return XSumHelper(table, target, X, nums, 0);
       
         
}
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 04:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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