DS Basics : Java Collections to Implement Stack and Queue

Hi folks ,
 
This is a very basic java lesson to how understand how we can best implement  a stack and a queue using Java Collections .
 
Stack - A stack is a data structure used to store a collection of objects. When an object is pushed to a stack, it is placed on the top of all previously entered items. When an item is popped off , it is removed from the top of the stack. It's a LIFO data structure.
 
Queue - Queue is also a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.
 
Let's use collections to implement a stack and a queue.
 
In this lesson we will be using Java's Deque interface and ArrayDeque implementation  to implement stack as well as queue.
 
The methods used will be :
 
push() | addFirst() -> Adds elements to the top of the stack .
pop() | removeFirst() -> Removes elements from the top of the stack.
 
add() |  addLast() -> Adds elements to the end of the queue.
remove() | removeFirst() -> Removes elements from the head of the queue.
 
Let's write a quick small program .

package arraydeq;
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDeqStack {
private Deque<Integer> stk = new ArrayDeque<Integer>();
 // We could have also used the stack class but the arraydeque is 
 // likely to be faster than Stack when used as a stack, and faster
 // than theLinkedList when used as a queue.  

public void stack() {
  stk.push(1);
  stk.push(2);
  stk.addFirst(3);
  stk.push(4);
  stk.push(5);
  System.out.println(stk);  // [5, 4, 3, 2, 1]
  System.out.println(stk.pop()); //5
  System.out.println(stk.removeFirst()); //4
  System.out.println(stk.pop()); //3
  System.out.println(stk.pop()); //2
  System.out.println(stk.pop()); //1
}

public void queue() {
  stk.add(1);
  stk.add(2);
  stk.addLast(3);
  stk.add(4);
  stk.add(5);
  System.out.println(stk); // [1, 2, 3, 4, 5]
  System.out.println(stk.remove()); //1
  System.out.println(stk.remove()); //2
  System.out.println(stk.remove()); //3
  System.out.println(stk.removeFirst()); //4
  System.out.println(stk.remove()); //5
 }
}
 
That's all folks , Happy Learning .

LRU cache implementation in Java using LinkedHashMap

Hi Folks , 

If you have not worked on this problem before , the following might help you get an understanding. Most of the people fail to recognize that LinkedHashMap provides the support and can be used off-the-self with minimal code.

What is Least Recently Used (LRU) Cache ?? 


First , What is  a cache ?? 

A cache in Computing World, is a place to store something temporarily in a computing environment. Active data from any data Source be it a database or a file system or network , is often cached to shorten data access times, reduce latency and improve input/output (I/O) and hence the application performance.

Cache always has limited memory and can contain only limited number of items. 

Now what happens if a cache is full ?? 

If a cache is full, an item needs to be evicted from the cache. There are different algorithms used in Cache item eviction. The most popular one is the Least-Recently-Used. Hence the name LRU cache. It uses an algorithm to detect and evict items which are the oldest in the cache. The algorithm keep tracks of the items’ last accessed time. It evicts the items which have oldest access timestamp.

LRU Cache Implementation

java.util.LinkedHashMap is quite helpful in implementing a LinkedHashMap. It has a method removeEldestEntry() , that should be overridden. This method gets called after put() and putAll(). 

Based on its return value Map removes the old entry. If this method returns true, then old entry is removed. Otherwise it can stay in the Map. The default implementation of this method returns false and in such a case , the old entries remain in the Map and never get deleted.

Override the method and return true if the number of entries in the map is greater than initial capacity.

Let's write some code now - 

