LRU Cache with pruning thread

Objective: Create a generic LRU cache with prune mechanism in different thread.

Approach: LRU cache stand for least recently used cache. In java, it is very common to use LinkedHashMap to implement this functionality. But, pruning process is also important. If we will do pruning process in same thread as adding LRU cache, it will take time. So, here is multi-threaded solution for this problem. We will add item in LRU cache, and prune old item in other thread.

Download full source code: LRU cache complete source code

Solution: Java Code

	package com.vectordirection;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.Map;
	import java.util.concurrent.Semaphore;
	import java.util.concurrent.TimeUnit;
	/**
	* Created by adarshpandey on 1/12/15.
	*/
	public class LRUCache<Key, Item extends CacheableItem<Key>> implements Runnable {
	private final int maxSize;
	private final Integer mutex = 1;
	private Semaphore semaphore = new Semaphore(0);
	private final Map<Key, Item> cache;
	private boolean isKeepRunning = true;
	public LRUCache(int cacheSize) {
	cache = new HashMap<>();
	maxSize = cacheSize;
	isKeepRunning = true;
	Thread thread = new Thread(this);
	thread.start();
	}
	public int size() {
	return cache.size();
	}
	public Item getValue(Key key) {
	return cache.get(key);
	}
	public void add(Item item) {
	synchronized (mutex) {
	if (cache.containsKey(item.getKey())) {
	cache.remove(item.getKey());
	}
	cache.put(item.getKey(), item);
	semaphore.release();
	}
	}
	public void shutdown() {
	synchronized (mutex) {
	isKeepRunning = false;
	semaphore.release();
	}
	}
	public void prune() {
	synchronized (mutex) {
	Iterator<Map.Entry<Key, Item>> itemIterator = cache.entrySet().iterator();
	while (itemIterator.hasNext()) {
	itemIterator.next();
	if (cache.size() > maxSize) {
	itemIterator.remove();
	} else {
	break;
	}
	}
	}
	}
	@Override
	public void run() {
	while (isKeepRunning) {
	try {
	semaphore.tryAcquire(5000, TimeUnit.MILLISECONDS);
	semaphore.drainPermits();
	if (isKeepRunning) {
	prune();
	}
	} catch (InterruptedException e) {
	e.printStackTrace();
	}
	}
	}
	}

view raw LRUCache.java hosted with ❤ by GitHub

	package com.vectordirection;
	/**
	* Created by adarshpandey on 1/12/15.
	*/
	public interface CacheableItem<Key> {
	Key getKey();
	}

view raw CacheableItem.java hosted with ❤ by GitHub

	package com.verctordirection.test;
	import com.vectordirection.LRUCache;
	import org.junit.Test;
	/**
	* Created by adarshpandey on 1/13/15.
	*/
	public class CachingTest {
	@Test
	public void testLRU() {
	System.out.println("=========================================");
	System.out.println("*********** Caching Test Start **********");
	System.out.println("=========================================");
	LRUCache<Integer, Store> storeLRUCache = new LRUCache<>(3);
	storeLRUCache.add(new Store(1, 22));
	storeLRUCache.add(new Store(2, 23));
	storeLRUCache.add(new Store(3, 27));
	storeLRUCache.add(new Store(4, 29));
	storeLRUCache.add(new Store(5, 28));
	storeLRUCache.add(new Store(6, 21));
	storeLRUCache.add(new Store(7, 24));
	try {
	Thread.sleep(10);
	} catch (InterruptedException e) {
	e.printStackTrace();
	}
	assert storeLRUCache.size() == 3;
	assert storeLRUCache.getValue(1) == null;
	assert storeLRUCache.getValue(7).getValue() == 24;
	storeLRUCache.shutdown();
	}
	}

view raw CachingTest.java hosted with ❤ by GitHub

	package com.verctordirection.test;
	import com.vectordirection.CacheableItem;
	/**
	* Created by adarshpandey on 1/13/15.
	*/
	public class Store implements CacheableItem<Integer> {
	private Integer key;
	private Integer value;
	public Store(Integer key, Integer value) {
	this.key = key;
	this.value = value;
	}
	@Override
	public Integer getKey() {
	return key;
	}
	public void setKey(Integer key) {
	this.key = key;
	}
	public Integer getValue() {
	return value;
	}
	}

