Sunday, July 3, 2016

 Design a stack that supports getMin() in O(1) time with extra space  
 Original problem statement from geeksforgeeks.org  
 This is the generic implementation of this stack data structure.  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public interface IStack <T>{  
  /**  
  * <p>This method will be used to push the element onto stack.<p>  
  *  
  * @param t  
  */  
  public void push(T t);  
  /**  
  * <p>This method will be used to get and remove the top element from stack.<p>  
  * @return  
  */  
  public T pop();  
  /**  
  * It will return the current size of the stack.<p>  
  * @return  
  */  
  public int size();  
  /**  
  * @return  
  * <p> returns <code>true</code> if stack reached its capacity else <code>false</code>.<p>  
  */  
  public boolean isFull();  
  /**  
  *  
  * @return  
  * returns <code>true</code> if stack empty else <code>false</code>.<p>  
  */  
  public boolean isEmpty();  
  /**  
  * <p>It will return minimum element at current position of the stack.<p>  
  * @return  
  *  
  */  
  public T minElement();  
  /**  
  *  
  * @return  
  * <p>It will return user defined {@link Comparator}<p>  
  */  
  Comparator<? super T> comparator();  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  *<p>Question: Design a Data Structure SpecialStack that supports all the stack operations<p>   
  *<p>like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should <p>  
  *<p>return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1).<p>  
  *<p> To implement SpecialStack, you should only use standard Stack data structure and no other data<p>  
  *  
  *  
  */  
 public class MinStack<T> implements IStack<T>{  
  /**This Object array will be used to store elements for stack data structure **/  
  private Object stack[];  
  /**This Object array will be used to store minimum elements for stack data structure **/  
  private Object minStack[];  
  /** Capacity will be used to define the maximum size of stack**/  
  private int capacity;  
  /** Index will be used to store the element in Object array.**/  
  private int index;  
  /** DEFAULT_CAPACITY is the maximum default capacity of stack**/   
  private final static int DEFAULT_CAPACITY=10;  
  /**   
  * <p>{@linkplain Comparator} Will be used to compare the current minimum element with new element for user define class.<p>  
  * <p>User defined class must implement {@linkplain Comparator} interface.<p>  
  * **/  
  private final Comparator<? super T> comparator;  
  /**  
  * <p>This Constructor can be used for all wrapper classes with default {@link MinStack#capacity}<p>  
  */  
  public MinStack() {  
  this.capacity = DEFAULT_CAPACITY;  
  this.comparator = null;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  * <p>This Constructor can be used for all wrapper classes with user defined {@link MinStack#capacity}<p>  
  * @param capacity  
  */  
  public MinStack( int capacity) {  
  this.capacity = capacity;  
  this.comparator = null;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  *<p>This Constructor can be used for all user defined classes and comparator with default {@link MinStack#capacity}<p>  
  * @param comparator  
  */  
  public MinStack(Comparator<? super T> comparator) {  
  this.capacity = DEFAULT_CAPACITY;  
  this.comparator = comparator;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  * <p>This Constructor can be used for all user defined classes and comparator with user defined {@link MinStack#capacity}<p>  
  * @param comparator  
  * @param capacity  
  */  
  public MinStack(Comparator<? super T> comparator, int capacity) {  
  this.capacity = capacity;  
  this.comparator = comparator;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#push(java.lang.Object)  
  */  
  @SuppressWarnings("unchecked")  
  @Override  
  public void push(T t) {  
  if(this.isFull()){  
   throw new RuntimeException("Stack is over flow.");  
  }  
  if(this.isEmpty()){  
   minStack[index] = t;  
  }else if(null != comparator && 0<=comparator.compare((T)minStack[index-1],t)){  
   minStack[index]=t;  
  }else if(0<=((Comparable< ? super T>)minStack[index-1]).compareTo(t)){  
   minStack[index]=t;  
  }else{  
   minStack[index]=minStack[index-1];  
  }  
  stack[index++] = t;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#pop()  
  */  
  @Override  
  public T pop() {  
  @SuppressWarnings("unchecked")  
  T t = (T)stack[--index];  
  stack[index] = null;  
  minStack[index]= null;  
  return t;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#size()  
  */  
  @Override  
  public int size() {  
  return index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#isFull()  
  */  
  @Override  
  public boolean isFull() {  
  return this.capacity==index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#isEmpty()  
  */  
  @Override  
  public boolean isEmpty() {  
  return 0==index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#minElement()  
  */  
  @SuppressWarnings("unchecked")  
  @Override  
  public T minElement() {  
  return (T)minStack[index-1];  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#comparator()  
  */  
  @Override  
  public Comparator<? super T> comparator() {  
  return comparator;  
  }  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public class User {  
  public int id ;  
  public User(int id) {  
  this.id=id;  
  }  
  /* (non-Javadoc)  
  * @see java.lang.Object#toString()  
  */  
  @Override  
  public String toString() {  
  return "id = "+id;  
  }  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 public class Main {  
  public static void main(String[] args) {  
  MinStack<String> minStack = new MinStack<>(3);  
  minStack.push("A");  
  minStack.push("C");  
  minStack.push("B");  
  minStack.pop();  
  MinStack<User> userDefinedClassMinStack = new MinStack<>(new Comparator<User>() {  
   @Override  
   public int compare(User o1, User o2) {  
   return o1.id > o2.id ? 1: o1.id == o2.id ? 0 : -1;  
   }  
  });  
  User t = new User(1);  
  User t1 = new User(2);  
  User t3 = new User(3);  
  userDefinedClassMinStack.push(t);  
  userDefinedClassMinStack.push(t1);  
  userDefinedClassMinStack.push(t3);  
  userDefinedClassMinStack.pop();  
  }  
 }
Posted by at No comments:

Tuesday, June 21, 2016

Reverse stack using recursion in java 

 Here I am going to implement stack with fixed size of array and it also has behavior that will reverse the stack data.  
 package com.raj;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public class Stack<T> {  
  private Object stack[];  
  private int capacity;  
  private int index;  
  private final static int DEFAULT_SIZE=10;  
  public Stack(){  
  this(DEFAULT_SIZE);  
  }  
  public Stack(int capacity){  
  this.capacity = capacity;  
  stack = new Object[capacity];  
  }  
  /**  
  *  
  * @return boolean  
  */  
  public boolean isEmpty(){  
  return this.index==0;  
  }  
  /**  
  *  
  * @return boolean  
  */  
  public boolean isFull(){  
  return this.capacity==this.index;  
  }  
  /**  
  * <p>This method will be used to push the data at top.<p>  
  * @param t  
  */  
  public void push(T t){  
  if(isFull())  
   throw new IllegalArgumentException("Stack over flow.");  
  stack[index++]=t;  
  }  
  /**  
  * <p>This method will return and remove the top element.<p>  
  * @return  
  */  
  @SuppressWarnings("unchecked")  
  public T pop(){  
  if(isEmpty())  
   throw new IllegalArgumentException("stack under flow.");  
   T t= (T)stack[--index];  
   stack[index] = null;  
   return t;  
  }  
  /**  
  * <p>This method will reverse the existing stack recursively.<p>  
  * @param size  
  */  
  public void reverse(int size){  
  if(size==0){  
   return;  
  }  
  T t = pop();  
  reverse(size-1);  
  inserAtBottom(t);  
  }  
  /**  
  * <p>This method returns number of elements in stack.<p>  
  * @return  
  */  
  public int size(){  
  return index;  
  }  
  /**  
  * <p>Inserts the element at bottom in existing stack.<p>  
  * @param t  
  */  
  private void inserAtBottom(T t){  
  if(isEmpty()){  
   push(t);  
  }else{  
   T tmp = pop();  
   inserAtBottom(t);  
   push(tmp);  
  }  
  }  
 }  
 Main method:  
 package com.raj;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public class StackMain{  
  public static void main(String[] args) {  
  Stack<Integer> stack = new Stack<>();  
  for (int i = 0; i < 10; i++) {  
   stack.push(i);  
  }  
  stack.reverse(stack.size());  
  while(stack.size()!=0){  
   System.out.println(stack.pop());  
  }  
  Stack<String> stacks = new Stack<>();  
  stacks.push("A");  
  stacks.push("B");  
  stacks.push("C");  
  stacks.reverse(stacks.size());  
  while(stacks.size()!=0){  
   System.out.println(stacks.pop());  
  }  
  }  
 }
Posted by at No comments:

Tuesday, August 11, 2015

Sieve of Eratosthenes Prime Number :-

Seive of Eratosthenes find the number on the based of upper bound, where you say, find the prime number less than equal to n.
Seive of Eratosthenes mark all the composite number first and then find all the non-composite number as prime number.
We know that 2 is the first prime number, so all the multiple of 2 would be composite number, Seive of Eratosthenes will mark all such number as composite and he will take next prime from the list and all it's multiple would be marked as composite number. This process will be followed till square root of n.
So Seive of Eratosthenes algorithm will be like below:-
  • For all numbers m: 2 .. √n, if m is unmarked:
    • add m to primes list;
    • mark all it's multiples, starting from square, lesser or equal than n (k * m ≤ n, k ≥ m);
  • otherwise, if m is marked, then it is a composite number;
  • check all numbers in range √n .. n. All found unmarked numbers are primes, add them to list.
2 is prime number so we will mark all multiple of 2 starting from square of 2 means 4 as composite number as in below table.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
3 is the next prime number so we will make all multiple of 3 starting from square of 3 means 9 as composite number as in below table.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

5 is the next prime number so we will make all multiple of 5 starting from square of 5 means 25 as composite number as in below table.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

By this way you can mark all the composite number and remaining non-marked number would be prime number as below table
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




Java implementation of Seive of Eratosthenes

package com.techguy.algo;

/**
 * @author techguylearning@gmail.com
 *
 */
public class PrimeNumberSieveOfEratosthenes {

public static void main(String[] args) {
new PrimeNumberSieveOfEratosthenes().primeNumbers(100);
}
public void primeNumbers(int upperBound){
boolean isComposite[] = new boolean[upperBound + 1];
int upperBoundSqrt = (int)Math.sqrt(upperBound);
for (int i = 2; i <=upperBoundSqrt ; i++) {
if(!isComposite[i]){
for(int k = i*i; k < upperBound; k = k+i){
isComposite[k]=true;
}
}
}
for (int i = 2; i < upperBound; i++) {
if(!isComposite[i]){
System.out.print(i+" ");
}
}
}
}

Note:- This algorithm is marking some number more than one times as composite that is drawback of this algorithm.
Posted by at No comments:
Subscribe to: Posts (Atom)