Wednesday, 5 October 2022

Data Structures and Algorithms - Problem - 2 Coin Change challenge 1

In this blog, We are going to solve another Dynamic Programming problem using Brute Force and Memoization.


Problem Statement:- You have an integer array of coins of different denominations and an integer amount representing an amount of money.  You have an infinite number of each coin, and the order of coins doesn't matter.

What we need to return is the fewest number of coins that we need to make up that amount.
 Example 1: coins [10,20,50] and the amount is 100  
 Option 1 :- 10 x 10 = 100  
 Option 2 :- 20 x 5 = 100  
 Option 3 :- 50 x 2 = 100  
 Option 4 :- 10 x 8 + 20 x 1 = 100  
As we can see we computed four options by which we can get to 100 using available coins but what we need is the fewest, and in that case, Option 3 is our best option. Now let's understand how we can solve this using Dynamic Programming.

Let's see another example 
 Example 2: coins [10,30,40,50] and the amount is 70  
 Option 1 :- 10 x 7 = 70   
 Option 2 :- 50 x 1 + 10 x 2 = 70  
 Option 3 :- 40 x 1 + 30 x 1 = 70  
In example 2 the fewest coins we would require is 2 as per option 3.

Can we solve this problem using a Greedy algorithm? Which always starts with the biggest number that's why "GREEDY". 

In Example 2,  Option 2 is the example of being Greedy, Where we started with the biggest number but that took us 3 coins value to get the final result, and option 3 took 2 coins value to get the result, Which means the GREEDY algorithm is not we want to use here.

What other approach, we can use here, Dynamic Programming and Brute Force? let's try that. In order to use Bruteforce, We need to implement DFS (Depth First Search)

What we are doing here is we are subtracting the coins {10,30,40,50} from 70 which is our total amount, and we will continue subtracting coins till we reach 0 or stop doing it if the output is negative. 




Let's see the code, and understand how we can solve this problem. In the below code,  we followed example 2 and the output is as expected.



We should try one more example and this time the coins[] = {1,2,3} and amount = 7.  The fewest coins combination would be 3 x 2 + 1 x 1 = 7, which means a total of 3 coins.




In the next blog, we will see another famous coin chance challenge.

Happy Coding and Keep Sharing!! Code Repo

Sunday, 2 October 2022

Data Structures and Algorithms - Problem - 1 Climbing Stairs

Today, We are going to solve a Dynamic Programming problem, and we will understand the fundamentals of Brute force and memoization. 


Problem Statement:- You are climbing a staircase, and it takes n steps to reach the top, Each time you can either take 1 or 2 steps. What we want to know is, In how many distinct ways we can climb to the top?.

Example 1:  If we want to climb two steps, so in how many ways we can climb. We have 2 options to climb.  

Option 1:- 1 Step + 1 Step
Option 2:- 2 Steps


Example 1


Example 2:  If we want to climb three steps, then we have three options to climb to the top

Option 1 Red:  1 Step + 1 Step + 1 Step
Option 2 Black: 1 Step + 2 Steps
Option 3 Green: 2 Steps + 1 Step

Example 2

So, In the above examples, We can see how many steps are required to climb 2 or 3 stairs, but it is hard to visualize, Let's try to visualize it in more ways by using a Decision Tree


Let's take n=5, where n is the number of stairs we want to climb. Using Brute Force Algorithm we are going to make decisions.



So we are starting at step zero and our goal is to reach step 5, and we can climb 1 step or 2 steps at a time, and depending on the decision we take, each outcome will lead to a different path. And we will continue to make 2 decisions at every step, and count how many steps were we able to take to reach 5. We are going to solve this recursively. 

As we can see "GREEN" 8 different paths to reach 5 and we are going to ignore the RED one. When we started the problem we are going to reach stair 5 starting from stair 0, but we had a sub-problem when we reached step 1 how many ways to reach 5. as we can see in the below Decision Tree.



So, If we are going to solve this problem like this, basically using recursion and probably using DFS (Depth- First Search), 

What would be the Time-complexity of that.? because there will be two decisions each time, it is going to (2^n).

