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);

}

}

}