Write a program to create forest from a tree by deleting set of input nodes

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

package com.test.algorithm.tree;

import java.util.*;

public class MakeForest {
    public static List<TreeNode> makeForestByDeletingNodes(TreeNode root, int[] toDeleteValueList) {
        List<TreeNode> forestNodes = new ArrayList<>();
        boolean isRootDeleted = false;
        for (int i=0; i<toDeleteValueList.length; i++) {
            if (root.getData() == toDeleteValueList[i]) {
                isRootDeleted = true;
            }
            List<TreeNode> childNodes = searchAndDeleteNodeAndReturnChildren(root, toDeleteValueList[i]);
            forestNodes.addAll(childNodes);
        }
        if (!isRootDeleted) {
            forestNodes.add(root);
        }
        return forestNodes;
    }

    public static List<TreeNode> searchAndDeleteNodeAndReturnChildren(TreeNode root, int toDeleteValue) {
        if (root == null) {
            return null;
        }

        List<TreeNode> childNodes = null;
        if(root.getData() == toDeleteValue) {
            childNodes = new ArrayList<>();
            if (root.getLeft() != null) {
                childNodes.add(root.getLeft());
            }
            if (root.getRight() != null) {
                childNodes.add(root.getRight());
            }
            return childNodes;
        }
        if(root.getLeft() != null && root.getLeft().getData() == toDeleteValue) {
            childNodes = new ArrayList<>();
            if (root.getLeft().getLeft() != null) {
                childNodes.add(root.getLeft().getLeft());
            }
            if (root.getLeft().getRight() != null) {
                childNodes.add(root.getLeft().getRight());
            }
            root.setLeft(null);
            return childNodes;
        }
        if(root.getRight() != null && root.getRight().getData() == toDeleteValue) {
            childNodes = new ArrayList<>();
            if (root.getRight().getLeft() != null) {
                childNodes.add(root.getRight().getLeft());
            }
            if (root.getRight().getRight() != null) {
                childNodes.add(root.getRight().getRight());
            }
            root.setRight(null);
            return childNodes;
        }
        childNodes = searchAndDeleteNodeAndReturnChildren(root.getLeft(), toDeleteValue);
        if (childNodes == null) {
            childNodes = searchAndDeleteNodeAndReturnChildren(root.getRight(), toDeleteValue);
        }
        return childNodes;
    }


    public static void main(String args[] ) throws Exception {
        TreeNode root = makeTree();
        List<TreeNode> forest = makeForestByDeletingNodes(root, new int[]{3,5});
        for (TreeNode node : forest) {
            printTree(node);
            System.out.println();
        }
    }

    private static void printTree(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.getData() + " ");
        printTree(node.getLeft());
        printTree(node.getRight());
    }

    private static TreeNode makeTree() {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        node3.setRight(node7);
        node6.setRight(node8);
        node7.setLeft(node9);
        node7.setRight(node10);

        return root;
    }
}

Write a concurrent LRU Cache using ReadWriteLock to allow parallel reads

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/cache

This LRUCache is implemented using ReadWriteLock allowing parallel reads where as only a single write can happen at a time. But caches are meant for read with less write and this approach would help in parallel reads for small scale of data.

This approach has a major disadvantage with respect to time taken for searching an entry if the scale of data to be retained is huge. This is because the ConcurrentLinkedQueue needs to be scanned to re-add after picking up the data every time. For large scale data it is better to use the synchronized LinkedHashMap approach.

package com.test.algorithm.cache;

