《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5763|回复: 37
收起左侧

Google 电面两道算法题

[复制链接] |试试Instant~ |关注本帖
yyboyz 发表于 2014-11-20 07:33:48 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Fail

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

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

x
刚GOOGLE电面完 估计已经挂了 因为没给出最优解 而且面试官口气不好 赶紧挂电话的感觉
.鏈枃鍘熷垱鑷1point3acres璁哄潧
直接上题吧:

1.找出missing number 范围
number范围[0,99]
input: [0, 1, 2,50 , 52, 75]
output: "3-49,51,53-74,76-99"
. 1point3acres.com/bbs



2. 找出一个数由最少几个平方的和的组成
例子:
input: 14    output:  9 ,4 , 1  虽然也能由1 +1 +....+1组成 但长度是14 不是最优解
input:   50     ouput :  25, 25
.1point3acres缃
我说用greedy approache, 但面试官是可能不对 然后我就说用暴力解法
面试官表示不悦,但没办法 硬头皮上了

坐等拒信ing....
. 1point 3acres 璁哄潧
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

legendava 发表于 2014-11-20 12:46:30 | 显示全部楼层
第二题dp
public int minNumber(int n){
                int [] f = new int[n+1];
                f[0] = 0;
                f[1] = 1;
                for (int i = 2; i <= n ; i++){
                        int j = 1;
                        int min = Integer.MAX_VALUE;
                        while(j*j <= i){. 1point 3acres 璁哄潧
                                int cur = 1 + f[i-j*j];. Waral 鍗氬鏈夋洿澶氭枃绔,
                                min = Math.min(min, cur);
                                j++;
                        }
                        f[i] = min;
                }
                return f[n];
        }
回复 支持 2 反对 0

使用道具 举报

Arthur2012 发表于 2014-11-20 08:11:28 | 显示全部楼层
请问:50 output:49 + 1可以吗?谢谢啦!
回复 支持 2 反对 0

使用道具 举报

Dexter_syr 发表于 2014-11-20 09:47:52 | 显示全部楼层
感谢lz, bless lz, 祝lz早日onsite.

第一题hash:

vector<pair<int, int> > findMissingNumber(pair<int, int> range, vector<int> input) {
.鐣欏璁哄潧-涓浜-涓夊垎鍦        vector<pair<int, int> > ret;. from: 1point3acres.com/bbs
        //sort(input.begin(), input.end());. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        unordered_set<int> uset(input.begin(), input.end());
. Waral 鍗氬鏈夋洿澶氭枃绔,        for (int i = range.first; i <= range.second;){
                if (uset.find(i) != uset.end())
                        ++i;. visit 1point3acres.com for more.
                else{. 鍥磋鎴戜滑@1point 3 acres
                        pair<int, int> p;
                        p.first = i;. Waral 鍗氬鏈夋洿澶氭枃绔,
                        int j;
                        for (j = i; j <= range.second && uset.find(j) == uset.end(); ++j){}
                        p.second = j - 1;. 1point3acres.com/bbs
                        ret.push_back(p);
                        i = j;
                }
        }
        return ret;. 1point 3acres 璁哄潧
}

第二题: dp

int calMinNum(int num){
        vector<int> dp(num);
        dp[0] = 1;
        for (int i = 1; i<num; ++i){
                // dp[i] : number i+1;
                if (i + 1 == (int)sqrt(i + 1) * (int)sqrt(i + 1))
                        dp[i] = 1;
                else{ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        int tmp = i + 1;
                        for (int j = i; j >= (i + 1) / 2; --j){
                                tmp = min(tmp, dp[j - 1] + dp[i + 1 - j - 1]);. 1point 3acres 璁哄潧
                                if (tmp == 2)
                                        break;
                        }
                        dp[i] = tmp;
                }
        }
        return dp.back();
}
回复 支持 2 反对 0

使用道具 举报

leros 发表于 2014-11-20 07:55:41 | 显示全部楼层
多谢分享! 讨论下关于第二道题的可能解法(用recursion):

1. 求input的平方根,取整数部分(假定为n)
2. 用input除以n^2, 取余数(设定为x)
3. 如果x = 0, 则为base case, 如果x != 0, 以x为input,重复1和2.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

重复的次数加1就是要找的解

重复的次数+1 即为
.鏈枃鍘熷垱鑷1point3acres璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2014-11-20 07:57):
回复中的最后一句应该删除。。
回复 支持 1 反对 0

使用道具 举报

