<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Bharat Kul Ratan on Medium]]></title>
        <description><![CDATA[Stories by Bharat Kul Ratan on Medium]]></description>
        <link>https://medium.com/@bharatkulratan?source=rss-2f7a73dcfa05------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*S6Uq8aXgdHEaTsHi.jpeg</url>
            <title>Stories by Bharat Kul Ratan on Medium</title>
            <link>https://medium.com/@bharatkulratan?source=rss-2f7a73dcfa05------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 02:34:22 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@bharatkulratan/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Implementation of Gradient Descent in Linear Regression]]></title>
            <link>https://medium.com/@bharatkulratan/implementation-of-gradient-descent-in-linear-regression-a56f353f2a80?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/a56f353f2a80</guid>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[linear-regression]]></category>
            <category><![CDATA[implementation]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[gradient-descent]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Sat, 07 Jul 2018 10:19:58 GMT</pubDate>
            <atom:updated>2018-07-07T10:19:58.104Z</atom:updated>
            <content:encoded><![CDATA[<p>Problem: Given some points<strong>(x,y)</strong> on 2-D graph we have to predict the line that fits them best.</p><p>Once we have that line we can use that to find out the values of <strong>y</strong> for the values of <strong>x</strong> other than that are given to us. For simplicity we taking the points in 2-D. It can be generalized to further dimensions too. This is the theme of Linear Regression. Now as given in the problem we have to find that line that fits best but how do we know what is best. For that, we define an error metric which would tell us that the predicted line is good enough or not. We will choose the Ordinary Least Squares method to define that metric. <a href="https://en.wikipedia.org/wiki/Ordinary_least_squares">Wikipedia</a> states it clearly,</p><blockquote>&quot;<strong>Ordinary Least Squares</strong> (OLS) or linear least squares is a method for estimating the unknown parameters in a linear regression model. OLS chooses the parameters of a linear function of a set of explanatory variables by minimizing the sum of the squares of the differences between the observed dependent variable (values of the variable being predicted) in the given data-set and those predicted by the linear function. Geometrically, this is seen as the sum of the squared distances, parallel to the axis of the dependent variable, between each data point in the set and the corresponding point on the regression surface – the smaller the differences, the better the model fits the data.&quot;</blockquote><p>To put more concretely the error function described in OLS is written as follows and is called <strong>Mean Squared Error</strong>(MSE)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/408/1*D8shfkPHYlaQQwrodEj-ZQ.png" /><figcaption>Equation 1: MSE calculation</figcaption></figure><p>We will use this MSE to evaluate fitness of the predicted line. The lower the value, the better it fits the given points. In equation 1, <strong>y</strong> is the value we already have and <strong>p</strong> is the value which will be predicted using <strong>m</strong> and <strong>c</strong>. This predicted value of <strong>p</strong> could be written as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/179/1*A9pRwa8X9s39lCDWBpxOwQ.png" /><figcaption>Equation 2: line which will predict the value given m(slope) and c(intercept)</figcaption></figure><p>Initially we will randomly choose values for <strong>m</strong> and <strong>c</strong>. Due to these random values, the probability of the resulting MSE having large values is high. So we will use <strong>Gradient Descent</strong> method to update <strong>m</strong> and <strong>c</strong> in such a manner that will lower the MSE for the predicted line. So our objective is to</p><ol><li>Choose the parameters(slope and intercept) of the linear function</li><li>Choose those parameters in a way that minimizes the MSE</li></ol><h4>Gradient Descent</h4><p>Gradient Descent is an optimization algorithm which updates the value of parameters in such a way that minimizes the value provided by error function. To find out the gradients we will do partial differentiation of MSE equation with respect to(w.r.t.) <strong>m</strong> and <strong>c</strong>. The resulting equations would be</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*HbuKxuahRF_7gZSwUaHYjA.png" /><figcaption>Equation 3: partial differentiation of MSE w.r.t. m</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/417/1*yXxkdVvDD4jSWJnDzw-EYA.png" /><figcaption>Equation 4: partial differentiation of MSE w.r.t. c</figcaption></figure><p>In Gradient Descent we would iterate over the given data-set and compute the gradients of all the parameters(here <strong>m</strong> and <strong>c</strong>) as given in equation 3 and 4. After each epoch(iteration on data-set) values of <strong>m</strong> and <strong>c</strong> would be updated using the summation value of gradients for each parameter. This could be written as</p><pre>for epochs=1 to n<br>   for each parameter in predicted equation<br>      w := w + ∆w where ∆w = 𝛂∑(parameter_gradient)</pre><p>Here ∆w is the value to be updated in parameters and is calculated as described in equation 3 and 4. 𝛂 is a constant, which is the learning rate to control the value of parameters.</p><p>Enough theory, let’s see it in action. We will plot some points and try to find out the best fitting line for them. First we plot some random points on graph which would look like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cOBjrCgM2LFtrApvplK4OQ.png" /><figcaption>Figure 1: plot of (x,y)</figcaption></figure><p>To start with, we will draw a line of the form <strong>y = m * x + c</strong> with random values of <strong>m</strong>(slope) and <strong>c</strong>(intercept), say <strong>m</strong> = 1, <strong>c</strong> = 0. Hence our predicted equation would be <strong>y</strong> = 1 * <strong>x</strong> + 0 which is reduced to <strong>y</strong> = <strong>x</strong>. Now we will use Gradient Descent to gradually update the parameters(i.e. <strong>m</strong> and <strong>c</strong>) as per equation 3 and 4. We will choose a learning rate of 0.001 and number of epochs to be 100000. After regular intervals in epoch we would note down the MSE and values of <strong>m</strong> and <strong>c</strong> so that we can see the values updating after those epochs. Let’s look at an implementation in Python.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5f378b616f163b2a524d5f4d4f418173/href">https://medium.com/media/5f378b616f163b2a524d5f4d4f418173/href</a></iframe><p>The output of this code is</p><pre>slope= 1 intercept= 0 mse= 175.4<br>slope= 2.071 intercept= 0.093 mse= 9.771<br>slope= 2.158 intercept= 0.197 mse= 8.578<br>slope= 2.1 intercept= 0.942 mse= 7.945<br>slope= 2.007 intercept= 2.128 mse= 7.559</pre><p>We have started with <strong>m</strong>=1 and <strong>c</strong>=0 which resulted in MSE of 175.4. Gradually as the parameters are updated we get the final value of <strong>m</strong>=2.007, <strong>c</strong>=2.128, and MSE=7.559. Let’s plot the predicted equation using these values</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CUieQy-B4AYr7F3ExG6zUQ.png" /><figcaption>Plotting the predicted line</figcaption></figure><p>In the above figure, the red line is the one which which Gradient Descent predicted and green line was the one with randomly selected values. We can see that red line fits better the given point in comparison to green line. We have chosen only one variable in this linear equation for simplicity but this technique works for more than one variable too.</p><p>This was a brief introduction to Linear Regression where we used only OLS method. There are many other methods to fit that line. Sometimes we fit that line with so little error on given data-set that that it causes problem of <strong>over-fitting</strong>. In over-fitting the line learns the given data-set such that it produces very low error on the input but produces high error on the data-set which it has not seen. We could avoid those scenarios using <strong>regularization</strong>. But we will cover those problems and solution in second part later.</p><p>That’s it for now. Feel free to leave your thoughts into comments. Thanks for reading.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a56f353f2a80" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[8-queen problem]]></title>
            <link>https://medium.com/@bharatkulratan/8-queen-problem-b0690effd3ff?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/b0690effd3ff</guid>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[dfs]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Sat, 09 Dec 2017 14:48:05 GMT</pubDate>
            <atom:updated>2017-12-09T14:48:05.653Z</atom:updated>
            <content:encoded><![CDATA[<p>The <a href="https://en.wikipedia.org/wiki/Eight_queens_puzzle"><strong>eight queens puzzle</strong></a> is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.</p><p>We can start the solution by putting 8 queens in 8 columns. But if you put the queens randomly there are very high chances that they will be attacking each other and hence not the solution. So we have to just find the row for each queen such that they don’t attack among themselves.</p><p>We will start from first column and will go to eighth column one by one. For each column we will try all the 8 rows to find that row in which putting the current queen will not affect the previously put queens. If we can not find such row, we’ll backtrack to previous column and start the process again.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/629e8ef7251ce978ddd3e65e158ca32f/href">https://medium.com/media/629e8ef7251ce978ddd3e65e158ca32f/href</a></iframe><p>isSafe() takes the 2-D array, row, and column as parameters and decides if the given cell denoted by row and column is safe to put the queen. dfs() takes 2-D array and current column for which we are trying to put the queen. It will recursively iterate to next column if we find a row to put the queen in current column and it will backtrack to previous one if there is no valid row available to put the queen.</p><p>I haven’t put much efforts in the code. So if you find any bug or optimization feel free to comment it.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b0690effd3ff" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A better way to look your git logs]]></title>
            <link>https://medium.com/@bharatkulratan/a-better-way-to-look-your-git-logs-86abca5987b0?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/86abca5987b0</guid>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[git]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Tue, 17 Oct 2017 11:24:23 GMT</pubDate>
            <atom:updated>2018-10-18T07:30:06.320Z</atom:updated>
            <content:encoded><![CDATA[<p>While searching for a better alternative to output of default git log command I came across this blog at</p><pre><a href="https://coderwall.com/p/euwpig/a-better-git-log">https://coderwall.com/p/euwpig/a-better-git-log</a></pre><p>This was better in comparison to default output but I needed two more things in that. First, I wanted to know which files were changed in that commit and second, how to show only a limited number of lines.</p><p>We can create an alias with the desired flags of git log but we also want this alias to accept an argument. This argument is the number of lines we want to show. Hence, I’ve created this simple function.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9316128cb494569a93baf08ab3dc744c/href">https://medium.com/media/9316128cb494569a93baf08ab3dc744c/href</a></iframe><p>You can add this function in ~/.bash_aliases or ~/.bashrc or ~/bash_profile but to keep all the aliases in one place I’ve added it in ~/.bash_aliases. In order to make this function work we have to reload the environment. For that use source ~/.bash_aliases command.</p><p>Finally we can use gitlog alias for our output. If you want the limited number of lines of log, pass a number as an argument. For e.g. gitlog 5. Omitting the argument will output all the lines for the log.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=86abca5987b0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Using Comparable and Comparator interfaces in Java]]></title>
            <link>https://medium.com/@bharatkulratan/using-comparable-and-comparator-interfaces-in-java-b793d06cdf7e?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/b793d06cdf7e</guid>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Sun, 15 Oct 2017 17:16:22 GMT</pubDate>
            <atom:updated>2017-10-15T17:16:22.847Z</atom:updated>
            <content:encoded><![CDATA[<p>In this tutorial we will learn how to sort a list of objects in Java. A list of primitive data type, for e.g. integers can be sorted by JVM (Java Virtual Machine) by default as they have a natural ordering which is used as the basis for sorting. JVM knows which integer is smaller than the other one and hence could sort them. But what if we had a list of our own objects. JVM can’t sort them as it doesn’t have any basis to compare them. To solve this, Java had provided two interfaces Comparable and Comparator. We will see how to use both of them in this tutorial.</p><p><strong>Comparable</strong></p><p>Comparable interface has just one method, public int compareTo(T object). It takes a single argument which would be compared to this object and determines the sorting order based on the returned value of this function. This function returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object. Let&#39;s take an example for more understanding.</p><pre>import java.util.ArrayList;<br>import java.util.Collections;</pre><pre>class Person implements Comparable&lt;Person&gt;{<br>	String name;<br>	int age;<br>	<br>	Person(String name, int age){<br>		this.name = name;<br>		this.age = age;<br>	}<br>	<br>	/**<br>	 * This function compares this class object<br>	 * to person object passed as an argument<br>	 * and returns negative integer, zero, or a positive integer <br>	 * as this object is less than, equal to, or greater than the specified object.<br>	 */<br>	@Override<br>	public int compareTo(Person person){<br>		if(this.age == person.age)<br>            return 0;<br>        else<br>            return (this.age &lt; person.age) ? -1 : 1;<br>	}<br>	<br>	@Override<br>	public String toString(){<br>		return this.name + &quot;:&quot; + this.age;<br>	}<br>}</pre><pre>class Comparison{<br>	public static void main (String ... args){<br>		ArrayList&lt;Person&gt; list = new ArrayList&lt;Person&gt;();<br>		list.add (new Person(&quot;Jack&quot;, 34));<br>		list.add (new Person(&quot;Tom&quot;, 42));<br>		list.add (new Person(&quot;Bond&quot;, 28));<br>		<br>		Collections.sort (list);<br>		System.out.println (list);<br>	}<br>}</pre><p>In the above code, <em>Person</em> class implements Comparable and overrides the method compareTo. The value returned by this function provides the basis for the ordering of objects. We can implement this method to compare whichever parameter should be used for comparing the objects. For e.g. we&#39;re comparing <em>Person</em> objects on basis of their age. Hence the person objects would be sorted in ascending order based on their age. But what if we want to sort them with respect to their names. For such cases we should Comparator interface.</p><p><strong>Comparator</strong></p><p>Let’s see how to use Comparator for ordering objects. This interface has a method compare(T object1, T object2). This function compares its two arguments for ordering of objects. This would be done on the basis of the value returned by this function. It returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. Let&#39;s see an example to make it more clear.</p><pre>import java.util.ArrayList;<br>import java.util.Collections;<br>import java.util.Comparator;</pre><pre>class Person {<br>	String name;<br>	int age;<br>	<br>	Person(String name, int age){<br>		this.name = name;<br>		this.age = age;<br>	}<br>	<br>	String getName(){<br>		return name;<br>	}</pre><pre>int getAge(){<br>		return age;<br>	}<br>	<br>	@Override<br>	public String toString(){<br>		return this.name + &quot;:&quot; + this.age;<br>	}<br>}</pre><pre>class NameComparator implements Comparator&lt;Person&gt;{<br>	@Override<br>	public int compare (Person p1, Person p2){<br>		// sorts Person in ascending order<br>		// for descending order use p2.compareTo(p1)<br>		return p1.getName().compareTo(p2.getName());<br>	}<br>}</pre><pre>class AgeComparator implements Comparator&lt;Person&gt;{<br>	@Override<br>	public int compare (Person p1, Person p2){<br>		// sorts Person in ascending order<br>		// for descending order use p2.compareTo(p1)<br>		return p1.getAge() - p2.getAge();<br>	}<br>}</pre><pre>class Comparison{<br>	public static void main (String ... args){<br>		ArrayList&lt;Person&gt; list = new ArrayList&lt;Person&gt;();<br>		list.add (new Person(&quot;Jack&quot;, 34));<br>		list.add (new Person(&quot;Tom&quot;, 29));<br>		list.add (new Person(&quot;Bond&quot;, 31));<br>		<br>		// sorts Person on basis of their age<br>		Collections.sort (list, new AgeComparator());<br>		System.out.println (list);<br>		<br>		// sorts Person on basis of their name<br>		Collections.sort (list, new NameComparator());<br>		System.out.println (list);<br>	}<br>}</pre><p>Output of the above code would be:</p><pre>[Tom:29, Bond:31, Jack:34]<br>[Bond:31, Jack:34, Tom:29]</pre><p>In above code we are using Comparator interface for comparison. In the previous code <em>Person</em> was sorted with the help of Comparable. But there was a little complication in that approach. What if we had to sort objects on basis of different parameters. Using Comparable would not be a good idea in that case as we have to change the method compareTo() for all the different parameters. Java provides us Comparator interface which would be apt to use in such cases. In this code, two different comparators are being used, one for age, and another for name. We can use these comparators in Collections.sort(). Similarly we can write all the Comparator objects in separate classes. Using this approach we don&#39;t have to disturb our class providing objects for ordering.</p><p>For any doubts or suggestions please drop a comment. Thanks for reading. Have a nice day!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b793d06cdf7e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Nested classes in Java]]></title>
            <link>https://medium.com/@bharatkulratan/nested-classes-in-java-d3530801f0ee?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/d3530801f0ee</guid>
            <category><![CDATA[java]]></category>
            <category><![CDATA[tutorial]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Sun, 15 Oct 2017 17:10:35 GMT</pubDate>
            <atom:updated>2017-10-15T17:10:35.862Z</atom:updated>
            <content:encoded><![CDATA[<p>Classes in Java are blueprint of Objects. These Objects are at the core of Object Oriented Programming (OOP). Generally classes are defined in top-level of program. But some classes which are defined within another class are called nested classes or member classes. There are four types of nested classes: <strong>static nested classes</strong>, <strong>non-static nested classes</strong>, <strong>anonymous classes</strong>, and <strong>local classes</strong>. Except static nested classes, rest others are known as inner classes. Let’s have a look on them one by one.</p><h4>Local classes:</h4><p>Local classes are classes that are defined in a block, which is a group of zero or more statements between balanced braces. Anything between { and } is a block. Classes within blocks will look like,</p><pre>public class Example {<br>	public static void main(String...args) {</pre><pre>// Class defined within a block<br>		{<br>			class DemoClass {<br>				DemoClass() {<br>					System.out.println(&quot;Example of local class&quot;);<br>				}<br>			}<br>			DemoClass demo = new DemoClass();<br>		}<br>	}<br>}</pre><p>In the above code, DemoClass is a local class. <a href="https://docs.oracle.com/javase/tutorial/java/javaOO/whentouse.html">According to reference</a>, Local classes should be used if we need to create more than one instance of a class, access its constructor, or introduce a new, named type. Typically the local classes are defined in the body of a method. For example,</p><pre>public class Example {<br>	<br>	static void CheckNumbers (int a, int b){<br>		class Assistant{<br>			boolean flag = false;<br>			Assistant(int num){<br>				if (num &gt; 0){<br>					flag = true;<br>				}<br>			}<br>			<br>			boolean getState(){<br>				return flag;<br>			}<br>		}<br>		<br>		Assistant first = new Assistant(a);<br>		Assistant second = new Assistant(b);<br>		<br>		if (first.getState() &amp;&amp; second.getState()){<br>			System.out.println (&quot;Both are positive integers&quot;);<br>		}<br>	}<br>					<br>	public static void main(String...args) {<br>		CheckNumbers (23, 67);<br>	}<br>}</pre><p>A local class has access to the members of its enclosing class. Also a local class has access to local variables. However, it can access only those local variables which are declared as final. When a local class accesses a local variable or parameter of the enclosing block, it captures that variable or parameter. The reason for accessing only final variables because they behave like constants. Their value does not change and hence remain same for both local and enclosing class. Values of the variables would become inconsistent if declared non-final.</p><h4>Anonymous classes:</h4><p>They are like local classes except that they do not have a name. They behave as expression. They should be used if we need to use a local class only once. Anonymous classes definition includes “new” operator, name of an interface to implement or a class to extend, parentheses that contain the arguments to a constructor and a body which is a class declaration body. More specifically, in the body, method declarations are allowed but statements are not.</p><p>For example,</p><pre>public class Example {<br>	<br>	public static void main(String...args) {<br>		Button button = new Button();<br>		<br>		//Approach 1<br>		button.setOnClickListener(new OnClickListener(){<br>			public void onClick(String message){<br>				System.out.println (&quot;Hello &quot; + message);<br>			}<br>		});<br>		<br>		//Approach 2<br>		OnClickListener clicklistener = new OnClickListener(){<br>			public void onClick(String message){<br>				System.out.println (&quot;Hello &quot; + message);<br>			}<br>		};	// watch this semi-colon<br>			//the definition of class is an expression.<br>		button.setOnClickListener ( clicklistener );<br>		<br>	}<br>}</pre><pre>interface OnClickListener {<br>	public void onClick(String message);<br>}</pre><pre>class Button{<br>	public void setOnClickListener(OnClickListener listener){<br>		listener.onClick(&quot;world&quot;);<br>	}<br>}</pre><p>Another example of anonymous classes.</p><pre>public class Example {<br>	abstract public static class Value {<br>		String name;<br>		Value(String name) {<br>			this.name = name;<br>		}<br>		<br>		abstract void printValue();<br>	}</pre><pre>public static final Value PLATINUM = new Value(&quot;PLATINUM&quot;) {<br>		void printValue() {<br>			System.out.println(&quot;Value 1000&quot;);<br>		}<br>	};<br>	<br>	public static final Value GOLD = new Value(&quot;GOLD&quot;) {<br>		void printValue() {<br>			System.out.println(&quot;Value 100&quot;);<br>		}<br>	};<br>	<br>	public static final Value SILVER = new Value(&quot;SILVER&quot;) {<br>		void printValue() {<br>			System.out.println(&quot;Value 10&quot;);<br>		}<br>	};</pre><pre>public static void showValue(Value object) {<br>		object.printValue();<br>	}</pre><pre>public static void main(String...args) {<br>		showValue(GOLD);</pre><pre>}<br>}</pre><h4>Non-static nested classes:</h4><p>Those classes which are simply defined inside inside another class. A typical usage of non-static nested class would be like here shown in example.</p><pre>public class Example {<br>	public static void main(String...args) {<br>		Movement catMove = new Cat().movement();<br>		catMove.move(); // Cat is walking</pre><pre>Movement birdMove = new Bird().movement();<br>		birdMove.move(); // Bird is flying<br>	}<br>}</pre><pre>class Cat {</pre><pre>Movement movement() {<br>		return new CatMovement();<br>	}</pre><pre>class CatMovement implements Movement {<br>		@Override<br>		public void move() {<br>			System.out.println(&quot;Cat is walking&quot;);<br>		}<br>	}<br>}</pre><pre>class Bird {</pre><pre>Movement movement() {<br>		return new BirdMovement();<br>	}</pre><pre>class BirdMovement implements Movement {<br>		@Override<br>		public void move() {<br>			System.out.println(&quot;Bird is flying&quot;);<br>		}<br>	}<br>}</pre><pre>interface Movement {<br>	public void move();<br>}</pre><p>Here Cat and Bird classes implement the Movement interface in their own ways. You might be asking why Cat and Bird don’t implement Movement interface and override the move(). Because when a class extends or implements there become IS-A relationship between them. Here it would not make much sense if Cat and Bird implements this interface. Neither Cat IS-A movement nor is Bird IS-A movement is correct. It is more convincing to see that Cat HAS-A movement, Bird HAS-A movement. Favor composition over inheritance always. That makes program more flexible.</p><h4>Static nested classes:</h4><p>A common use of private static member classes is to represent components of the object represented by their enclosing class. Consider the following example.</p><pre>public class Example {<br>	public static void main ( String ... args){<br>		Map map = new Map();<br>		map.put (4, 7);<br>		System.out.println (&quot; &quot; + map.get(4));<br>	}<br>}</pre><pre>class Map{<br>	static int array [] = new int [10];<br>	<br>	private static class Entry{<br>		Entry(){<br>		}<br>	<br>		int getValue( int key){<br>			return  array[key];	<br>		}<br>		<br>		void setKeyValue(int key, int value){<br>			array[key] = value;<br>		}<br>	}<br>	<br>	void put (int key, int value){<br>		Map.Entry entry = new Map.Entry();<br>		entry.setKeyValue (key, value);<br>	}<br>	<br>	int get (int key){<br>		Map.Entry entry = new Map.Entry();<br>		return entry.getValue(key);<br>	}<br>}</pre><p>This example will still work even if Entry would not be a static class. As Entry class do not need an instance of Map class to work, we will declare it as static. If we will not use the static modifier, each Entry instance will contain an extraneous reference to the Map object. Maintaining this reference costs time and space with no corresponding benefits.</p><p>If we look at the syntax, only difference visible is keyword <strong>static</strong> between both types of classes. Static nested classes do not need an instance of the enclosing class which makes them independent. On the other hand, non-static nested classes always require an instance of enclosing class. Within instance methods of a non-static member class, it is possible to invoke methods on the enclosing instance. Given a reference to an instance of a non-static member class, it is possible to obtain a reference to the enclosing instance. Hence performance wise non-static classes should be avoided as we need an extra outer class reference to access non-static nested class objects.</p><p>That was a brief introduction to nested classes. For more details you might want to check out this reference :</p><p><a href="https://docs.oracle.com/javase/tutorial/java/javaOO/nested.html">https://docs.oracle.com/javase/tutorial/java/javaOO/nested.html</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d3530801f0ee" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Print all the paths between two nodes in a Graph]]></title>
            <link>https://medium.com/@bharatkulratan/print-all-the-paths-between-two-nodes-in-a-graph-89aee57544a4?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/89aee57544a4</guid>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Sun, 15 Oct 2017 16:57:10 GMT</pubDate>
            <atom:updated>2017-10-15T16:57:10.487Z</atom:updated>
            <content:encoded><![CDATA[<p>In this tutorial we will learn how to find all the simple paths(paths without a cycle) between two nodes in a graph. We are given a graph, a source node, and a destination node and we have to find all the paths originating from source node to ending at destination node.<br> <a href="https://en.wikipedia.org/wiki/Depth-first_search"><strong>Depth First Search</strong></a><strong>(DFS)</strong> is generally used when finding a simple path between two nodes. Our problem is similar to that as we have to find out not just any single path but all the paths. So we will tweak the DFS algorithm a little to print all possible paths. The basic idea is that, after the destination node is found by DFS, print the path and mark it as unvisited so that DFS could continue finding all the remaining paths.</p><p>For example, let’s take a <a href="https://en.wikipedia.org/wiki/Complete_graph"><strong>complete graph</strong></a> for five nodes. Graph is given as 2-D matrix. Here’s the graph</p><pre>0 1 1 1 1<br>1 0 1 1 1<br>1 1 0 1 1<br>1 1 1 0 1<br>1 1 1 1 0<br>1<br>5</pre><p>The last two entries of 1 and 5 are source and destination nodes respectively. This graph will look like this</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/563/1*TYGfOEXeyEhgPX6wAJAzTA.png" /><figcaption>complete graph of five nodes</figcaption></figure><p>A sample solution to the problem :</p><pre>import java.io.BufferedReader;<br>import java.io.FileReader;<br>import java.io.IOException;<br>import java.util.ArrayList;<br>import java.util.Arrays;<br>import java.io.InputStreamReader;</pre><pre>class AllPathBetweenTwoNodes{<br>	 static int dim = 5; // dim is number of nodes in graph</pre><pre>//color is used to mark if the node is visited or not<br>    static boolean[] color = new boolean[dim + 1];<br>    <br>    //graph is given in 2-D matrix form<br>    static int[][] graph = new int[10][10];<br>    <br>    // this list will store nodes on the path from source to destination<br>    static ArrayList&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;();<br>    <br>    // this is the size of &quot;list&quot; declared above<br>    // size is used to remember index of the node in the list to be removed<br>    // when  the node is marked unvisited<br>    static int size;<br>    <br>	public static void main (String ... args) throws IOException{<br>	<br>		BufferedReader br = new BufferedReader (/*new FileReader(&quot;input.txt&quot;)*/new InputStreamReader ((System.in)));<br>        for (int I = 1; I &lt;= dim; I++) {<br>			<br>            String[] input = br.readLine().split(&quot; &quot;);<br>            int len = input.length;<br>            <br>            for (int J = 1; J &lt;= len; J++) {<br>                graph[I][J] = Integer.parseInt(input[J - 1]);<br>            }<br>        }<br>        <br>        Arrays.fill(color, false);// initially all are unvisited<br> <br>        int src = Integer.parseInt(br.readLine()); //Source node</pre><pre>//Destination node        <br>        int dst = Integer.parseInt(br.readLine());<br> <br>        dfs(src, dst);  // backtracking<br>	}<br>	<br>	 static void dfs(int src, int dst) {<br>		//node added to path<br>        list.add(src);<br>        size++;<br>        <br>        //node marked as visited<br>        color[src] = true;<br>        <br>        //when the destination node is found<br>        if (src == dst) {<br>			<br>			// Print the path<br>            for (Integer node : list) {<br>                System.out.print(node + &quot;  &quot;);<br>            }<br>            System.out.println();<br>            return;<br>        }<br>        <br>        <br>        for (int I = 1; I &lt;= dim; I++) {<br>        // if there&#39;s an edge between  src and node<br>            if (graph[src][I] == 1) {<br>				<br>	//and that node is not visited yet<br>                if (color[I] == false) {<br>					<br>	//start dfs from that node<br>                    dfs(I, dst);<br>                    <br>       //This line is critical to understand<br>       //it marks the node unvisited which we have just visited<br>       //so that the dfs could find another path to destination<br>                    color[I] = false;<br>                    <br>                    //size of list reduced by 1<br>                    //as the node is marked unvisited<br>                    //hence removed from the list<br>                    size--;<br>                    <br>                    //remove that node at index &quot;size&quot; from list<br>                    list.remove(size);<br>                }<br>            }<br>        }<br>    }<br>}</pre><p>This code print all the paths between node 1(source) and 5(destination). All the paths will be :</p><pre>1  2  3  4  5<br>1  2  3  5<br>1  2  4  3  5<br>1  2  4  5<br>1  2  5<br>1  3  2  4  5<br>1  3  2  5<br>1  3  4  2  5<br>1  3  4  5<br>1  3  5<br>1  4  2  3  5<br>1  4  2  5<br>1  4  3  2  5<br>1  4  3  5<br>1  4  5<br>1  5</pre><p>Comments in the code make it self-explanatory, still for any doubts please drop a comment. Thanks for reading. Have a nice day!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=89aee57544a4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Lazy propagation in Segment Tree]]></title>
            <link>https://medium.com/@bharatkulratan/lazy-propagation-in-segment-tree-977d3f4b0d3b?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/977d3f4b0d3b</guid>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Sun, 15 Oct 2017 16:48:30 GMT</pubDate>
            <atom:updated>2017-10-15T16:48:30.604Z</atom:updated>
            <content:encoded><![CDATA[<p>In the last last tutorial we learned how to build a Segment tree, query it and update point values to it. In this tutorial we will learn a useful technique <strong>Lazy Propagation</strong> for Segment trees. Using lazy propagation we can update a range in the tree efficiently. In this technique we update the value in a lazy manner, as the name suggests itself. Being lazy, values are not updated unless needed. Hence “lazy propagation” roughly translates to propagating values from root in a lazy manner.</p><p>Let’s make it clear with an example. Suppose we’ve built a Segment tree and there are two types of queries available on the tree. First one is update, which adds some value to nodes in a particular range. Second type is query for sum, which asks for sum of node values for a given range. In lazy propagation, “Lazy” refers to the idea that we will not update the range down to the leaf nodes every time it is called. Because the query for sum is called in the last, we will accumulate the values in an another array every time update() is called and these accumulated values will provide sum only for query which asks for sum in a range. Let’s take an example to make the concept clear.</p><p><strong>Question</strong><br>You are given an array of N elements, which are initially all 0. After that you will be given C commands. They are:<br>* 0 p q v — you have to add v to all numbers in the range of p to q (inclusive), where p and q are two indexes of the array.</p><p>* 1 p q — output a line containing a single integer which is the sum of all the array elements between p and q (inclusive)</p><p><strong>Input:</strong><br>In the first line you’ll be given T, number of test cases.</p><p>Each test case will start with N (N&lt;=100 000) and C (C&lt;=100 000). After that you’ll be given C commands in the format as mentioned above. 1 &lt;= p,q &lt;= N and 1 &lt;= v &lt;= 10⁷.</p><p><strong>Output:</strong><br>Print the answers of the queries.</p><p>Source of the question : <a href="http://www.spoj.com/problems/HORRIBLE/">SPOJ — HORRIBLE</a></p><pre>import java.io.BufferedReader;<br>import java.io.IOException;<br>import java.util.Arrays;<br>import java.io.InputStreamReader;<br>import java.util.StringTokenizer;<br>import java.io.FileInputStream;</pre><pre>class lazypropagation {<br> long tree[];  //the Segment tree <br> long helper[]; //this array accumulates value to be updated<br> //if true, values are pending for this node to be updated<br> boolean flag[];<br> <br> lazypropagation(){<br>  tree = new long [262145];<br>        helper = new long [262145];<br>        flag  = new boolean [262145];<br>        <br>        //initialize all node of tree and helper with zero<br>  Arrays.fill (tree, 0);<br>        Arrays.fill (helper, 0);<br>        <br>        //initially set all flags to false as their is no pending value for any node<br>        Arrays.fill (flag, false);<br> }<br> <br> <br> /**<br>  * <a href="http://twitter.com/param">@param</a> nodeToUpdate node in tree to be updated<br>  * <a href="http://twitter.com/param">@param</a> valueToUpdate value to be updated<br>  * <a href="http://twitter.com/param">@param</a> left is beginning index of array<br>  * <a href="http://twitter.com/param">@param</a> right is ending index of array<br>  * <a href="http://twitter.com/param">@param</a> start is beginning index of query<br>  * <a href="http://twitter.com/param">@param</a> end is ending index of query<br>  **/<br> private void update (int node, int value, int left, int right, int start, int end){<br>  /**<br>   *   Legends:<br>   *   S = Start, E = End, L = Left, R = Right<br>   *   dotted lines ---- represents array<br>   *   square brackets [ ] denote range of query<br>   * <br>   **/<br>  <br>  // When range to be updated does not intersect <br>  // with the array indices [left, right]<br>  // ...E]  L------R [S...<br>   if ( end &lt;left || start &gt; right )<br>            return ;<br>         <br>        // left == right means we&#39;ve reached to a single element of array. <br>        if (left == right ){<br>            tree[node]+= value;<br>            <br>            //flag is true mean some value is pending in helper[node]<br>            //so we should add this to tree[node] and clear helper[node]<br>            if (flag[node]==true){<br>                tree[node] += helper[node];<br>                helper[node]=0;<br>            }<br>            return;<br>        }<br>        <br>        int leftChild = 2*node;<br>        int rightChild = 2*node + 1;<br>        <br>        //Each of the below case finds a range by right-left+1 or end-left+1<br>        //this range should be multiplied by value and should be added to tree[node]<br>        <br>        //   [S   L------R E]<br>        if (start &lt;= left &amp;&amp; right &lt;= end){<br>            helper[leftChild] += value;<br>            helper[rightChild] += value;<br>            <br>            flag[leftChild] = flag[rightChild] = true;<br>            <br>            tree[node] += (value *(right - left +1));<br>            return ;<br>        }<br>        //  ---[S---R   E]<br>        else if (start &lt;= right &amp;&amp;  right &lt; end)<br>            tree[node ] += (value*(right - start +1));<br>        <br>        //  [S    L----E]----<br>        else if (start &lt; left &amp;&amp; left &lt;= end )<br>            tree[node] += (value*(end - left + 1));<br>            <br>        //  ----L----[S-----E]-----R-----<br>        else if (left &lt;= start &amp;&amp; end &lt;= right)<br>            tree[node] += (value*(end - start + 1));<br> <br>        update (leftChild, value, left, (left+right)/2, start, end );<br>        update (rightChild, value, ((left+right)/2)+1, right, start, end);<br> }<br> <br> private long sum_of_range (int node, int left, int right, int start, int end){<br>  // query does not overlaps with array range<br>  // ---R---- [S  E]----L-----<br>        if (right &lt; start || end &lt; left)<br>            return 0;<br>            <br>        int leftChild = 2*node;<br>  int rightChild = 2*node+1;<br>  <br>  // true means value updates are pending for the node<br>        if (flag[node] == true){<br>   <br>   //update value in tree node<br>   // right-left+1 gives the range for which <br>   //values to be updated in parent node which here is tree[node]<br>            tree[node] += (helper[node] *(right-left+1));<br>            <br>            //after values are updated, set flag to false<br>            flag[node]=false;<br>            <br>            // if it&#39;s not a leaf node<br>            if (left != right){<br>    <br>    //push the flag downward to children of node because<br>    //after recursive call these children will act as parent<br>    //and then tree[node] would be calculated<br>                flag [ leftChild ] = flag [ rightChild ] = true;<br>                 <br>                //push down the parent value to leftChild and rightChild<br>                //hence updated values for child nodes would be the sum of their own values + parent node value<br>                helper[ leftChild ] += helper[node];<br>                helper[ rightChild ] += helper[node];<br>            }<br>            <br>            //as value of helper[node] is already added to its children<br>            // set helper[node] = 0 to receive fresh values<br>            helper[node]=0;<br>        }<br>        <br>  // return value of tree[node] as query completely overlaps the array range<br>  // hence no need to go further on its children nodes.<br>  // [S---L---R---E]<br>        if (start &lt;= left &amp;&amp; right &lt;= end){<br>            return tree[node];<br>        }<br>        <br>        //sum returned for left half of tree intersecting with query<br>        long s1 = sum_of_range(leftChild, left, (left+right)/2, start, end);<br>        <br>        //sum returned for right half of tree intersecting with query<br>        long s2 = sum_of_range(rightChild, ((left+right)/2)+1, right, start, end);<br>        return s1+s2;<br>    }<br>    <br> public static void main (String [] args) throws IOException{<br>  // for reading input from console use new InputStreamReader (System.in)<br>        BufferedReader br = new BufferedReader (new InputStreamReader (new FileInputStream(&quot;input.txt&quot;)));<br>        StringTokenizer st =null;<br>        int t = Integer.parseInt(br.readLine());<br>        for(;t&gt;0;t--){<br>            st = new StringTokenizer (br.readLine());<br>            int N = Integer.parseInt(st.nextToken());<br>            int C = Integer.parseInt(st.nextToken());<br>            lazypropagation segtree = new lazypropagation();<br>            for (int I=1;I&lt;=C;I++){<br>                st = new StringTokenizer(br.readLine());<br>                if (st.nextToken().equals(&quot;0&quot;)){<br>                    int P = Integer.parseInt(st.nextToken());<br>                    int Q = Integer.parseInt(st.nextToken());<br>                    int V = Integer.parseInt(st.nextToken());<br>                    segtree.update (1, V, 1, N, P,Q);<br>                }<br>                else {<br>                    int P = Integer.parseInt(st.nextToken());<br>                    int Q = Integer.parseInt(st.nextToken());<br>                    long ans = segtree.sum_of_range (1,1,N, P,Q);<br>                    System.out.println(ans);<br>                }<br>            }<br>        }<br>    }<br>}</pre><p>In the above code, update() is responsible for both building the tree and updating the values in it. In update(), we took array indices left to 1 and right to N as N is the number of elements in array. There are four possible cases regarding intersection of array range and query range. All those cases are represented in the comments of update(). Basic idea of update() is to accumulate the value to be updated for those node which are the intersection of query range and array range in helper[node]. These values will be accumulated for each update() and will be processed when sum_of_range() is called. I’ve put a lot of comments in the code to make it self-explanatory. Still for any doubts please drop a comment. Thanks for reading. Have a nice day!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=977d3f4b0d3b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Introduction to Segment Tree]]></title>
            <link>https://medium.com/@bharatkulratan/introduction-to-segment-tree-dfcba8456f0c?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/dfcba8456f0c</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Sun, 15 Oct 2017 16:44:52 GMT</pubDate>
            <atom:updated>2017-10-15T16:44:52.117Z</atom:updated>
            <content:encoded><![CDATA[<p>Segment tree is a data structure <a href="https://en.wikipedia.org/wiki/Heap_(data_structure)">similar to hea</a>p. Every node of this tree has zero or two children. Nodes having zero child are called leaf nodes and represent the single element from the given array for which Segment tree would be built. Each node of the tree will hold information about a range from the given array. The closer the node to root, the more range it covers. Because it’s a tree, we can perform queries in <strong>O(log2N)</strong> where N is number of elements given. Here base of this logarithm is two as every node of this tree will have at most two child nodes. Left child will hold information for left half of the parent range and right child will hold info for remaining right half. For the interval [A, B] ([A,B] represents <a href="http://mathworld.wolfram.com/ClosedInterval.html">closed interval</a> for A and B) in the given array, the Segment tree would be defined in the following recursive manner:<br>* The root node will hold the information for the interval [A, B]<br> * For A &lt; B, the left child will hold the information for interval [A, (A+B)/2] and right child will hold the information for the interval [((A+B)/2)+1, B]</p><p>For example, Segment tree for an array having thirteen elements in an array [0, 12] would look like,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1005/1*_QaIBUylqItyIUoS1QGq0Q.png" /></figure><p>Let’s take an example. Suppose we are given an array of 13 integers and numerous queries to find out maximum value between a given range. To perform our queries in O(log2N) time we will build a Segment tree from this array. Each of its node will hold maximum value for a particular interval for which this node is responsible for as shown in the above figure. The tree is built in O(N) and let us do queries in O(log(N)). Here is the code for the above example. In this code the Segment tree is built for an array and queries maximum value for a range.</p><pre>import java.util.Random;<br>import java.util.Arrays;</pre><pre>class SegmentTree{<br> // arr is given array<br> // segTree is our Segment tree in form of array<br> public int arr [], segTree [];<br> <br> SegmentTree(int arrayLength){<br>  arr = new int [arrayLength];<br>  Random generator = new Random();<br>  <br>  for (int I=0; I&lt;arrayLength; I++){<br>   //putting random values in array<br>   arr[I] = generator.nextInt(100);<br>  }</pre><pre>//We will be building seg tree for array of length 13<br>  //for now let&#39;s take segTree length 32<br>  <br>  int segTreeLen = 32;<br>  segTree = new int [segTreeLen];<br>  Arrays.fill (segTree, 0);<br> }<br> <br> /**<br>  * <a href="http://twitter.com/param">@param</a> node is the root node of tree<br>  * <a href="http://twitter.com/param">@param</a> left is the beginning index of array<br>  * <a href="http://twitter.com/param">@param</a> right is the ending index of array<br>  **/<br> private void buildSegmentTree(int node, int left, int right){<br>  if (left == right){<br>   segTree [ node ] = arr[left];<br>  }<br>  else {<br>   //recursively approach left half of tree until a leaf is found<br>   buildSegmentTree (2 * node, left, (left+right)/2 );<br>   <br>   //recursively build the right half of tree<br>   buildSegmentTree (2 * node + 1, ((left+right)/2)+1, right);<br>   <br>   // value in left child of node<br>   int valueInLeftChild = segTree [2 * node];<br>   <br>   // value in right child of node<br>   int valueInRightChild = segTree [ 2 * node +1];<br>   <br>   <br>   // comapare both childs for greater value<br>   // and assign to node that value<br>   if ( valueInLeftChild  &gt;= valueInRightChild ){<br>    segTree [ node ] = valueInLeftChild;<br>   }<br>   else segTree [ node ] = valueInRightChild;<br>  }<br> }<br> <br> /**<br>  * <a href="http://twitter.com/param">@param</a> node is the root node of tree<br>  * <a href="http://twitter.com/param">@param</a> left is the beginning of the array index<br>  * <a href="http://twitter.com/param">@param</a> right is ending index of array<br>  * <a href="http://twitter.com/param">@param</a> start is the beginning index of the query<br>  * <a href="http://twitter.com/param">@param</a> end is ending index of query<br>  **/<br> private int query (int node, int left, int right, int start, int end){<br>  <br>  // if query range is out of array interval no valid value is returned<br>  if ( start &gt; right || end &lt; left){<br>   return -1;<br>  }<br>  <br>  /**<br>   * if query range includes the array interval<br>   * return the value of node in the tree<br>   * which holds the maximum value for the range<br>   * Segment tree saves our computation in this manner<br>   * because segTree[treeNode] already holds maximum value for this range<br>   **/ <br>  if ( start &lt;= left &amp;&amp;  end &gt;= right){<br>   return segTree [node];<br>  }<br>  <br>  int half = (left+right)/2;<br>  <br>  //Computing maximum value in left half of the tree<br>  int leftMax = query (2*node, left, half, start, end);<br>  <br>  //Computing maximum value in right half of the tree<br>  int rightMax = query (2*node+1, half+1, right, start, end);<br>  <br>  int leftCorner, rightCorner;<br>  leftCorner =(start&lt;left)?left:start;<br>  rightCorner = (right&lt;end)?right:end;<br>  <br>  /**<br>   * Below if-else statements updates the node value<br>   * according to the maxium value from its child node<br>   **/<br>  if (leftMax == -1){<br>   System.out.println (&quot;max value is &quot; + rightMax + &quot; between index &quot; + leftCorner  + &quot; and &quot; + rightCorner);<br>   return segTree[node] = rightMax;<br>  }<br>  if (rightMax == -1){<br>   System.out.println (&quot;max value is &quot; + leftMax + &quot; between index &quot; + leftCorner + &quot;  &quot; + rightCorner);<br>   return segTree[node] = leftMax;<br>  }<br>  if (leftMax &gt; rightMax){<br>   System.out.println (&quot;max value is &quot; + leftMax + &quot; between index &quot; + leftCorner + &quot;  &quot; + rightCorner);<br>   return segTree[node] = leftMax;<br>  }<br>  else {<br>   System.out.println (&quot;max value is &quot; + rightMax + &quot; between index &quot; + leftCorner + &quot;  &quot; + rightCorner);<br>   return segTree[node] = rightMax;<br>  }<br> }<br>  <br> <br> public static void main (String ... args){<br>  //Build the Segment tree for an array having 13 elements<br>  SegmentTree tree = new SegmentTree (13);<br>  <br>  //Print the given array<br>  System.out.println (Arrays.toString(tree.arr));<br>  <br>  // 0 is the left index from array and 12 is the right index<br>  // 1 is choosen as root node because we need to calculate left and right child<br>  // by using formula 2*node and 2*node+1 which won&#39;t work for 0 <br>  tree.buildSegmentTree(1, 0, 12);<br>  <br>  // Uncomment below line to print the Segment tree<br>  //System.out.println (Arrays.toString(tree.segTree));<br>  <br>  // We are finding maximum value between index 3 and 11 of given array for now<br>  System.out.println (&quot;Max value between index 3 and 11 is &quot; + tree.query (1, 0, 12, 3, 11));<br> }<br>}</pre><p>For this example we are asking for maximum value between range [3,11]. In the figure below, path is show in the red which includes the starting and ending index 3 and 11 respectively. Query starts from the root node. As it continues down, those nodes will not be queried down further which are completely in the queried range.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/975/1*FKuyxkzyAqsQpiYPtEq3XA.png" /></figure><p>We’ve build a static Segment tree. Static means once the tree is built it does not change. We perform queries which are read-only, they don’t modify the tree. Let’s take another operation of updating an element in array as well as in the tree. Again this point update operation would be performed in O(log(N)). And it’s code is almost similar to <em>buildSegmentTree()</em>. Here’s the code for updating point values:</p><pre>private void update (int nodeToUpdate, int valueToUpdate){<br>  update (nodeToUpdate, valueToUpdate, 1, 0, 12);<br> }<br>  <br> /**<br>  * <a href="http://twitter.com/param">@param</a> nodeToUpdate is the node to be updated in array and tree<br>  * <a href="http://twitter.com/param">@param</a> valueToUpdate is the value to be updated at the nodeToUpdate<br>  * <a href="http://twitter.com/param">@param</a> node root node of tree<br>  * <a href="http://twitter.com/param">@param</a> left is the beginning index of array<br>  * <a href="http://twitter.com/param">@param</a> right is the ending index of array<br>  **/<br> private void update(int nodeToUpdate, int valueToUpdate, int node, int left, int right){<br>  if (left == right){<br>   segTree [ node ] = arr[left];<br>   // only the below if condition is different from buildSegmentTree()<br>   // which does the job of point update.<br>   if ( left == nodeToUpdate){<br>    segTree[node] = arr[left] = valueToUpdate;<br>   }<br>  }<br>  else {<br>   update (nodeToUpdate, valueToUpdate, 2 * node, left, (left+right)/2 );<br>   update (nodeToUpdate, valueToUpdate, 2 * node + 1, ((left+right)/2)+1, right);<br>   <br>   <br>   int valueInLeftChild = segTree [2 * node];<br>   int valueInRightChild = segTree [ 2 * node +1];<br>   <br>   if ( valueInLeftChild  &gt;= valueInRightChild ){<br>    segTree [ node ] = valueInLeftChild;<br>   }<br>   else segTree [ node ] = valueInRightChild;<br>  }<br> }</pre><p>We need to call this function from main() as</p><pre>tree.update (nodeToUpdate, valueToUpdate);<br>// e.g. tree.update (4, 99);</pre><p>In this article we learned how to build a Segment tree, performing queries over it and do point updates. In case of any doubts regarding this tutorial, please drop a comment. In the next part of this series we will learn about updating the tree using <strong>lazy propagation</strong> which is a very useful technique and saves a lot of calculation. So stay tuned. Have a nice day!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dfcba8456f0c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Bit Shift Operators in Java]]></title>
            <link>https://medium.com/@bharatkulratan/bit-shift-operators-in-java-3e993b309f3a?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/3e993b309f3a</guid>
            <category><![CDATA[java]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Tue, 19 Sep 2017 13:34:57 GMT</pubDate>
            <atom:updated>2017-09-19T13:34:57.215Z</atom:updated>
            <content:encoded><![CDATA[<p>Java provide us some operators which shifts the bit pattern of the integral type data. There are three such operators, <strong>signed right shift(&gt;&gt;), signed left shift(&lt;&lt;), and unsigned right shift(&gt;&gt;&gt;) operator</strong>. Difference between signed and unsigned is that signed operator depends on the sign of the data type. Let’s take an int data type which by default is a 32-bit signed <a href="https://en.wikipedia.org/wiki/Two%27s_complement"><strong>two’s complement</strong></a> integer, which has a minimum value of -2³¹ and a maximum value of 2³¹–1. The left most bit in the int represents the sign of it, 1 for negative, and 0 for positive.<br> The signed right shift operator (&gt;&gt;) will shift the bit pattern to the right and the resulting gap produced by this shifting would be filled with the sign value of int, i.e. if left most bit is 1(int has negative value), there would be 1’s in the gap and similarly if the left most bit is 0(int has positive value), the gap would be filled by 0’s. In case of signed left shift (&lt;&lt;), there would be no gap in the left and gap created in the right side would be filled with zeros. Also keep in mind that in left shift, shifting could re-write the sign bit of an int so it’s possible to apply left shift on negative int (1 in left most bit) and making it positive (0 in left most bit) and vice versa. In case of unsigned right shift operator, the gap produced in left because of shifting the bits to right will always be filled with zeros. Let’s see an example code which would make it more clear.</p><pre>class ShiftOperatorDemo{<br>	public static void main (String ... args){<br>		<br>		int I = 255;		<br>		//0000 0000 0000 0000 0000 0000 1111 1111<br>		<br>		int J = -256;<br>		//1111 1111 1111 1111 1111 1111 0000 0000<br>		<br>		/**<br>		 *  signed right shift operatore demo<br>		 **/<br>		<br>		I = I &gt;&gt; 4;		<br>		//Resulting value after shifting to 4 places right<br>		//0000 0000 0000 0000 0000 0000 0000 1111<br>		System.out.println (&quot;After signed right shift to 4 places, I is &quot; + I);<br>		<br>		J = J &gt;&gt; 4;<br>		//Resulting value after shifting to 4 places right<br>		//1111 1111 1111 1111 1111 1111 1111 0000<br>		System.out.println (&quot;After signed right shift to 4 places, J is &quot; + J);<br>		<br>		<br>		<br>		/**<br>		 * signed left shift operator demo<br>		 **/<br>		 <br>		I = I &lt;&lt; 8;<br>		//Resulting value after shifting to 8 places left<br>		//0000 0000 0000 0000 0000 1111 0000 0000<br>		System.out.println (&quot;After signed left shift to 8 places, I is &quot; + I);<br>		<br>		<br>		J = J &lt;&lt; 8;<br>		//Resulting value after shifting to 8 places left<br>		//1111 1111 1111 1111 1111 0000 0000 0000<br>		System.out.println (&quot;After signed left shift to 8 places, J is &quot; + J);<br>		<br>		/**<br>		 * Unsigned right shift operator demo<br>		 **/<br>		 I = I &gt;&gt;&gt; 4;<br>		 //0000 0000 0000 0000 0000 0000 1111 0000<br>		 System.out.println (&quot;After unsigned right shift to 4 places, I is &quot; + I);<br>		 <br>		 J = J &gt;&gt;&gt; 4;<br>		 //0000 1111 1111 1111 1111 1111 0000 0000<br>		 System.out.println (&quot;After unsigned right shift to 4 places, J is &quot; + J);<br>	}<br>}</pre><p>Also note that shifting right to x positions is equal to dividing by 2x and shifting to left by x positions is equivalent of multiplication by 2x. If the value of x exceeds 32 which is the number of bits in an int, the modulo operator will be used. This modulo operator will provide us the remainder when x is divided by 32. For example if you shift an int to 64 places its value will remain the same as 64%32 == 0 (% is <a href="https://en.wikipedia.org/wiki/Modulo_operation">modulo operator</a> in Java). These bit shifting makes code faster but also a little hard to read and understand but that shouldn’t stop us from learning this useful feature Java provides.</p><p>In case of any doubts please drop a comment. Stay tuned for more articles. Thanks for reading. Have a nice day!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3e993b309f3a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Coin Change problem]]></title>
            <link>https://medium.com/@bharatkulratan/coin-change-problem-57ea55fade76?source=rss-2f7a73dcfa05------2</link>
            <guid isPermaLink="false">https://medium.com/p/57ea55fade76</guid>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Bharat Kul Ratan]]></dc:creator>
            <pubDate>Mon, 18 Sep 2017 16:50:27 GMT</pubDate>
            <atom:updated>2017-09-18T16:50:27.789Z</atom:updated>
            <content:encoded><![CDATA[<p>In this tutorial we will learn about the <a href="http://www.algorithmist.com/index.php/Coin_Change"><strong>Coin change problem</strong></a>. The problem asks for number of ways of making changes for a particular amount of a sum, using a given set of coins with different denominations. We are given unlimited supply of coins of each denomination and order of coins does not matter. Please keep in mind, this problem asks for <strong>all the ways to produce this sum </strong>. It does not ask for minimum number of coins to do so. For e.g. we are given coins of denomination 1, 2, and 3. The asked sum is 5, then there are five possible solutions to this problem, viz. {1, 1, 1, 1, 1}, {1, 1, 1, 2}, {1, 2, 2}, {1, 1, 3}, {2, 3}.<br> This problem could be rephrased in a lot of ways. For e.g. if you have to cover 100 units and you are allowed to move only 1 unit, 2 units, and 5 units at a time then the problem asks, how many ways are possible to cover that 100 units. But let’s continue with our coin change problem to solve it.<br> <br>The key idea to solve this problem is to consider that <strong>either a coin will be present in the solution or not</strong>.</p><pre>S(sum, list[1...m]) = S(sum, list[1...m-1]) + S(sum - list[m], list[1...m])</pre><pre>S           : solution<br>sum         : the sum to be produced by using given coins<br>list[1...m] : list of m coins given.<br>list[m]     : denomination of m-th coin</pre><p>This equation is the core of solution. This equation tells us why the <strong>recursion</strong> and table approach works. Suppose S is the solution to problem where <em>sum</em> is required sum and we are given a list of coins. Now if a coin is excluded from S, then it becomes the sub problem of finding the sum with one less coin which is represented as <strong>S(sum, list[1…m-1])</strong>. If the coin is included, it becomes sub problem of finding the (sum — denomination of coin) with the given list of coins. This is represented as <strong>S(sum — list[m], list[1…m])</strong>. This recursive approach can be visualized as shown in the below figure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/630/1*A3jpMtpolzw1w10mKhZjxA.png" /></figure><p>In the above figure 5(1,2,3) represent 5 as the sum and list of coins as 1,2,3. This notation is valid for all the nodes. In this figure 5(1,2,3) leads to 5(1,2) and 2(1,2,3) as coin with denomination 3 was selected for including and excluding. You can choose any coin from the list of coins you have, to include and exclude. Your <strong>recursion tree</strong> might look different depending on your coin selection but it will provide the correct solution. Let’s look at the code for more understanding.</p><pre>class CoinChange{<br>	int list[];<br>	int value;<br>	<br>	CoinChange(){<br>		list = new int [4];<br>		<br>		//We&#39;re given 3 denominations of value 1, 2, and 3<br>		list[1] = 1;<br>		list[2] = 2;<br>		list[3] = 3;<br>	}<br>	<br>	int recursionCount (int sum, int denom){<br>		// Zero sum is possible with only one way<br>		// which is not to include any coins at all<br>		if (sum == 0){<br>			return 1;<br>		}<br>		<br>		/**<br>		 * These two conditions return zero ways<br>		 * 1.  when sum is negative<br>		 * 2.  denominations have values less than 1<br>		 **/<br>		if ( sum &lt; 0 || ( denom &lt;=0 &amp;&amp; sum &gt;= 1) ){<br>			return 0;<br>		}<br>		<br>		/**<br>		 * This part represent when the coin is excluded<br>		 * In this case,list[] becomes shorter by length 1<br>		 * as the a less coin is participating in producing the sum<br>		 **/<br>		int coinIncluded = recursionCount (sum, denom-1);<br>		<br>		<br>		/**<br>		 * This part represents when the coin is included<br>		 * In this case, list[] remains the same as <br>		 * all the coins are participating but in producing<br>		 * sum - denomination of the coin.<br>		 * <br>		 * Note that this is the subproblem. If we could find number of ways<br>		 * to produce sum - denomination by using all the coins, we could<br>		 * also produce sum by using the same coins as we could add that<br>		 * denomination later which will give the original sum asked.<br>		 **/<br>		int coinExcluded = recursionCount (sum - list[denom], denom);<br>		<br>		return coinIncluded + coinExcluded;<br>	}</pre><pre>int dpApproach (int sum, int coins){<br>		// row stands for denominations<br>		// columns are for required sum<br>		int table[][] = new int[coins+1][sum+1];<br>		<br>		//if sum is zero, there is only one way<br>		//which is not to include any coin<br>		for (int I=0; I&lt;=coins; I++){<br>			table[I][0] = 1;<br>		}<br>		<br>		//if denomination is of zero value<br>		//there&#39;s no way to produce a sum<br>		for (int I=1; I&lt;=sum; I++){<br>			table[0][I] = 0;<br>		}<br>		<br>		int included, excluded;<br>		<br>		//iterate over all given coins<br>		for (int I=1; I&lt;=coins; I++){<br>			<br>			//fill the table with values from zero to sum<br>			for (int J=0; J&lt;= sum; J++){<br>				<br>				// if the coin is included<br>				// table[I][J-list[I]] is answer of subproblem <br>				included = (J - list[I] &gt;= 0)? table[I][J - list[I]] : 0;<br>				<br>				// if the coin is excluded<br>				// table[I-1][J] is answer of subproblem<br>				excluded = (I &gt;= 1) ? table[I-1][J] : 0;<br>				<br>				// these subproblems provide us the value of this cell in table<br>				table[I][J] = included + excluded;<br>			}<br>		}<br>	<br>		/*<br>		for (int I=0;I&lt;=coins;I++){<br>			for(int J=0;J&lt;=sum;J++){<br>				System.out.print (table[I][J] + &quot;  &quot;);<br>			}<br>			System.out.println();<br>		}<br>		*/<br>		return table [coins][sum];<br>	}<br>		<br>	public static void main (String ... args ){<br>		CoinChange object = new CoinChange();<br>		<br>		System.out.println (&quot;Recursive approach &quot; + object.recursionCount (5, 3));<br>		System.out.println (&quot;DP approach &quot; + object.dpApproach(5, 3));<br>	}<br>}</pre><p>This code first uses recursive approach to solve the problem. In recursive approach the sub problems are easy to see but some computations are done over and over again which could be avoided using <strong>memoization</strong>. Second approach uses the table to store the results, hence this <strong>dynamic programming</strong> approach is faster and better than recursive counterpart. In this table, columns are the sum values starting from 1 to <em>sum</em>. Rows are for the coins given. All cells in the table for a particular row and column provides a solution for some sub-problem. Our solution resides in cell which is in the rightmost column and in the bottom row of table.</p><p>For any further doubts please drop a comment. Thanks for reading. Have a nice day!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=57ea55fade76" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>