import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LRUCacheWithReadWriteLock<K, V> {

    private final int limit;
    private final Map<K, V> internalCache;
    private final Queue<K> trackingQueue;

    private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock();

    public LRUCacheWithReadWriteLock(int limit){
        internalCache = new ConcurrentHashMap<>();
        trackingQueue = new ConcurrentLinkedQueue<>();
        this.limit = limit;
    }

    public V get(K key) {
        this.readWriteLock.readLock().lock();
        try {
            V value = internalCache.get(key);
            if (value != null) {
                if (trackingQueue.remove(key)) {
                    trackingQueue.add(key);
                }
            }
            return value;
        } finally {
            this.readWriteLock.readLock().unlock();
        }
    }

    public void put(K key, V value) {
        this.readWriteLock.writeLock();
        try {
            if (internalCache.containsKey(key)) {
                trackingQueue.remove(key);
            }
            if (trackingQueue.size() == limit) {
                K expiredKey = trackingQueue.poll();
                internalCache.remove(expiredKey);
            }
            internalCache.put(key, value);
            trackingQueue.add(key);
        } finally {
            this.readWriteLock.writeLock().unlock();
        }
    }

    public static void main(String arg[]){
        LRUCacheWithReadWriteLock<Integer, String> lruCache = new LRUCacheWithReadWriteLock<>(4);

        lruCache.put(1, "Object1");
        lruCache.put(2, "Object2");
        lruCache.put(3, "Object3");
        lruCache.get(1);
        lruCache.put(4, "Object4");
        System.out.println(lruCache);
        lruCache.put(5, "Object5");
        lruCache.get(3);
        lruCache.put(6, "Object6");
        System.out.println(lruCache);
        lruCache.get(4);
        lruCache.put(7, "Object7");
        lruCache.put(8, "Object8");
        System.out.println(lruCache);
    }

    @Override
    public String toString() {
        return "LRUCacheWithReadWriteLock{" +
                "internalCache=" + internalCache +
                '}';
    }
}

Write a concurrent LRU Cache using LinkedHashMap

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/cache

For handling concurrency, we will have to synchronize the methods of LinkedHashMap being used as LRU Cache.

For better performance, LRU Cache can be implemented using ReadWriteLock, ConcurrentLinkedQueue and a ConcurrentHashMap - refer the implementation

package com.test.algorithm.cache;

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

public class LRUCacheWithLinkedHashMap<K, V> {

    private final Map<K, V> internalCache;

    public LRUCacheWithLinkedHashMap(int limit){
        internalCache = Collections.synchronizedMap(new LinkedHashMap<K, V>(limit, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > limit;
            }
        });
    }

    public V get(K key) {
        return internalCache.get(key);
    }

    public void put(K key, V value) {
        internalCache.put(key, value);
    }

    public V remove(K key) {
        return internalCache.remove(key);
    }

    public static void main(String arg[]){
        LRUCacheWithLinkedHashMap<Integer, String> lruCache = new LRUCacheWithLinkedHashMap<>(4);

        lruCache.put(1, "Object1");
        lruCache.put(2, "Object2");
        lruCache.put(3, "Object3");
        lruCache.get(1);
        lruCache.put(4, "Object4");
        System.out.println(lruCache);
        lruCache.put(5, "Object5");
        lruCache.get(3);
        lruCache.put(6, "Object6");
        System.out.println(lruCache);
        lruCache.get(4);
        lruCache.put(7, "Object7");
        lruCache.put(8, "Object8");
        System.out.println(lruCache);
    }

    @Override
    public String toString() {
        return "LRUCacheWithLinkedHashMap{" +
                "internalCache=" + internalCache +
                '}';
    }
}

Write a program to print a Binary Tree in Spiral Order Traversal

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

package com.test.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class SpiralTraversal {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.setLeft(new TreeNode(2));
        root.getLeft().setRight(new TreeNode(3));
        root.getLeft().setLeft(new TreeNode(1));

        root.setRight(new TreeNode(6));
        root.getRight().setRight(new TreeNode(7));
        root.getRight().setLeft(new TreeNode(5));

        printTreeInOrder(root);

        printSpirally(root);
    }

    private static void printSpirally(TreeNode root) {

        Stack<TreeNode> rightToLeftStack = new Stack<>();
        rightToLeftStack.push(root);
        Stack<TreeNode> leftToRightStack = new Stack<>();
        while(!rightToLeftStack.isEmpty() || !leftToRightStack.isEmpty()) {
            while(!rightToLeftStack.isEmpty()) {
                TreeNode node = rightToLeftStack.pop();
                System.out.println(node);
                if (node.getLeft() != null) {
                    leftToRightStack.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    leftToRightStack.push(node.getRight());
                }
            }
            while(!leftToRightStack.isEmpty()) {
                TreeNode node = leftToRightStack.pop();
                System.out.println(node);
                if (node.getRight() != null) {
                    rightToLeftStack.push(node.getRight());
                }
                if (node.getLeft() != null) {
                    rightToLeftStack.push(node.getLeft());
                }
            }
        }
    }

    private static void printTreeInOrder(TreeNode root) {
        if (root == null){
            return;
        }
        printTreeInOrder(root.getLeft());
        System.out.println(root);
        printTreeInOrder(root.getRight());
    }
}