package sampleLru;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheImpl<K, V> extends LinkedHashMap<K, V> {

private static final long serialVersionUID = 1L;
private int capacity;

public LRUCacheImpl(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}

public int getCapacity() {
return capacity;
}

/**
* removeEldestEntry() should be overridden by the user, otherwise it will
* not remove the oldest object from the Map.
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
if (size() > this.capacity) {
System.out.println("Cache is full : Eldest Entry is "
+ eldest.getKey());
}
return size() > this.capacity;
}

}

--------------------------------------------------------------------

package sampleLru;

import java.util.Map;

public class UseLRUCache {

public static void main(String[] args) {

Map<Integer, String> cache = new LRUCacheImpl<>(3);

cache.put(1, "One");

cache.put(2, "Two");

cache.put(3, "Three");

System.out.println(cache + " SIZE " + cache.size());

cache.get(1);

cache.put(4, "Four");

cache.get(3);

System.out.println(cache + " SIZE " + cache.size());

cache.put(5,"Five");

}

}

Console Output : 

{1=One, 2=Two, 3=Three} SIZE 3

Cache is full : Eldest Entry is 2

{1=One, 4=Four, 3=Three}

Cache is full : Eldest Entry is 1

-------------------------------------------------------------------

Let's try to understand the program and the output .

-> Extend the java.util.LinkedHashMap class, define a constructor that takes the capacity of the cache and instantiate a cache of that capacity.

for super(capacity, 0.75f, true); , see here for LinkedHashMap constructor , to understand what it means to send true or false.




accessOrder - the ordering mode - true for access-order, false for insertion-order.

-> Further override the removeEldestEntry method 

UseLRUCache : 

-> Create a cache of capacity 3 , add three elements to the cache with key 1,2 and 3.

-> Access element 1 , now 1 is the recently used entry and then 3 and least recently used entry is 2.

-> Add key 4 , this prints Cache is full : Eldest Entry is 2

-> Access element with key 3.

Now the 1 is the oldest entry then 4 and  the recently accessed is 3.

-> Adding key 5 to the cache , removes the entry 1 from the cache.

Please run the above program to better understand the LRU cache. Thanks for reading . My next blog will be about implementing an LRU cache in java from scratch using other collections.

Happy Learning

One way InterThread communication using Buy Item / Replenish Store example

Hi Folks, 

Below i am explaining a basic E-commerce example where a user has two actions A (Add to Store) and B (Add to Cart) . The inventory is stored with an item number and quantity. 

Add to Cart : 
-> If item does not exist - return false with item not exists logger. 
-> If item exists , and quantity is short , wait for 5 seconds till another user adds the required quantity to the store, and calls notifyAll .
-> If after 5 seconds or after notify call , the quantity is not replenished , log it and return false. 
-> If after 5 seconds or after notify call , the quantity is replenished , return true .

Add to Store :
-> If item exists , update its quantity , call notifyAll to awake any waiting threads.
-> If item does not exists , create Inventory .

Please find the code that explains the above problem :

Thanks for reading, if any doubts please comment out , will be happy to help .

Happy Learning 

package ecomm;

public class Inventory {

    private int itemNumber;
    private int quantity;

    Inventory(int itemNumber, int quantity) {
        this.itemNumber = itemNumber;
        this.quantity = quantity;
    }

    public int getItemNumber() {
        return itemNumber;
    }

    public void setItemNumber(int itemNumber) {
        this.itemNumber = itemNumber;
    }

    public int getQuantity() {
        return quantity;
    }

    public void setQuantity(int quantity) {
        this.quantity = quantity;
    }
}
 
 ========================================================

package ecomm;

import java.time.Duration;
import java.time.Instant;
import java.util.Iterator;
import java.util.List;

public class InventoryManager {

    private List<Inventory> inventory;

    public InventoryManager(List<Inventory> inventory) {
        this.inventory = inventory;
    }

    public List<Inventory> getInventory() {
        return inventory;
    }

    public synchronized void addToStore(Inventory inventory) {
        for (Iterator<Inventory> itr = this.inventory.iterator(); itr.hasNext();) {
            Inventory current = itr.next();
            if (current.getItemNumber() == inventory.getItemNumber()) {
                System.out.println("Existing Inventory "
                        + current.getItemNumber() + " : "
                        + current.getQuantity() + " Adding more "
                        + inventory.getQuantity());
                current.setQuantity(current.getQuantity()
                        + inventory.getQuantity());
                notifyAll();
                return;
            }
        }
        System.out.println("New Inventory " + inventory.getItemNumber() + " : "
                + inventory.getQuantity());
        this.inventory.add(inventory);
    }

    public synchronized boolean addToCart(Inventory inventory) {
        boolean exists = false;
        Instant t = null;
        for (Inventory inv : this.inventory) {
            if (inv.getItemNumber() == inventory.getItemNumber()) {
                exists = true;
                if (inventory.getQuantity() > inv.getQuantity()) {
                    try {
                        System.out.println("Inventory is less in number "
                                + inv.getItemNumber() + " : "
                                + inv.getQuantity() + " Need : "
                                + inventory.getQuantity());
                        t = Instant.now();
                        wait(5000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                Instant n = Instant.now();
                System.out.println("Elements found "
                        + Duration.between(t, n).getSeconds());
                if (inventory.getQuantity() > inv.getQuantity()) {
                    System.out
                            .println("Quantity not replenished : failing order");
                    return false;
                } else {
                    System.out.println("Order Found " + inventory.getQuantity()
                            + " = " + inv.getQuantity());
                    inv.setQuantity(inv.getQuantity() - inventory.getQuantity());
                    break;
                }
            }
        }
        if (!exists) {
            System.out.println("Inventory not found exception");
            return false;
        }
        return true;
    }
}
 
==========================================================

package ecomm;

import java.util.List;
import java.util.Scanner;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Starter {

    public static void main(String[] args) throws InterruptedException,
            ExecutionException {
        List<Inventory> inventory = new CopyOnWriteArrayList<Inventory>();
        for (int i = 1; i < 100; i++) {
            inventory.add(new Inventory(i, i * 3));
        }
        InventoryManager iM = new InventoryManager(inventory);
        ExecutorService service = Executors.newCachedThreadPool();
        Scanner sc = new Scanner(System.in);
        String read = sc.nextLine();
        while (!read.equals("quit")) {
            String[] nextSet = read.split(" ");
            String action = nextSet[0];
            int itemNumber = Integer.parseInt(nextSet[1]);
            int quantity = Integer.parseInt(nextSet[2]);
            service.execute(new Runnable() {

                @Override
                public void run() {
                    if (action.equals("B")) {
                        iM.addToCart(new Inventory(itemNumber, quantity));
                    } else if (action.equals("A")) {
                        iM.addToStore(new Inventory(itemNumber, quantity));
                    }
                }
            });
            read = sc.nextLine();
        }
    }
}

Binary Search Based Problems

Local Minima 

1). For example in the array 9,6,2,14,5,7,4 – 2 is a local minima as it is smaller than its left and right number 6 and 14. Similarly 5 is another local minima as it is between 14 and 7, both larger than 5. You need to find any one of the local minima.

/* package whatever; // don't place packageg name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
                int arr[] = {1,5,17,15,12,10,7,11,6,2,4};
int min = localMin(arr , 0 , arr.length  -1);
System.out.println("Min " + min);

}

public static int localMin(int[] arr , int start , int end) {
if (arr.length == 1) {
return arr[0];
}
if (arr.length == 2) {
if (arr[0] < arr[1]) {
return arr[0];
} else {
return arr[1];
}
}
int mid = (start + end) / 2;
if (arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1]) {
return arr[mid];
} if (arr[mid-1] < arr[mid]) {
return localMin(arr ,start , mid-1);
} else {
return localMin(arr,mid+1,end);
}
}
}

Missing Number in An Array

2). You are given an array of n – 1 unique numbers in the range from 0 to n – 1. There is only one number missing in the range from 0 to n – 1 . 

Since numbers from 0 to n – 1 are sorted in an array, the first numbers should be same as their indexes. That’s to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. Therefore, it is required to search in an array to find the first cell whose value is not identical to its value. Since the array is sorted, we could find it in O(log n) time based on the binary search algorithm as implemented below:

/* package whatever; // don't place packageg name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {0, 1,2,4,5,6,7 , 8,9,10,11,12,13,14,15,16,17,18};
int number = missingNumber(arr , 0 , arr.length -1);
System.out.println("Missing " + number);

}

public static int missingNumber(int[] a , int start , int end) {
int mid = (start + end) /2;
if (a[mid] != mid && a[mid-1] == (mid -1)) {
return mid ;
}
if (a[mid-1] == (mid -1)) {
return missingNumber(a, mid+1 , end);
} else {
return missingNumber(a ,start , mid-1);
}
}
}

Find the Minimum Element in the Rotated Sorted array

3). Find the minimum element in the rotated sorted array.

For example we have array as  1,3,6,9,12,15.

Now suppose the array is rotated k times ( we don’t know k), such that array becomes

12,15,1,3,6,9

/* package whatever; // don't place packageg name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

int arr[] = {6,9,12,15,1,3};

int elem = minElement(arr , 0 , arr.length-1);

System.out.println("Minimum " + elem);

}

public static int minElement(int[] a , int start , int end) {

int mid = (start + end) /2 ;

if (start == mid) {

return a[mid + 1];

}

if (a[start] > a[mid]) {

return minElement(a,start,mid-1);

}

else {

return minElement(a,mid+1,end);

}

}

}

Find a Peak Element in Array

4). A peak element in an integer array is defined as an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [2, 4, 8, 3], 8 is a peak element and your function should return the index number 2.

/* package whatever; // don't place packageg name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

        int arr[] = {1,5,9,11,13,2,6,3,14};

int peak = peakElement(arr , 0 , arr.length  -1);

System.out.println("Peak " + peak);

}

public static int peakElement(int[] arr , int start , int end) {

if (arr.length == 1) {

return arr[0];

}

if (arr.length == 2) {

if (arr[0] > arr[1]) {

return arr[0];

} else {

return arr[1];

}

}

int mid = (start + end) / 2;

if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {

return arr[mid];

} if (arr[mid-1] > arr[mid]) {

return peakElement(arr ,start , mid-1);

} else {

return peakElement(arr,mid+1,end);

}

}

}

Java Initialization blocks, constructors and order of execution

Hi folks ,

This session brings to you the understanding of what initialization blocks are and how they are executed in java programs.

Initialization blocks are the blocks of code where one can perform operations like initialization of variables or execution of some statements. They are of two types :

1. static initialization blocks
2. instance initialization blocks.

Static initialization blocks are static and hence they belong to a particular class and not to the instances of class. e.g.

static {
         // piece of code
}

Instance initialization blocks do not belong to a class and they are executed every time a new instance of the class is created. e.g.

{
        // piece of code
}

Let's write a basic simplest java program with a base Class and another subclass extending this base Class , write parameterized constructors , empty constructors , with static and instance initialization blocks both in base class and sub class .

BaseClass : 

package execOrder;

public class BaseClass {

    private String baseClassStr;
    private boolean baseClassBool;
   
    static {
        System.out.println("BaseClass static init block 1");
    }
   
    {
        System.out.println("BaseClass instance init block 1");
    }
   
    public BaseClass(boolean baseClassBool) {
        this.baseClassBool = baseClassBool;
        System.out.println("BaseClass constructor - baseClassBool is : " + baseClassBool);
    }
   
    public BaseClass() {
        System.out.println("BaseClass no Args Constructor");
    }

    static {
        System.out.println("BaseClass static init block 2");
    }
   
    {
        System.out.println("BaseClass instance init block 2");
        System.out.println("baseClassBool is : " + baseClassBool);
    }  
}

SubClass :

package execOrder;

public class SubClass extends BaseClass {

    private String subClassStr;
    private int subClasssInt;

    static {
        System.out.println("SubClass static init block 1");
    }

    public SubClass(String val) {
        super(true);
        System.out.println("SubClassConstructor : subClassInt =  " +  subClasssInt);
        this.subClassStr = val;
        System.out.println("SubClassConstructor : subClassStr =  " +  subClassStr);
    }

    public SubClass() {
        super();
        System.out.println("SubClass no Args Constructor");
    }

    {
        System.out.println("SubClass instance init block 1");
    }

    static {
        System.out.println("SubClass static init block 2");
    }

    {
        System.out.println("SubClass instance init block 2");
        System.out.println("SubClassInt =  " +  subClasssInt + " SubClassStr = " + subClassStr);
        subClasssInt = 1;
        System.out.println("SubClassInt =  " +  subClasssInt);
    }
   
    public static void main(String[] args) {
        new SubClass();
 System.out.println("--------------################--------------");
        new SubClass("start");
    }
} 

-----------------------------------------------------------------
Console Output : 
BaseClass static init block 1
BaseClass static init block 2
SubClass static init block 1
SubClass static init block 2
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false
BaseClass no Args Constructor
SubClass instance init block 1
SubClass instance init block 2
SubClassInt =  0 SubClassStr = null
SubClassInt =  1
SubClass no Args Constructor
--------------################--------------
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false
BaseClass constructor - baseClassBool is : true
SubClass instance init block 1
SubClass instance init block 2
SubClassInt =  0 SubClassStr = null
SubClassInt =  1
SubClassConstructor : subClassInt =  1
SubClassConstructor : subClassStr =  start

Let's try to analyse the above output : 

new SubClass(); calls the subClass constructor , and at this point of time all the static initialization happens in order of derivation of classes , here Base class first and Sub class later.This happens only once when the class is loaded into the JVM . These set of statements will not be executed for further object creation of this class.
 
--------------
BaseClass static init block 1
BaseClass static init block 2
SubClass static init block 1
SubClass static init block 2
--------------
 
The static initialization blocks got executed in order of inheritance.


Next is what , next though the control was passed to the constructor of the subclass which called super() passing control to the constructor of the base class . Now before the constructor actually executes code , some important activities are done .

-> Instance variables are initialized to default values. In this case baseClassStr will get a value null and baseClassBool will get the default value false.
-> Then the instance initialization blocks are executed in order of their appearance in the code.

------------------
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false // value is by default initialization.
------------------ 

Then finally the constructor's code of the super class got executed and prints: 
------------------
BaseClass no Args Constructor
------------------

Similarly now control comes back to sub class and the same set of activities happen in the sub class as well.

------------------ // instance init blocks
SubClass instance init block 1
SubClass instance init block 2
------------------
SubClassInt =  0 SubClassStr = null // default initialization
------------------
SubClassInt =  1 // explicit initialization as part of instance
                 // init block 
------------------
SubClass no Args Constructor  // and finally the sub class
                              // constructor.
------------------ 

The next of line in code creates another object of the sub class but this time calling the parametrized constructor.

The same set of activities happen in the base class first and then in the sub class , except for the static blocks getting called and executed again , because they are called only once during class loading and are not called per instance creation of the class unlike Instance initialization block which is called for each instance created of the class.

Base class execution 
-----------------
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false
BaseClass constructor - baseClassBool is : true
-----------------

Sub class execution
-----------------
SubClass instance init block 1
SubClass instance init block 2
SubClassInt =  0 SubClassStr = null
SubClassInt =  1
SubClassConstructor : subClassInt =  1
SubClassConstructor : subClassStr =  start
-----------------

To summarize : 

1. Static initialization happens when class is loaded into the JVM .This piece of code is only executed once.
2. Next , the constructor is called and calls the super class constructors till the top most class Object.class's constructor gets called.
3. In the top most base class , the instance variables get their default values. 
4. The initialization blocks get executed in the order of appearance in the code. Instance initialization code is run for each instance of the class created.
5. The part of the code written in constructor of the super-most class , now gets executed. 
6. The same set of steps if followed until the all the above operations are considered done in the lower most sub Class.

Hope this session taught you something new and now you understand the concepts being discussed here .

Happy Learning .