一亩三分地论坛

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

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

Google 电面两道算法题

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

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

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

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

x
刚GOOGLE电面完 估计已经挂了 因为没给出最优解 而且面试官口气不好 赶紧挂电话的感觉. from: 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
直接上题吧:

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

.鏈枃鍘熷垱鑷1point3acres璁哄潧

. more info on 1point3acres.com
2. 找出一个数由最少几个平方的和的组成
例子:
input: 14    output:  9 ,4 , 1  虽然也能由1 +1 +....+1组成 但长度是14 不是最优解
input:   50     ouput :  25, 25

我说用greedy approache, 但面试官是可能不对 然后我就说用暴力解法
面试官表示不悦,但没办法 硬头皮上了

坐等拒信ing....



评分

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;
. more info on 1point3acres.com                for (int i = 2; i <= n ; i++){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        int j = 1;
                        int min = Integer.MAX_VALUE;
                        while(j*j <= i){
                                int cur = 1 + f[i-j*j];
                                min = Math.min(min, cur);
                                j++;
                        }
                        f[i] = min;
                }
                return f[n];.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
回复 支持 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;
        //sort(input.begin(), input.end());
        unordered_set<int> uset(input.begin(), input.end());
        for (int i = range.first; i <= range.second;){
                if (uset.find(i) != uset.end())
                        ++i;. more info on 1point3acres.com
                else{
                        pair<int, int> p;. 1point 3acres 璁哄潧
                        p.first = i;
                        int j;
                        for (j = i; j <= range.second && uset.find(j) == uset.end(); ++j){}
                        p.second = j - 1;
                        ret.push_back(p);. Waral 鍗氬鏈夋洿澶氭枃绔,
                        i = j;
                }
        }
        return ret;
}

第二题: 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{. From 1point 3acres bbs
                        int tmp = i + 1;
                        for (int j = i; j >= (i + 1) / 2; --j){
                                tmp = min(tmp, dp[j - 1] + dp[i + 1 - j - 1]);
                                if (tmp == 2). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                        break;. Waral 鍗氬鏈夋洿澶氭枃绔,
                        }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                        dp[i] = tmp;
                }. From 1point 3acres bbs
        }. from: 1point3acres.com/bbs
        return dp.back();
}
回复 支持 2 反对 0

使用道具 举报

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

1. 求input的平方根,取整数部分(假定为n)
2. 用input除以n^2, 取余数(设定为x). Waral 鍗氬鏈夋洿澶氭枃绔,
3. 如果x = 0, 则为base case, 如果x != 0, 以x为input,重复1和2.

重复的次数加1就是要找的解
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
重复的次数+1 即为



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

使用道具 举报

laj5122 发表于 2014-11-20 08:07:15 | 显示全部楼层
leros 发表于 2014-11-20 07:55
多谢分享! 讨论下关于第二道题的可能解法(用recursion):
.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. 求input的平方根,取整数部分(假定为n)
. Waral 鍗氬鏈夋洿澶氭枃绔,
你这个实质还是贪心吧 每次都尽量取最大的?
回复 支持 反对

使用道具 举报

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可以吗?谢谢啦!

-google 1point3acres可以。 只要是最短
回复 支持 反对

使用道具 举报

 楼主| 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.1point3acres缃
多谢分享! 讨论下关于第二道题的可能解法(用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:

膜拜一个!!第二题dp的解法没太看懂。。。


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

使用道具 举报

王可雪 发表于 2014-11-20 11:45:09 | 显示全部楼层
第二题可以greedy + binary search。
. visit 1point3acres.com for more.
补充内容 (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):
好烦
. visit 1point3acres.com for more.
补充内容 (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){
                int [] f = new int[n+1];

果然是高手啊。。. 1point 3acres 璁哄潧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我实在是没能想出来。。 两题总共给了40分钟时间
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 01:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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