view raw Store.java hosted with ❤ by GitHub

Euclid's Algorithm to find Greatest Common Divisor

Objective: Given 2 number m and n, we have to find Greatest Common Divisor.

Approach: Euclid's Algorithm to find Greatest common Divisor. Suppose m and n is two integer, m > n. 
1. Get reminder while divide m by n, if it 0 then we have our answer n as GCD.
2. If reminder is not 0, then divide m by n and then get reminder. Thereafter, set reminder to n = r; m = n; and repeat step 1 to get GCD of 'm' and 'n'.

Solution: Java Code

	public class EuclidAlgo {
	public static void main(String ...arg) {
	Scanner scanner = new Scanner(System.in);
	int m = scanner.nextInt();
	int n = scanner.nextInt();
	System.out.println("GCD: "+ gcd(m, n));
	}
	private static int gcd(int m, int n) {
	int r = m % n;
	int q = m / n;
	if(r == 0) return n;
	return gcd(n, r);
	}
	}

view raw EuclidAlgo.java hosted with ❤ by GitHub

 

Permutation of two String in ordered form

Objective: Generate permutation of two string in ordered form. e.g. if "abc" and "def" is two strings, we need to generate all permutation having these two string characters the only condition if "a" come before "b" then its must come before "b" in the permutations.
i.e. "adebfc", "abcdef", "daebcf" and so on are permutation of these string.

Approach: As we can see either we start with first string or second string, but we need to maintain each string character order in our permutation.

In general, we can say that all permutation either start with first string character or second string character.

i.e. if "abc" and "def" is two strings then, 

perumation("abc", "def") = ("a" + permutation("bc", "def")) and ("d" + permutation("abc", "ef")

Solution: Java Code

	public class GeneratePermutation2Strings {
	public static void main(String... arg) {
	Scanner scanner = new Scanner(System.in);
	String s1 = scanner.nextLine();
	String s2 = scanner.nextLine();
	generateSequence("", s1, s2);
	}
	private static void generateSequence(String prefix, String s1, String s2) {
	if(s1.length() + s2.length() == 0) {
	System.out.println(prefix);
	}
	if(s1.length() > 0) {
	String temp1 = s1.length() <= 1 ? "" : s1.substring(1, s1.length());
	generateSequence(prefix + (s1.length() > 0 ? s1.charAt(0) : ""),temp1 , s2);
	}
	if(s2.length() > 0) {
	String temp2 = s2.length() <= 1 ? "" : s2.substring(1, s2.length());
	generateSequence(prefix + (s2.length() > 0 ? s2.charAt(0) : ""), s1, temp2);
	}
	}
	}

view raw GeneratePermutation2Strings.java hosted with ❤ by GitHub

 

Permutation of a given String

Objective: Given an String we need to generate all permutation of that string. e.g. if "abc" is an String we need to generate all possible permutation of this string. i.e. "abc", "acb", "bac", "bca", "cab", "cba" would be the possible permutation.

Approach: To understand the problem solving approach lets consider the following tree

In above tree we can see leaf of the tree represent the all permutations that we needed.

To describe the algorithm in functional way, if we want to generate permutation of "abc" with leading "a". We can have

'a' + permutation("bc")

Similarly, for leading "b" and "c", 

'b' + permutation("ac") and 'c' + permutation("ab")

Solution: Java Code

	public class GenerateAllPermutation {
	public static void main(String... arg) {
	Scanner scanner = new Scanner(System.in);
	String sequence = scanner.nextLine();
	generatePermutation("", sequence);
	}
	private static void generatePermutation(String prefix, String sequence) {
	if(sequence.length() == 0) System.out.println(prefix);
	for (int i = 0; i < sequence.length(); i++) {
	generatePermutation(prefix + sequence.charAt(i), sequence.substring(0, i) + sequence.substring(i+1));
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub