Groupon面经

楼主今天刚面的。楼主是悲剧了，希望后面的筒子再接再厉~
一小时的技术面，花13分钟讨论了一下简历，然后就上codepad了。
题目经典，但是楼主只做出了一问，楼主太渣了，面到最后楼主尴尬症都犯了。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
的方法做了。当然不满意。。。后来楼主时间不多，也没改进算法。

求各位看官给点米~楼主谢啦~

1.         public int minNum(int n){
   
2.                 int[] result=new int[n+1];
   
3.                 result[0]=0;
   
4.                 for(int i=1; i<=n; i++){
   
5.                         if(i<7){
   
6.                                 result[i]=i;
   
7.                         }
   
8.                         else if(i>=7 && i<10){
   
9.                                 result[i]=i%7+1;
   
10.                         }
    
11.                         else{
    
12.                                 result[i]=Math.min(result[i-1], Math.min(result[i-7], result[i-10]))+1;
    
13.                         }
    
14.                 }
    
15.                 return result[n];
    
16.         }

复制代码

动归这样做吧

vivyao 发表于 2015-12-31 08:36
请问一下，greedy的复杂度为什么是O(4)呀？还有这题要求的是最少零钱的总数量还是要求出怎么组合呀？

我之前想的是先换大面额的，比如用106换｛25，10，5，1｝，就先换4张25，再换1张5，最后换1张1.但是如果提供的零钱面值不是这样有规律的话，这样换可能换不开，比如用106换｛20，5，3，2｝，先换5张20，再换一张5块，这样导致换不开（虽然是可以用5张20，两张3换开）。还是用DP吧，现在leetcode上已经有这道题了322. Coin Change
（https://leetcode.com/problems/coin-change/）

贴下我的DP答案， C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int numCoin = coins.size();
        if(amount == 0) return 0;
        vector<int> count(amount+1, -1);
        for(int i = 0; i < numCoin; i++) {
            if(coins[i] <= amount) count[coins[i]] = 1;
        }
        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < numCoin; j++) {
                if(i-coins[j] < 0 || count[i - coins[j]] < 0) continue;
                else { // i - coints[j] >= 0 && count[i - coins[j]] > 0
                    if(count[i] < 0) count[i] = count[i - coins[j]] + 1;
                    else count[i] = min(count[i], count[i - coins[j]] + 1);
                }
            }
        }
        return count[amount];
    }
};

请问楼主面的什么职位啊？我下周有个data engineer的电面都不知道会问什么

lyj87372517 发表于 2015-11-8 04:14
请问楼主面的什么职位啊？我下周有个data engineer的电面都不知道会问什么

面的software developer

lyj87372517 发表于 2015-11-8 04:42
动归这样做吧

谢谢楼主~

libralavender 发表于 2015-11-8 21:19
谢谢楼主~

哈哈你才是楼主吧。。

lyj87372517 发表于 2015-11-8 04:14
请问楼主面的什么职位啊？我下周有个data engineer的电面都不知道会问什么

你好 你是周几面啊？

wendy920217 发表于 2015-11-9 09:21
你好 你是周几面啊？

周一。。。字数字数

lyj87372517 发表于 2015-11-9 10:58
周一。。。字数字数

祝楼主好运 顺求面经

这个题如果用DP的话，复杂度是O（total）吗？greedy是不是复杂度是O(number of available changes)， 是不是更简单一些，从大额的面值开始换，换不了就换小面值。
比如total是100，复杂度就是O（100）， 如果只有25， 10， 5， 1四种面值，用greedy就是O（4）？