一亩三分地论坛

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

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

Google

[复制链接] |试试Instant~ |关注本帖
yangzeyao 发表于 2015-11-12 06:59:01 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other在职跳槽

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

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

x
1. 三种水果,价钱分别是x,y,z给你m的钱,一定要把钱花到不能买水果的情况下,最少买多少水果一开始说贪心算法,先从最贵的买起,然后他说most case work,让我想反例。哎,竟然没想出来,然后他给了2,5,6;10这个例子。然后我用dfs做了,不知道为什么他没有很看懂代码,然后讲了不少时间,然后他说差不多明白了,我们已经在这道题花了太多时间了,下一道吧,哎。
2. 给定这个形式2^i*5^j依次输出i=0到j=0开始依次递增的数列,例如:1,2,4,5,8,10之类的
印象中之前见过这道题,但是怎么都想不起来了,然后就用min heap做了。
然后follow up是优化空间复杂度,没想到,呵呵。面经写的这里的时候忽然想到了我当时是怎么做的了,不过也只是用两个array优化了插入的时间复杂度,并没有优化空间复杂度。

哎,感觉不是很好,希望能给个二面机会。

本帖被以下淘专辑推荐:

宝贝忆彼岸 发表于 2015-11-12 07:45:31 | 显示全部楼层
第一题
        public int findSmallest(int[] array,int money){
                if(money == 0 || array == null || array.length == 0){
                        return 0;
                }
. Waral 鍗氬鏈夋洿澶氭枃绔,                int length = array.length;
                int[] res = new int[money+1];
                res[0] = 0;. 1point3acres.com/bbs
                for(int i=1;i<=money;i++){
                        int min = Integer.MAX_VALUE;
                        for(int j=0;j<length;j++){
                                int cur = array[j];.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                if(cur > i){
                                        continue;
                                }
                                else{.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                        if(1+res[i-cur] < min){
                                                min = 1 + res[i-cur];. 1point 3acres 璁哄潧
                                                res[i] = min;
                                        }
                                }
                        }
                       
                }
                return res[money];
        }

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

marthew777 发表于 2015-11-12 07:07:21 | 显示全部楼层
多谢分享! 第一题:类似min coin change,greedy并不能保证对所有价钱组合都给最优,但是DP可以。转换方程基本不变,除了终止条件由0变到小于最小的物品单价。第二题LC原题变形,ugly num

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-12 07:22:58 | 显示全部楼层
marthew777 发表于 2015-11-12 07:07
多谢分享! 第一题:类似min coin change,greedy并不能保证对所有价钱组合都给最优,但是DP可以。转换方程 ...

请教一下第一题的话dp的思路是?
另外,第二题返回去看了当时ugly num的代码,感觉空间复杂度没有差很多的样子,都是需要记录从下一个值一直到前面所有数下一步能到达的比下一个值要大的数。
  1. class Solution {
  2. public:
  3.     int nthUglyNumber(int n) {
  4.         vector<int> res(1, 1);
  5.         int l2 = 0, l3 = 0, l5 = 0;
  6.         for (int i=2; i<=n; i++) {
  7.             int m2 = res[l2] * 2, m3 = res[l3] * 3, m5 = res[l5] * 5;. more info on 1point3acres.com
  8.             int next = min(m2, min(m3, m5));
  9.             if (next == m2) l2++;. from: 1point3acres.com/bbs
  10.             if (next == m3) l3++;
  11.             if (next == m5) l5++;
  12.             res.push_back(next);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.         }
  14.         return res.back();. From 1point 3acres bbs
  15.     }
  16. };
复制代码
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-12 08:05:59 | 显示全部楼层
marthew777 发表于 2015-11-12 07:07
多谢分享! 第一题:类似min coin change,greedy并不能保证对所有价钱组合都给最优,但是DP可以。转换方程 ...

