Graphs - BFS and DFS

BFS  -  Breadth First Search

DFS  - Depth First Search

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

/**

 * 

 */

/**

 * @author sachin.srivastava

 * @tek9g.blogspot.com

 * @github.com/sks1130/

 *

 */

public class Graph_BFS_DFS {

private static int numberOfNodes;

private static int[][] adjMatrix;

private static boolean[] visited;

public static void main(String[] args) {

numberOfNodes   = 9 ;

adjMatrix  = new int[numberOfNodes][numberOfNodes];

visited = new boolean[numberOfNodes];

adjMatrix = new int[][]{  { 0, 1, 0, 1, 0, 0, 0, 0, 1 },  

                 { 1, 0, 0, 0, 0, 0, 0, 1, 0 },       

                 { 0, 0, 0, 1, 0, 1, 0, 1, 0 },  

                 { 1, 0, 1, 0, 1, 0, 0, 0, 0 },  

                 { 0, 0, 0, 1, 0, 0, 0, 0, 1 },  

                 { 0, 0, 1, 0, 0, 0, 1, 0, 0 },  

                 { 0, 0, 0, 0, 0, 1, 0, 0, 0 },  

                 { 0, 1, 1, 0, 0, 0, 0, 0, 0 },  

                 { 1, 0, 0, 0, 1, 0, 0, 0, 0 } };

for (int i = 0; i < numberOfNodes; i++) {

System.out.println(Arrays.toString(adjMatrix[i]));

}

BFS(0);

DFS(0);

}

public static void BFS(int root){

if(root >= numberOfNodes){

System.out.println("input node is beyond range");

return;

}

System.out.println("---BFS--------");

Queue<Integer> queue = new LinkedList<>();

queue.add(root);

visited[root]  = true;

System.out.println("visited node-->" + root + " ");

while(queue.size()!=0){

int head = queue.remove();

int child = -1;

while((child=getUnvisitedNode(head))!=-1){

queue.add(child);

visited[child] = true;

System.out.println("visited node-->" + child + " ");

}

}

clearAllVisitedNodes();

}

public static void DFS(int root){

if(root >= numberOfNodes){

System.out.println("input node is beyond range");

return;

}

System.out.println("---DFS--------");

Stack<Integer> stack = new Stack<>();

stack.push(root);

visited[root]  = true;

System.out.println("visited node-->" + root + " ");

while(!stack.isEmpty()){

int head = stack.peek();

int child = -1;

if(( child = getUnvisitedNode(head))!=-1){

stack.push(child);

visited[child] = true;

System.out.println("visited node-->" + child + " ");

} else {

stack.pop();

}

}

clearAllVisitedNodes();

}

public static void clearAllVisitedNodes(){

for (int i = 0; i < visited.length; i++) {

visited[i] = false;

}

}

public static int getUnvisitedNode(int n ){

for (int i = 0; i < adjMatrix[n].length; i++) {

if( adjMatrix[n][i] == 1 && !visited[i]){

return i;

}

}

return -1;

}

}

Output : 

[0, 1, 0, 1, 0, 0, 0, 0, 1]

[1, 0, 0, 0, 0, 0, 0, 1, 0]

[0, 0, 0, 1, 0, 1, 0, 1, 0]

[1, 0, 1, 0, 1, 0, 0, 0, 0]

[0, 0, 0, 1, 0, 0, 0, 0, 1]

[0, 0, 1, 0, 0, 0, 1, 0, 0]

[0, 0, 0, 0, 0, 1, 0, 0, 0]

[0, 1, 1, 0, 0, 0, 0, 0, 0]

[1, 0, 0, 0, 1, 0, 0, 0, 0]

---BFS--------

visited node-->0 

visited node-->1 

visited node-->3 

visited node-->8 

visited node-->7 

visited node-->2 

visited node-->4 

visited node-->5 

visited node-->6 

---DFS--------

visited node-->0 

visited node-->1 

visited node-->7 

visited node-->2 

visited node-->3 

visited node-->4 

visited node-->8 

visited node-->5 

