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

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.