语言不可知的洗牌卡片问题

Question

不久前我在接受采访时,需要解决两个非常有趣的问题.我很好奇你会如何处理这些解决方案.

问题1:

除了当前的一切产品

编写一个函数,将两个长度为len,input和index的整数数组作为输入,并生成第三个数组result,结果如下:result [i] =输入中除输入[index [i]]之外的所有内容的乘积

例如,如果使用len = 4,input = {2,3,4,5}和index = {1,3,2,0}调用该函数,则结果将设置为{40,24,30 ,60}.

重要信息:您的算法必须以线性时间运行.

问题2 :(主题在Jeff帖子中)

洗牌卡甲板均匀

1. 设计(在C++或C#中)一个类Deck代表一张有序的牌组,其中牌组包含52张牌,分为13个等级(A,2,3,4,5,6,7,8,9, 4,J,Q,K)四件套装:黑桃(？),心形(？),钻石(？)和球杆(？).

2. 基于这个类,设计和实现一个有效的算法来洗牌一副牌.牌必须均匀洗牌,也就是说,原牌中的每张牌必须具有相同的概率才能最终进入洗牌牌的任何可能位置.该算法应该在Deck类的方法shuffle()中实现:void shuffle()

3. 算法的复杂程度是多少(作为卡片中卡片数量n的函数)？

4. 解释如何测试您的方法均匀地洗牌(黑盒测试).

PS我有两个小时来编写解决方案代码

Answer 1

第一个问题:

int countZeroes (int[] vec) {
int ret = 0;
foreach(int i in vec) if (i == 0) ret++;

return ret;
}

int[] mysticCalc(int[] values, int[] indexes) {
    int zeroes = countZeroes(values); 
    int[] retval = new int[values.length];
    int product = 1;

    if (zeroes >= 2) { // 2 or more zeroes, all results will be 0
        for (int i = 0; i > values.length; i++) {
            retval[i] = 0;      
        }
        return retval;
    }
    foreach (int i in values) {
        if (i != 0) product *= i; // we have at most 1 zero, dont include in product;
    }
    int indexcounter = 0;
    foreach(int idx in indexes) {
        if (zeroes == 1 && values[idx] != 0) {  // One zero on other index. Our value will be 0
            retval[indexcounter] = 0;
        }
        else if (zeroes == 1) { // One zero on this index. result is product
            retval[indexcounter] = product;
        }
        else { // No zeros. Return product/value at index
            retval[indexcounter] = product / values[idx];
        }
        indexcouter++;
    }   
    return retval;
}

最糟糕的情况是,该程序将逐步通过3个向量.

Answer 2

对于第一个，首先计算 input 的全部内容的乘积，然后对于索引的每个元素，将计算出的乘积除以 input[index[i]]，以填充结果数组。

当然，我必须假设输入没有零。