visited node-->6 

Enjoy the coding!!!!

Checking a number is product of two prime numbers

If  m and n are positive integer and n is a divisor or factor of m  then there exists a non zero integer p such that :

n * p = m where (n , p , m  > 0) and n | m (Usual notation to show n is divisor of m)

Case : We need to find a if a number is multiplier of two prime numbers  so we need to find n and p such that n * p = m

E.g ,

Input =35  then output = true   [ 35 = 7 * 5 (both are prime numbers)]

Input =21  then output = true  [21 = 7 * 3 ]

Input =20  then output = false [20 = 2 * 10 or 4 *5   not prime numbers]

Code snippet : 

public static boolean checkMultiplierOfPrime(int n){

if( n< 6){

return false;  ///as least number satifying the condition is 6 = 2 * 3

}

int k = (int) Math.sqrt(n);  /////important catch here to find the square root

for (int i = k; i >= 2; i--) {

if(n % i == 0){

int j = n/i;

if(isPrimeNumber(i) && isPrimeNumber(j)){

return true;

}

}

}

return false;

}

 public static boolean isPrimeNumber(int number){

    if(number<=1){

    return false;

    }

    for(int i=2; i<=number/2; i++){

    if(number % i == 0){

    return false;

    }

    }

    return true;

    }

Time Complexity : O(n) for a number of n  , iteration would from 2 to n/2 , hence complexity would be O(n/2) means O(n)

Enjoy the coding !!!!!!

       

Aggregation Framework - finding & removing the duplicate elements in MongoDB

 Given a collection  name product having following documents in the collection.


{ "_id" : NumberInt("1"),"account" : "abc","vendor" : "amazon","category" : "mobile"},
{"_id" : NumberInt("2"), "account" : "abc","vendor" : "overstock","category" : "mobile"},
{"_id" : NumberInt("3"),"account" : "xyz","vendor" : "fashionStreet","category" : "fashion"},
{"_id" : NumberInt("4"),"account" : "pqr","vendor" : "foodTruck","category" : "food"},
{"_id" : NumberInt("5"),"account" : "abc","vendor" : "amazon", "category" : "mobile"}

If one notice there are duplicate elements exist in the collection with the composite key(account+ vendor+ category) marked in blue on colour , so how do we identify the duplicates in a collection and how do we remove the duplicate keys in the MongoDB?

This problem is easily solved using Aggregation pipeline framework which provides  $group operator to group an compound or composite key along with the $match operator to match a criteria.

db.product.aggregate([

{ $group: { 

_id: { account: "$account", vendor: "$vendor", category: "$category" }, 
count: { $sum: 1 } 
}}, 
{
    $match: {
        count: { $gt: 1 }
    }
}, 
{
 $sort: { 
    count : -1 }
 }
]);

Above query find all the duplicates elements whose account, vendor , category  values are same and having duplicate values and output of the above query is as follow  with the descending order of count : 

Output : 

{

"_id" : {

"account" : "abc",

"vendor" : "amazon",

"category" : "mobile"

},

"count" : 2

}

Note that _id is made composite of  3 columns account , vendor , category so in general 

_id :  { key1 : "$key1",  key2 : "$key2", key3 : "$key3", key4 : "$key4", key5 : "$key5" }

and count plays an important role to find out the number of duplicates in the collection.

With the above example , we have identified the duplicate elements in the collection , so the next question arises , how to remove duplicate keys in a collection in MongoDB?

var duplicates = [];

db.product.aggregate([

  { $group: { 

    _id: { account: "$account" , vendor : "$vendor", category : "$category"}, // can be grouped on multiple properties/keys/columns 

    dups: { "$addToSet": "$_id" }, 

    count: { "$sum": 1 } 

  }}, 

  { $match: { 

    count: { "$gt": 1 }    // Duplicates considered as count greater than one

  }}

])             

.forEach(function(doc) {

    doc.dups.shift();      // First element skipped for deleting and important line here

    doc.dups.forEach( function(dupId){ 

        duplicates.push(dupId);   // Getting all duplicate ids

        }

    )    

});

