Wednesday, 15 August 2018

Algorithms | Write a program to generate n prime numbers


package com.algorithmforum.misc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class NPrimesInJava {

      /**
       * Sieve of Eratosthenes
       *
       * @param n
       * @return list of n prime numbers.
       */
      private static List getNPrimesUsingSieve(int n) {

            boolean[] array = new boolean[n * n + 1];
            Arrays.fill(array, true);
            List list = new ArrayList<>();

            int i = 2;
            // exit from loop is the n number has been generated.
            while (list.size() < n) {
                  int j = 2;
                 
                  while (array[i] && i * j < array.length - 1) {
                        array[i * j] = false;
                        j++;
                  }
                  if (array[i]) {
                        list.add(i);
                  }
                  i++;
            }
            return list;
      }

      /**
       * Why is every prime no of form 6k+1 or 6k-1?
       *
       * It is because every third number is divisible by 3 and every second number is
       * divisible by 2. Suppose a number, say 17, then 15 16 17 18 19 ...... now you can
       * see number below and above it are divisible by 2, and either of it has to be
       * a multiple of 3, so this formula holds!
       *
       * @param n
       * @return list of n prime numbers.
       */
      private static List getNPrimes(int n) {
            List primeList = new LinkedList<>(Arrays.asList(2, 3));
            int i = 1;
            while (primeList.size() < n) {
                  int prime1 = 6 * i - 1;
                  int prime2 = 6 * i + 1;

                  if (isPrime(prime1)) {
                        primeList.add(prime1);
                  }
                  if (isPrime(prime2)) {
                        primeList.add(prime2);
                  }
                  i++;
            }
            return primeList;
      }

      /**
       * To check that a number is prime or not.
       *
       * @param prime
       * @return return boolean for number is prime or not.
       */
      private static boolean isPrime(int prime) {
            for (int i = 2; i * i <= prime; i++) {
                  if (prime % i == 0) {
                        return false;
                  }
            }
            return true;
      }
     
      public static void main(String[] args) {
            try (Scanner scan = new Scanner(System.in)) {
                  System.out.println("Enter the number: ");
                  int n = scan.nextInt();
                  List primeList = getNPrimes(n);
                  System.out.println(primeList);

                  primeList = getNPrimesUsingSieve(n);
                  System.out.println(primeList);
            }
      }
}


Monday, 13 August 2018

Algorithms | Animal Shelter

An animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the built-in Linked list data structure.

There are many approaches to solve this problem
1. We could maintain a single queue and keep inserting the element in the Queue. Using a single queue, dequeueAny is easy, but dequeueDog and dequeueCat would require iteration through the queue to find the first dog or cat. This would increase the complexity of the solution and decrease the efficiency.


2. An alternative approach that is simple, clean and efficient is to simply use separate queues for dogs and cats, and to place them within a wrapper class called an AnimalShelterQueue. We will store some sort of time stamp (insertion order) to mark when each animal was enqueued. When we call dequeueAny, will return the oldest of the tops of both the dog and cat queue. For operation dequeueDog and dequeueCat, we will return the top of respective queue.

package com.algorithmforum.cci.stack;
import java.util.EmptyStackException;
import java.util.LinkedList;
import java.util.Queue;

abstract class Animal {
      private String name;
      private int order;

      public Animal(String name) {
            this.name = name;
      }

      public int getOrder() {
            return order;
      }

      public void setOrder(int order) {
            this.order = order;
      }

      public String getName() {
            return name;
      }

      /**
       * Inserting the element with Order and incrementing the order by one for every new element.
       * Latest element will maintain the largest value of the Order.
       *
       * @param animal
       * @return boolean value
       */
      public boolean isOlderThan(Animal animal) {
            return this.order < animal.getOrder();
      }
}

class Dog extends Animal {
      public Dog(String name) {
            super(name);
      }

      @Override
      public String toString() {
            return "Dog Name: " + this.getName();
      }
}

class Cat extends Animal {
      public Cat(String name) {
            super(name);
      }

      @Override
      public String toString() {
            return "Cat Name: " + this.getName();
      }
}

/**
 * A clean and efficient approach to maintaining separate queues for dogs and cats,
 * and to place them within a wrapper class called An AnimalShelterStack.
 *
 * We then store some sort of time stamp(insertion order) to mark when each animal was enqueued.
 * When we call dequeueAny, will return the oldest of the tops of both the dog
 * and cat queue.
 * @author rajesh.kumar
 * @since Aug 13, 2018 11:22:56 AM
 */
public class AnimalShelterQueue {

      private Queue dogs;
      private Queue cats;
      private int order;

      public AnimalShelterQueue() {
            this.order = 0;
            this.dogs = new LinkedList<>();
            this.cats = new LinkedList<>();
      }

      /**
       * dequeueAny cases:
       * #1: if both stacks are empty, throw exception as no Animal will found.
       * #2: if dogs stack is empty, return top from the cats stack.
       * #3: if cats stack is empty, return top from the dogs stack.
       * #4: if cats & dogs contains element, return older of top of both stack.
       * @return
       */
      public Animal dequeueAny() {

            System.out.println("------------------dequeueAny------------------");
            if (dogs.isEmpty() && cats.isEmpty()) {
                  throw new EmptyStackException();
            } else if (dogs.isEmpty()) {
                  return dequeueCat();
            } else if (cats.isEmpty()) {
                  return dequeueDog();
            }

            /**
             * Look at top of dog and cat queues, and pop the queue with the oldest value.
             */
            Animal dog = dogs.peek();
            Animal cat = cats.peek();
            boolean isDog = dog.isOlderThan(cat);

            if (isDog) {
                  return dequeueDog();
            } else {
                  return dequeueCat();
            }
      }

      /**
       * Check the type of Animal instance and insert in respective 'stack'.
       * @param animal
       * @return boolean
       */
      public boolean enqueue(Animal animal) {
            /**
             * order is used as a sort of time stamp.
             * It can be used to compare the insertion order of a dog to a cat.
             **/
            animal.setOrder(order++);
            if (animal instanceof Cat) {
                  return cats.add((Cat) animal);
            } else {
                  return dogs.add((Dog) animal);
            }
      }

      /**
       * Return the top of dogs Queue.
       * @return animal
       */
      public Animal dequeueDog() {
            System.out.println("------------------dequeueDog------------------");
            return dogs.poll();
      }

      /**
       * Return the top of cats Queue.
       * @return animal
       */
      public Animal dequeueCat() {
            System.out.println("------------------dequeueCat------------------");
            return cats.poll();
      }

      /**
       * Test the queue.
       * @param args
       */
      public static void main(String[] args) {

            AnimalShelterQueue queue = new AnimalShelterQueue();
            queue.enqueue(new Dog("dog1"));
            queue.enqueue(new Cat("cat1"));
            queue.enqueue(new Cat("cat2"));
            queue.enqueue(new Dog("dog2"));
            queue.enqueue(new Cat("cat2"));
            queue.enqueue(new Dog("dog3"));

            // Should print 'cat1' as it was the first cat entered in Shelter.
            System.out.println(queue.dequeueCat());

            // Should print dog1 as it was the first animal entered in Shelter.
            System.out.println(queue.dequeueAny());

            // Should print cat1 as it is the only cat in the Shelter.
            System.out.println(queue.dequeueDog());
      }
}

OUTPUT:
------------------dequeueCat------------------
Cat Name: cat1
------------------dequeueAny------------------
------------------dequeueDog------------------
Dog Name: dog1
------------------dequeueDog------------------
Dog Name: dog2
Related Posts Plugin for WordPress, Blogger...