Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

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:

1. Use sieve of erastosthenes or another prime mapping method to create a lookup set of all prime vals from 1 to the highest value in the array

2. create three arrays, lets's call them Prime, Even, Odd

3. Scan through array, if a value is in the prime lookup set from step 1, add it to Prime, if that value modded by 2 is 0, add it to Even (two can be treated as a special case, the only even prime), otherwise, add it to Odd

4. Scan through Prime and Even at same rate, adding Prime[i],Even[i] to array until one or both of the arrays has ended. After that, add all values remaining in Even and any values in Odd to the array.

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:

import sieve 	#not an actual library but just assume

def pair_prime_even(vals):
	prime, even, odd = [], [], []
	max_val = 0
	for val in vals:
		if val > max_val:
			max_val = val
	prime_ref = sieve.get_all_primes_up_to(max)  #assume it returns a hashset or similar
	for val in vals:
		if prime_ref.get(val,None):
			prime.append(val)
		elif val%2 == 0:
			even.append(val)
		else:
			odd.append(val)
	output = merge_arrays(prime, even)
	for x in odd:
		output.append(x)
	return output
	
def merge_arrays(a,b):
	i = 0
	output = []
	while i < len(a) or i < len(b):
		if i <len(a) and i < len(b):
			output.append(a[i])
			output.append(b[i])
		elif i < len(a):
			output.append(a[i])
		else:
			output.append(b[i])
		i += 1
	return output

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
		}
	}
}

- Omkar April 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
		}
	}
}

- Omkar April 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
		}
	}
}

- Omkar April 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
		}
	}
}

- Omkar April 10, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More