In the below screenshot, in the red block section, they both look exactly the same, because we are solving the same sub-problem and because we are using DFS the one at the LEFT will be solved first, so why don't we save the result of that.



and when reaching RIGHT, we can say we already know the result and we don't have to draw the entire decision tree. 



Now, if we look at the other Sub-Problem which is starting at step 3, we are asking the same question how many steps to reach 5. In this case, also, the LEFT one will end up computing first, and we don't need the RIGHT side one, so let's just eliminate that. 



Let's look if we have another sub-problem, Yes at step 4, which is also exactly the same decision tree and one at the LEFT will compute first so we eliminate the RIGHT one.




After eliminating all our repeated our, the Decision Tree will end up looking like this, and this is roughly O(n), a liner time solution where we are solving only a sub-problem once. 

Where the original problem started at 0, then 1, then 2, then 3, then 4 and finally 5, This is basically DP(Dynamic Programming) where we are caching (Memoization)



THE MOST interesting part is, We now know the path to reach 5 which is our base case, There is another way to solve this by starting from the bottom which means instead of starting from Step 1 we will start computing from the TOP.



In this approach, We will start from 5 to 1. 

When we are at 5 which is our step 1
  • Then from 4 to 5, we just need to take one more step, which is 1.
  • Next is step 3, here we can take 1 step or 2 steps to reach 5. which means we can take 2 steps in total. 
  • Next From 2, If we take one step and go to 3 and since we already computed how many steps it would take from 3 to reach 5, which is 2,  so we can add that and the total number of steps need to take is 1 step+2 steps = 3 Steps.
  • If we notice and are familiar with Fibonacci numbers, that is exactly what we are doing. 😃
and we have to loop n-1 to compute all the values to get the result. Now let's do some coding, and see how much code we need to right to solve this problem.

 package com.hemkant.DSA;  
 public class ClimbingStairs {  
   public static void main(String[] args)  
   {  
     System.out.println("Number of ways = " + findSteps(5));  
   }  
   static int findSteps(int n)  
   {  
     int temp;  
     int num1 =1, num2=1;  
     for (int i=0;i<(n-1);i++)  
     {  
       temp=num1;  
       num1=num1+num2;  
       num2=temp;  
       System.out.println(num2);  
     }  
     return num1;  
   }  
 }  

Yes, that's all we need to do to solve this problem. Code Repo


Happy Coding and Keep Sharing!!

Friday, 1 October 2021

Infrastructure as Code (IaC)

Is the process where Developers and DevOps team auto-magically manages and provision tech stack for an application using a software rather than doing it manual configuration of Hardware or OS using declarative definition file. 

With IaC we can build stable environment much Faster and Scale it, we can also enforce the consistency via code. 

There is no single standard syntax for declarative IaC, different platform supports different and often multiple ,file formats as well such as YAML, JSON and XML.

IaC is supported by list of popular third party tools such as Terraform, Ansible, Puppet. In this post we will use Terraform and cloud provider will be AWS. Terraform is supported by all major cloud provider i,e GCP, Azure.

First we need to install Terraform , I am using Mac so I can use brew to install Terraform if you are on Windows or Linux you can download it from here 


Now, you might be working for different client who uses different version of terraform for that there is a quick switchTo program which you can install and its really helpful in such cases.                          

 brew install warrensbox/tap/tfswitch


Now let's use code and create Infrastructure but before that I need to configure the aws-cli and secure the key, you can put them in the env. variables or in Vault providers as well, first I would like to create a VPC, its very simple just couple of lines of code and we will see who easy it is.

provider "aws" {
region = "eu-west-1"
}

resource "aws_vpc" "myvpc" {
cidr_block = "10.0.0.0/16"
}


In the above code snippet, I have aws as provider and resource which I want to create is aws_vpc with cidr_block given To run this we need to execute two commands "terraform init" and "terraform apply".



Let's check the AWS console and see if we have this VPC ID 


Next , let's take an another example and create a free-tier EC2 instance with web security enabled for both ingress(Inbound) & egress(outbound). 


and we have our t2.micro EC2 instance is ready, with Security Groups for both inbound and outbound  



