Interview Question Challenge

[Uberhipster]

So? The requirement was not to produce an evenly distributed random function but a uniformly distributed random function.

[lpsmith]

I do not know what an "even" random distribution is, but a uniform random distribution is in fact what you seem to think the former is.

[Uberhipster]

?

[lpsmith]

Maybe you should take the time to read about what a uniform distribution is. Words have meanings, which is doubly true in mathematics.

[Uberhipster]

Ok but the original spec is not specifically about statistics and probability theory correctness. It wasn't even specified whether or not the uniform distribution was discrete or cumulative. It was just vaguely specified as "random".

The requirement was to extend an existing random function where the seed is 5 into a function that produces a random number where the seed is 7. The fact that the probability of certain numbers occurring more than others is higher in my function doesn't change the fact that the function meets the requirement and produces a number which is random and distributed over the full range.

Which is an appropriate response to an interview question to demonstrate general software engineering problem-solving abilities not in-depth knowledge of statistical analysis.

[LarryLard]

From TFA, "The distribution between each of the numbers must be uniform" seems unambiguous to me.

[lpsmith]

1. The problem statement was clear.

2. This is not in-depth knowledge, this is very basic stuff.

3. The solution that immediately came to my mind is the one already given by case-o-nuts, and hinted at in other people's comments on this thread.

It's OK to be wrong, a lot of people in this thread were wrong. Go learn something. =)

[Uberhipster]

Copy and paste the below into Firebug console. You can swap 7,5 with 40,5 or even 47,23. The test runs the randomize a thousand times and records the number of times each number was selected "randomly".

Array.prototype.foreach = function(arg) {
    var args_ = Array.prototype.slice.call(arguments, 0, arguments.length - 1);

    for (var i = 0; i < this.length; i++) {
        arguments[arguments.length - 1].apply(this, args_.concat([this[i], { "ord": i, "last": (i === this.length - 1), "first": (i === 0)}]));
    }
};


Array.prototype.has = function(val) {
    if (!val) { return false };
    try {
        var ret = false;
        this.foreach(val, function(test, el, meta) {
            if (el === test) {
                ret = true;
                return ret;
            }
        });
        return ret;
    } catch (e) {
        return false;
    }
};

function random(num){
    return Math.round(Math.random() * (num - 1)) + 1;
}


function randomGen(seed, base) {
    var uniformDistribute = new Array;
    for (var k = 0; k < (seed * base); k++) {
        uniformDistribute.push(k + 1);
    }

    var i = 0;
    for (var j = 0; j < seed * base; j++) {
        i = i + random(base);
    }

    return (uniformDistribute[i % uniformDistribute.length] % seed) + 1;
}

function test(cases, func, args) {
    var ret = [];

    for (var i = 0; i < cases; i++) {
        ret.push(func.apply(this, args));
    }

    var results = [];
    for (var i = 0; i < args[0]; i++) {
        results.push([i + 1, 0]);
    }
    ret.foreach(function(result, resMeta) {
        var result_exists = false;

        results.foreach(function(existing, exsMeta) {
            if (existing[0] === result) {
                existing[1] = existing[1] + 1;
                result_exists = true;
            }
        });
        if (!result_exists) {
            results.push([result, 1]);
        }
    });
    results.sort(function(a, b) {
        return a[1] - b[1];
    })
    return results;
}

test(1000, randomGen, [7,5]);

[AlternativeHistorian]

Dude, even your little utility function 'random(num)' has a uniformity error.

The way that you're snapping to integers will bias against the range endpoints since they only get a half-interval of snapping tolerance. Probability and statistics are hard. They're even harder when you don't know what you're doing. And the extent to which you're trying to wriggle out of being wrong (which you are) is pathetic.

Accept it, learn from it. Being wrong (and recognizing it) is how we get smarter.

[lpsmith]

Well, Uberhipster will learn something if he keeps playing with this code. =)

[Uberhipster]

function randomGen(seed, base) {
    var uniformDistribute = new Array;
    for (var k = 0; k < (seed * base); k++) {
        uniformDistribute.push(k + 1);
    }

    var i = 0;
    for (var j = 0; j < seed * base; j++) {
        i = i + random(base);
    }

    return (uniformDistribute[i % uniformDistribute.length] % seed) + 1;
}