patternjavaModerate
Returning an array of integers with 1000 elements
Viewed 0 times
elementsarraywithreturning1000integers
Problem
Write a function that returns an array of integers with 1000 elements
containing the values 1 to 1000 in random order. No number can be
repeated or omitted.Your answer should show good programming style,
technique and attention to accuracy and performance.
Hint: use Random rnd=new Random() to create a new instance of the
random number generator and rnd.Next(1,1000) to get a random integer
value between 1 and 1000. No other .Net framework classes should be
needed outside of the intrinsic data types (i.e. DO NOT use
collections).
For that I have developed the following code:
JUnit test class:
```
import java.util.HashSet;
import java.util.Set;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
public class DomainJunitTest {
Domain domain = null;
int arraySize = 0;
@Before
public void initialize() throws Exception {
domain = new Domain();
arraySize = 1000;
}
@Test
public void randomIntArray_size_check() {
int intArrayHolder[] = domain.randomIntArray(arraySize);
Assert.assertEquals(arraySize, intArrayHolder.length);
containing the values 1 to 1000 in random order. No number can be
repeated or omitted.Your answer should show good programming style,
technique and attention to accuracy and performance.
Hint: use Random rnd=new Random() to create a new instance of the
random number generator and rnd.Next(1,1000) to get a random integer
value between 1 and 1000. No other .Net framework classes should be
needed outside of the intrinsic data types (i.e. DO NOT use
collections).
For that I have developed the following code:
import java.util.Random;
public class Domain {
public int[] randomIntArray(int size) {
Random random = new Random();
int intArrayHolder[] = new int[size];
for (int i = 0; i < intArrayHolder.length; i++) {
boolean isDuplicate = false;
/*
* because random.nextInt(int var) return between 0 and given-no and
* we do not want 0. So size +1 and later in program, we do not
* assign 0 to the intArrayHolder.
*/
int randomNextInt = random.nextInt(size + 1);
for (int j = 0; j < i; j++) {
if (intArrayHolder[j] == randomNextInt) {
isDuplicate = true;
break;
}
}
if ((!isDuplicate) && (randomNextInt != 0)) {
intArrayHolder[i] = randomNextInt;
} else {
i--;
}
}
return intArrayHolder;
}
}JUnit test class:
```
import java.util.HashSet;
import java.util.Set;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
public class DomainJunitTest {
Domain domain = null;
int arraySize = 0;
@Before
public void initialize() throws Exception {
domain = new Domain();
arraySize = 1000;
}
@Test
public void randomIntArray_size_check() {
int intArrayHolder[] = domain.randomIntArray(arraySize);
Assert.assertEquals(arraySize, intArrayHolder.length);
Solution
Your approach is not incorrect. It will get the job done (albeit, slower). If you want to improve your approach, keep reading. But first a few points on your code:
Points on Your code
Therefore, the refactored code would be:
A Better Solution
Your solution's best case running time is \$\Omega(n^2)\$. Moreover, as Boris the Spider pointed out: "... there is absolutely no guarantee that Random.nextInt()
Points on Your code
intArrayHolderseems a bit wordy to me. I believeintArrayor evenarraywould serve your purpose, without sacrificing readibility. Same forrandomNextInt.
for (int i = 0; i
- Please note that random.nextInt(size + 1)
does not return an integer between 1 and 1000. It returns an integer in the range \$[0, 1001)\$, i.e. a number \$x\$ such that \$0\leq x
- ((!isDuplicate) && (randomNextInt != 0))
can be shortened to!(isDuplicate || ramdomNextInt == 0), by using De Morgan's laws. It would be even better if you flip the condition and force next iteration before adding the element to the array.
- A general advice is to update the loop counter only once. People generally estimate the number of times the loop will execute by stealing a glance at the for (...
statement. Awhileloop is preferred when the number of iterations is unknown or updation is irregular.
- You seem to be using snake_case
along withcamelCase. The standard in Java is to usecamelCase.
Therefore, the refactored code would be:
import java.util.Random;
public class Domain {
public int[] randomIntArray(int size) {
Random random = new Random();
int array[] = new int[size];
int i = 0;
while (i < size) {
boolean isDuplicate = false;
int randomInteger = random.nextInt(size) + 1;
for (int j = 0; j < i; j++) {
if (array[j] == randomInteger) {
isDuplicate = true;
break;
}
}
if (isDuplicate) {
continue;
} else {
array[i++] = randomInteger;
}
}
return array;
}
}A Better Solution
Your solution's best case running time is \$\Omega(n^2)\$. Moreover, as Boris the Spider pointed out: "... there is absolutely no guarantee that Random.nextInt()
won't decide to return 1 for ever and ever. ..." Therefore, it might be possible that your code never terminates (although it will be very unlikely). You can make it faster in the following manner:
import java.util.Random;
public class Domain {
public int[] randomIntArray(int size) {
Random random = new Random();
int array[] = new int[size];
// populate the array with sequential values
for (int i = 0; i < size; i++) {
array[i] = i + 1;
}
// "shuffle" the array
for (int i = 0; i < size; i++) {
int j = random.nextInt(size - i) + i;
// swap
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
return array;
}
}
It's running time is linear i.e. \$\Theta(n)\$1. I am basically describing the Fisher-Yates shuffle
Some Background Info: The Big-O stuff
The Big-O notation is used to define an upper limit of the number of operations executed (the maximum running time, in simpler terms). For example, if the exact number of iterations based on a given parameter (like the number of elements, digits, etc) called \$n\$ is
$$2n^2+3n-4$$
we can say that a reasonable upper limit is \$3n^2\$. In the Big-O notation, the constant term gets absorbed. When we represent this in the Big-O notation, we say: "the (maximum) running time is proportional to \$O(n^2)\$".
People tend to forget the other two notations: the Big-Omega (\$\Omega\$) and the Big-Theta (\$\Theta\$) The former defines a lower limit and the latter is the Big-O and the Big-Omega combined together. In the example above, the lower limit can be \$2n^2\$. Absorbing the constant, we say:"the (minimum) running time is proportional to \$\Omega(n^2)\$". The function can therefore be bounded within both upper and lower limits, or both the upper and the lower limits are in the order of \$\Theta(n^2)\$.
Your code has no upper limit. It only has a lower limit. So, only the \$\Omega\$ is defined for your code (unless we set out to do a lengthy mathematical analysis of the behaviour of the nextInt() function).
I suggest that you read the related Wikipedia articles. (I didn't cover \$o, \omega\$ and \$\theta\$, that's your homework). Remember, Google is your friend!
1 Assuming that the nextInt()` method takes \$O(1)\$ (i.e. constant) time to execute.Code Snippets
import java.util.Random;
public class Domain {
public int[] randomIntArray(int size) {
Random random = new Random();
int array[] = new int[size];
int i = 0;
while (i < size) {
boolean isDuplicate = false;
int randomInteger = random.nextInt(size) + 1;
for (int j = 0; j < i; j++) {
if (array[j] == randomInteger) {
isDuplicate = true;
break;
}
}
if (isDuplicate) {
continue;
} else {
array[i++] = randomInteger;
}
}
return array;
}
}import java.util.Random;
public class Domain {
public int[] randomIntArray(int size) {
Random random = new Random();
int array[] = new int[size];
// populate the array with sequential values
for (int i = 0; i < size; i++) {
array[i] = i + 1;
}
// "shuffle" the array
for (int i = 0; i < size; i++) {
int j = random.nextInt(size - i) + i;
// swap
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
return array;
}
}Context
StackExchange Code Review Q#104419, answer score: 12
Revisions (0)
No revisions yet.