Sunday 29 January 2017

poll(), peek() and remove() Method in the Queue

E java.util.PriorityQueue.poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.

Specified by: poll() in Queue
Returns: the head of this queue, or null if this queue is empty


E java.util.PriorityQueue.peek()
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Specified by: peek() in Queue
Returns: the head of this queue, or null if this queue is empty

E java.util.AbstractQueue.remove()
Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.

Specified by: remove() in Queue
Returns: the head of this queue
Throws: NoSuchElementException - if this queue is empty




poll() vs remove() Method in the Queue

E java.util.PriorityQueue.poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.
Specified by: poll() in Queue
Returns: the head of this queue, or null if this queue is empty

E java.util.AbstractQueue.remove()
Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.

Specified by: remove() in Queue
Returns: the head of this queue
Throws: NoSuchElementException - if this queue is empty.


Monday 16 January 2017

PiorityQueue in Java

PiorityQueue(=belongs to the Java Collections Framework) is an unbounded Queue, which is based on  priority heap and it is an implementation of Queue interface. It can be used to keep elements in a particular order, according to their natural order (=Comparable) or custom order defined by Comparator interface based on each element’s priority.

PriorityQueue is not synchronized i.e. it cannot be safely shared between multiple threads. To avoid the Concurrent Modification Exception, PriorityBlockingQueue(= thread-safe) can be used in multithreaded environment.

Priority queue provides O(log(n)) time performance for common enqueing and dequeing methods e.g. offer(), poll() and add(), but constant time for retrieval methods e.g. peek() and element().

It was introduced in JDK 1.5.

Java PriorityQueue key points:
1. A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided.

public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator)
If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.

2. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

3. null is not allowed in this Collection. It will throw the NullPointerException.

4. The head of this queue is the least element with respect to the specified ordering.

5. Ordering ties between the PriorityQueue elements are decided arbitrarily (=on the basis of random choice).

5. PriorityQueue is not synchronized. PriorityBlockingQueue is the thread-safe counterpart of PriorityQueue.

6. PriorityQueue is unbounded and it grows dynamically based on the number of elements in the Queue. It has internal capacity at any given time and it is increased as the elements are added. The policy for this internal capacity and increment is not specified or standardized.

7. The iterator() of this PriorityQueue does not guarantee for traversal of the Queue elements in any particular order.

PriorityQueueTest.java
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueTest {

      public static void main(String args[]) {

            Queue<MobilePhone> items = new PriorityQueue<MobilePhone>();
            items.add(new MobilePhone("Samsung", 100));
            items.add(new MobilePhone("Iphone", 400));
            items.add(new MobilePhone("Blackberry", 200));
            items.add(new MobilePhone("HTC", 300));

            System.out.println("Mobiles phones list: ");
            System.out.println(items);
      }
}

class MobilePhone implements Comparable<MobilePhone> {
     
      private String name;
      private int price;

      public MobilePhone(String name, int price) {
            this.name = name;
            this.price = price;
      }

      public String getName() {
            return name;
      }

      @Override
      public int compareTo(MobilePhone phone) {
            return this.price - phone.price;
      }

      @Override
      public String toString() {
            return String.format("Brand:%s Price: $%d", name, price);
      }     
}

References:

Thursday 12 January 2017

Maximum Subarray Sum: Kadane's algorithm

Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.

Usage of Kadane's algorithm         

It is used to obtain the maximum subarray sum from an array of integers.

Pseudo code:

Initialize: max_so_far = 0
max_ending_here = 0

Loop for each element of the array
               max_ending_here = max_ending_here + a[i]
               if(max_ending_here < 0)
                              max_ending_here = 0
               if(max_so_far < max_ending_here)
                              max_so_far = max_ending_here
return max_so_far

Code in Java:


import java.util.Scanner;

/* Class kadane */
public class KadaneAlgorithm {
      /* Function to largest continuous sum */
      public static int maxSequenceSum(int[] arr) {       
            int maxSoFar = arr[0], maxEndingHere = arr[0];

            for (int i = 1; i < arr.length; i++) {
                 
                  /* calculate maxEndingHere */
                  if (maxEndingHere < 0) {
                        maxEndingHere = arr[i];
                  } else {
                        maxEndingHere += arr[i];
                  }
                  /* calculate maxSoFar */
                  if (maxEndingHere >= maxSoFar) {
                        maxSoFar = maxEndingHere;
                  }
            }
            return maxSoFar;
      }

      public static void main (String[] args) {
            int[] arr = {8,6,5,-19,-24,2,8,9,14,-1,7};
            int sum = KadaneAlgorithm.maxSequenceSum(arr);
            System.out.println("Maximum Sequence sum is: "+ sum);
      }
}
Output: Maximum Sequence sum is: 39

Wednesday 11 January 2017

Significance of using Spring’s Hibernate Template



Spring's Hibernate Template (i.e. org.springframework.orm.hibernate.HibernateTemplate) is a helper class which provides utility methods for querying/retrieving data from the database. It also converts checked HibernateExceptions into unchecked DataAccessExceptions.

Benefits of HibernateTemplate:
  • HibernateTemplate, a Spring Template class simplifies interactions with Hibernate Session.
  •  Common functions are simplified to single method calls.
  •  Sessions are automatically closed.
  •  Exceptions are automatically caught and converted to runtime exceptions.


Tuesday 10 January 2017

Cut Paper into Minimum Number of Squares


Given a paper of size L x W, cut the paper into squares of any size and the count of the squares should be minimum.

Examples:
Input: 4 x 5
Output: 5
Explanation:
1 (squares of size 4x4) +
4 (squares of size 1x1)

Think that if we want to cut minimum number of squares from the paper then we would have to cut largest square possible from the paper first and largest possible square will contain the side as smaller side of the paper. Same operation will perform recursively on remaining paper.

public class MinNumSqr {
    
     private static int getMinNumSqr(int len, int wid) {

           int count = 0;
          
           if(wid>len) {
                int tmp = len;
                len = wid;
                wid = tmp;
           }

           while(wid>0) {
                count = count + len/wid;
               
                int rem = len % wid;
                len = wid;
                wid = rem;
           }
          
           return count;
     }   
    
     public static void main(String[] args) {
           int len = 13, wid = 29;
           int minSqr = getMinNumSqr(len,wid);
           System.out.println("Min Number of square#"+ minSqr);
     }
}




Related Posts Plugin for WordPress, Blogger...