Microsoft Interview Question
Junior programmersCountry: Israel
Interview Type: In-Person
The trick here is to find the prefix, the prefix requires a loop: we divide the number by 10 until we hit a single digit result - this is our prefix. The suffix is a simple modulo by 10.
We do some optimizations so won't be calculating the prefix until we actually met all the other conditions:
// Stub (given function)
bool isPrime(int number) { return true; }
bool isSuperPrime(int number)
{
if(!isPrime(number)) return false;
if(number < 10) return true; // Single digit number, no need to test further
// Get the suffix (its faster without loop required)
if(!isPrime(number % 10)) return false;
// so far, we have met both conditions, suffix and prime
// time to get the prefix
int prefix = (number / 10);
while(prefix > 9) {
prefix /= 10;
}
return isPrime(prefix);
}
I interprete the question as follows:
- suppose number n is split into prefix p and suffix s in such a way that p * 10^log(s+9) + s = n (assuming log returns the integer floor of 10-based logarithm)
e.g. n = 192 -> {(p=1, s=92), (p=19, s=2)}
- it's a superprime if and only if isPrime(s) and isPrime(p)
for a number n, there are log(n) such combinations.
I just create a loop which checks for s and p if they are prime. I could "fast-check" before calling isPrime and only do that if s%2 != 0 and p%2 != 0 and thus avoid at least one potential expensive call, but I suppose that's not the big catch here.
bool isSuperPrime(unsigned int n)
{
unsigned int prefix = n / 10; // e.g. 19
unsigned int suffix = n % 10; // e.g. 2
unsigned int mul = 10;
while(prefix != 0) {
if(isPrime(suffix) && isPrime(prefix)) return true;
suffix += (prefix % 10) * mul; // increase suffix, e.g. 9*10 + 2 = 92
prefix /= 10; // reduce prefix, e.g. 1
mul *= 10;
}
return false;
}
@PenChief: agree, except to calculate a single digit prefix you don't need a loop.
// for number > 0
uint div = pow(10, static_cast<int>(log(number))); // static_cast<int> to floor the double
prefix = number / div; // e.g. from 91234 = 9
suffix = number % div; // e.g. from 91234 ) 1234
or suffix = number % 10; // if you only want the '4' as in your code
an other detail, the question didn't say the number itself must be prime either, so I wouldn't agree with your first if statement. e.g 21 is no prime, but 2 is a prime and 1 is a prime.
JavaScript solution in O(log10 n * sqrt(n)), assuming isPrime runs in O(sqrt(n))
, which is a common implementation.
function isSuperPrime(n){
let tenPow = 10;
let prefix = n / tenPow;
let suffix = n % tenPow;
while(prefix > 0){
if (isPrime(prefix) && isPrime(suffix)){
return true;
}
tenPow *= 10;
prefix = n / tenPow;
suffix = n % tenPow;
}
return false;
}
I read that super-primes are prime numbers whose position in the sequence of prime numbers is also prime. E.g. 3 is prime and it's position is 2nd, which is also prime.
- Anonymous October 10, 2017