Denmin Group Interview Question for Software Engineer / Developers






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

This solution seems to be working, though I have some shaky logic.
love to be proven wrong :)
//Assuming start and end gives the range inclusieve and we have primes given in hashset
//if not we need to create a hashset in the code
//Also end should be less than 101 since we are given only the first 100 primes

public List<int> GetAlmostPrimes(int start, int end, HashSet<int> primes)
        {
            List<int> almostPrimes = new List<int>();
            for (int i = start; i < end; i++)
            {
                //if the number is already prime ignore it
                if (!primes.Contains(i)) 
                {
                    //An array to hold factors size is 4 to avoid out of bounds exception
                    int[] factors = new int[4];
                    int cnt = 0;
                    //We start from 2 because 1 is universal factor 
                    //We end at i/2 because there will be no factors above the mid point of a number
                    for (int j = 2; j <= i / 2; j++)
                    {
                        if (cnt > 2) //Almost primes should have only 4 factors
                            break;
                        if (i % j == 0)
                        {
                            factors[cnt++] = j;
                            factors[cnt++] = i / j;
                        }
                    }
                    //Here we are banking on the fact that the first 2 factors of 
                    //an almost prime should also be prime, otherwise automatically 
                    //its not an almost prime eg. 12
                    //May be shaky logic but have to prove to be buggy to fix the bug :)
                    if (primes.Contains(factors[0]) && primes.Contains(factors[1]))
                        almostPrimes.Add(i);
                }
            }
            return almostPrimes;

}

- prolific.coder May 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

prolific coder, i dont kniow if your logic is working. I will write pseduo code for what i answered:
1. i greated three methods
a. public Int getAlmostPrimes(int start, int last) - this method iterates through the rate and return an int number of all the almost primes in the range
b. private boolean isPrime(int n) - this method test to see the number is prime - i created an array of the prime numbers and just tested the inputted number to the array
c. private boolean isAlmostPrime(int n) - this method just test to see if the number is an almost prime

2. in the public method - first create an int counter, second loop through range, if almost prime increase counter by 1, return counter

3. loop logic - if the number in the range is not a prime and almost prime add one to counter

4. isAlmostPrime - **only divide by lower primes 2 - 13 **
a. test for reminder first - n%prime number - if their is a reminder then go to next number, if there isn't a reminder divide n/prime without reminder, then test to see the answer is a prime. if the answer is a prime return true

- biggied88 May 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

basic code of above psuedo code:

class variable:

//array of all prime numbers 0 to 100
int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

//logic to count the almost prime numbers in the range
public int getAlmostPrimes(int start, int last){
int counter = 0;
for(int i = start; i <= last; i++){
if(!isPrime(i)){
if(isAlmostPrime(i)){
count++;
}
}
i++;
}

//figure out if the given number is a prime number
private boolean isPrime(int n){
boolean prime = false;
for (int item : this.primes) {
if(n == item){
prime = true;
}
}
return prime;
}

//logic to find if the number is an almost prime
private boolean isAlmostPrime(int n){
boolean almostPrime = false;
int value = 0;
if(n < 4){
return almostPrime;
}else if(n % 2 == 0){
value = n / 2;
if(isPrime(value)){
almostPrime = true;
}
}
//repeat logic for lower prime number 3,5,7,11,13
}

}

- biggied88 May 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry bout the alignment, hope you guys can read my code good. I forgot to add the return of the boolean in the isAlmostPrime method. in the almostprime method if the number is less then 4 then you know it can not be an almostprime number - it would of been beeter to add the logic to the get loop method

- biggied88 May 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry bout the alignment, hope you guys can read my code good. I forgot to add the return of the boolean in the isAlmostPrime method. in the almostprime method if the number is less then 4 then you know it can not be an almostprime number - it would of been beeter to add the logic to the get loop method

- biggied88 May 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is wrong.
A k-ary Almost Prime is a number where the sum of the powers of the prime factors is .
The examples are 2-Almost Primes. So 26 = 13 * 2 = prime * prime. 4 = 2*2 = prime * prime.
45 = 3 * 3 * 5 so 45 is 3-AlmostPrime.

- Walter Milner February 13, 2014 | 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