// If you want to Check all "_id" which you are deleting

printjson(duplicates); 

Output : 

[ NumberInt("1") ]

Now we have identified the array of duplicate "_id"   as shown in the output of the above query.

To remove all the duplicates from the collection  , need to execute the following 

// Remove all duplicates in one go    

db.product.remove({_id:{$in:duplicates}});

db.product.find({});

Output : 

{"_id" : NumberInt("2"), "account" : "abc","vendor" : "overstock","category" : "mobile"},
{"_id" : NumberInt("3"),"account" : "xyz","vendor" : "fashionStreet","category" : "fashion"},
{"_id" : NumberInt("4"),"account" : "pqr","vendor" : "foodTruck","category" : "food"},
{"_id" : NumberInt("5"),"account" : "abc","vendor" : "amazon", "category" : "mobile"}


So you will get an amazing result with the all the records are unique in the collection.

Be alert while applying an index on the composite columns with {unique: true, dropDups: true}). 

Suppose in the above scenario we have applied these condition then it will throw an error as 

{
    "createdCollectionAutomatically" : false,
    "numIndexesBefore" : 1,
    "errmsg" : "exception: E11000 duplicate key error index
    "code" : 11000,
    "ok" : 0
}

Note that dropDups has been removed in the Mongo 3.x release and has a severe disadvantage of removing the any random duplicate element.

Even if you apply ensureIndex() or createIndex()  at the time of collection having duplicate keys then it will prompt   exception "exception: E11000 duplicate key error index"  , so its important to remove the duplicate elements with the above mentioned aggregation example and  then applying the {unique: true}  on the composite index created with the fields say here {account, vendor , category}.

Enjoy the MongoDB  and the brilliant  Aggregation Framework !!!!

Enjoy  the coding with tek9g!!! 

Determining a sequence is sorted or not

If you have a list or array of elements then how should we determine the given sequence is either sorted in ascending or descending order.

There are many ways of finding it  but the following solution provides a solution in one iteration so complexity is O(n).

We need to compare the elements such that either elements are either increasing or decreasing  , if this condition is not matching then unsorted sequence otherwise its a sorted sequence.

/**

 * @author sachin.srivastava

 * @tek9g.blogpspot.com

 * {@code checking various scenarios of handling the sorting cases.}

 */

//checking if a list is sorted means asceding or descending in either way.

//complexity is O(n) beacaue of traversal of n elements of the list

public static <T extends Comparable<T>> boolean isSorted(List<T> list) {

if(list == null || list.isEmpty()){

return false;

}

if(list.size() == 1) {

return true;

}

T prev =null;

boolean asc = true;

boolean desc = true;

for (T t : list) {

//ascending

if(prev!=null && prev.compareTo(t) > 0 ){

asc = false;

} 

//descending

if(prev!=null && prev.compareTo(t) < 0 ){

desc = false;

}

prev  = t;

}

return asc || desc;

}

Testcases : 

            System.out.println(isSorted(Arrays.asList(1,2,4,5)));//true

System.out.println(isSorted(Arrays.asList(5,2,4,5)));//false

System.out.println(isSorted(Arrays.asList("abc","bcd","def","fgh")));//true

System.out.println(isSorted(Arrays.asList("b","a","c","d")));//false

Enjoy the coding !!!!

Knight minimum moves to get checkmate in chess - An algorithm challenge

 

Problem Statement :   

Given on a chessboard a Black Knight position (x, y) and the opponent white King position is at the the coordinate of (m, n), assuming the King is not moving to any place, then find the minimum moves of Black Knight requires to get a checkmate and to win the game. [Coordinates are shown in the above picture]

Solution : 

The Knight moves with respect to its current position (x,y)  in the 8 possible coordinates : 

 (x+2 , y+1 ) ,  (x+2 , y-1 ) ,  (x-2 , y+1 ) , (x-2 , y-1 ) ,  (x+1 , y+2 ) ,  (x-1 , y+2 ) ,  (x+1 , y-2 ) , 

