Friday, 18 December 2020

Write a program to group given set of numbers by even and odd

 

Write a program to group given set of numbers by placing all the even numbers first and then all odd numbers with O(n) time complexity and O(1) space complexity.

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

package com.test.algorithm;

public class GroupByEvenAndOdd {
public static void main(String[] args) {
int[] numArray = new int[]{4,2,5,8,12,11,10};
groupNumsByEvenAndOdd(numArray);
for (int i=0; i< numArray.length; i++) {
System.out.println(numArray[i]);
}
}

private static void groupNumsByEvenAndOdd(int[] numArray) {
int newEvenIndex = 0;
for (int i=0; i< numArray.length; i++) {
if(numArray[i]%2 == 0) {
if (i != newEvenIndex) {
// swap
int temp = numArray[newEvenIndex];
numArray[newEvenIndex] = numArray[i];
numArray[i] = temp;
}
newEvenIndex++;
}
}
}
}

Write a program to print nearest greater number along with each number in a given list

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

Nearest greater number is not the next greater number.

For example - for a given input - {4,2,5,8,12,11,10}

output will be like:

2 -> 5

4 -> 5

5 -> 8

8 -> 12

10 -> -1

11 -> -1

12 -> -1


package com.test.algorithm.stack;

import java.util.Stack;

public class NearestGreaterNumber {

public static void main(String[] args) {
int[] numArray = new int[]{4,2,5,8,12,11,10};
printNumWithNearestGreaterNumber(numArray);
}

private static void printNumWithNearestGreaterNumber(int[] numArray) {
Stack<Integer> numStack = new Stack<>();
for (int i=0; i< numArray.length; i++) {
while (!numStack.isEmpty() && numStack.peek() < numArray[i]) {
System.out.println(numStack.pop() + " -> " + numArray[i]);
}
numStack.push(numArray[i]);
}
while (!numStack.isEmpty()) {
System.out.println(numStack.pop() + " -> -1");
}
}
}

Write a program to print left view of a binary tree

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

A left view of a binary tree is the left most elements at each level a binary tree.


package com.test.algorithm.tree;

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

public class LeftView {

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

printLeftView(root);
}

private static void printLeftView(TreeNode root) {
Queue<TreeNode> queue1 = new LinkedList<>();
queue1.add(root);
Queue<TreeNode> queue2 = new LinkedList<>();
while (!queue1.isEmpty() || !queue2.isEmpty()) {
boolean isQueue1LeftPrinted = false;
boolean isQueue2LeftPrinted = false;
while (!queue1.isEmpty()) {
TreeNode node = queue1.poll();
if (!isQueue1LeftPrinted) {
System.out.println(node.getData());
isQueue1LeftPrinted = true;
}
if (node.getLeft() != null) {
queue2.add(node.getLeft());
}
if (node.getRight() != null) {
queue2.add(node.getRight());
}
}
while (!queue2.isEmpty()) {
TreeNode node = queue2.poll();
if (!isQueue2LeftPrinted) {
System.out.println(node.getData());
isQueue2LeftPrinted = true;
}
if (node.getLeft() != null) {
queue1.add(node.getLeft());
}
if (node.getRight() != null) {
queue1.add(node.getRight());
}
}
}
}
}

Write a program to print right view of a binary tree

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

A right view of a binary tree is the right most elements at each level a binary tree.

package com.test.algorithm.tree;

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

public class RightView {

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

printRightView(root);
}

private static void printRightView(TreeNode root) {
Queue<TreeNode> queue1 = new LinkedList<>();
queue1.add(root);
Queue<TreeNode> queue2 = new LinkedList<>();
while (!queue1.isEmpty() || !queue2.isEmpty()) {
while (!queue1.isEmpty()) {
TreeNode node = queue1.poll();
if (queue1.size() == 0) {
System.out.println(node.getData());
}
if (node.getLeft() != null) {
queue2.add(node.getLeft());
}
if (node.getRight() != null) {
queue2.add(node.getRight());
}
}
while (!queue2.isEmpty()) {
TreeNode node = queue2.poll();
if (queue2.size() == 0) {
System.out.println(node.getData());
}
if (node.getLeft() != null) {
queue1.add(node.getLeft());
}
if (node.getRight() != null) {
queue1.add(node.getRight());
}
}
}
}
}