Write a program to print a Binary Tree in Level Order Traversal

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

package com.test.algorithm.tree;

import java.util.*;

public class LevelOrderTraversal {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.setLeft(new TreeNode(2));
        root.getLeft().setRight(new TreeNode(3));
        root.getLeft().setLeft(new TreeNode(1));

        root.setRight(new TreeNode(6));
        root.getRight().setRight(new TreeNode(7));
        root.getRight().setLeft(new TreeNode(5));

        printTreeInOrder(root);

        printInLevelOrder(root);
    }

    private static void printInLevelOrder(TreeNode root) {

        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        treeNodeQueue.add(root);
        while(!treeNodeQueue.isEmpty()) {
            TreeNode node = treeNodeQueue.poll();
            System.out.println(node);
            if (node.getLeft() != null) {
                treeNodeQueue.add(node.getLeft());
            }
            if (node.getRight() != null) {
                treeNodeQueue.add(node.getRight());
            }
        }
    }

    private static void printTreeInOrder(TreeNode root) {
        if (root == null){
            return;
        }
        printTreeInOrder(root.getLeft());
        System.out.println(root);
        printTreeInOrder(root.getRight());
    }
}

Write a program to print Lowest Common Ancestor of a given node in a Binary Search Tree

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

package com.test.algorithm.tree;

public class LowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.setLeft(new TreeNode(2));
        root.getLeft().setRight(new TreeNode(3));
        root.getLeft().setLeft(new TreeNode(1));

        root.setRight(new TreeNode(6));
        root.getRight().setRight(new TreeNode(7));
        root.getRight().setLeft(new TreeNode(5));

        System.out.println("lowestCommonAncestor for: " + lowestCommonAncestor(root, 3, 1));
    }

    private static TreeNode lowestCommonAncestor(TreeNode root, int data1, int data2) {
        if(root == null) {
            return null;
        }
        if (root.getData() < data1 && root.getData() < data2) {
            return lowestCommonAncestor(root.getRight(), data1, data2);
        } else if (root.getData() > data1 && root.getData() > data2) {
            return lowestCommonAncestor(root.getLeft(), data1, data2);
        }
        return root;
    }
}

Write a program to mirror a Binary Tree

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

package com.test.algorithm.tree;

public class MirrorBinaryTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.setLeft(new TreeNode(2));
        root.getLeft().setRight(new TreeNode(3));
        root.getLeft().setLeft(new TreeNode(1));

        root.setRight(new TreeNode(6));
        root.getRight().setRight(new TreeNode(7));
        root.getRight().setLeft(new TreeNode(5));

        printTreeInOrder(root);

        mirrorBinaryTree(root);
        printTreeInOrder(root);
    }

    private static TreeNode mirrorBinaryTree(TreeNode root) {

        if (root == null) {
            return null;
        }
        TreeNode leftMirror = mirrorBinaryTree(root.getRight());
        TreeNode rightMirror = mirrorBinaryTree(root.getLeft());

        root.setLeft(leftMirror);
        root.setRight(rightMirror);
        return root;
    }

    private static void printTreeInOrder(TreeNode root) {
        if (root == null){
            return;
        }
        printTreeInOrder(root.getLeft());
        System.out.println(root);
        printTreeInOrder(root.getRight());
    }
}