We saw couple of examples of IaC, how it can help us in managing and provision infrastructure using simple code and provides consistency. We can do everything that is required to manage Infrastructure.

IMPORTANT NOTE :- Use "terraform destroy" command to delete the resource.

Happy coding and keep sharing!! 


Wednesday, 29 September 2021

Event Driven Architecture using Apache Kafka

A quick recap of what we discussed in the previous post about the EDA, and In this post, we will see more insight. EDA It is a pattern that uses events to communicate between decoupled components or services, and these events will need to be published to an event broker platform and then sent to the consuming applications.  

Event-Driven Architecture is comprised of three components.

  • Producers:- are the apps or services that publish the events to an event broker platform.
  • Router:- Routes them to their respective consuming applications 
  • Consumers:- Another app or service that consumes a particular topic in an event router.
When Designing the Event-Driven Models we can implement two Models.

  • Pub/Sub (Publish/Subscribe):- Events are published to a topic and sent to one or more subscribers, once received, the event cannot be backtracked or reread again, and new subscribers do not see the event.
  • Event Streaming:- Events are written to a log and ordered in a partition. A client app can read from any part of the stream and reply to the events.

We are going to use Apache Kafka, to implement the event-driven architecture, which is an open-source, distributed, event streaming platform. 

Using Apache Kafka we could have multiple apps or services that write event events to Kafka cluster and at the same time, we could also have multiple consumers apps that subscribe or stream events from Kafka, Where a Kafka Cluster is a collection of brokers and they could be actual physical servers or single rack and If you are using Kafka on the cloud or as (PaaS) then you don't have to concerned about it. 

Here, Zookeeper is the one who is responsible for the cluster & Failure management and decides which among the replicated brokers can be the new leader.   

The broker can store multiple topics where producers write events, where a topic is a collection of related events or messages. When producers produce an event we need to specify the topic where we want to write or publish it.


In the next post, we will build Spring Boot API, which will produce events and we will see end to end flow of producers, routers and consumers using that, until then.

Happy coding and keep sharing!!
 

Monday, 27 September 2021

An Overview :- What is Event-Driven Architecture ?

Before, We jump into the EDA, let's understand the standard guidelines for system design or generally reactive manifesto. Which is something is community driven guidelines that are indented to give cohesive approach to system.     

So, the core of the reactive manifesto is make system message driven, more specifically "async" messaging.  



We want to make the system async messaging driven with scalabilityresilient and this helps us to build distributed systems or K8s. Where Scalable means our hardware should expand as the workload expands and By resilient we don't want any single point of failure and if it does we should be able to handle it elegantly.

Based on the above three foundations, we should be able to build a system that is responsive.   

Now, we have our core setup let's understand What is an event ?. In simple words, an event is a statement of facts that happened in the past. Let's talk about an example of a Retail application.




So, In an application, we have a checkout service and that service wants to talks to other services such as "Inventory", "Shipping", "Contact".

In the messaging model, if the inventory wants to know what the checkout is doing, the checkout will send a message directly to inventory to let it know a checkout happens. and to others as well directly to Shipping and to Contact service OR these services can message directly to checkout as well "Conversational Messaging", till now the message is sitting on a host machine.

When we design the event application our event producer might web app, mobile app, etc.. this will enable the events logs being produced by all the producing applications. 

Event logs can be used to Trigger an action In the case of IoT when any device turns on, It spins a pod on the Infra and that pod is a function as a Service (FaaS) that sits on top of Serverless Infrastructure and turns down when our function finishes by sending the event.  

With event logs we can optimize and custom data persistence, so can be possible that our Inventory service will consume data from stream send by web application m it will modify the local data and produce in the event backbone and this new stream is giving the most correct inventory data to any other application in the system.

Important things which happen here is we can save all our data raw or transformed in a Data Lake, this will help heavy application like AI.

Another thing that EDA enables is stream processing which is built on top of the Apache Kafka streams API.  

Benefits of Event/Driven Architecture
  • Asynchronous
  • Scalable and Failure Independent
  • Auditing and Point-in-time recovery 