Monday, 7 December 2020

MongoDB Basics


Stores JSON objects in BSON format. 

Javascript based. Allows to query in javascript style.


Master-Slave architecture - shards and replicasets

There is a router with a table of contents and shard keys using which it decides where to query the data and in some cases multiple shards.

mongos - process which manages cluster

client connects to mongos


> use recipe

switched to db recipe

> show dbs

admin   0.000GB

config  0.000GB

local   0.000GB

recipe  0.000GB


db.<collectionName>.insertOne({<entire json document to be inserted>}) -> this will dynamically create a collection


db.<collectionName>.find({"fieldToQuery":"valueOfFieldToQuery"}, {"filedstLimitOutput": 1})

.sort("fieldToSortBy": 1).limit(1).skip(1)


> show collections

recipe


> db.recipe.find({}, {"title": 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


> db.recipe.find({"title" : "Pancakes"}, {"title": 1});

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


> db.recipe.find({},{"title": 1}).sort({"title":1});

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }


> db.recipe.find({},{"title": 1}).sort({"title":1}).limit(1);

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


> db.recipe.find({},{"title": 1}).sort({"title":1}).limit(1).skip(1);

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


# nested objects can also be queried

> db.recipe.find({"ingredients.name" : "egg"}, {"title" : 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


# querying arrays

> db.recipe.find({"tags" : "easy"}, {"title" : 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


# match both entries in an array

> db.recipe.find({"tags" : {$all: ["easy","mexican"]}}, {"title" : 1});

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


# match either entries in an array

> db.recipe.find({"tags" : {$in: ["easy","mexican"]}}, {"title" : 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


#using expression

> db.recipe.find({$and :[{"ingredients.name" : "egg"}, {"ingredients.name" : "milk"}]}, {"title" : 1});

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }



$regex - for doing a regex search on a field


can store arrays, nested documents


comparison operators:

$eq, $lt, $lte, $gt, $gte, $ne, $in, $nin


logical operators:

$and, $or, $not


evalution:

$exists - to match documents with specified field


$where - documents satisfying javascript expression


it even have geospatial evaluation operators - $geoWithin, $geoIntersects etc


db.<collectionName>.updateOne({"fieldToQuery":"valueOfFieldToQuery"}, {$set :{"filedstLimitOutput": 1}});


> db.recipe.updateOne({"title" : "Zucchini Brownies" }, {$set: {"title" : "Zucchini Browniesss" }});

{ "acknowledged" : true, "matchedCount" : 1, "modifiedCount" : 1 }


$push $pull can be used for updating data in an array


# for getting the execution statistics, explain("executionStats") can be used

db.recipe.find({"tags" : {$in: ["easy","mexican"]}}, {"title" : 1}).explain("executionStats");


Reference documentation - https://docs.mongodb.com/manual/reference


sample_json = {

   "title":"Zucchini Brownies",

   "calories_per_serving":271,

   "comments": [{

      "body": "This is really gross.",

      "date": {

          "$date": "2020-09-07T18:42:30.000Z"

      },

      "name": "Caderyn Jenkins",

      "user_id": 1

  }, {

      "body": "Who thought of this? It's so bad.",

      "date": {

          "$date": "2000-02-03T18:42:30.000Z"

      },

      "name": "Grace Hopper",

      "user_id": 2

  }],

   "cook_time":32,

   "desc":"Don't worry, they won't turn out green",

   "directions":[

      "Combine brownie mix with other ingredients",

      "Bake as it says on box",

      "Don't actually make or eat this."

   ],

   "ingredients":[

      {

         "amount":{

            "quantity":1,

            "unit":"cup"

         },

         "name":"butter"

      },

      {

         "amount":{

            "quantity":2,

            "unit":null

         },

         "name":"egg"

      },

      {

         "amount":{

            "quantity":0.75,

            "unit":"cup"

         },

         "name":"plain yogurt"

      },

      {

         "amount":{

            "quantity":0.75,

            "unit":"cup"

         },

         "name":"shredded zucchini"

      },

      {

         "amount":{

            "quantity":0.75,

            "unit":"cup"

         },

         "name":"chocolate chips (semisweet)"

      },

      {

         "amount":{

            "quantity":3,

            "unit":"lbs"

         },

         "name":"creamy peanut butter"

      },

      {

         "amount":{

            "quantity":1,

            "unit":null

         },

         "name":"brownie mix"

      }

   ],

   "prep_time":12,

   "rating":[

      1,

      1,

      1,

      1,

      5

   ],

   "rating_avg":1.8,

   "servings":12,

   "tags":[

      "sweets",

      "easy"

   ],

   "type":"Dessert"

}


db.recipe.insertOne(sample_json);


Start/Stop mongod services in Mac:

brew services start mongodb-community@4.4

brew services stop mongodb-community@4.4



Microservices Authorization, JWT, OAuth 2.0 and SSO

 

In a microservices architecture, once the user logs in, the identity of the user needs to be communicated to all the services that handles the requests to the application and each service needs to know that this is an authenticated user and need to check whether the user have privileges for requested operation. 

The entry point to a microservice based application is an API gateway which hide the complexity due to multiple services from the end user. The gateway will contact an Authentication and Authorization server which authenticates and logs in the user and returns a JWT access token. This access token is further used in each request to verify the identity of the user from Authorization server.

JWT is a Base64 encoded string which can be decoded into a the following (all separated by "."):

1. a header with an algorithm used for signing the token, 

2. a payload which consists of basic user info like userId and iat (issued at time) and some basic info but not credentials

3. a footer consisting of a signature generated out of header and payload using the algorithm mentioned in the header and a secret key which is held only by the authorization server.

The JWT token is issued to the user based on the login using the credentials and is typically send in the further requests as a bearer token (by placing Bearer <token> in the Authorization header). The JWT token is normally saved in the cookies for the browser to send it in the further requests.

The authorization server generates a signature by extracting header and payload from the bearer token provided to it and compare with the signature in the bearer token for validating the authenticity on subsequent requests.


OAuth 2.0 

Important Terminologies:

Resource owner - The user who owns a resource (e.g. files on a google drive).

Resource server - The server which maintains the resource (e.g. google drive server)

Authorization server - The server which validates authorization to access resource server

Client application - Any client application that wants to access user resource on behalf of the user.

Grant type client credentials

In a microservice architecture, if a microservice needs to access data from another microservice:

1. The Authorization server grants a client credentials access token to the microservice

2. The authorization server validates the requests from the source microservice based on the client credential access token.

3. permission needs to be managed for the client credential access token for restricting the access of the service to APIs in the destination microservice as required. 

Grant type authorization code

If a client application wants to access certain details from a resource server on behalf of an end user:

1. The client application sends a request to authorization server requesting the access for the resource.

2. The authorization server redirects to the end user asking him to allow the client application to access the resource on his behalf, the user has to login if he has not already logged in to the authorization server.

3. Once the user gives consent for the client application to access the resource, the authorization server will send an authorization code/token to the client application.

4. The client application may store the same and calls the authorization server with the authorization code to get an access token.

5. The client application uses this access token for communicating with the resource server.

Grant type device code

OAuth 2.0 extension that enables devices with no browser or limited input capability to obtain an access token.

Grant type refresh token

This is used for getting a new access token when the original access token is expired. The original access token will have an expiry time when refresh token is required.


Handling SSO using OAuth 2.0

Although OAuth was meant for authorization, this model is extended to implement Single Sign On using grant type authorization code flow:

1. The client application sends a request to authorization server requesting the profile information of the user.

2. The authorization server redirects to the end user asking him to allow the client application to access his profile information, the user has to login if he has not already logged in to the authorization server.

3. Once the user gives consent for the client application to access his profile info, the authorization server will send an authorization code/token to the client application.

4. The client application may store the same and calls the authorization server with the authorization code to get an access token.

5. The client application uses this access token for communicating with the resource server and gets the profile info.

6. The client application trusts the authorization server and since authorization server validated the user, the user is considered valid by the client application

6. The user profile info is then set in the security context of the client app and will proceed. 

Saturday, 28 November 2020

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