Write a program to validate if a given Binary Tree is a Binary Search Tree

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

package com.test.algorithm.tree;

public class BinarySearchTreeValidator {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.setLeft(new TreeNode(2));
        root.getLeft().setRight(new TreeNode(3));
        root.getLeft().setLeft(new TreeNode(1));

        root.setRight(new TreeNode(6));
        root.getRight().setRight(new TreeNode(7));
        root.getRight().setLeft(new TreeNode(5));

        printTreeInOrder(root);

        System.out.println("isBinarySearchTree: " + isBinarySearchTree(root));
    }

    private static boolean isBinarySearchTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.getLeft() != null && root.getData() <= root.getLeft().getData() ||
                root.getRight() != null && root.getData() >= root.getRight().getData()) {
            return false;
        }
        return isBinarySearchTree(root.getLeft()) && isBinarySearchTree(root.getRight());
    }

    private static void printTreeInOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        printTreeInOrder(root.getLeft());
        System.out.println(root);
        printTreeInOrder(root.getRight());
    }
}

Write a program to print longest unique substring of a given string

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/slidingwindow

package com.test.algorithm.slidingwindow;

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring(" "));
        System.out.println(lengthOfLongestSubstring("abcba"));
        System.out.println(lengthOfLongestSubstring("bbbbbb"));
        System.out.println(lengthOfLongestSubstring("pwwkew"));
    }

    public static int lengthOfLongestSubstring(String s) {
        int lengthOfLongestSubstring = 0;
        Map<Character, Integer> charIndexMap = new HashMap<>();
        int startIndex = 0;
        int currentSequenceLength = 0;
        for (int i = 0; i < s.length(); i++) {
            if(charIndexMap.containsKey(s.charAt(i))) {
                currentSequenceLength = i - startIndex;
                if (currentSequenceLength > lengthOfLongestSubstring) {
                    lengthOfLongestSubstring = currentSequenceLength;
                }
                startIndex = Math.max(startIndex, charIndexMap.get(s.charAt(i)) + 1);
            }
            charIndexMap.put(s.charAt(i), i);
        }
        currentSequenceLength = s.length() - startIndex;
        if (currentSequenceLength > lengthOfLongestSubstring) {
            lengthOfLongestSubstring = currentSequenceLength;
        }
        return lengthOfLongestSubstring;
    }
}

Write a program to solve Sudoku

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/backtracking

package com.test.algorithm.backtracking;

public class Sudoku {
    public static void main(String[] args) {
        int[][] sudoku = new int [][] {
                {0,7,0,0,0,1,0,0,8},
                {6,0,0,0,0,0,0,3,7},
                {0,2,0,0,0,0,1,0,0},
                {0,6,0,7,1,0,0,0,4},
                {0,0,0,2,0,8,0,0,0},
                {7,0,0,0,4,9,0,8,0},
                {0,0,5,0,0,0,0,7,0},
                {9,3,0,0,0,0,0,0,2},
                {4,0,0,3,0,0,0,6,0}
        };
        printSudoku(sudoku);
        if (solveSudoku(sudoku)) {
            System.out.println("*************Solution**************");
            printSudoku(sudoku);
        } else {
            System.out.println("can't solve");
        }
    }

    private static boolean solveSudoku(int[][] sudoku) {
        // get unsolved index
        int unsolvedRow = -1;
        int unsolvedColumn = -1;
        boolean isUnsolvedElementFound = false;

        for (int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku[i].length; j++) {
                if (sudoku[i][j] == 0) {
                    unsolvedRow = i;
                    unsolvedColumn = j;
                    isUnsolvedElementFound = true;
                    break;
                }
            }
            if (isUnsolvedElementFound) {
                break;
            }
        }
        // if no unsolved index, return true
        if (!isUnsolvedElementFound) {
            return true;
        }

