Microsoft Interview Question for Junior programmers


Country: Israel
Interview Type: In-Person




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

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.

bool
is_superprime (int n) {
  int i, loc;
  Hashmap *h=NULL;

	if (n==2) {
		return True;
	}

  	if (is_prime(n) == False) {
		return False;
  	}
	
	for (i=3, loc=1; i<=n; i=i+2) {
  		if (is_prime(i) == True) {
			if (i==n) {
				return (exists_in_hashap(loc));
			} else {
				insert_in_hashmap(loc++);
			}
		}
	}
	return False;
}

- Anonymous October 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- PenChief October 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ChrisK October 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK my assumptions are similar to yours, except that I only consider one digit as prefix and suffix. The OP should have given an example for more clarifications. e.g. in your example "192" "1" is the prefix, "2" is the suffix.

- PenChief October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- ChrisK October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK Yes, I assumed it from its name "super-prime" - a prime number with "extras" :)

- PenChief October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You can break number for 2 parts : 0 and Number.
Move in loop from 0/Number to Number/0 by div/mod by 10.
Get 1 loop and isPrime calls equal to number of digits.

- lalka October 10, 2017 | 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