A database table for your questions might look like this:
QuestionID PK
Question Text
Difficulty Int
Keep track of the questions already asked and answered in another table:
StudentID FK
TestID FK
QuestionID FK
AnswerID FK (assumes multiple choice)
Possible answers to questions (multiple choice):
AnswerID PK
QuestionID FK
Answer Text
IsTheCorrectAnswer boolean
As said before, this question actually doesn't have an answer: The restrictions imposed on the numbers make the randomness questionable at best.
However, you could come up with a procedure that returns a list of numbers like that:
Let's say we have picked the first two numbers randomly as -0.8 and -0.7. Now the requirement is to come up with 3 'random' numbers that sum up to 2.5 and are all in the range [-1,1]. This problem is very similar to the starting problem, only the dimensions have changed. Now, however, if we take a random number in the range [-1,1] we might end up with no solution. We can restrict our range to make sure that solutions still exist: The sum of the last 2 numbers will be within the range [-2,2]. This means we need to pick a number in the range [0.5,1] to make sure we can reach a total of 2.5.
The section above describes one step in the process.
In general: Determine the range for the next number by applying the range of the rest of the numbers to the required sum.
Pseudo-code:
function randomNumbers (number, range, sum) {
restRange = range * (number - 1)
myRange = intersection ([sum - restRange.upper, sum - restRange.lower], range)
myNumber = random(myRange)
rest = randomNumbers (number-1, range, sum - myNumber)
return [myNumber, rest]
}
So for the case described above
randomNumbers (3, [-1,1], 2.5)
restRange = [-1,1] * (3-1) = [-2,2]
myRange = intersection ([2.5-2,2.5-(-2)], [-1,1]) = intersection ([0.5,4.5],[-1,1]) = [0.5,1]
A quick-and-dirty implementation in Java:
public class TestRandomNumberList
{
@Test
public void test()
{
double[] numbers = new double[5];
randomNumbers(numbers, 0, -1, 1, 1);
assertEquals(sum(numbers), 1.0, 0.00001);
for (double d : numbers)
{
assertTrue(d >= -1 );
assertTrue(d <= 1);
}
}
private void randomNumbers(double[] numbers, int index, double lowerBound, double upperBound, double sum)
{
int next = index + 1;
if (next == numbers.length)
{
numbers[index] = sum;
}
else
{
int rest = numbers.length - next;
double restLowerBound = lowerBound * rest;
double restUpperBound = upperBound * rest;
double myLowerBound = Math.max(lowerBound, sum - restUpperBound);
double myUpperBound = Math.min(upperBound, sum - restLowerBound);
numbers[index] = random(myLowerBound, myUpperBound);
randomNumbers(numbers, next, myLowerBound, myUpperBound, sum - numbers[index]);
}
}
private double random(double myLowerBound, double myUpperBound)
{
double random = Math.random();
return myLowerBound + random * (myUpperBound - myLowerBound);
}
private double sum(double[] numbers)
{
double result = 0;
for (double num : numbers)
{
result += num;
}
return result;
}
}
Best Answer
When a function or algorithm allocates
n
atomic items of memory likethen it has a space complexity of at least O(n), regardless of what this array is used for. If it is used exclusively for returning some results, or for a completely different purpose, does not matter.
However, many programming languages allow to return sequences of arbitrary numbers of items in ways the space complexity stays O(1), utilizing streams or generator expressions. For example, in C# you can write
Now it is up to the callers what they do with the result - if they process it sequentially, space complexity can stay O(1). If they store the full result in a list or an array, space complexity will be again O(n) at least.
(In Java, this seems to be possible, too, using
Iterable<int>
, but it seems to require more code).