(x-1 , y-2 ) 

So it can be noted that position (x,y ) can be treated as the head vertex of the Graph and reaming 8 possible coordinates are adjacent vertex of the  graph. So we need to find all the possible paths of reaching to king ( m,n ) and figure out then shortest path among all. 

There are 2 ways to solve the problem : 

1.  Dijkstra's algorithm 

2.  Breadth First Traversal or BFS

We will follow the 2 option of BFS to solve it  and following code snippet written in java to demonstrate the solution of the above problem.

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

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

/**

 * @author sachin.srivastava

 * tek9g.blogspot.coml

* @email tek9gworld@gmail.com

 *

 */

public class KnightChess {

public static int  traverseCount(Node start , Node end){

if(start ==null || end == null || (start.x == end.x && start.y == end.y) ){

return 0;

} 

List<Node> visitedNodes = new ArrayList<>();

Queue<Node> queue = new LinkedList<>();

start.visited = true;

queue.add(start);

int minMoves = 0;

while (!queue.isEmpty()) {

Node head = queue.poll();

if(head.x < 1 || head.x > 8 || head.y <1 || head.y > 8 ){

continue;

}

if(head.x == end.x && head.y == end.y){

head.visited = true;

break;

}

List<Node> adjNodes = adjNodes(head, visitedNodes, end);

int count = printVisitedNodes(adjNodes,end,head);

if(count > 0){

if(minMoves <= count -1){

minMoves = count-1;

}

}

for (Node node : adjNodes) {

if(!node.visited){

queue.add(node);

node.visited = true;

}

}

}

return minMoves;

}

public static int printAllNodes(Node node, int count){

if(node == null){

System.out.print("\n");

return count;

}

count++;

System.out.print( "("+ node.x + "," +node.y + ")" + " ");

return printAllNodes(node.parent,count);

}

public static int printVisitedNodes(List<Node> visitedNodes,Node end,Node parent){

if(visitedNodes!=null && !visitedNodes.isEmpty()){

for (Node node : visitedNodes) {

if(matchEndNode(node, end)){

return printAllNodes(node,0);

}

}

}

return 0;

}

public  static boolean nodeVisited(Node node,List<Node> visitedNodes,Node end ){

boolean flag = false;

if(node.x <1 || node.x >8 || node.y <1 || node.y >8 || (node.x == 1 && node.y == 1 || node.x==8 && node.y==8)) {

node.visited = true;

return true;

}

if(node!=null && !node.visited && visitedNodes!=null && !visitedNodes.isEmpty()){

for (Node node2 : visitedNodes) {

if(node2.x == node.x && node2.y == node.y ){

node.visited = true;

node2.visited = true;

flag= true;

break;

}

}

}

return flag;

}

public static boolean matchEndNode(Node start, Node end){

if(start.x== end.x && start.y == end.y){

return true;

}

return false;

}

public static List<Node> adjNodes(Node start , List<Node> visitedNodes,Node end){

int x = start.x;

int y = start.y;

Node parent = start;

List<Node> adjNodes = new ArrayList<>();

if(!nodeVisited(new Node(x+2, y+1,parent), visitedNodes,end)){

adjNodes.add(new Node(x+2, y+1,parent));

if(matchEndNode(new Node(x+2, y+1,parent), end)){

return adjNodes;

}

}

if(!nodeVisited(new Node(x+2, y-1,parent), visitedNodes,end)){

adjNodes.add(new Node(x+2, y-1,parent));

if(matchEndNode(new Node(x+2, y-1,parent), end)){

return adjNodes;

}

}

if(!nodeVisited(new Node(x+1, y+2,parent), visitedNodes,end)){

adjNodes.add(new Node(x+1, y+2,parent));

if(matchEndNode(new Node(x+1, y+2,parent), end)){

return adjNodes;

}

}

if(!nodeVisited(new Node(x-1, y+2,parent), visitedNodes,end)){

adjNodes.add(new Node(x-1, y+2,parent));

if(matchEndNode(new Node(x-1, y+2,parent), end)){

return adjNodes;

}

}

if(x > end.x){

if(!nodeVisited(new Node(x-2, y+1,parent), visitedNodes,end)){

adjNodes.add(new Node(x-2, y+1,parent));

if(matchEndNode(new Node(x-2, y+1,parent), end)){

return adjNodes;

}

}

if(!nodeVisited(new Node(x-2, y-1,parent), visitedNodes,end)){

adjNodes.add(new Node(x-2, y-1,parent));

if(matchEndNode(new Node(x-2, y-1,parent), end)){

return adjNodes;

}

}

}

if(y > end.y){

if(!nodeVisited(new Node(x+1, y-2,parent), visitedNodes,end)){

adjNodes.add(new Node(x+1, y-2,parent));

if(matchEndNode(new Node(x+1, y-2,parent), end)){

return adjNodes;

}

}

if(!nodeVisited(new Node(x-1, y-2,parent), visitedNodes,end)){

adjNodes.add(new Node(x-1, y-2,parent));

if(matchEndNode(new Node(x-1, y-2,parent), end)){

return adjNodes;

}

}

}

return adjNodes;

}

static class Node{

int x;

int y;

Node parent;

boolean visited;

public Node(int x , int y, Node parent) {

this.x = x;

this.y = y;

this.parent = parent;

}

}

public static void main(String[] args) {

Node start = new Node(1, 1, null);

Node end = new Node(1,7, null);

System.out.println("Minimum moves for knight="+ traverseCount(start, end));

}

}

