<?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 Hary Krishnan on Medium]]></title>
        <description><![CDATA[Stories by Hary Krishnan on Medium]]></description>
        <link>https://medium.com/@harycane?source=rss-5bfffd10375c------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*tnlR2szXDoUEpna2i0lxEw.jpeg</url>
            <title>Stories by Hary Krishnan on Medium</title>
            <link>https://medium.com/@harycane?source=rss-5bfffd10375c------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 15:29:48 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@harycane/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[String to Integer (atoi)]]></title>
            <link>https://medium.com/@harycane/string-to-integer-atoi-1e75325c5fd7?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/1e75325c5fd7</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Wed, 01 Aug 2018 07:56:18 GMT</pubDate>
            <atom:updated>2018-08-01T07:56:18.496Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/string-to-integer-atoi/description/">String to Integer (atoi) - LeetCode</a></p><p>Implement atoi which converts a string to an integer.</p><p>The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.</p><p>The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.</p><p>If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.</p><p>If no valid conversion could be performed, a zero value is returned.</p><p>Note:</p><ul><li>Only the space character ‘ ‘ is considered as whitespace character.</li><li>Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.</li></ul><p>Example 1:</p><pre>Input: &quot;42&quot;<br>Output: 42</pre><p>Example 2:</p><pre>Input: &quot;   -42&quot;<br>Output: -42<br>Explanation: The first non-whitespace character is &#39;-&#39;, which is the minus sign.<br>             Then take as many numerical digits as possible, which gets 42.</pre><p>Example 3:</p><pre>Input: &quot;4193 with words&quot;<br>Output: 4193<br>Explanation: Conversion stops at digit &#39;3&#39; as the next character is not a numerical digit.</pre><p>Example 4:</p><pre>Input: &quot;words and 987&quot;<br>Output: 0<br>Explanation: The first non-whitespace character is &#39;w&#39;, which is not a numerical <br>             digit or a +/- sign. Therefore no valid conversion could be performed.</pre><p>Example 5:</p><pre>Input: &quot;-91283472332&quot;<br>Output: -2147483648<br>Explanation: The number &quot;-91283472332&quot; is out of the range of a 32-bit signed integer.<br>             Thefore INT_MIN (−231) is returned.</pre><p><strong>Algorithm:</strong></p><p>1 Since the function discards as many white spaces as present until the first non white space character is found, we can go ahead and trim the given string firstly, before which we can sanity check if it is null and if so return 0.</p><p>2 After trimming, if the string length is 0, ie it is an empty string, then return 0 as well.</p><p>3 In order to take care of the optional + or — sign, we check whether the first character of the string is ‘+’ or ‘-’, and if so we increment the startIndex from initial value of 0. If the first character is ‘-’ then we toggle the isNegative boolean initially initialized to false, to true.</p><p>4 In order to take care of numeric case, we get the ith character from the string and subtract it by ‘0’ and cast the result to int and store in a digitValue variable. And update our result variable in order to regenerate the numeric value as result * 10 + digitValue. Prior to taking care of the numeric case, care has to be taken care in order to ensure that the current character is not out of the asci range of ‘0’ or ‘9’. If it so, then according to the given rule, we break from the string iteration to return the result, subject to certain conditions.</p><p>5 If isNegative is true, then we toggle the result to point to the negative version of its value.</p><p>6 If result which is of type double, is less than Integer.MIN_VALUE, then we return Integer.MIN_VALUE. Likewise if the result is greater than Integer.MAX_VALUE then we return the Integer.MAX_VALUE. This will take care of cases of integer underflow and overflow.</p><p>7 Finally we cast the result back to int and return the resultant converted value.</p><p><strong>Test:</strong></p><p>1 Test with multiple + — consecutive to each other followed by numeric or textual values, should return 0, since after the first optional sign, there is no numeric value.</p><p>2 Test with underflow and overflow resultant values.</p><p>3 Test with empty string.</p><p>4 Test with words interleaved with numbers. Test with numbers interleaved with + — signs.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fcd2f3dd17f658d400ab7653c2f61647/href">https://medium.com/media/fcd2f3dd17f658d400ab7653c2f61647/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since we end up iterating through the entire string in the worst case, the time complexity is T O(n), since we do not use any auxiliary space, S O(1).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1e75325c5fd7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reverse String]]></title>
            <link>https://medium.com/@harycane/reverse-string-f7c288f93a45?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/f7c288f93a45</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Sun, 29 Jul 2018 22:39:12 GMT</pubDate>
            <atom:updated>2018-07-29T22:39:12.677Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/reverse-string/description/">Reverse String - LeetCode</a></p><p><strong>Example:</strong></p><p>Write a function that takes a string as input and returns the string reversed.</p><p>Example:</p><p>Given s = “hello”, return “olleh”.</p><p><strong>Algorithm:</strong></p><p>1 Convert the given string to a character array.</p><p>2 Have two pointers to mark the first and the last index of this character array.</p><p>3 Iterate until while first is less than last, each time swapping within the character array, the first and the last values, and incrementing and decrementing the first and last pointers respectively thereafter for the next iteration.</p><p>4 At the end of the iteration, the character array will contain the string in the reversed order. Convert it to a string and return the resultant value.</p><p><strong>Test:</strong></p><p>1 Test with non palindromic and palindromic strings.</p><p>2 Test with empty null and same character strings.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f0ac07448ffb09bdfe814d95dc723c01/href">https://medium.com/media/f0ac07448ffb09bdfe814d95dc723c01/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since we iterate through to half the length of the given string in order to reverse it, the time complexity is T O(n). Space Complexity is S O(n) since we use an auxiliary array in order to convert the given string into a character array so as to swap and reverse.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f7c288f93a45" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Roman To Integer]]></title>
            <link>https://medium.com/@harycane/roman-to-integer-118ff56132df?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/118ff56132df</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Sun, 29 Jul 2018 21:46:40 GMT</pubDate>
            <atom:updated>2018-07-29T21:46:40.270Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/roman-to-integer/description/">Roman to Integer - LeetCode</a></p><p><strong>Example:</strong></p><p>Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.</p><pre>Symbol       Value<br>I             1<br>V             5<br>X             10<br>L             50<br>C             100<br>D             500<br>M             1000</pre><p>For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.</p><p>Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:</p><ul><li>I can be placed before V (5) and X (10) to make 4 and 9.</li><li>X can be placed before L (50) and C (100) to make 40 and 90.</li><li>C can be placed before D (500) and M (1000) to make 400 and 900.</li></ul><p>Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.</p><p>Example 1:</p><pre>Input: &quot;III&quot;<br>Output: 3</pre><p>Example 2:</p><pre>Input: &quot;IV&quot;<br>Output: 4</pre><p>Example 3:</p><pre>Input: &quot;IX&quot;<br>Output: 9</pre><p>Example 4:</p><pre>Input: &quot;LVIII&quot;<br>Output: 58<br>Explanation: C = 100, L = 50, XXX = 30 and III = 3.</pre><p>Example 5:</p><pre>Input: &quot;MCMXCIV&quot;<br>Output: 1994<br>Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.</pre><p><strong>Algorithm:</strong></p><p>1 If the given string contains either IV or IX add -2 each time to the result storing sum variable, likewise if the given string contains either XL or XC add -20 each time to the sum, and if the given string contains either CD or CM add -200 each time to the sum. This is done to offset the equivalent sum computed when examining from left to right. (i.e. IV would result in sum value being -2 to which examining from left to right would add a value of 6 thus resulting in the net value of 4.)</p><p>2 Iterate through each character in the given roman string, and add its equivalent value to a variable sum, which would eventually contain the resultant integer value.</p><p><strong>Test:</strong></p><p>1 Test with roman values within 1–10, 11–99,100–999 and 1000–3000.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1443e59f710346d340ece954862913fe/href">https://medium.com/media/1443e59f710346d340ece954862913fe/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since we iterate through each character in the given string, the time complexity is T O(n) and Space complexity is S O(1) since we do not use of any auxiliary space.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=118ff56132df" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Ransom Note]]></title>
            <link>https://medium.com/@harycane/ransom-note-af09b54904d0?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/af09b54904d0</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Mon, 16 Jul 2018 04:03:32 GMT</pubDate>
            <atom:updated>2018-07-16T04:03:32.946Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/ransom-note/description/">Ransom Note - LeetCode</a></p><p><strong>Example:</strong></p><p>Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.</p><p>Each letter in the magazine string can only be used once in your ransom note.</p><pre>canConstruct(&quot;a&quot;, &quot;b&quot;) -&gt; false<br>canConstruct(&quot;aa&quot;, &quot;ab&quot;) -&gt; false<br>canConstruct(&quot;aa&quot;, &quot;aab&quot;) -&gt; true</pre><p><strong>Algorithm:</strong></p><p>1 Since each letter in the magazine string can only be used once in the ransom note, hence one viable algorithm would be to build a frequency array iterating over and accounting for each character occurring in the magazine string.</p><p>2 Now iterate over the ransomNote string, each time decrementing the frequency of occurrence of the ransomNote character from the frequency array table built from the magazine string. If the decremented value goes below 0, then it means there is a letter in ransomNote which is not present in the magazine string and hence return false in such a case.</p><p>3 If the program does not return false throughout the iteration over the ransomNote, then it means that each character in the ransomNote is present in the magazine string, hence return true outside the iterating loop of ransomNote.</p><p><strong>Test:</strong></p><p>1 Test for null or empty ransomNote string, and null or empty magazine string.</p><p>2 Test for ransomNote being the subset of Magazine string and vice versa.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1fef06cb2b88492cd23d0f930674dfd5/href">https://medium.com/media/1fef06cb2b88492cd23d0f930674dfd5/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since we iterate over both the magazine string length(m) and the ransomNote string length(n) in the worst case, therefore the time complexity is T O(m + n). Space complexity is S O(1) since we use a fixed size array of size 26.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=af09b54904d0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Array Nesting]]></title>
            <link>https://medium.com/@harycane/array-nesting-3d410e4424ea?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/3d410e4424ea</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Mon, 16 Jul 2018 03:56:10 GMT</pubDate>
            <atom:updated>2018-07-16T03:56:10.070Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/array-nesting/description/">Array Nesting - LeetCode</a></p><p><strong>Example:</strong></p><p>A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], … } subjected to the rule below.</p><p>Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.</p><p>Example 1:</p><pre>Input: A = [5,4,0,3,1,6,2]<br>Output: 4<br>Explanation: <br>A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.</pre><pre>One of the longest S[K]:<br>S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}</pre><p>Note:</p><ol><li>N is an integer within the range [1, 20,000].</li><li>The elements of A are all distinct.</li><li>Each element of A is an integer within the range [0, N-1].</li></ol><p><strong>Algorithm:</strong></p><p>1 Iterate through each element in the array, and with each value as the starting index, incrementing the count while exploring the next value whose index is represented by the current element’s value, until the next value has not been visited already (which is indicated by setting the element value already explored to Integer.MAX_VALUE).</p><p>2 As each element is considered as the start index of our non duplicate set satisfying the required relationship, compute the global max result as a max of result and the current starting index’s count.</p><p>3 Since N is an integer in the range of upto 20,000, Integer.MAX_VALUE can be confidently used to mark a particular element to be visited. Also doing so would ensure that as we iterate through each element of the array, we do not end up computing duplicate counts, resulting from the same sequence of elements, merely with the starting index being different among the sequence of elements. (ie if a sequence of elements leads to a duplicate after a particular count of distinct elements, for a particular start index, the count of distinct elements in the set is not going to change regardless of changing up the starting index among the cyclic sequence of elements)</p><p>4 Since each element in the array is unique, no two different values would result in a collision of index; and owing to the same reason of each element being distinct, no element outside the cycle could lead to an element in the cycle, thus validating the mark up of an element as visited, as a viable algorithm to our problem.</p><p><strong>Test:</strong></p><p>1 Test for a set with uniformly increasing and decreasing elements but containing all values from 0 — n-1.</p><p>2 Test for a set with haphazard order of elements but with all values from 0 — n-1.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/42755829f6612a5bb1e607b6b7b0aa08/href">https://medium.com/media/42755829f6612a5bb1e607b6b7b0aa08/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>By making use visited elements concept within the array, we save auxiliary space and ensure that duplicate counts are not computed by merely shifting the starting index among the same sequence of elements that are eventually found to be cyclic in nature (thanks to each element being distinct). However since we still have to iterate across the length of the array to compute the global max result, therefore the time complexity is T O(n) and S O(1).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3d410e4424ea" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Max points on a line]]></title>
            <link>https://medium.com/@harycane/max-points-on-a-line-1e38f51d591f?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/1e38f51d591f</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Mon, 16 Jul 2018 03:50:39 GMT</pubDate>
            <atom:updated>2018-07-16T03:50:39.830Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/max-points-on-a-line/description/">Max Points on a Line - LeetCode</a></p><p><strong>Example:</strong></p><p>Given <em>n</em> points on a 2D plane, find the maximum number of points that lie on the same straight line.</p><p>Example 1:</p><pre>Input: [[1,1],[2,2],[3,3]]<br>Output: 3<br>Explanation:<br>^<br>|<br>|        o<br>|     o<br>|  o  <br>+-------------&gt;<br>0  1  2  3  4</pre><p>Example 2:</p><pre>Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]<br>Output: 4<br>Explanation:<br>^<br>|<br>|  o<br>|     o        o<br>|        o<br>|  o        o<br>+-------------------&gt;<br>0  1  2  3  4  5  6</pre><p><strong>Algorithm:</strong></p><p>1 Basically for two points to be on the same line they should be sharing the same slope. From this idea, we can, for each point, compute the slope w.r.t to all other points, mapping the number of points having a particular slope, and calculate the local max as the max of the previous local max and the maximum number of points across all the slopes originating from that point.</p><p>2 As we iterate the origin from one point to the next in the array, we can compute the global maximum as the maximum from the previous global max and the current local max + number of overlapping points + 1 to take into account the current origin point being considered.</p><p>3 Key thing to be considered while storing the slope in the map is that, storing them as a result of the x/y, in the form of decimal, shall lead to precision errors due to floating point numbers. Hence to mitigate it, a design decision of storing the slope as rational number x/y is considered in the form of map1 (x, map2(y, frequency of points with x/y slope)). Also, in order to avoid considering 2/4 and 1/2 as different slopes, while storing x/y in the hash-map, care is taken to ensure that it is reduced to its simplest form by dividing both x and y by its GCD.</p><p><strong>Test:</strong></p><p>1 Test for points on the same horizontal line and the case where points align on the same vertical line.</p><p>2 Test for maximum number of points on a decreasing slope and also the case where maximum points align on an increasing slope.</p><p>3 Test for a case where all points are overlapping.</p><p><strong>Solution</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ffc506d1a40c7fc4651ea66f7cb5b5b6/href">https://medium.com/media/ffc506d1a40c7fc4651ea66f7cb5b5b6/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since for each point in the array, we iterate across all other points in the array to compute and map the slope, therefore time complexity is T O(n²). S O(n) to consider the size of the hash map.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1e38f51d591f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Convert Sorted Array to BST]]></title>
            <link>https://medium.com/@harycane/convert-sorted-array-to-bst-35781e940ca5?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/35781e940ca5</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Mon, 16 Jul 2018 03:45:32 GMT</pubDate>
            <atom:updated>2018-07-16T03:45:32.620Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/">Convert Sorted Array to Binary Search Tree - LeetCode</a></p><p>Given an array where elements are sorted in ascending order, convert it to a height balanced BST.</p><p>For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of <em>every</em> node never differ by more than 1.</p><p><strong>Example:</strong></p><pre>Given the sorted array: [-10,-3,0,5,9],</pre><pre>One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:</pre><pre>      0<br>     / \<br>   -3   9<br>   /   /<br> -10  5</pre><p><strong>Algorithm:</strong></p><p>1 Since the given array is sorted, we can assume it to be the result of an inorder traversal of the given tree.</p><p>2 In which case the mid value of the given sorted array would represent the root of one possible BST that can be constructed from the given array elements.</p><p>3 To be in alignment with the definition of a Binary Search Tree, the elements in the array to the left of the mid value, would contribute to the left subtree of our root while the elements in the array to the right of the mid value, would contribute to the right subtree of our root.</p><p>4 Hence we can recursively construct out binary search tree, by using binary search algorithm on the array, to construct the root, left and right subtree respectively by recursively invoking the convertToBstHelper method with appropriate boundary conditions, that of low, mid -1 for the left subtree and mid+1, high for the right subtree.</p><p>5 The base condition that would terminate the recursion would then be if low boundary index exceeds high boundary index, in which case return null.</p><p><strong>Test:</strong></p><p>1 Test with sanity input like null or empty values.</p><p>2 Test with negative and positive array elements.</p><p>3 Test after constructing the BST, whether the in order of the constructed tree returns back the array elements or not.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7a571f748ae56e776e45098ac00aaa36/href">https://medium.com/media/7a571f748ae56e776e45098ac00aaa36/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since we perform binary search on the array elements, splitting the input size by half through each recursion, therefore the time complexity that would be incurred from the aforementioned algorithm would be same as that incurred in binary search, that of T O(log n). Space complexity due to recursion stack space would incur in the worst case of S O(n).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=35781e940ca5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Coin Change]]></title>
            <link>https://medium.com/@harycane/coin-change-ad9ef6da3fc3?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/ad9ef6da3fc3</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[interview]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Mon, 16 Jul 2018 03:26:21 GMT</pubDate>
            <atom:updated>2018-07-16T03:26:21.064Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/coin-change/description/">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p><strong>Example:</strong></p><p>You are given coins of different denominations and a total amount of money <em>amount</em>. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.</p><p>Example 1:</p><pre>Input: coins = [1, 2, 5], amount = 11<br>Output: 3 <br>Explanation: 11 = 5 + 5 + 1</pre><p>Example 2:</p><pre>Input: coins = [2], amount = 3<br>Output: -1</pre><p>Note:</p><p>You may assume that you have an infinite number of each kind of coin.</p><p><strong>Algorithm:</strong></p><p>1 This problem makes a case for applying dynamic programming. The bigger problem is represented by the minimum number of coins needed to construct the given amount. Say the value is given by a dp array whose index = amount given. In order to determine whether a given coin denomination goes into constructing the given amount, we subtract that coin denomination from the index (equal to given amount) to reuse the solution to a subproblem of finding how many coins needed to construct a sub-amount = amount — coins[j] denomination.</p><p>2 The dp array is initialized with amount + 1. This not only helps in evaluating number of coins with respect to Math.min values initially, but also serves as a check at the end of constructing the dp array. If the index = amount in dp array still corresponds to a value greater than amount then the given combination of denomination can not be used to construct the given amount hence can safely return -1, else can return the value stored in the dp array with index = amount to indicate the minimum number of coins needed.</p><p><strong>Test:</strong></p><p>1 Test with an amount that can not be constructed using the given denominations.</p><p>2 Test with an even amount and all odd denominations/ one odd denomination. Likewise an odd amount and all even denominations.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/903572591f016ea5be11906f2acad3dd/href">https://medium.com/media/903572591f016ea5be11906f2acad3dd/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since we iterate through the loop of amount size and coins array size, therefore time complexity is T O(amt * coins). Space complexity is given by S O(amt), the size of the dp array.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ad9ef6da3fc3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Intersection of Two LinkedLists]]></title>
            <link>https://medium.com/@harycane/intersection-of-two-linkedlists-e6c25ae41c8?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/e6c25ae41c8</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Mon, 16 Jul 2018 03:10:41 GMT</pubDate>
            <atom:updated>2018-07-16T03:10:41.565Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/intersection-of-two-linked-lists/description/">Intersection of Two Linked Lists - LeetCode</a></p><p><strong>Example:</strong></p><p>Write a program to find the node at which the intersection of two singly linked lists begins.</p><p>For example, the following two linked lists:</p><pre>A:          a1 → a2<br>                   ↘<br>                     c1 → c2 → c3<br>                   ↗            <br>B:     b1 → b2 → b3</pre><p>begin to intersect at node c1.</p><p>Notes:</p><ul><li>If the two linked lists have no intersection at all, return null.</li><li>The linked lists must retain their original structure after the function returns.</li><li>You may assume there are no cycles anywhere in the entire linked structure.</li><li>Your code should preferably run in O(n) time and use only O(1) memory.</li></ul><p><strong>Algorithm:</strong></p><p>1 Initialize two pointers tempA and tempB to headA and headB and iterate until respective next is not null, and compute the lengthA and lengthB of each of the given linked lists. At the end of iterating through each linked lists, if tempA and tempB do not refer to the same node, then we can assert that there has been no intersection at all and hence return false.</p><p>2 Assuming the program did not return and hence an intersection exists, find which is the larger length, and accordingly assign tempA reference to the larger linked list and compute the difference of length into a ‘diff’ variable. Now iterate until this diff variable becomes 0, advancing the tempA reference each iteration while progressively decrementing (oxymoron spotted!) the diff variable. This way, aside from ensuring that the loop does not plod along infinitely, we also ensure that at the end of the iteration, we tempA shall be pointing to the linked list at such a node such that the remaining length of the larger linked list would be the same as that of tempB, which is pointing to the head of the shorter linked list.</p><p>3 Now iterate until tempA is not equal to tempB, advancing both tempA and tempA in each iteration. Once the loop terminates, we have found the intersecting node, as pointed by either of tempA or tempB, so return either of them as resultant intersection of two given linked lists.</p><p><strong>Test:</strong></p><p>1 Test with two linked lists which are both null, or empty. Test with one of them being null or empty.</p><p>2 Test with two linked lists with unequal lengths. Test with two linked lists of equal lengths.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bff1b222016c0e54a8b811df18d8bfb7/href">https://medium.com/media/bff1b222016c0e54a8b811df18d8bfb7/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since we iterate through each of the given two linked lists to determine the intersection node, therefore time complexity is given by T O(m + n) where m and n are the number of nodes in each of the given linked lists respectively. Since we do not use any auxiliary space therefore space complexity is S O(1).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e6c25ae41c8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Word Break]]></title>
            <link>https://medium.com/@harycane/word-break-4da79fedcf43?source=rss-5bfffd10375c------2</link>
            <guid isPermaLink="false">https://medium.com/p/4da79fedcf43</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Hary Krishnan]]></dc:creator>
            <pubDate>Mon, 16 Jul 2018 02:46:58 GMT</pubDate>
            <atom:updated>2018-07-16T02:46:58.824Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://leetcode.com/problems/word-break/description/">Word Break - LeetCode</a></p><p><strong>Example:</strong></p><p><strong>Given a non-empty string </strong><em>s</em> and a dictionary <em>wordDict</em> containing a list of non-empty words, determine if <em>s</em> can be segmented into a space-separated sequence of one or more dictionary words.</p><p>Note:</p><ul><li>The same word in the dictionary may be reused multiple times in the segmentation.</li><li>You may assume the dictionary does not contain duplicate words.</li></ul><p>Example 1:</p><pre>Input: s = &quot;leetcode&quot;, wordDict = [&quot;leet&quot;, &quot;code&quot;]<br>Output: true<br>Explanation: Return true because &quot;leetcode&quot; can be segmented as &quot;leet code&quot;.</pre><p>Example 2:</p><pre>Input: s = &quot;applepenapple&quot;, wordDict = [&quot;apple&quot;, &quot;pen&quot;]<br>Output: true<br>Explanation: Return true because &quot;applepenapple&quot; can be segmented as &quot;apple pen apple&quot;.<br>             Note that you are allowed to reuse a dictionary word.</pre><p>Example 3:</p><pre>Input: s = &quot;catsandog&quot;, wordDict = [&quot;cats&quot;, &quot;dog&quot;, &quot;sand&quot;, &quot;and&quot;, &quot;cat&quot;]<br>Output: false</pre><p><strong>Algorithm:</strong></p><p>1 This problem makes for a case of applying dynamic programming. Lets assume a boolean 1D dp array of size s.length() + 1. If index = s.length() in this array is true, then it implies the given input string s can be segmented into space separated sequence of words that exist in the given dictionary.</p><p>2 In order to determine whether dp[s.length()] is true, which is a huge composite problem, we break it down into sub problems with recurrence relationship. Therefore we try to find whether there exists a j &lt; s.length such that substring from 0 to j can be further segmented into space separated sequence of dictionary words (as given by dp[j] = true) and substring j+1 to s.length() is contained in the dictionary as a valid word. Notice that again to determine whether substring from 0 to j can be further segmented into a space separated sequence of dictionary words, we apply dynamic programming and further split that subproblem into smaller subproblem to test the above condition.</p><p><strong>Test:</strong></p><p>1 Test with words that cannot be segmented into space separated dictionary words.</p><p>2 Test with words that can be segmented into multiple combinations of space separated dictionary words.</p><p>3 Test with words that reuse dictionary words in order to be split into space separated dictionary words.</p><p><strong>Solution:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4d1a9bfdffb385b468016de595536056/href">https://medium.com/media/4d1a9bfdffb385b468016de595536056/href</a></iframe><p><strong>Complexity Analysis:</strong></p><p>Since for each incremental length upto the string length, we iterate twice implicitly, therefore the time complexity is T O(n²) in the worst case. Space complexity is S O(n), auxiliary space needed to construct the dp array.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4da79fedcf43" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>