Last months have been trying to seek a career change. Among different job interviews and screenings I got to know also Intercom. It left an awesome and bitter experience. I did manage to go to the on-site interview but I did not get an offer (sigh)… but that story would belong to another post.
I spent three days in Dublin and had a chance to make a second visit to the city. All is left from this trip are the souvenirs on the left, which I’ll get rid very quickly 🍻 (I could not find Programmer’s Tears whiskey), and the preparation with Codility Lessons. These lessons consist in various algorithm solving problems which in my case helped me a lot to polish some CS algorithm concepts. I solved all ‘Painless’ and most of ‘Respectable’ ones by myself, and noticed that in particular the solution of two problems could not be found online. So I just wanted to publish my solution to the problems of Sieve of Eratosthenes lesson. Unfortunately I cannot post the problems because they are subject of copyright by Codility. Both solutions get 100% score on correctness and performance. Please find the spartan explanation as comments between source code lines.
CountSemiprimes
class Solution { public int[] solution(int N, int[] P, int[] Q) { //the first semi prime is number 4 if (N <= 3){ return new int[1]; } // build the sieve of primes up to N/2. Since // the smallest prime is 2, we cannot consider // primes bigger than N/2 because the product // with 2 would result bigger than N. boolean[] primes = new boolean[N/2 + 1]; for (int i = 0;i <= N / 2;i++){primes[i] = true;} primes[0] = false; primes[1] = false; int i = 2; while (i * i <= N / 2){ if (!primes[i]){ i++; continue; } int k = i * i; while(k <= N / 2){ primes[k] = false; k += i; } i++; } // build another sieve for semi primes now boolean[] semiPrimes = new boolean[N + 1]; for (int j = 1; j <= N/2; j++){ if (primes[j]){ int k = j; // be aware here, the product may overflow // resulting in a negative number that passes // the check to be smaller than N long product = (long)k * j; while(product <= N){ if (primes[k]){ semiPrimes[j*k] = true; } k++; product = (long)k * j; } } } //use prefix sum to count the semi primes //in the required queries. int[] prefix_sum = new int[N + 1]; int sum = 0; for (int j = 0; j <= N;j++){ if (semiPrimes[j]){ sum++; } prefix_sum[j] = sum; } int[] result = new int[P.length]; for (int j = 0; j < P.length; j++){ result[j] = prefix_sum[Q[j]] - prefix_sum[P[j]-1]; } return result; } }
CountNonDivisible
class Solution { public int[] solution(int[] A) { //each element A is within the range [1..2 * N] int[] factors = new int[A.length * 2 + 1]; //count how many times each factor appear for (int i = 0;i < A.length; i++){ factors[A[i]]++; } //build a sieve which saves all the common //multiples smaller than 2 * N of the input factors int multi[] = new int [factors.length]; for (int i = 1;i < multi.length;i++){ if (factors[i] == 0) continue; int k = 1; long product = (long)i * k; while(product < multi.length){ //we increase the number of multiples //by the number of factors in the input //array multi[k * i] += factors[i]; k++; product = (long)i * k; } } //for each input element the number of non divisors //is the difference of the total number of elements //and the number of times that element appears as a //multiple of other input elements int result[] = new int[A.length]; for (int i = 0;i < A.length; i++){ result[i] = A.length - multi[A[i]]; } return result; } }
Any suggestion is more than welcome! Happy coding!!!
Leave A Comment