Input : 1 , 1 , 1, 7 

Output : 

(1,7) (3,6) (4,4) (3,2) (1,1) 

(1,7) (2,5) (4,4) (3,2) (1,1) 

(1,7) (3,6) (2,4) (3,2) (1,1) 

(1,7) (2,5) (1,3) (3,2) (1,1) 

(1,7) (3,6) (4,4) (2,3) (1,1) 

(1,7) (2,5) (4,4) (2,3) (1,1) 

(1,7) (3,6) (1,5) (2,3) (1,1) 

Minimum moves for knight=4

Input : 2 , 1 , 6, 5

Output :  

(6,5) (8,4) (6,3) (4,2) (2,1) 

(6,5) (7,3) (6,1) (4,2) (2,1) 

(6,5) (5,3) (6,1) (4,2) (2,1) 

(6,5) (7,3) (5,4) (4,2) (2,1) 

(6,5) (4,6) (5,4) (4,2) (2,1) 

(6,5) (5,3) (3,4) (4,2) (2,1) 

(6,5) (4,6) (3,4) (4,2) (2,1) 

(6,5) (7,3) (5,4) (3,3) (2,1) 

(6,5) (4,6) (5,4) (3,3) (2,1) 

(6,5) (7,3) (5,2) (3,3) (2,1) 

(6,5) (4,4) (5,2) (3,3) (2,1) 

(6,5) (5,7) (4,5) (3,3) (2,1) 

(6,5) (4,6) (2,5) (3,3) (2,1) 

(6,5) (4,4) (2,5) (3,3) (2,1) 

(6,5) (5,3) (3,4) (1,3) (2,1) 

(6,5) (4,6) (3,4) (1,3) (2,1) 

(6,5) (5,3) (3,2) (1,3) (2,1) 

(6,5) (4,4) (3,2) (1,3) (2,1) 

(6,5) (4,6) (2,5) (1,3) (2,1) 

(6,5) (4,4) (2,5) (1,3) (2,1) 

Minimum moves for knight=4

Input : 5 , 5 , 6, 6

Output : 

(6,6) (7,4) (5,5) 

(6,6) (4,7) (5,5) 

Minimum moves for knight=2

Enjoy the chess and coding !!!!!

Merging M sorted sequence into one sequence in Java

Suppose you have M number of List/Array/Sequence  and each one is sorted with total of N number of elements. So  best optimal way to solve it with the the complexity O(NlogM) time using a heap.
Minimum of each sequence can form a heap with the O(logM) time to insert elements in the heap and O(1) time to delete an element.