        // check what value is safe to place for unsolved index
        for (int newValue=1; newValue<=9; newValue++) {
            if (isSafeToPlace(sudoku, unsolvedRow, unsolvedColumn, newValue)) {
                sudoku[unsolvedRow][unsolvedColumn] = newValue;
                if (solveSudoku(sudoku)) {
                    return true;
                } else {
                    sudoku[unsolvedRow][unsolvedColumn] = 0;
                }
            }
        }
        return false;
    }

    private static boolean isSafeToPlace(int[][] sudoku, int unsolvedRow, int unsolvedColumn, int newValue) {
        for (int i = 0; i < sudoku.length; i++) {
            if (sudoku[unsolvedRow][i] == newValue) {
                return false;
            }
            if (sudoku[i][unsolvedColumn] == newValue) {
                return false;
            }
        }
        int sudokuSquareRowStart = unsolvedRow - unsolvedRow % 3;
        int sudokuSquareColumnStart = unsolvedColumn - unsolvedColumn % 3;
        for (int i = sudokuSquareRowStart; i < sudokuSquareRowStart+3; i++) {
            for (int j = sudokuSquareColumnStart; j < sudokuSquareColumnStart+3; j++) {
                if (sudoku[i][j] == newValue) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void printSudoku(int[][] sudoku) {
        for (int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku[i].length; j++) {
                System.out.print(sudoku[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Write a program to print Tower of Hanoi solution

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/recursion

package com.test.algorithm.recursion;

public class TowerOfHanoi {

    public static void solve(int numOfDiscs, String srcTower, String destTower, String interTower) {
        if (numOfDiscs == 1) {
            System.out.println("Move disc1 from " + srcTower + " to " + destTower);
        } else {
            solve(numOfDiscs-1, srcTower, interTower, destTower);
            System.out.println("Move disc" + numOfDiscs + " from " + srcTower + " to " + destTower);
            solve(numOfDiscs-1, interTower, destTower, srcTower);
        }
    }

    public static void main(String[] args) {
        solve(3, "A", "B", "C");
    }
}

Write a program to print top N trending hashtags

 You are given a set of hashtags and the number of times those have occured. 

Write a java program to print top N trending hashtags from the list of values.

Solution: The best suited data structure for figuring out top N elements is a heap - PriorityQueue is the java implementation for heap.

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/heap

package com.test.algorithm.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class TopNHashtags {

    public static void main(String[] args) {
        int n = 3;
        List<HashTagCount> hashTagList = new ArrayList<>();
        hashTagList.add(new HashTagCount("#sometag", 10));
        hashTagList.add(new HashTagCount("#sometag1", 1000));
        hashTagList.add(new HashTagCount("#sometag2", 900));
        hashTagList.add(new HashTagCount("#sometag3", 100));
        hashTagList.add(new HashTagCount("#sometag4", 50));
        hashTagList.add(new HashTagCount("#sometag", 10));

        printTopNTrendingHashTags(n, hashTagList);
    }

    private static void printTopNTrendingHashTags(int n, List<HashTagCount> hashTagList) {
        PriorityQueue<HashTagCount> topTrendingHashTags =
                new PriorityQueue<>(Comparator.comparing(HashTagCount::getCount).reversed());
        topTrendingHashTags.addAll(hashTagList);
        for (int i = 0; i< n; i++) {
            System.out.println(topTrendingHashTags.poll());
        }
    }
}

package com.test.algorithm.heap;

import java.util.Objects;

public class HashTagCount {

    private String hashTag;

    private long count;

    public HashTagCount(String hashTag, long count) {
        this.hashTag = hashTag;
        this.count = count;
    }

    public String getHashTag() {
        return hashTag;
    }

    public void setHashTag(String hashTag) {
        this.hashTag = hashTag;
    }

    public long getCount() {
        return count;
    }

    public void setCount(long count) {
        this.count = count;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        HashTagCount that = (HashTagCount) o;
        return hashTag.equals(that.hashTag);
    }

    @Override
    public int hashCode() {
        return Objects.hash(hashTag);
    }

    @Override
    public String toString() {
        return "TweetCount{" +
                "hashTag='" + hashTag + '\'' +
                ", count=" + count +
                '}';
    }
}