laj5122 发表于 2014-11-20 08:07:15 | 显示全部楼层
leros 发表于 2014-11-20 07:55
多谢分享! 讨论下关于第二道题的可能解法(用recursion):

1. 求input的平方根,取整数部分(假定为n)

你这个实质还是贪心吧 每次都尽量取最大的?
回复 支持 反对

使用道具 举报

laj5122 发表于 2014-11-20 08:14:09 | 显示全部楼层
Arthur2012 发表于 2014-11-20 08:11
请问:50 output:49 + 1可以吗?谢谢啦!

我第一反应也是为啥不输出49+1。。
回复 支持 反对

使用道具 举报

cow12331 发表于 2014-11-20 08:15:09 | 显示全部楼层
感觉第二题只能用暴力解法 结合hashmap储存部分已经算过的最小值
回复 支持 反对

使用道具 举报

 楼主| yyboyz 发表于 2014-11-20 08:32:34 | 显示全部楼层
Arthur2012 发表于 2014-11-20 08:11. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问:50 output:49 + 1可以吗?谢谢啦!

可以。 只要是最短
回复 支持 反对

使用道具 举报

 楼主| yyboyz 发表于 2014-11-20 08:33:03 | 显示全部楼层
leros 发表于 2014-11-20 07:55
多谢分享! 讨论下关于第二道题的可能解法(用recursion):

1. 求input的平方根,取整数部分(假定为n)

不好意思 没看懂
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2014-11-20 08:43:53 | 显示全部楼层
leros 发表于 2014-11-20 07:55
多谢分享! 讨论下关于第二道题的可能解法(用recursion):

1. 求input的平方根,取整数部分(假定为n)

贪心应该有问题,比如:74 = 25 + 49 = 64 + 9 + 1,这里就不能直接取sqrt(74)。
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2014-11-20 09:11:35 | 显示全部楼层
可不可以用贪心求出次优解,然后记忆化搜索+贪心解剪枝
回复 支持 反对

使用道具 举报

ydybati 发表于 2014-11-20 11:26:31 | 显示全部楼层
Dexter_syr 发表于 2014-11-20 09:47
感谢lz, bless lz, 祝lz早日onsite.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一题hash:

. From 1point 3acres bbs膜拜一个!!第二题dp的解法没太看懂。。。

. From 1point 3acres bbs
补充内容 (2014-11-20 12:11):
**看了好久终于明白了。。。再膜拜个
回复 支持 反对

使用道具 举报

王可雪 发表于 2014-11-20 11:45:09 | 显示全部楼层
第二题可以greedy + binary search。.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2014-11-20 11:50):
好像不对,我再想想。
回复 支持 反对

使用道具 举报

tbtc888 发表于 2014-11-20 11:55:35 | 显示全部楼层
get the possible sequence of items 1,4,9...(which takes O(sqrt n)), and then use dp or bfs to solve it(which takes about O(n^(3/2))).
回复 支持 反对

使用道具 举报

laj5122 发表于 2014-11-20 11:57:47 | 显示全部楼层
ydybati 发表于 2014-11-20 11:26
膜拜一个!!第二题dp的解法没太看懂。。。

没理解错的话类似给你k种硬币 让你凑出n这个钱数 要求硬币数量最少
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2014-11-20 11:58:47 | 显示全部楼层
好难。
google就喜欢出这样的数字游戏题。。。。。

补充内容 (2014-11-20 11:59):
好烦. 1point3acres.com/bbs

补充内容 (2014-11-20 11:59):
好烦
回复 支持 反对

使用道具 举报

kurtwang 发表于 2014-11-20 12:20:23 | 显示全部楼层
第二个感觉像是完全背包
回复 支持 反对

使用道具 举报

 楼主| yyboyz 发表于 2014-11-20 13:50:56 | 显示全部楼层
legendava 发表于 2014-11-20 12:46
第二题dp
public int minNumber(int n){. 鍥磋鎴戜滑@1point 3 acres
                int [] f = new int[n+1];

-google 1point3acres果然是高手啊。。

我实在是没能想出来。。 两题总共给了40分钟时间
回复 支持 反对

使用道具 举报

rettyye3 发表于 2014-11-20 16:23:32 | 显示全部楼层
其实第二题有证明的 任意自然数都能表示为4个平方数的和 然后满足一定条件就一定能表示为三个平方书的和  然后满足一定条件就一定能表示为两个平方数的和 具体见wiki 不过面试应该不要求这样吧 0.0
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-19 20:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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