<?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 Mithra Talluri on Medium]]></title>
        <description><![CDATA[Stories by Mithra Talluri on Medium]]></description>
        <link>https://medium.com/@mithratalluri?source=rss-e34679e789b1------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*u-jnY_7jfPvy-g6cZFfwTw.jpeg</url>
            <title>Stories by Mithra Talluri on Medium</title>
            <link>https://medium.com/@mithratalluri?source=rss-e34679e789b1------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 07:12:58 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mithratalluri/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[Why you should prefer Kotlin to Java]]></title>
            <link>https://medium.com/@mithratalluri/why-you-should-prefer-kotlin-to-java-c739c2b94fe8?source=rss-e34679e789b1------2</link>
            <guid isPermaLink="false">https://medium.com/p/c739c2b94fe8</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[kotlin]]></category>
            <dc:creator><![CDATA[Mithra Talluri]]></dc:creator>
            <pubDate>Wed, 18 Sep 2019 08:50:24 GMT</pubDate>
            <atom:updated>2019-09-24T06:45:28.664Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QYWrKRnNDf-KJFX0N4hLFA.jpeg" /></figure><p>I’m new to Kotlin and have recently checked it out, after using Java in the past and I must say, I think there’s no place where using only Java would be better. In fact, Kotlin is now Google’s preferred language for Android app development.</p><p>Kotlin is a statically typed programming language built and maintained by JetBrains.</p><h3><strong>Interesting facts about Kotlin:</strong></h3><ul><li><strong><em>100% interoperable with Java</em></strong><em>: </em>You could have Java code and Kotlin code in the same project. This means you could also use all your favourite Java frameworks with Kotlin.</li><li><strong><em>Kotlin compiler compiles code to Bytecode!</em></strong> (also compiles to JavaScript and native)</li><li><strong><em>Null Safety</em></strong><em> </em>(more on this later)</li><li><strong><em>Type Inference:</em></strong></li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8ffc879c2247f443ddd567ea59a88af2/href">https://medium.com/media/8ffc879c2247f443ddd567ea59a88af2/href</a></iframe><p>Java also started having type inference from Java 10</p><ul><li><strong><em>Operator Overloading</em></strong></li><li><strong><em>Equality checks are more intuitive and simpler</em></strong></li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1bd07f171bfbbe6ce1f220a0f4745023/href">https://medium.com/media/1bd07f171bfbbe6ce1f220a0f4745023/href</a></iframe><ul><li><strong><em>Semicolons are optional</em></strong></li></ul><h3>Here are my reasons for why you should pick Kotlin over Java:</h3><h3>1. Extension Functions</h3><p>How many times have you written helper functions to your old classes by passing the class object as parameter? Not anymore!</p><p>In Kotlin, you can use extension functions to extend the class, i.e., you can add methods to the class outside the class. Say you want to get the last character in a String, you could say</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b4c1c6bdb6798f34937d5930383ccd8a/href">https://medium.com/media/b4c1c6bdb6798f34937d5930383ccd8a/href</a></iframe><h3>2. Data Classes</h3><p>We all love our POJO classes, but aren’t they verbose with all those explicitly mentioned getters and setters in Java?</p><p>Let’s say I want a POJO class Person which has readonly name and age properties. The Java class would be</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/293a4fa4feece80a91276727c204f5ad/href">https://medium.com/media/293a4fa4feece80a91276727c204f5ad/href</a></iframe><p>The same class in Kotlin would be</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/228a02019eea5d4ab1f824265906e9db/href">https://medium.com/media/228a02019eea5d4ab1f824265906e9db/href</a></iframe><p>So Kotlin makes POJOs incredibly concise and much more readable.</p><h3>3. Null Safety and Nullables</h3><blockquote>I call it my billion-dollar mistake — Tony Hoare, Inventor of null reference</blockquote><p>Ah! The dreaded Null Pointer Exception.</p><p>In Kotlin, it is upon the programmer to explicitly handle nullable types for the code to compile, hence making development smoother and better.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c77ad489cb52befb8c370cdcf9facd6f/href">https://medium.com/media/c77ad489cb52befb8c370cdcf9facd6f/href</a></iframe><p>Check out <a href="https://kotlinlang.org/docs/reference/null-safety.html">Null Safety in Kotlin</a> for more details.</p><h3>4. More power to Lambdas</h3><p>Although Kotlin isn’t really a purely functional language, it makes your code look more functional with powerful lambda support.</p><p>A lot of extensions in the Kotlin Standard Library on Collections are actually lambdas. Kotlin provides excellent lambda support for Collections with functions like filter, map, any, all, none, find, count, partition, etc. (I’ll talk about them in detail in a separate blog post). Using Lambdas makes your code more beautiful and readable.</p><h3>5. Named and default arguments</h3><p>Say goodbye to using Builders for having default arguments. In Kotlin, you can define default arguments to functions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e05f24b02b656ca3db5189ac8fb9b51b/href">https://medium.com/media/e05f24b02b656ca3db5189ac8fb9b51b/href</a></iframe><p>You also have support for named arguments, so now, you don’t need to check the documentation or follow the order of arguments when initializing objects or calling functions with many arguments.<br>You could call the function in the above example using named arguments like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/23c066a610456aa0e1502622d3fa39ca/href">https://medium.com/media/23c066a610456aa0e1502622d3fa39ca/href</a></iframe><p>I also suggest you check out other things that make life easier, with Kotlin.</p><ul><li><a href="https://kotlinlang.org/docs/reference/control-flow.html#when-expression">The When Expression</a></li><li><a href="https://kotlinlang.org/docs/reference/multi-declarations.html">Destructuring Declarations</a></li><li><a href="https://kotlinlang.org/docs/reference/ranges.html">Ranges</a></li><li><a href="https://kotlinlang.org/docs/tutorials/kotlin-for-py/objects-and-companion-objects.html">Objects and Companion objects</a></li><li><a href="https://kotlinlang.org/docs/reference/sequences.html">Sequences</a></li></ul><p>If you’re happy and you know it *clap clap* <br>Thank you for reading! 😃</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c739c2b94fe8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Manacher’s Algorithm Explained— Longest Palindromic Substring]]></title>
            <link>https://medium.com/hackernoon/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f?source=rss-e34679e789b1------2</link>
            <guid isPermaLink="false">https://medium.com/p/22cb27a5e96f</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[palindrome]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Mithra Talluri]]></dc:creator>
            <pubDate>Sat, 06 Jul 2019 23:27:48 GMT</pubDate>
            <atom:updated>2019-07-07T17:47:08.943Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DlF5-M3twGqmx0EIisrhbA.jpeg" /></figure><p>Manacher’s Algorithm helps us find the longest palindromic substring in the given string. It optimizes over the brute force solution by using some insights into how palindromes work. How? Let’s see!</p><p>Let’s focus on odd length palindromes for simplicity. We go about the string from left to right.</p><p><strong><em>Notations:</em></strong></p><p>Let c be the center of the longest length palindrome we have encountered till now. And let l and r be the left and right boundaries of this palindrome, i.e., the left-most character index and the right-most character index respectively. Now, let’s take an example to understand c, l, and r.</p><p>Eg: “abacabacabb”</p><p>When going from left to right, when i is at index 1, the longest palindromic substring is “aba” (length = 3).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8On8DfmxTXExgw_Ac-Y8nw.jpeg" /><figcaption>c, l, and r for palindromic string “aba”</figcaption></figure><p>The answer for the given string is 9 when the palindrome is centered at index 5; c, l, and r are as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sYkO6lOWxbsvR1XbbiHyYQ.jpeg" /><figcaption>Final c, l, and r positions for the whole string</figcaption></figure><p>Now that we know what c, l, and r denote, let’s take a small break from the algorithm and understand a few interesting facts about palindromes.</p><p><strong>Mirror index: </strong>For any palindrome centered at a center c, the mirror of index j is j’ such that</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cf50f98d9970c7f2d092ffcd959a1bba/href">https://medium.com/media/cf50f98d9970c7f2d092ffcd959a1bba/href</a></iframe><p>For palindrome “abacaba”, <strong>the mirror of j is j’ and the mirror of j’ is j</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YcXzqyZ6oskuNVAOpyTwvA.jpeg" /><figcaption>for some j, its mirror j’ for palindrome “abacaba”</figcaption></figure><p>Now, come back to the algorithm. When we move i from left to right, we try to “<strong>expand</strong>” the palindrome <strong>at each i</strong>. When I say the word expand, it means that I’ll check whether there exists a palindrome centered at i and if there exists one, I’ll store the “<strong>expansion length</strong>” to the left or to the right in a new array called<strong> P[] array</strong> or (some prefer) <strong>LPS[]</strong>.</p><blockquote><strong>If the palindrome at i expands beyond the current right boundary r, then c is updated to i and new l, r are found and updated.</strong></blockquote><p>Example time. Let’s take the previously discussed palindrome “abacaba” which is centered at i = 3.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*u7zwifrQrJYvkTLxoHTObg.jpeg" /><figcaption>P[i] = 3 as expansion length for palindrome centered at i is 3</figcaption></figure><p>Therefore, the P[] array stores the expansion length of the palindrome centered at each index. But we don’t need to manually go to each index and expand to check the expansion length every time. This is exactly where Manacher’s algorithm optimizes better than brute force, by using some insights on how palindromes work. Let’s see how the optimization is done.</p><p><em>Important recap: </em><strong>c</strong> indicates the center of the current longest odd length palindrome. And <strong>l</strong>, <strong>r</strong> denote the palindrome’s left and right boundaries.</p><p>Let’s see the P[] array for the string “abacaba”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tuhfTCNm-xHxwxK7wSUcbA.jpeg" /></figure><p>When i = 4, the index is inside the scope of the current longest palindrome, i.e., i &lt; r. So, instead of naively expanding at i, we want to know the minimum expansion length that is certainly possible at i, so that we can expand on that minimum P[i] and see, instead of doing from start. So, we check for mirror <strong>i’</strong>.</p><blockquote><strong>As long as the palindrome at index i’ does NOT expand beyond the left boundary (l) of the current longest palindrome, we can say that the minimum certainly possible expansion length at i is P[i’].</strong></blockquote><p>Remember that we are only talking about the minimum possible expansion length, the actual expansion length could be more and, we’ll find that out by expanding later on. In this case, P[4] = P[2] = 0. We try to expand but still, P[4] remains 0.</p><blockquote><strong>Now, if the palindrome at index i’ expands beyond the left boundary (l) of the current longest palindrome, we can say that the minimum certainly possible expansion length at i is r-i.</strong></blockquote><p>Eg: “acacacb”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/664/1*P7-_fzuiMqa3O5Q344lKxQ.jpeg" /><figcaption>Here, palindrome centered at i’ expands beyond the left boundary</figcaption></figure><p>So, P[4] = 5–4 = 1</p><p>You could ask but why can’t the palindrome centered at i expand after r in this case? If it did, then it would have already been covered with the current center c only. But, it didn’t. So, P[i] = r-i.</p><p>(That is, if palindrome at i were to expand beyond r, then the character at index 6 should have been ‘a’. But if that were to happen, the current palindrome centered at c would NOT have been “cacac” but “acacaca”)</p><p>So, we can sum the two quoted points above as follows:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/06620359b9829160ab3ea39887ddd6c3/href">https://medium.com/media/06620359b9829160ab3ea39887ddd6c3/href</a></iframe><p>That’s it. Now the only thing left is to<strong> expand at i after P[i]</strong>, so we check characters from index (P[i] + 1) and keep expanding at i.</p><p>If this palindrome expands beyond r, update c to i and r to (i + P[i]).</p><p>Voila! The P[] array is now filled and the maximum value in this array gives us the longest palindromic substring in the given string!</p><p><em>We have taken an odd length string for the above explanation. So, for this algorithm to work out, we simply append N + 1 special characters (say ‘#’) in between every two characters, just to make sure that our modified string is always of odd length.</em></p><p>Eg1: aba -&gt; #a#b#a#<br>Eg2: abba-&gt; #a#b#b#a#</p><p>Here’s the implementation in Java:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f2a86a0a29aed75a6b8e7b6a438932b7/href">https://medium.com/media/f2a86a0a29aed75a6b8e7b6a438932b7/href</a></iframe><p>Time Complexity: O(N)<br>Space Complexity: O(N)</p><p>Feel free to voice your doubts and concerns in the comments below. Thank you for reading! 😃</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=22cb27a5e96f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f">Manacher’s Algorithm Explained— Longest Palindromic Substring</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Kadane’s Algorithm Explained]]></title>
            <link>https://medium.com/hackernoon/kadanes-algorithm-explained-50316f4fd8a6?source=rss-e34679e789b1------2</link>
            <guid isPermaLink="false">https://medium.com/p/50316f4fd8a6</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Mithra Talluri]]></dc:creator>
            <pubDate>Wed, 20 Feb 2019 08:10:20 GMT</pubDate>
            <atom:updated>2019-02-28T02:45:18.963Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/836/1*XuUYS-A4W7gk4RCrI4aAaw.jpeg" /></figure><p>Given an array, the algorithm to find the maximum subarray sum is called Kadane’s Algorithm.<br>The array can be of any dimension. For simplicity, let’s start with a 1D array.</p><p>Let’s take a 0-indexed array:</p><p>arr: [5, 7, -3, 2, 9, 6, 16, 22, 21, 29, -14, 10, 12]</p><p>We can start the subarray at any point. <br>Let’s say we start at index 2 i.e., arr[2] = -3. Now, at index 3, the sum will be -3 + 2 = -1. If we started the subarray at index 3 instead, the sum at index 3 is 2, which is greater than the previous sum.</p><p>So we have two choices: either start at the current index or add the current element to the previous sum.</p><p>And since we want the maximum subarray sum, we add the current element to the maximum of 0 and previous sum (zero here denotes that we’re starting anew from the current element).</p><p>This problem falls under Dynamic Programming Paradigm.</p><p>Let’s take an array dp[] where each dp[i] denotes maximum subarray sum ending at index i (including i).</p><p>We can say that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/890/1*T4JsrEKrbZcwmFDz3R2ooQ.jpeg" /></figure><p>Base conditions: <br><em>dp[0] = arr[0]</em></p><p>Answer:<br>A maximum element in the dp[] array</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4cf7613eca32c85143a6575fdb295e47/href">https://medium.com/media/4cf7613eca32c85143a6575fdb295e47/href</a></iframe><p>Time Complexity: O(N)<br>Space Complexity: O(N)</p><p>We could optimize the space complexity by taking dp[i-1] which is the previous sum into a variable, eliminating the need for dp[] array.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/798d0ffe267a4b30fec0af2496b23216/href">https://medium.com/media/798d0ffe267a4b30fec0af2496b23216/href</a></iframe><p>Time Complexity: O(N)<br>Space Complexity: O(1)</p><p>We could also find the indices of the subarray having the maximum sum.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0ebd1d28d23dbec9b19f0b3190e4a55e/href">https://medium.com/media/0ebd1d28d23dbec9b19f0b3190e4a55e/href</a></iframe><p>We could apply Kadane’s to 2D matrix as well, where we have to find the maximum submatrix sum. Feel free to try out kadane’s for 2D matrices. Thank you for reading! 😃</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=50316f4fd8a6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/kadanes-algorithm-explained-50316f4fd8a6">Kadane’s Algorithm Explained</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary Search In Detail]]></title>
            <link>https://medium.com/hackernoon/binary-search-in-detail-914944a1434a?source=rss-e34679e789b1------2</link>
            <guid isPermaLink="false">https://medium.com/p/914944a1434a</guid>
            <category><![CDATA[binary-search]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[binary-search-details]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Mithra Talluri]]></dc:creator>
            <pubDate>Tue, 25 Dec 2018 08:33:04 GMT</pubDate>
            <atom:updated>2019-01-10T05:41:36.345Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DOR__3reJYPwGuyytG520g.jpeg" /></figure><p>I hope we all have some idea about what binary search is and does. But I’m not going to explain the algorithm step by step, rather I’m going to give an insight into how binary search works and can be used.</p><p>Check out: <a href="http://geeksforgeeks.org/binary-search">geeksforgeeks.org/binary-search</a> if you’re unaware of Binary Search.</p><p>Given a sorted array, we find the middle-most element and check the element with the key. If the middle-most element is equal to key, we’ve found the key. If the middle-most element is greater than the key, we search on the left half of the middle-most element, else we search on the right half.</p><p>Here’s an iterative code for Binary Search in Java</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/da762279033b5bea50f5497a0df94f81/href">https://medium.com/media/da762279033b5bea50f5497a0df94f81/href</a></iframe><p>Notice that in line 6, we use</p><pre>int mid = (low + high) / 2;</pre><p>But calculating mid this way is ineffective. Why? Let’s take an example.<br>Let us take integers from an integer low to an integer high (both included).</p><p>Notice the mids computed by formulae in 3rd and 4th columns.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/df6c9406d09c9122abe59c2cf30d3604/href">https://medium.com/media/df6c9406d09c9122abe59c2cf30d3604/href</a></iframe><ul><li>for low = 3 and high = 11, the number of elements (#elements) = 9<br>So there is only 1 mid, i.e., 7<br>* Both formulae have computed the mid correctly</li><li>for low = 3 and high = 10, #elements = 8<br>So there are 2 mids, 6 (lower mid) and 7 (higher mid)<br>* Both formulae have computed the lower mid correctly</li><li>for low = -11 and high = -3, #elements = 9<br>So there is only 1 mid, i.e., -7<br>* Both formulae have computed the mid correctly</li><li>for low = -10 and high = -3, #elements = 8<br>So there are 2 mids, -7 (lower mid) and -8 (higher mid)<br>* The formula(low + high) / 2 has failed to compute the lower mid correctly but the other formula has computed it correctly.</li></ul><p>So, we should always use the below formula to compute lower mid as it is much more reliable:</p><pre>int mid = low + ((high - low)/2);</pre><p>When #elements = odd, we have only 1 mid. So we can use the above formula to compute mid.<br>When #elements = even, the above formula only gives the lower mid. <br>The higher mid can be computed by the below formula:</p><pre>int mid2 = low + ((high - low + 1) / 2);</pre><p>Now, the interesting part…</p><p>Let’s go back to the iterative code for Binary Search. Notice three things.<br>1. How we are moving low and high<br>2. How we are computing mid<br>3. The condition in while loop</p><p>The beauty of Binary Search lies in these three things alone. Let us explore this further.</p><p>For a simple binary search where we just have to find the element in the array,<br>we use the following:<br>1. low = mid - 1 for moving low <br>2. high = mid + 1 for moving high <br>3. mid = low + ((high - low) / 2) (why? discussed above)<br>4. low &lt;= high in the while loop</p><p>Is it always the case that we use the same conditions for binary search?<br>It depends…on our problem statement.</p><p>Example #1:</p><p>Given an integer x, find the maximum element y in an array of size N that satisfies the condition y &lt;= x</p><p>Solution:</p><p>We know that x might not be in the array. So the simple binary search for x in the given array won’t work. But for binary search, all we know is x, the key. We need to find the element in the array that’s the closest to x and less than or equal to x (if it exists).</p><p>Three things should always come to your mind when using binary search:<br>1. How should we move low and high?<br>2. How should we compute mid?<br>3. What would be the condition in while loop?</p><p><em>We always start with ‘How to move low and high?’ and then find out how to compute mid and what might be the while condition. NOT the other way round.</em></p><ol><li><em>How to move low and high?</em> <br>When array[mid] &lt; x , there is a possibility that the current element might be the answer (since y can be less than x).<br>So, we shouldn’t discard mid while moving low.<br>Hence, low becomes low = mid , not low = mid + 1 <br>High remains the same as it is irrelevant to our problem statement.</li><li><em>How to compute mid?<br></em>When we use mid = low + ((high - low) / 2) , we are calculating the lower mid. So when the #elements in the array is even, the <br>if(array[mid] &gt; x) becomes false, so control will go to else clause where low = mid . This results in an infinite loop. (why? take an example)<br>Hence, we take the higher mid, i.e., mid = low + ((high - low + 1) / 2)</li><li><em>What would be the condition in while loop?<br></em>Since we are storing the maximum element that is less than or equal to x in low, we should stop when low = high and return array[low] or array[high]. Hence, the condition in while loop is low &lt; high .</li></ol><p>The Solution in Java looks like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/93a66cc11753b5094f1e812a358135fd/href">https://medium.com/media/93a66cc11753b5094f1e812a358135fd/href</a></iframe><p>Example #2:</p><p>Given an integer x, find the minimum element y in an array of size N that satisfies the condition y &gt;= x</p><p>Solution:</p><p>Using a similar analytical approach we used in example 1 (try it out yourself), we can say that</p><ol><li>low = mid + 1 for moving low</li><li>high = mid for moving high</li><li>mid = low + ((high - low) / 2) for calculating mid</li><li>low &lt; high for the condition in while loop</li></ol><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a75b674dfacf355b1b9f38c8013eea35/href">https://medium.com/media/a75b674dfacf355b1b9f38c8013eea35/href</a></iframe><p>Hence we can tabulate different scenarios of using Binary Search as follows:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e0381af185f3bfb99f495603a7f40d05/href">https://medium.com/media/e0381af185f3bfb99f495603a7f40d05/href</a></iframe><p>Feel free to experiment with these conditions and I hope you have gotten some insight into how to use binary search.</p><p>Namaste!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=914944a1434a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/binary-search-in-detail-914944a1434a">Binary Search In Detail</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Basic Graph Implementation in Java]]></title>
            <link>https://medium.com/@mithratalluri/basic-graph-implementation-in-java-9ed12e328c57?source=rss-e34679e789b1------2</link>
            <guid isPermaLink="false">https://medium.com/p/9ed12e328c57</guid>
            <category><![CDATA[java]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Mithra Talluri]]></dc:creator>
            <pubDate>Sat, 13 Oct 2018 18:58:43 GMT</pubDate>
            <atom:updated>2018-10-28T16:18:29.984Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/823/1*PRSdO4485XYMPbmy7PgHnQ.jpeg" /></figure><p>There are two fundamental ways we implement a graph in Java.</p><ol><li>By using an Adjacency Matrix</li><li>By using an Adjacency List</li></ol><p>So which should you use? It depends…on what operations you want to perform on the graph.</p><p><strong>Adjacency Matrix</strong></p><p>Pros:</p><ul><li>Fast lookup for finding an edge — <em>O(1)</em> time</li><li>Better for dense graphs i.e., having a lot of edges</li></ul><p>Cons:</p><ul><li>Uses <em>O(V²)</em> space</li><li>Iterates over all of the edges in <em>O(V²) </em>time</li></ul><p>V = number of vertices</p><p><strong>Adjacency List</strong></p><p>Pros:</p><ul><li>Uses <em>O(V+E) </em>space (worst case)</li><li>Better for sparse graphs i.e., having less number of edges</li></ul><p>Cons:</p><ul><li>Look up for finding an edge takes <em>O(V)</em> time</li></ul><p>V = number of vertices, E = number of edges</p><p>Most graphs are pretty sparse and typically V² &gt;&gt; E so adjacency lists are widely used.</p><p><strong>Here’s an implementation of a Graph using Adjacency List in Java</strong></p><p>I implemented a <em>weighted directed</em> <em>graph </em>as a HashSet of vertices. We can implement an undirected and/or unweighted graph using the same approach (refer to the comments in the code).</p><p>Each vertex has a name and contains a list of all of its outgoing edges.<br>(I used an ArrayList. You could use a LinkedList too.)</p><p>Each edge has a weight and a destination vertex.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/80187b51484e569b6502eeeba5820ad5/href">https://medium.com/media/80187b51484e569b6502eeeba5820ad5/href</a></iframe><p>Our Input graph looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/238/0*T1RN2JZIRMDh66uZ" /></figure><p>Output:</p><pre>vertex name: 3: destVertex: 2 weight: 4 | <br>vertex name: 0: destVertex: 1 weight: 2 | <br>vertex name: 1: destVertex: 2 weight: 3 | <br>vertex name: 2: destVertex: 0 weight: 1 | destVertex: 3 weight: 1 |</pre><p>Thanks for reading. Give this post a clap if you find it interesting. <br>Have any doubts? Please feel free to leave it in the comments below. Namaste!</p><p><em>Originally published at </em><a href="https://mithratalluri.wordpress.com/2018/10/14/basic-graph-implementation-in-java/"><em>mithratalluri.wordpress.com</em></a><em> on October 13, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9ed12e328c57" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Trees: Top View of a Tree]]></title>
            <link>https://medium.com/@mithratalluri/trees-top-view-of-a-tree-438a775c21d3?source=rss-e34679e789b1------2</link>
            <guid isPermaLink="false">https://medium.com/p/438a775c21d3</guid>
            <category><![CDATA[java]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[trees]]></category>
            <dc:creator><![CDATA[Mithra Talluri]]></dc:creator>
            <pubDate>Tue, 02 Oct 2018 10:02:24 GMT</pubDate>
            <atom:updated>2018-10-31T03:27:25.257Z</atom:updated>
            <content:encoded><![CDATA[<p>Top View of a tree is the set of all the nodes that are visible from the tree top.</p><p>Now, let’s say you’re given a pointer to the root of the tree. How would you print the top view?</p><p>Example 1:</p><pre>   1<br>    \<br>     2<br>      \<br>       5<br>      /  \<br>     3    6<br>      \<br>       4</pre><p>Output: 1 2 5 6</p><p>Example 2:</p><pre>        1<br>      /   \<br>    2       3<br>     \   <br>      4  <br>       \<br>        5<br>         \<br>          6</pre><p>Output: 2 1 3 6</p><p><em>Solution:</em></p><p>I’m printing the nodes from left to right, however, you can follow any order.</p><p>In my solution, I’m implementing the tree node with an extra variable called ‘node level’. An example of the new tree looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/797/1*yZbtPFoG_eJL-a_Q_v3keA.png" /></figure><p>Implementation in Java with suitable comments</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d5088b7c2d9abfbd45c38230c880d062/href">https://medium.com/media/d5088b7c2d9abfbd45c38230c880d062/href</a></iframe><p>If you have any doubts, please feel free to leave it in the comments below. Give it a clap if you find this post helpful. Namaste!</p><p><em>Originally published at </em><a href="https://mithratalluri.wordpress.com/2018/10/02/trees-top-view-of-a-tree/"><em>mithratalluri.wordpress.com</em></a><em> on October 2, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=438a775c21d3" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>