<?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 Manish Sakariya on Medium]]></title>
        <description><![CDATA[Stories by Manish Sakariya on Medium]]></description>
        <link>https://medium.com/@manishsakariya?source=rss-8f771988cbb2------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*zyQ3fq1vV6ccjUNQ</url>
            <title>Stories by Manish Sakariya on Medium</title>
            <link>https://medium.com/@manishsakariya?source=rss-8f771988cbb2------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 12:36:55 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@manishsakariya/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[Low Level Design Logger with Java]]></title>
            <link>https://medium.com/@manishsakariya/low-level-design-logger-with-java-9c7d522c29d1?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c7d522c29d1</guid>
            <category><![CDATA[low-level-design]]></category>
            <category><![CDATA[lld]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Fri, 11 Aug 2023 11:05:16 GMT</pubDate>
            <atom:updated>2024-02-12T19:42:31.268Z</atom:updated>
            <content:encoded><![CDATA[<p>If you’re preparing for LLD design interview then this is one of the must question you should practise. So let’s get started.</p><p>First of all we should create interfaces and required constants.</p><h3>1) Log levels can be INFO,WARNING,ERROR</h3><pre>enum LogLevel {<br>    TRACE(1),<br>    DEBUG(2),<br>    INFO(3),<br>    WARNING(4),<br>    ERROR(5);<br><br><br>    final int level;<br><br>    LogLevel(int level) {<br>        this.level = level;<br>    }<br>}</pre><h3>2) Interface and classes for Log Sink</h3><p>log sink is the media to which you want to publish log.<br>You can have 2 basic types of log synk<br>1) Console log synk [which prints the logs on the console]<br>2) File log synk [which stores the logs inside the file]</p><pre>// LogSink interface<br>interface LogSink {<br>    void log(String message);<br>}<br><br>// ConsoleLogSink implementation<br>class ConsoleLogSink implements LogSink {<br>    @Override<br>    public void log(String message) {<br>        System.out.println(message);<br>    }<br>}<br><br>// FileLogSink implementation<br>class FileSink implements LogSink {<br>    private String filename;<br>    public FileSink(String filename) {<br>        this.filename = filename;<br>    }<br>    @Override<br>    public void log(String message) {<br>        try (PrintWriter writer = new PrintWriter(new FileWriter(filename,true))) {<br>            writer.println(message);<br>        } catch (IOException e) {<br>            e.printStackTrace();<br>        }<br>    }<br>}</pre><h3>3) Logger implementation.</h3><p><em>Here we willl use Singleton design pattern so whole application have single instance of logger.Also it is thread safe</em></p><pre>// Logger class<br>class Logger {<br>    private static Logger instance;<br>    private LogLevel logLevel;<br>    private LogSink logSink;<br><br>    private Logger() {<br>        logLevel = LogLevel.INFO; // Default log level<br>        logSink = new ConsoleLogSink(); // Default log sink<br>    }<br><br>    public static Logger getInstance() {<br>        if (instance == null) {<br>            instance = new Logger();<br>        }<br>        return instance;<br>    }<br><br>    public void setLogLevel(LogLevel level) {<br>        logLevel = level;<br>    }<br><br>    public void setLogSink(LogSink sink) {<br>        logSink = sink;<br>    }<br><br>    public void log(LogLevel level, String message) {<br>        if (logLevel.ordinal() &lt;= level.ordinal()) {<br>            String logMessage = &quot;[&quot; + new Date() + &quot;] [&quot; + level + &quot;] &quot; + message;<br>            logSink.log(logMessage);<br>        }<br>    }<br>}</pre><p>we are handling if we should print log or not based on below logic<br>level.ordinal() &gt;= logLevel.ordinal()</p><p>Ordinal is the Enum level method which gives the rank of Enum instance.</p><p>so let’s say if my global log level is INFO(0) then i should allow INFO(0),WARNING(1),ERROR(2)</p><h4>4) Let’s create the client code.</h4><pre>public class Solution {<br>    public static void main(String[] args) {<br>        Logger logger = Logger.getInstance();<br><br>        // Using ConsoleLogSink<br>        logger.setLogSink(new ConsoleLogSink());<br><br>        logger.setLogLevel(LogLevel.INFO);<br><br>        logger.log(LogLevel.INFO, &quot;This is an info message&quot;);<br>        logger.log(LogLevel.WARNING, &quot;This is a warning message&quot;);<br>        logger.log(LogLevel.ERROR, &quot;This is an error message&quot;);<br><br>        // Using FileLogSink<br>        logger.setLogSink(new FileLogSink(&quot;log.txt&quot;));<br><br>        logger.log(LogLevel.INFO, &quot;Logging to a file&quot;);<br>    }<br>}</pre><h4>5) We can use factory design pattern to create a particular type of Logger.</h4><pre>interface LoggerFactory {<br>    Logger createLogger();<br>}<br>class ConsoleLoggerFactory implements LoggerFactory {<br>    @Override<br>    public Logger createLogger() {<br>        Logger instance = Logger.getInstance(LogLevel.INFO,new ConsoleSink());<br> // below 2 lines needed as Logger is singleton and at the time of creation<br> // it could have FileSynk and it will return that only<br>        instance.setLogLevel(LogLevel.INFO);<br>        instance.setLogSink(new ConsoleSink());<br>        return instance;<br>    }<br>}<br>class FileLoggerFactory implements LoggerFactory {<br>    private String filename;<br>    public FileLoggerFactory(String filename) {<br>        this.filename = filename;<br>    }<br>    @Override<br>    public Logger createLogger() {<br>        Logger instance = Logger.getInstance(LogLevel.WARNING, new FileSink(filename));<br>        instance.setLogLevel(LogLevel.INFO);<br>        instance.setLogSink(new FileSink(filename));<br>        return instance;<br>    }<br>}<br><br>public static void main(String[] args) {<br>        LoggerFactory consoleLoggerFactory = new ConsoleLoggerFactory();<br>        LoggerFactory fileLoggerFactory = new FileLoggerFactory(&quot;log.txt&quot;);<br><br>        Logger consoleLogger = consoleLoggerFactory.createLogger();<br>        consoleLogger.log(LogLevel.INFO, &quot;This is an info message&quot;);<br><br>        Logger fileLogger = fileLoggerFactory.createLogger();<br>        fileLogger.log(LogLevel.WARNING, &quot;This is a warning message&quot;);<br>    }</pre><h4>6) Generally while using Log4j type of library you could have used below statement<br>log.info(), log.error(), log.debug()</h4><p>we can easily modify our logger to do this.</p><pre>class Logger {<br>    private LogLevel logLevel;<br>    private LogSink logSink;<br>    private static Logger instance;<br>    private Logger(LogLevel logLevel, LogSink logSink) {<br>        this.logLevel = logLevel;<br>        this.logSink = logSink;<br>    }<br>    public static Logger getInstance(LogLevel logLevel, LogSink logSink) {<br>        if (instance == null) {<br>            instance = new Logger(logLevel, logSink);<br>        }<br>        return instance;<br>    }<br><br>    public void info(String message) {<br>        log(LogLevel.INFO, message);<br>    }<br>    public void error(String message) {<br>        log(LogLevel.ERROR, message);<br>    }<br>    public void debug(String message) {<br>        log(LogLevel.WARNING, message);<br>    }<br><br>    public void setLogSink(LogSink logSink) {<br>        this.logSink = logSink;<br>    }<br>    public void setLogLevel(LogLevel logLevel) {<br>        this.logLevel = logLevel;<br>    }<br>    public void log(LogLevel level, String message) {<br>        if (level.ordinal() &gt;= logLevel.ordinal()) {<br>            String logMessage = &quot;[&quot; + level + &quot;] &quot; + message;<br>            logSink.log(logMessage);<br>        }<br>    }<br>}<br><br>    public static void main(String[] args) {<br>// factory class is in this blog only<br>        LoggerFactory consoleLoggerFactory = new ConsoleLoggerFactory();<br><br>        Logger consoleLogger = consoleLoggerFactory.createLogger();<br>        consoleLogger.log(LogLevel.INFO, &quot;This is an info message&quot;);<br>        consoleLogger.info(&quot;this is simple way&quot;);<br>    }</pre><p>7) Can do this with chain of responsibility principles. Log sink is good design practice and should be added in chain of responsibility kind of implementation also.</p><pre>public interface LogSink {<br>    void log(String message);<br>}<br>import java.io.IOException;<br>import java.io.PrintWriter;<br><br>class FileSink implements LogSink {<br>    private String filename;<br><br>    public FileSink(String filename) {<br>        this.filename = filename;<br>    }<br><br>    @Override<br>    public void log(String message) {<br>        try (PrintWriter writer = new PrintWriter(filename)) {<br>            writer.println(&quot;FILE: &quot; + message);<br>        } catch (IOException e) {<br>            e.printStackTrace();<br>        }<br>    }<br>}<br><br>class ConsoleSink implements LogSink {<br>    @Override<br>    public void log(String message) {<br>        System.out.println(&quot;CONSOLE: &quot; + message);<br>    }<br>}<br><br>public abstract class LogProcessor {<br><br>    public static int INFO = 1;<br>    public static int DEBUG = 2;<br>    public static int ERROR = 3;<br><br>    LogProcessor nextLoggerProcessor;<br>    LogSink logSink;<br><br>    LogProcessor(LogProcessor nextLoggerProcessor, LogSink logSink) {<br>        this.nextLoggerProcessor = nextLoggerProcessor;<br>        this.logSink = logSink;<br>    }<br><br>    public void log(int logLevel, String message) {<br><br>        if (nextLoggerProcessor != null) {<br>            nextLoggerProcessor.log(logLevel, message);<br>        }<br>    }<br>}<br><br>public class InfoLogProcessor extends LogProcessor{<br><br>    InfoLogProcessor(LogProcessor nexLogProcessor,LogSink logSink){<br>        super(nexLogProcessor,logSink);<br>    }<br><br>    public void log(int logLevel,String message){<br><br>        if(logLevel == INFO) {<br>            logSink.log(&quot;[&quot; + new Date() + &quot;][INFO]&quot;+message);<br>        } else{<br><br>            super.log(logLevel, message);<br>        }<br><br>    }<br>}<br><br>public class ErrorLogProcessor extends LogProcessor{<br><br>    ErrorLogProcessor(LogProcessor nexLogProcessor,LogSink logSink){<br>        super(nexLogProcessor,logSink);<br>    }<br><br>    public void log(int logLevel,String message){<br><br>        if(logLevel == ERROR) {<br>            logSink.log(&quot;[&quot; + new Date() + &quot;][ERROR]&quot;+message);<br>        } else{<br><br>            super.log(logLevel, message);<br>        }<br><br>    }<br>}<br><br>public class DebugLogProcessor extends LogProcessor{<br><br>    DebugLogProcessor(LogProcessor nexLogProcessor,LogSink logSink){<br>        super(nexLogProcessor,logSink);<br>    }<br><br>    public void log(int logLevel,String message){<br><br>        if(logLevel == DEBUG) {<br>            logSink.log(&quot;[&quot; + new Date() + &quot;][DEBUG]&quot;+message);<br>        } else{<br><br>            super.log(logLevel, message);<br>        }<br><br>    }<br>}<br><br>public class Main {<br><br>    public static void main(String args[]) {<br><br>        LogSink fileSink = new FileSink(&quot;abc.txt&quot;);<br>        ErrorLogProcessor nexErrorLogProcessor = new ErrorLogProcessor(null, fileSink);<br>        DebugLogProcessor debugLogProcessor = new DebugLogProcessor(nexErrorLogProcessor, fileSink);<br><br>        LogProcessor logObject = new InfoLogProcessor(debugLogProcessor,fileSink);<br><br>        logObject.log(LogProcessor.ERROR, &quot;exception happens&quot;);<br>        logObject.log(LogProcessor.DEBUG, &quot;need to debug this &quot;);<br>        logObject.log(LogProcessor.INFO, &quot;just for info &quot;);<br><br>    }<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c7d522c29d1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Java deadlock example]]></title>
            <link>https://medium.com/@manishsakariya/java-deadlock-example-d1178c932c68?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/d1178c932c68</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[multithrading]]></category>
            <category><![CDATA[parellel]]></category>
            <category><![CDATA[performance]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Thu, 27 Jul 2023 12:41:19 GMT</pubDate>
            <atom:updated>2023-07-27T12:41:19.059Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="DeadLock image" src="https://cdn-images-1.medium.com/max/189/1*B7o8VPC_UNrATjGomRY6Fw.png" /><figcaption>deadlock java</figcaption></figure><p>Deadlock in java is a programming situation where two or more threads are blocked forever. Java deadlock situation arises with at least two threads and two or more resources. Here I have written a simple program that will cause java deadlock scenario and then we will see how to analyze it.</p><pre>package J_DeadLock;<br><br>class A {<br><br>    public synchronized  void d1(B b) throws InterruptedException {<br>        System.out.println(&quot;Thread 1 has aquired lock on A object&quot;);<br>        Thread.sleep(500);<br>        System.out.println(&quot;Thread 1 waiting for  lock on B object&quot;);<br>        b.last();<br>    }<br><br>    public synchronized void last(){<br>        System.out.println(&quot;a last&quot;);<br><br>    }<br>}<br><br>class B {<br><br>    public synchronized  void d1(A a) throws InterruptedException {<br>        System.out.println(&quot;Thread 2 has aquired lock on B object&quot;);<br>        Thread.sleep(500);<br>        System.out.println(&quot;Thread 2 waiting  lock on A object&quot;);<br>        a.last();<br>    }<br><br>    public synchronized void last(){<br>        System.out.println(&quot;b last&quot;);<br><br>    }<br><br>}<br>public class Solution {<br><br><br>    public static void main(String[] args) {<br>        A a = new  A();<br>        B b = new B();<br><br>        Thread t1 = new Thread(()-&gt;{<br>            try {<br>                a.d1(b);<br>            } catch (InterruptedException e) {<br>                throw new RuntimeException(e);<br>            }<br>        });<br>        Thread t2 = new Thread(()-&gt;{<br>            try {<br>                b.d1(a);<br>            } catch (InterruptedException e) {<br>                throw new RuntimeException(e);<br>            }<br>        });<br><br>        t1.start();<br>        t2.start();<br>    }<br>}</pre><p>Here Thread 1 acquires lock on Object ‘a’ of class A when it runs d1 synchronized method.</p><p>Thread 1 now needs lock on ‘b’ Object to finish the task.</p><p>Thread 2acquires lock on Object ‘b’ of class B when it runs d1 synchronized method.</p><p>Thread 1 now needs lock on ‘a’ Object to finish the task.</p><p>Thread1 is waiting for a resouce which is already occupied By Thread2.</p><p>Thread2 is waiting for a resouce which is already occupied By Thread1.</p><p>This never ending wait for resource is called deadlock.</p><p>Thanks for reading. Happy coding.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d1178c932c68" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Composition Chart- When Relative and absolute Differences matters]]></title>
            <link>https://medium.com/@manishsakariya/composition-chart-when-relative-and-absolute-differences-matters-9c396dec1260?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c396dec1260</guid>
            <category><![CDATA[stacked-column-chart]]></category>
            <category><![CDATA[charts]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[chart-suggestions]]></category>
            <category><![CDATA[choosing-a-good-chart]]></category>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Thu, 16 May 2019 15:36:07 GMT</pubDate>
            <atom:updated>2019-05-16T18:55:10.603Z</atom:updated>
            <content:encoded><![CDATA[<blockquote><strong>Stacked Column Chart</strong> — absolute and relative differences matters</blockquote><p>Let’s look at data below. we want to visualize the sell of each game over period of time. we want to visualize two things here.</p><ol><li>how our individual game if performing compare to other game at particular month(relative difference)</li><li>how our game is performing over a period of time. is sell increasing from one month to other month.? (absolute difference)</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_QgG_KQBMvP56s-THi4HIg.png" /></figure><p>we can use excel stack column chart to visualize this. chart would look something like this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/854/1*6J2Zq37dml-ijp2r5ooFdQ.png" /></figure><p>from graph we can say that sell of chess is more in February than January.</p><blockquote><strong>100% Stacked Column Chart<em> </em></strong>— only relative differences matters</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WU5b_xazQtxd1JQHtuKfCw.png" /></figure><p>if we want to know sell of chess in the month of January with respect to total game sold. chess was around 20% of total game sold in month of January.</p><p>we can also check % change in game sold over period of time with this chart.</p><p>let’s see how we can plot this stacked column chart using python matplotlib and pandas. download the file to create the chart. or you can generate your own csv.</p><p><a href="https://drive.google.com/file/d/1ts6SW8ZF1pmJhIi5XT5vnPsV4SHPUxJG/view?usp=sharing">Game_data.csv</a></p><blockquote><strong><em>Python code to generate Column Stack chart</em></strong></blockquote><p>________________________________________________________________</p><pre><strong><em>import pandas as pd<br>import matplotlib.pyplot as plt<br>pd.__version__<br>data=pd.read_csv(“enter data file location”)</em></strong></pre><pre><strong><em>chess=data.iloc[0][1:]<br>monopoly=data.iloc[1][1:]<br>snooker = data.iloc[2][1:]<br>domino = data.iloc[3][1:]<br>poker_dice = data.iloc[4][1:]<br>Call_of_Duty = data.iloc[5][1:]<br>indexes = data.columns[1:]</em></strong></pre><pre><strong><em>figure=plt.figure()<br>plt.bar(x=indexes, height=chess,width=0.35)<br>plt.bar(x=indexes, height=monopoly, width=0.35, bottom=chess)<br>plt.bar(x=indexes, height=snooker, width=0.35, bottom=chess+monopoly)<br>plt.bar(x=indexes, height=domino, width=0.35, bottom=chess+monopoly+snooker)<br>plt.bar(x=indexes, height=poker_dice, width=0.35, bottom=chess+monopoly+snooker+domino)<br>plt.bar(x=indexes, height=Call_of_Duty, width=0.35, bottom=chess+monopoly+snooker+domino+poker_dice)</em></strong></pre><pre><strong><em>print(data)</em></strong></pre><pre><strong><em>plt.show()</em></strong></pre><p>__________________________________________________________________</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/975/1*aCVI8vQdOVhUP8dU3AUPeQ.png" /></figure><blockquote><strong><em>Python code to generate 100% Column Stack chart</em></strong></blockquote><pre>chess sell data<br>Month             sale    total_sell               %chess<br>January            49        376        49/376*100= 13%<br>February           70        456                    15%<br>March              92        455                    20%<br>April              50        387                    12%<br>May                36        377                    9%<br>June               85        383                    22%<br>July               98        473                    20%<br>July               98        389                    25%</pre><p>same process should be done for all the game. so we will get our data between 0 to 100. and if we plot the graph we will get <strong><em>100% Column Stack chart.</em></strong></p><blockquote><strong>Python code to generate Percent stacked barplot</strong></blockquote><p>_______________________________________________________</p><pre>import pandas as pd<br>import matplotlib.pyplot as plt<br>pd.__version__<br>data=pd.read_csv(&quot;C:\\Users\\i342011\\Desktop\\Tech Know School\\Blog\\Game_data.csv&quot;)<br>data<br>chess=data.iloc[0][1:]<br>monopoly=data.iloc[1][1:]<br>snooker = data.iloc[2][1:]<br>domino = data.iloc[3][1:]<br>poker_dice = data.iloc[4][1:]<br>Call_of_Duty = data.iloc[5][1:]<br>total = data.iloc[6][1:]<br>print(chess,total)</pre><pre>indexes = data.columns[1:]</pre><pre>#finding the percentage for each cell as i explained above<br>chess = [i/j*100  for i, j in zip(chess,total)]<br>monopoly = [i/j*100  for i, j in zip(monopoly,total)]<br>snooker = [i/j*100  for i, j in zip(snooker,total)]<br>domino = [i/j*100  for i, j in zip(domino,total)]<br>poker_dice = [i/j*100  for i, j in zip(poker_dice,total)]<br>Call_of_Duty = [i/j*100  for i, j in zip(Call_of_Duty,total)]</pre><pre>indexes= [&#39;JAN&#39;,&#39;FRB&#39;,&#39;MAR&#39;,&#39;APR&#39;,&#39;MAY&#39;,&#39;JUNE&#39;,&#39;JULY&#39;,&#39;AUG&#39;]</pre><pre>figure=plt.figure()<br>plt.bar(x=indexes, height=chess,width=0.35)<br>plt.bar(x=indexes, height=monopoly, width=0.35, bottom=chess)<br>plt.bar(x=indexes, height=snooker, width=0.35,bottom=[i+j for i,j in zip(chess, monopoly)])<br>plt.bar(x=indexes, height=domino, width=0.35, bottom=[i+j+k for i,j,k in zip(chess, monopoly,snooker)])<br>plt.bar(x=indexes, height=poker_dice, width=0.35, bottom=[i+j+k+l for i,j,k,l in zip(chess, monopoly,snooker,domino)])<br>plt.bar(x=indexes, height=Call_of_Duty, width=0.35, bottom=[i+j+k+l+m for i,j,k,l,m in zip(chess, monopoly,snooker,domino,poker_dice)])</pre><pre>print(data)</pre><pre>plt.xlabel(&#39;Months&#39;)<br>plt.ylabel(&#39;Game Sales&#39;)<br>plt.title(&#39;stack column chart&#39;)<br>plt.xticks(indexes)</pre><pre>plt.show()</pre><p>Output:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Z1HXfhUpIcqIfDmpjspFfQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c396dec1260" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Finding position of first least significant non-zero bit in Binary number]]></title>
            <link>https://medium.com/@manishsakariya/finding-position-of-first-least-significant-non-zero-bit-in-binary-number-6df144602f89?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/6df144602f89</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[binary]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Sun, 05 May 2019 20:37:24 GMT</pubDate>
            <atom:updated>2019-05-22T14:53:50.254Z</atom:updated>
            <content:encoded><![CDATA[<p>let’s say we have x = 111100<strong>1</strong>0</p><p>here the position of first non-zero least significant is 2 as shown in Bold.</p><p>how to find that position</p><p>let’s understand subtraction by one in binary</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*mCI8WMEikxho80iiP5QBtg.png" /></figure><p>we can not do 0–1 in first bit so we need to borrow from second bit</p><p>second bit represents 2 in decimal</p><p>so 2 = 1+1</p><p>so we can have 2 number of 1’s if we borrow from 2nd place</p><p>so that second bit will become zero in result.</p><p>now we know that whenever we subtract 1 from the number,the first least significant bit will become zero in the result.</p><p>we can use this to our advantage.</p><p>lets say we do ~(x-1)</p><p>in this operation of ~(x-1) our first non zero bit which was turned off due to (x-1) operation will be turned on. but other bit will become toggled from initial position.</p><p>we have x-1 = 11110001</p><p>now we have ~(x-1) = 000011<strong>1</strong>0</p><p>initial x = 11110010</p><p>now compare x with ~(x-1)</p><p>if we (~)toggle x the we will have 000011<strong>0</strong>1</p><p>~ x = 000011<strong>0</strong>1</p><p>~(x-1)= 000011<strong>1</strong>0</p><p>now we can see that only difference between ~x and ~(x-1) is least significant non zero position bit. which is indicated in bold</p><p>so if we do x &amp; ~(x-1)</p><p>then we will have only least significant non-zero bit signed on.</p><p>x &amp; ~(x-1) = 11110010 &amp; 000011<strong>1</strong>0</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*ibx_kapvIF88MV7XtHyHfQ.png" /></figure><p>we we have our answer as 2 now</p><p>___________________________________________________________</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6df144602f89" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Masters Theorem for dividing functions]]></title>
            <link>https://medium.com/@manishsakariya/masters-theorem-for-dividing-functions-bed89d4a9e0b?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/bed89d4a9e0b</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[time-complexity]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[masters-theorem]]></category>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Sat, 04 May 2019 10:16:36 GMT</pubDate>
            <atom:updated>2019-05-04T10:16:36.897Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/256/1*CwEI5FR8kB24hphs0KYfPw.png" /><figcaption>i’ll help you find time complexity of dividing recursive function quickly</figcaption></figure><p>It can be used when your recursive relation is of this type</p><p>T(n)=aT(n/b)+nᵏlogᵖ</p><p>I’ll divide this in 3 parts</p><blockquote>PART 1</blockquote><p>when logᵦa &gt; k</p><p>Time complexity = Θ(nˡᵒᵍᵦᵃ)</p><p>Example 1:</p><p>T(n)= 2T(n/2)+1</p><p>here log₂2=1 and k=0</p><p>so logᵦa &gt; k</p><p>T(n)=Θ(nˡᵒᵍᵦᵃ)=O(n)</p><p>Example 2: 4T(n/2)+nlogn</p><p>log₂4=2 and k=1</p><p>so T(n)=Θ(nˡᵒᵍᵦᵃ)=Θ(n²)</p><blockquote>Part 2</blockquote><blockquote>case 1: logᵦa =k and p&gt;-1</blockquote><blockquote>Time complexity = Θ(f(n)*logn)</blockquote><p>example when p&gt;-1</p><p>T(n)=2T(n/2)+nlogn</p><p>log₂2=1 and k=1</p><p>T(n)=f(n)*logn=nlog²n</p><blockquote>case 2: logᵦa =k and p=-1</blockquote><blockquote>Time complexity = Θ(nᵏ*loglogn)</blockquote><p>example T(n)= 2T(n/2) + n/logn</p><p>logᵦa =k and p=-1</p><p>T(n)=Θ(n*loglogn)</p><blockquote>case 3: logᵦa =k and p&lt;-1</blockquote><blockquote>Time complexity = Θ(nᵏ)</blockquote><p>example:</p><p>T(n)= 2T(n/2) + n/log²n</p><p>T(n)=n</p><blockquote>Part 3</blockquote><blockquote>case 1: logᵦa &lt;k and p≥0</blockquote><blockquote>Time complexity = Θ(nᵏlogᵖ)</blockquote><p>Example</p><p>T(n) = 2T(n/2)+n²log²p</p><p>Time complexity = n²log²p</p><blockquote>case 2: logᵦa &lt;k and p&lt;0</blockquote><blockquote>Time complexity = Θ(nᵏ)</blockquote><p>Example</p><p>T(n) = 2T(n/2)+n²/log²p</p><p>Time complexity = n²</p><p>— — — — — — — — — — — — — — — — — — — — — — — -</p><p>hope you guys liked the post. don’t forget to clap and follow for more on</p><p>algorithms and data structure.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bed89d4a9e0b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Masters Theorem for decreasing function]]></title>
            <link>https://medium.com/@manishsakariya/masters-theorem-for-decreasing-function-90153ca2c4ce?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/90153ca2c4ce</guid>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Fri, 03 May 2019 06:33:25 GMT</pubDate>
            <atom:updated>2020-01-16T18:29:34.606Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/256/1*CwEI5FR8kB24hphs0KYfPw.png" /><figcaption>I’ll Help you find time complexity of recursive function.</figcaption></figure><p>let us break it into 3 parts</p><blockquote>PART 1:</blockquote><p>T(n) = T(n-k)+f(n)</p><p>time complexity = O(n*f(n))</p><p>f(n) =n^k and k&gt;0</p><blockquote>examples</blockquote><blockquote>T(n) = T(n-1)+1 =&gt; O(n*1)=O(n)</blockquote><blockquote>T(n) = T(n-2)+1=&gt;O(n*1) = O(n)</blockquote><blockquote>T(n) = T(n-3)+ n⁵ =&gt; O(n*n⁵)=O(n⁶)</blockquote><blockquote>T(n) = T(n-3)+ logn=&gt; O(logn*n)=O(nLogn)</blockquote><blockquote>T(n) = T(n-100)+ nlogn=&gt; O(nlogn*n)=O(n²Logn)</blockquote><blockquote>T(n) = T(n-100)+n(n-1)=&gt; O(n*n²)=O(n³)</blockquote><blockquote>PART 2:</blockquote><p>T(n) = a T(n-b)+f(n)</p><p>where a&gt;1 f(n) = O(nᵏ)</p><p>time complexity = O(aⁿ/ᵇ nᵏ)</p><blockquote>examples</blockquote><blockquote>T(n) = 2T(n-1)+1 =&gt; O(2ⁿ*1)=O(n)</blockquote><blockquote>T(n) = 2T(n-3)+n=&gt;O(2ⁿ/³*n) = O(2ⁿ/³*n)</blockquote><blockquote>T(n) = 5T(n-3)+ n⁵ =&gt; O(5ⁿ/³*n⁵)=O(5ⁿ/³*n⁵)</blockquote><blockquote>PART 3:</blockquote><p>T(n) = a T(n-b)+f(n)</p><p>where a&lt;1 f(n) = O(nᵏ)</p><p>time complexity = O( nᵏ)</p><blockquote>T(n) = 0.5*T(n-1)+1 =&gt; O(1)=O(1)</blockquote><blockquote>T(n) = 0.75*T(n-5)+n² =&gt; O(n²)=O(n²)</blockquote><ul><li>*****when not to use this*******</li><li>T(n)=aT(n-b)-f(n)</li><li>it does not work when funtion is negative</li><li>T(n) =aT(n-b)+n⁻¹</li><li>it does not work when power of n is negative</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=90153ca2c4ce" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Time Complexity Examples]]></title>
            <link>https://medium.com/@manishsakariya/time-complexity-examples-6a4877a1b923?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/6a4877a1b923</guid>
            <category><![CDATA[example]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[time-complexity]]></category>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Mon, 29 Apr 2019 18:11:42 GMT</pubDate>
            <atom:updated>2022-01-17T15:37:36.076Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>Example 1: O(n) Simple Loop</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/653/1*vA03-SojaUVU06RJuCXrvg.png" /></figure><blockquote>Example 2: O(n²) Nested Loop</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/793/1*xtcxiaUEeQPH3hf8DYykSQ.png" /></figure><blockquote>Example 3: O(n²) Consecutive Statements.</blockquote><p>Here time complexity of first loop is O(n) and nested loop is O(n²). so we will take whichever is higher into the consideration.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/672/1*40jWQy6XMG3ejDtw_04rKw.png" /></figure><blockquote>Example 4: O(n) with if-else loop.</blockquote><p>time complexity of if statement is O(1) and else is O(n). as O(n)&gt;O(1) time complexity of this program is O(n)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/744/1*oS3XNKt0s0P82nz2k8RLOA.png" /></figure><blockquote>Example 5: O(logn) logarithmic complexity</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/629/1*F_zfEbvz6vT2ZyokqDclXg.png" /></figure><pre>+-----------+--------------------+<br>| Iteration  |     Value of M     |        <br>+-----------+--------------------+<br>| 1         | n                  | <br>| 2         | n/2                |<br>| 3         | n/2^2              | <br>| 4         | n/2^3              |<br>| .         |  .                 |<br>| .         |  .                 |<br>| k         | n/2^k              |<br>+-----------+--------------------+</pre><p>loop will run k times so that m&gt;1.</p><p><em>m&gt;1 ; putting value of m for as n/2^k</em></p><p><em>n/2^k &gt;1</em></p><p><em>2^k &gt; n</em></p><p><em>k &gt; logn</em></p><blockquote>Example 6: O( √n)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/792/1*tHzWHxWqyAA_WEf9-hzCZw.png" /></figure><pre>+-----------+--------------------+---------------+<br>|  Iteration|      value of i    |value of s=s+i |<br>+-----------+--------------------+---------------+<br>|  1        | 1                  | 1+1           |<br>|  2        | 2                  | 1+1+2         |<br>|  3        | 3                  | 1+1+2+3       |<br>|  4        | 4                  | 1+1+2+3+4     |<br>|  .        |  .                 | .             |<br>|  .        |  .                 | .             |<br>|  k        |  k                 | 1+1+2+3+4+..+k|<br>+-----------+--------------------+---------------+</pre><p>number of time the loop will run is k</p><p>so 1+2+3+..+k&gt;n (that’s when loop breaks)</p><p>k(k+1)/2&gt;n</p><p>k²+k&gt;n</p><p>k²&gt;n (ignoring k as k²&gt;k)</p><p>k&gt;√n</p><p>so time complexity of program is √n</p><blockquote>Example 7: O(√n)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/737/1*UiBioHc6Nk9Lpp8wW9omTQ.png" /></figure><p>let’s say loop runs k times</p><p>so k²&gt;n (to break the condition)</p><p>k&gt;√n</p><p>so time complexity is √n</p><blockquote>Example 8: O(n²logn)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/803/1*7gWtnDDKnMFhb55RwyM3FA.png" /></figure><p>first loop will run n/2 times</p><p>second loop will run n/2 times as j+n/2&lt; n is the condition. so n/2 is already added to the iterator so only n/2 times loop will run.</p><p>third loop : 2^k &gt;n ( iteration wise 2⁰, 2¹,2²,…2^k)</p><p>k&gt;logn</p><p>so time complexity is n/2*n/2*logn</p><p>so n²logn is the time complexity.</p><blockquote>Example 9: O(nlog²n)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/807/1*-b8iPDwLIeSKyFiqW36nRQ.png" /></figure><p>first loop will run n/2 times</p><p>second and third loop as per above example will run logn times</p><p>so time complexity = n/2*logn*logn = O(nLog²n)</p><blockquote>Example 10: O(n) with break statement</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/715/1*ft4GFHJorEzrm8s-zy2axw.png" /></figure><p>first loop will run N times</p><p>second will break out after every first iteration. so it will run 1 time</p><p>so time complexity is O(n) instead of O(n²)</p><blockquote>Example 11: O(nLogn)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*1ztvZ6cUNyb9Lu40RQcEpw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1014/1*WkgYyMhCnAKDk8ZrqYxufQ.png" /></figure><p>so n+n/2+n/3+..+1 times total loop will run</p><p>n(1+1/2+1/3+1/4) = nlogn</p><p>so time complexity is nlogn.</p><blockquote>Example 12: O(n²)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/696/1*JF3x8ZQuwx2H9r3_CEyQgA.png" /></figure><p>outer loop will run n/3 times</p><p>inner loop will run n/4 times</p><p>so total time complexity is (n/3)*(n/4)=n²/12=O(n²)</p><blockquote>Example 13: O(log²n)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/738/1*LVdvylI2n17om7forMTmpA.png" /></figure><p>outer loop will run <em>logn </em>times [ 2^k&gt;n]</p><p>inner loop will run <em>logn </em>times [n/2^k&gt;1]</p><p>so total time complexity=logn*logn=log²n</p><blockquote>Example 14: O(n⁵)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*h7Klj1GDl_8XMvIFT8yO5w.png" /></figure><p>first loop will run n times</p><p>second loop will run n² times [ 1,2²,3²,…,n²]</p><p>third loop will run n times. approx as there is no clear pattern.</p><p>total time complexity = n*n*n² = O(n⁴)</p><blockquote>Example 15: O(n)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/582/1*nAPzQU-3NAgh9qU4ulZ_bg.png" /></figure><p>loop will run N+N/2+N/4+..N/2^n</p><p>=N(1+1/2+1/4+…+1/2^n)</p><p>=N(1+1)</p><p>=2N = 0(n)</p><p>sum of the series for reference</p><p>[ Sₙ= 1/2+1/4+…+1/2ⁿ</p><p>2Sₙ=2/2+2/4+2/8+…+2/2ⁿ</p><p>2Sₙ=1+1/2+1/4+..+1/2ⁿ⁻¹</p><p>2Sₙ=1+Sₙ-1/2ⁿ</p><p>Sₙ=1–1/2ⁿ</p><p>Sₙ=1 (when n= ∞)]</p><blockquote>Example 16: O(logn)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/816/1*387mIgYTTbSZ7TO9V95zKg.png" /></figure><p>Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,..</p><p>lets take gcd of 8 and 5 (it is two Fibonacci numbers)</p><p>gcd(8,5) =&gt; gcd (5,8%5)=&gt;gcd(5,3)=&gt;gcd(3,5%3)=&gt;</p><p>gcd(3,2)==&gt;gcd(2,1)=&gt;gcd(1,1)=&gt;gcd(1,0)</p><p>look at the second argument in the gcd function.</p><p>it is 5,3,2,1,1,0 in recursive calls.</p><p>it is following Fibonacci series pattern.</p><p>why we have taken gcd of Fibonacci numbers?</p><p>because it takes maximum number of steps.</p><p>so time complexity of gcd algo==time complexity of fib series</p><p>hence time complexity is O(logn)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6a4877a1b923" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ALGORITHMS]]></title>
            <link>https://medium.com/series/algorithms-5142a107e25f?source=rss-8f771988cbb2------2</link>
            <guid isPermaLink="false">https://medium.com/p/5142a107e25f</guid>
            <dc:creator><![CDATA[Manish Sakariya]]></dc:creator>
            <pubDate>Mon, 29 Apr 2019 14:34:34 GMT</pubDate>
            <atom:updated>2019-04-29T14:35:34.614Z</atom:updated>
            <content:encoded><![CDATA[<p>Trying out few things</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5142a107e25f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>