第一题我感觉可以-google 1point3acres
dp[j] = Max(dp[i - 1][j]) + prices[j]   i 是第几个水果, j是那种水果,

当发现第一个没法买的i 退出。 不知道这样可以吗?
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-12 08:45:56 | 显示全部楼层
hyliu0000 发表于 2015-11-12 08:05
第一题我感觉可以
dp[j] = Max(dp[j]) + prices[j]   i 是第几个水果, j是那种水果,
  1. dp[i] = min(dp[i], dp[i-p[j]] + 1)    0<=j<p.length, i>=p[j]
复制代码
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-12 08:52:11 | 显示全部楼层

比我的要好,  谢谢
回复 支持 反对

使用道具 举报

luzcn 发表于 2015-11-12 08:54:28 | 显示全部楼层
marthew777 发表于 2015-11-12 07:07
多谢分享! 第一题:类似min coin change,greedy并不能保证对所有价钱组合都给最优,但是DP可以。转换方程 ...
. 鍥磋鎴戜滑@1point 3 acres
第一题他提示你Greedy不能保证正确的时候就应该想到DP了。 第二题 就是Ugly Number的简化版。
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-12 12:49:58 | 显示全部楼层
第一题背包变种,dp无疑
第二题用heap 是要付出额外时间复杂度的,用lz自己想到的这个方法是线性时间
没错, ugly number
回复 支持 反对

使用道具 举报

marvin_2015 发表于 2015-11-12 14:21:41 | 显示全部楼层
yjfox 发表于 2015-11-12 12:49
第一题背包变种,dp无疑
第二题用heap 是要付出额外时间复杂度的,用lz自己想到的这个方法是线性时间.1point3acres缃
没 ...

请教下能具体讲下第二题如何用ugly number的思路来解吗?i和j不像ugly number里的系数一样单调递增的。谢谢
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-12 15:34:01 | 显示全部楼层
marvin_2015 发表于 2015-11-12 14:21-google 1point3acres
请教下能具体讲下第二题如何用ugly number的思路来解吗?i和j不像ugly number里的系数一样单调递增的。谢 ...

public static void solve(int n) {
                List<Integer> list = new ArrayList();
                int i2 = 0, i5 = 0;
                list.add(1);
                for (int i = 0; i <= n; i++) {
                        int t = Math.min(list.get(i2) * 2, list.get(i5) * 5);
                        if (t == list.get(i2) * 2) {
                                i2++;
                        }
                        if (t == list.get(i5) * 5){
                                i5++;
                        }
                        list.add(t);
                        print(t);
                }
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧

空间的优化就是,remove掉list里面 2 和 5 都用过的数, 可以考虑用linkedlist
回复 支持 反对

使用道具 举报

marvin_2015 发表于 2015-11-13 02:26:03 | 显示全部楼层
yjfox 发表于 2015-11-12 15:34
public static void solve(int n) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                List list = new ArrayList();
                int i2 = 0, i5 = 0;

谢谢啦,后来用ugly number的思路演算了下确实是这样的:)
回复 支持 反对

使用道具 举报

netario 发表于 2015-11-13 02:40:35 | 显示全部楼层
第一题只要DP money%(x,y,z的最小公倍数)就行了吧
回复 支持 反对

使用道具 举报

corn 发表于 2015-11-13 23:01:43 | 显示全部楼层
yjfox 发表于 2015-11-12 15:34. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
public static void solve(int n) {
                List list = new ArrayList();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                int i2 = 0, i5 = 0;

好机智~ 可是这样生成的数列有重复的。不过在add时和前一个数比较一下就可以了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-9 12:14:26 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-12 07:45
第一题
        public int findSmallest(int[] array,int money){
                if(money == 0 || array == null || array. ...

应该是对的,起始不引入min也可以,跟简洁,直接 res = Math.min(res, i + res[i - cur])

补充内容 (2015-12-9 12:15):
怎么这么多错别字,是其实,更, res i
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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