Each element would take O(logM) time to insert in the heap and with the total number of elements N, it gives an O(NlogM) time solution. 

In Java 1.5 onwards  PriorityQueue/PriorityBlockingQueue are being introduced to cater as priority heap.

We are really thankful to Joshua Bloch, father of Java Collection Framework, to enlighten with the real world of programming in Java. 

Following are the description available in the Oracle Docs Java 1.5 : 

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll,remove, peek, and element access the element at the head of the queue.

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

This class and its iterator implement all of the optional methods of           the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueueclass.

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

This class is a member of the Java Collections Framework.

Lets see some example to elaborate the solution : 

/**

 * @author sachin srivastava

 * tek9g.blogspot.com

 *

 */

public class MergingSortedSequence {

public static void main(String[] args) {

int[] arr1  = {1,3,6,4,8,90,133};

int[] arr2  = {2,3,1,17,18};

int[] arr3  = {4,5,6,8,11};

int[] arr4  = {125,9,10,13,34};

int[] arr = new int[arr1.length + arr2.length + arr3.length + arr4.length];

PriorityQueue<Integer> prq = new PriorityQueue<>();

for (int i = 0; i < arr.length; i++) {

if(i<arr1.length){

prq.add(arr1[i]);

}

if(i<arr2.length){

prq.add(arr2[i]);

}

if(i<arr3.length){

prq.add(arr3[i]);

}

if(i<arr4.length){

prq.add(arr4[i]);

}

}

while (!prq.isEmpty()) {

System.out.print(prq.poll()+" ");

}

}

}

Output : 1 1 2 3 3 4 4 5 6 6 8 8 9 10 11 13 17 18 34 90 125 133 

Output is sorted in the ascending order  using Min heap .

Point here is if we don't have the M sorted sequence even then using the PriorityQueue , we can have a sorted collection .

Let see the example using the Random number generation : 

public static void main(String[] args) {

/**

 * @author sachin srivastava

 * tek9g.blogspot.com

 *

 */

PriorityQueue<Integer> prq = new PriorityQueue<>();

Random random = new Random();

for (int i = 0; i < 20; i++) {

int rand = random.nextInt(20);

System.out.print(rand +" ");

prq.add(rand);

}

System.out.println("\n------\n");

while (!prq.isEmpty()) {

System.out.print(prq.poll()+" ");

}

}

  
Output : 

Random generated sequence : 

8 11 18 14 6 5 10 19 7 3 3 17 14 10 18 8 17 5 5 9 

------

Sorted merged sequence : 

3 3 5 5 5 6 7 8 8 9 10 10 11 14 14 17 17 18 18 19 

If you are working in a multithreaded  environment then these thread should not have concurrent access to the PriorityQueue and if any of the thread is modifying the queue then to make it thread safe , we need to use PriorityBlockingQueue instead of PriorityQueue which has been designed to cater the concurrent modification problem.

In the above mentioned scenarios  Min heap PriorityQueue is implemented which is by default the implementation of the queue.

If we want to create Max heap using the PriorityQueue then we need to pass the comparator to it and then output will be in the descending order. 

Consider the above random number problem : 

public static void main(String[] args) {

/**

 * @author sachin srivastava

 * tek9g.blogspot.com

 *

 */

//Max heap by passing a comparator

PriorityQueue<Integer> prq = new PriorityQueue<>((x,y)-> y-x);

Random random = new Random();

for (int i = 0; i < 20; i++) {

int rand = random.nextInt(20);

System.out.print(rand +" ");

prq.add(rand);

}

System.out.println("\n------\n");

while (!prq.isEmpty()) {

System.out.print(prq.poll()+" ");

}

}

  
Output : 

Random generated sequence : 

17 0 4 12 9 11 5 12 12 12 3 18 19 9 9 17 8 19 1 14  

------

Sorted merged sequence using the max heap in the descending order : 

19 19 18 17 17 14 12 12 12 12 11 9 9 9 8 5 4 3 1 0  

Enjoy the beautiful world of Java and coding !!!!!!