Interview Question
Country: United States
public class PrimeEvenPair {
static int primeIndex = -1;
static int evenIndex = -1;
static int input_array[];
static int track_array[];
static int output_array[];
private static void init(int[] input) {
input_array = input;
track_array = new int[input_array.length];
output_array = new int[input_array.length];
}
private static int[] getOutput() {
int outIndex = -1;
evenIndex = 0;
primeIndex = 0;
for (int i = 0; i < input_array.length; i++) {
if (isPrime(input_array[i])) {
for (int j = i + 1 > evenIndex + 1 ? i + 1 : evenIndex + 1; j < input_array.length; j++) {
if (isEven(input_array[j])) {
primeIndex = i;
evenIndex = j;
output_array[++outIndex] = input_array[primeIndex];
output_array[++outIndex] = input_array[evenIndex];
track_array[primeIndex] = 1;
track_array[evenIndex] = 1;
break;
}
}
}
}
for (int i = 0; i < track_array.length; i++) {
if (track_array[i] == 0) {
output_array[++outIndex] = input_array[i];
}
}
return output_array;
}
private static boolean isEven(int i) {
return (i % 2) == 0;
}
private static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
double sqrtN = Math.floor(Math.sqrt(n));
for (int i = 5; i <= sqrtN; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[] input = { 3, 4, 2, 0 };
init(input);
int[] ouput = getOutput();
for (int i = 0; i < ouput.length; i++) {
System.out.printf("%d, ", ouput[i]);
}
}
}
public class PrimeEvenPair {
static int primeIndex = -1;
static int evenIndex = -1;
static int input_array[];
static int track_array[];
static int output_array[];
private static void init(int[] input) {
input_array = input;
track_array = new int[input_array.length];
output_array = new int[input_array.length];
}
private static int[] getOutput() {
int outIndex = -1;
evenIndex = 0;
primeIndex = 0;
for (int i = 0; i < input_array.length; i++) {
if (isPrime(input_array[i])) {
for (int j = i + 1 > evenIndex + 1 ? i + 1 : evenIndex + 1; j < input_array.length; j++) {
if (isEven(input_array[j])) {
primeIndex = i;
evenIndex = j;
output_array[++outIndex] = input_array[primeIndex];
output_array[++outIndex] = input_array[evenIndex];
track_array[primeIndex] = 1;
track_array[evenIndex] = 1;
break;
}
}
}
}
for (int i = 0; i < track_array.length; i++) {
if (track_array[i] == 0) {
output_array[++outIndex] = input_array[i];
}
}
return output_array;
}
private static boolean isEven(int i) {
return (i % 2) == 0;
}
private static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
double sqrtN = Math.floor(Math.sqrt(n));
for (int i = 5; i <= sqrtN; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[] input = { 3, 4, 2, 0 };
init(input);
int[] ouput = getOutput();
for (int i = 0; i < ouput.length; i++) {
System.out.printf("%d, ", ouput[i]);
}
}
}
Java solution:
public class PrimeEvenPair {
static int primeIndex = -1;
static int evenIndex = -1;
static int input_array[];
static int track_array[];
static int output_array[];
private static void init(int[] input) {
input_array = input;
track_array = new int[input_array.length];
output_array = new int[input_array.length];
}
private static int[] getOutput() {
int outIndex = -1;
evenIndex = 0;
primeIndex = 0;
for (int i = 0; i < input_array.length; i++) {
if (isPrime(input_array[i])) {
for (int j = i + 1 > evenIndex + 1 ? i + 1 : evenIndex + 1; j < input_array.length; j++) {
if (isEven(input_array[j])) {
primeIndex = i;
evenIndex = j;
output_array[++outIndex] = input_array[primeIndex];
output_array[++outIndex] = input_array[evenIndex];
track_array[primeIndex] = 1;
track_array[evenIndex] = 1;
break;
}
}
}
}
for (int i = 0; i < track_array.length; i++) {
if (track_array[i] == 0) {
output_array[++outIndex] = input_array[i];
}
}
return output_array;
}
private static boolean isEven(int i) {
return (i % 2) == 0;
}
private static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
double sqrtN = Math.floor(Math.sqrt(n));
for (int i = 5; i <= sqrtN; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[] input = { 3, 4, 2, 0 };
init(input);
int[] ouput = getOutput();
for (int i = 0; i < ouput.length; i++) {
System.out.printf("%d, ", ouput[i]);
}
}
}
Java solution:
public class PrimeEvenPair {
static int primeIndex = -1;
static int evenIndex = -1;
static int input_array[];
static int track_array[];
static int output_array[];
private static void init(int[] input) {
input_array = input;
track_array = new int[input_array.length];
output_array = new int[input_array.length];
}
private static int[] getOutput() {
int outIndex = -1;
evenIndex = 0;
primeIndex = 0;
for (int i = 0; i < input_array.length; i++) {
if (isPrime(input_array[i])) {
for (int j = i + 1 > evenIndex + 1 ? i + 1 : evenIndex + 1; j < input_array.length; j++) {
if (isEven(input_array[j])) {
primeIndex = i;
evenIndex = j;
output_array[++outIndex] = input_array[primeIndex];
output_array[++outIndex] = input_array[evenIndex];
track_array[primeIndex] = 1;
track_array[evenIndex] = 1;
break;
}
}
}
}
for (int i = 0; i < track_array.length; i++) {
if (track_array[i] == 0) {
output_array[++outIndex] = input_array[i];
}
}
return output_array;
}
private static boolean isEven(int i) {
return (i % 2) == 0;
}
private static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
double sqrtN = Math.floor(Math.sqrt(n));
for (int i = 5; i <= sqrtN; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[] input = { 3, 4, 2, 0 };
init(input);
int[] ouput = getOutput();
for (int i = 0; i < ouput.length; i++) {
System.out.printf("%d, ", ouput[i]);
}
}
}
please define for us the meaning of "pair of prime number and even number", as that doesn't really specify anything beyond that pairs need to be a prime matched to an even? Is there some ordering rule, a requirement of how they be paired? My answer is going to be based on what I can interpret from your example
To take a preliminary stab at this with my limited understanding, I would say a answer which yields an array of paired prime-evens with the unpaired values on the end would be:
I'm not going to implement the sieve as it is irrelevant and can be replaced by any standard method of mapping primes.
The python solution:
While the main logic here will run in O(n) time (O(1) lookups for primes, O(2n) for merging prime and even, O(n) for for merging in odd), the choice of function for getting the reference set of primes is what will most likely determine the overall runtime.
- Javeed April 01, 2015