Till now we have seen an overview and benefits of EDA that sit on top of reactive manifesto ideas for system designing.

In the next post, we will learn more about this in detail with some demo examples, Until then 

Happy coding and keep sharing!!  



 

Wednesday, 4 December 2019

Using AWS Services to Monitor Tridion

When you have a very important and bulk publishing is going on and you want to monitor each state then AWS service is a great way of doing it. Recently, I had this opportunity to implement AWS services to monitor SDL Tridion publishing and Broker Database spike.  We need to monitor the publishing state and Broker DB connections limit and for that I used the following AWS services.

All these activity is required and becomes almost mandatory when yon have Huge INFRA to manage.
  1. AWS CloudWatch
  2. AWS SNS (Simple Notification Service)
  3. AWS lambda Function

To monitor the publishing I used the AWS Lambda function which is in python and some inline SQL script. Yes, just few lines of code gives you all the info.



This matrix is then used in the dashboard to generate the realtime GRAPH and Similarly, we have script for other publishing state which helps us in monitoring the progress of publishing. These scripts are very helpful when you have thousands of the items in queue and waiting for publishing.

Failed items

Published items

Next, is we need to implement the notification service to send the notification whenever the Broker Database DBconnectin limit reaches the higher side or more than expected so that we can take action pro-actively. To Implement this we used the AWS default Matrix and with the help of AWS SNS we are sending the notification, for notification you can use (EMAIL,SMS,HTTP,Notification etc) depending upon your requirement.


 You need to go to the CloudWatch--> Alarm and create a New Alarm. By Default in SQL Server the default DB connection is set to 0 which mean Unlimited, but using AWS CloudWatch you can monitor and can take pro.active steps when its starts increasing.   

Next is send the notification if the limit is crossed and for that we can use AWS SNS.
Configure SNS to send Notification. 

Where SNS is your notification service. We first need to create a Topics and based on Publisher and Subscriber model we can send the notification. Protocol supported by the AWS SNS to subscribe.

Protocol Available 

Or, you can configure the Auto Scaling of you EC2 instance, we only have notifications service configured but yes, we also have this options as well. It all depends on your requirements.

Auto Scaling option in case of Alarm 

We just saw how we can monitor SDL Tridion using AWS Service and takes pro-active steps. Configuring the AWS Service is pretty easy.


Happy Coding and Keep Sharing!!! 



Thursday, 29 August 2019

SDL Tridion Sites 9.1 New Feature Integration Framework

Today SDL released the latest version SDL Tridion Sites 9.1 and in this release we have so many new features, but today we are going to discuss the SDL Tridion Integration Framework. These features enable you to quickly connect with your DAM, CRM, ERP, Marketing Automation, Commerce, PIM, Portal technology, Analytics, and Social Media platforms.

In this blog we will see how Unified Extensions/Connectors build using this framework will simplify the process of deploying multiple extensions in SDL Tridion Sites it combines multiple extensions that should be deployed together as a single solution. We can pack all together Content Manager, Content Manager Explorer, Dynamic Content Delivery and External Content Library extensions.

With EMS the problems that it solves is, we don't have to do configuration on multiple places, no need to restart services and IIS, one single package for multiple extensions and one of the biggest advantage is it supports scaled out environments - so if you have 3 x CM, 5 x publishers, etc. it's a one drop shop.


The package that is built contains.
  • Single zipped file
  • Manifest.json in the root of the zip
  • All reference to jars, dlls and other resources in the manifest.json file will be relative to the root of the zip
  • Dependent jars and dlls should be in the same folder as the source jar or dll
SDL released number of ready made connectors for us, we can download it from  https://appstore.sdl.com/

  1. Adding existing connector [Read More] If the Connector you are adding is written in C# (.NET Core), ensure that version 2.2 of the .NET Core Runtime is installed on the host machine the Content Service. Download the .NET Core Runtime for either Windows or Linux from the following location: https://dotnet.microsoft.com/download/dotnet-core/2.2
  2. Build a new connector [Read More]




In the next blog, we will be creating Extensions until then. 

Happy Coding and keep Sharing!!!