[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2429|回复: 14
收起左侧

Google

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

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

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

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

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

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

本帖被以下淘专辑推荐:

宝贝忆彼岸 发表于 2015-11-12 07:45:31 | 显示全部楼层
第一题. 1point 3acres 论坛
        public int findSmallest(int[] array,int money){
                if(money == 0 || array == null || array.length == 0){
                        return 0;
                }.本文原创自1point3acres论坛
                int length = array.length;
                int[] res = new int[money+1];
                res[0] = 0;
                for(int i=1;i<=money;i++){. From 1point 3acres bbs
                        int min = Integer.MAX_VALUE;
                        for(int j=0;j<length;j++){
                                int cur = array[j];
                                if(cur > i){. from: 1point3acres
                                        continue;
                                }
                                else{. From 1point 3acres bbs
                                        if(1+res[i-cur] < min){
                                                min = 1 + res[i-cur];
                                                res[i] = min;
                                        }
                                }. visit 1point3acres for more.
                        }
                       
                }
                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;. from: 1point3acres
  6.         for (int i=2; i<=n; i++) {
  7.             int m2 = res[l2] * 2, m3 = res[l3] * 3, m5 = res[l5] * 5;
  8.             int next = min(m2, min(m3, m5));. 1point3acres
  9.             if (next == m2) l2++;
  10.             if (next == m3) l3++;
  11.             if (next == m5) l5++;
  12.             res.push_back(next); 来源一亩.三分地论坛.
  13.         }
  14.         return res.back();. 留学申请论坛-一亩三分地
  15.     }
  16. };
复制代码
回复 支持 反对

使用道具 举报

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

第一题我感觉可以. 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. more info on 1point3acres
第一题我感觉可以
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可以。转换方程 ...
. 牛人云集,一亩三分地
第一题他提示你Greedy不能保证正确的时候就应该想到DP了。 第二题 就是Ugly Number的简化版。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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自己想到的这个方法是线性时间. 1point 3acres 论坛
没 ...

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

使用道具 举报

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

public static void solve(int n) {
                List<Integer> list = new ArrayList();. visit 1point3acres for more.
                int i2 = 0, i5 = 0;. 1point 3acres 论坛
                list.add(1);
                for (int i = 0; i <= n; i++) {
                        int t = Math.min(list.get(i2) * 2, list.get(i5) * 5);. From 1point 3acres bbs
                        if (t == list.get(i2) * 2) {
                                i2++;
                        }
                        if (t == list.get(i5) * 5){
                                i5++;
                        }
                        list.add(t);
                        print(t);
                }. from: 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.本文原创自1point3acres论坛
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
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-24 22:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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