与语言无关的随机洗牌问题 [英] shuffle card deck issues in language agnostic

问题描述

不久前，我在接受采访时，需要解决两个非常有趣的问题.我很好奇您将如何解决这些问题.

Not so long ago I was in an interview, that required solving two very interesting problems. I'm curious how would you approach the solutions.

问题1:

除当前内容之外的所有内容的产品

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

Write a function that takes as input two integer arrays of length len, input and index, and generates a third array, result, such that: result[i] = product of everything in input except input[index[i]]

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

For instance, if the function is called with len=4, input={2,3,4,5}, and index={1,3,2,0}, then result will be set to {40,24,30,60}.

重要提示:您的算法必须在线性时间内运行.

IMPORTANT: Your algorithm must run in linear time.

问题2 :(该主题在Jeff的一篇文章中)

Problem 2 : ( the topic was in one of Jeff posts )

均匀推洗卡座

1. 设计(用C ++或C#语言)Deck类代表有序纸牌，其中纸牌包含52张纸牌，分为13个等级(A，2、3、4、5、6，四种花色中的7、8、9、10，J，Q，K):黑桃(?)，心形(?)，钻石(?)和球杆(?).

1. Design (either in C++ or in C#) a class Deck to represent an ordered deck of cards, where a deck contains 52 cards, divided in 13 ranks (A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K) of the four suits: spades (?), hearts (?), diamonds (?) and clubs (?).

基于此类，设计并实现一种有效的算法来洗牌.纸牌必须均匀地混洗，也就是说，原始纸牌中的每张纸牌都必须具有相同的概率才能出现在纸混牌中的任何可能位置. 该算法应在Deck类的shuffle()方法中实现: 无效shuffle()

Based on this class, devise and implement an efficient algorithm to shuffle a deck of cards. The cards must be evenly shuffled, that is, every card in the original deck must have the same probability to end up in any possible position in the shuffled deck. The algorithm should be implemented in a method shuffle() of the class Deck: void shuffle()

算法的复杂度是多少(取决于卡组中n张牌的数量)?

What is the complexity of your algorithm (as a function of the number n of cards in the deck)?

说明如何测试卡是否被您的方法均匀洗净(黑盒测试).

Explain how you would test that the cards are evenly shuffled by your method (black box testing).

P.S.我有两个小时编写解决方案的代码

P.S. I had two hours to code the solutions

推荐答案

第一个问题:

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个向量.

Worst case this program will step through 3 vectors once.

这篇关于与语言无关的随机洗牌问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！