<?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 Riddhi Dutta on Medium]]></title>
        <description><![CDATA[Stories by Riddhi Dutta on Medium]]></description>
        <link>https://medium.com/@rite2riddhi?source=rss-7a4482d58c13------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*m9-aP_R3vcjZABhg.jpg</url>
            <title>Stories by Riddhi Dutta on Medium</title>
            <link>https://medium.com/@rite2riddhi?source=rss-7a4482d58c13------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 15:17:18 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@rite2riddhi/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[The Resume that got me into FAANG.]]></title>
            <link>https://rite2riddhi.medium.com/the-resume-that-got-me-into-faang-ca168ac15df2?source=rss-7a4482d58c13------2</link>
            <guid isPermaLink="false">https://medium.com/p/ca168ac15df2</guid>
            <category><![CDATA[resume]]></category>
            <category><![CDATA[cv]]></category>
            <category><![CDATA[resume-writing]]></category>
            <category><![CDATA[cv-writing]]></category>
            <category><![CDATA[faang]]></category>
            <dc:creator><![CDATA[Riddhi Dutta]]></dc:creator>
            <pubDate>Tue, 10 Nov 2020 17:28:42 GMT</pubDate>
            <atom:updated>2020-12-23T20:41:23.157Z</atom:updated>
            <content:encoded><![CDATA[<h3>THE RESUME THAT GOT ME INTO FAANG !!</h3><p>Applying to companies but not getting shortlisted?</p><p>Hang on , maybe I have the solution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/868/0*XEunYuNFFpuK4W0n.jpg" /></figure><p>I had faced this similar situation a couple of months back, but then I spent some time structuring out my resume.</p><p>And guess what , not only my resume got shortlisted after applying but also I got calls from the recruiter even without applying.</p><p>Now let’s drill down a bit into what should be there in your resume</p><p>1. <strong>Experience — </strong>Here you can include your internships and current company you are working for. Make sure you include your roles and responsibilities in the team. The company is more interested to see <strong>What have you done </strong>instead of <strong>What Your Organization/Team Does</strong>. Use action verbs like improved , optimized , managed etc. ( Read more <a href="https://www.thebalancecareers.com/top-words-to-include-and-avoid-in-your-resume-2063329">here</a>). Try to emphasize on what impact you had on your team. The interviewer will focus more on your roles and responsibilities. Also make sure you know the project architecture really well.</p><p>2. <strong>Projects </strong>— Include at least 2 good projects that you can talk about confidently in an interview. Make sure you know those projects in and out. It’s better to avoid saying to the interviewer that I didn’t do this part and hence I am not aware of.</p><p>Also , identify that what and how you could have done better. The interviewer might ask you the shortcomings of your project and will also enquire that how could you improve it. Don’t give answers like “I don’t think it can be improved further” , “There are no shortcomings” etc as there is always room for improvement. That will make you sound arrogant.</p><p>Make sure you have an answer to justify the tech stacks and frameworks you have used. Like let’s say , you used Java and Spring framework in order to develop a web application , then expect questions like “Why Java &amp; Spring?” and “Why not Python &amp; Django?”. A bad way to answer this question is “Because I knew Java and not Python.” You have to give proper justifications that made you to choose a particular tech stack , like “I preferred SQL over NoSQL because I needed to ensure ACID properties.”</p><p><strong>Achievements :- </strong>Include achievements related to your field as the company is not bothered to see whether you stood first in a relay race or won a music competition. Also quantify your achievements. Like instead of saying “stood 1st in XYZ competition” , state, “Rank 1 out of 3000 participants in XYZ competition”. It makes a greater impact and helps the recruiter to understand your potential.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*mvuG2PZSsaUz_IgQfxHkHw.png" /></figure><p><strong>Coding Profiles &amp; Social Links</strong> :- Make sure to link your competitive coding profiles and mention your Max Rating in those platforms. Also link your Github and Linkedin profile.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/378/1*U1_Et2egfC9IFJe8IM6zhg.png" /></figure><p><strong>Education : </strong>Mention your college from where you got your degree. I feel there is no need to mention your CGPA if it is on the lower side and you have at least an year of experience. Try to highlight the strong points and omit the weak links.</p><p><strong>Skills </strong>: Include the languages and tech stacks you have worked upon and are familiar with. Also attribute how comfortable you are with those languages and frameworks. (Like Wrote Over 5000 lines of codes in JAVA , or give a rating meter.) Don’t include subjects like DBMS , OOPS etc. over here as that would go in your <strong>Coursework </strong>section.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/370/1*10UGJJ5OJPQBFy7ojpELxQ.png" /></figure><p><strong>Extra-Curricular</strong> — This is an optional section and include only if you have place left to fill. Also include activities that are more related.</p><p>Keep your Resume neat and clean. Try to fit everything in 1 page. Remember your Resume should strike an impression at one glance.</p><p>Last but not the least , as Prabhudeep Singh says , name your Resume File properly. Don’t name it “Resume.pdf” or “CV.pdf” and instead “Riddhi Dutta-1 YOE-Backend-Developer.pdf”.</p><p>You can find some awesome templates over <a href="https://www.overleaf.com/latex/templates/tagged/cv">here</a>.</p><p>Hope it helps.</p><p>Feel free to connect with me over <a href="https://www.linkedin.com/in/riddhi-dutta-698910129/">LinkedIn </a>or <a href="https://www.instagram.com/code.blooded.voyager/">Instagram </a>for any further queries.</p><p>Also checkout my <a href="https://www.youtube.com/channel/UCKyTTBdDH3I635HQMrPvz_A">YouTube Channel.</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ca168ac15df2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[TCS Codevita Interview Experience 2018]]></title>
            <link>https://rite2riddhi.medium.com/tcs-codevita-interview-experience-2018-81ff9ce28fbb?source=rss-7a4482d58c13------2</link>
            <guid isPermaLink="false">https://medium.com/p/81ff9ce28fbb</guid>
            <dc:creator><![CDATA[Riddhi Dutta]]></dc:creator>
            <pubDate>Tue, 01 Sep 2020 13:04:27 GMT</pubDate>
            <atom:updated>2020-12-23T20:42:29.885Z</atom:updated>
            <content:encoded><![CDATA[<h3>About TCS — Codevita</h3><p><strong>TCS CodeVita</strong>, is a contest for engineering and science students to experience the joy of coding and to sharpen their programming skills through real-life computing practices. The contest also aims at identifying the talent, besides providing the student community, an opportunity to earn peer recognition.</p><p>It is an ideal opportunity to get into TCS and earn yourself a direct interview chance without having to sit for the TNQT(TCS National qualifier Test). Even if you fail in the Codevita Interview, you will get another chance to have a go through TNQT.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/628/0*QBEExW7WH8_OKSfm" /></figure><h3>Codevita Pre Qualifier Round</h3><p>You will be given 6 questions to solve within a 6 hour time frame. If you solve at-least 1 question , you will earn an interview chance with them. If you are conversant with competitive coding , cracking one question should not be much difficult for you. TCS Codevita focuses a lot on dynamic programming and maths based problems , so make sure to be prepared with that. Also I would recommend to give the Mockvita which usually happens a few weeks before the original contest , so that you get a feel about the competition.</p><p><em>Note : Presentation error is equivalent to a correct answer. So if you get such kind of error after submitting your solution , don’t waste your time and move on to the next solution.</em></p><h3>TCS Codevita Interview</h3><p>After around 10 days from the original contest , the results were announced , and the interviews happened after a week. We were called to TCS campus where the interviews took place . Make sure to carry all the necessary documents as they are very particular with that. Interviews might go on till 8 PM, so just keep your patience.</p><p>My interview happened for more than an hour . There were 2 interviewers in the panel. After giving a brief introduction about myself , I was asked to explain the solution of the question that I successfully solved in the qualifier round. They also asked me the approaches of the questions which I couldn’t solve.( so be prepared with that).</p><p><em>Questions asked to me from JAVA included :</em></p><ul><li>Explain encapsulation with an example</li><li>What is an abstract class and can they be extended?</li><li>What is the difference between abstract class and interface?</li><li>What are final classes? Can they be extended?</li><li>What are the different ways to handle exception in java?</li><li>What is Just In Time Compiler?</li><li>What is bytecode?</li><li>What is the difference between static and runtime polymorphism ? Explain with an example</li><li>What is this and super keyword?</li></ul><p><em>Questions asked to me from C included :</em></p><ul><li>What are pointers?</li><li>What is the difference between structure and union?</li><li>Write a program in C to copy one file from another.</li><li>What are different types of storage classes in C?</li></ul><p><em>Questions asked to me from DBMS included :</em></p><ul><li>What is a primary key?</li><li>How many types of relationships are possible?</li><li>What is a recursive relationship?</li><li>Why is normalisation necessary and what is denormalisation?</li><li>Why are indexes needed?</li><li>What are triggers?</li></ul><p>At the end , I was asked whether I have worked with A.I , Machine Learning or Mean stack , and also they were checking whether I have knowledge about recent technologies.</p><p>In between I was also asked some behavioural questions , as my HR Round didn’t happen separately.</p><p>After a week , I received an OFFER.</p><p><em>TIPS : T.C.S usually focuses a lot on your resume so make sure you are prepared on the topics from your resume. Since I had mentioned , JAVA , C , Data Structures , DBMS in my resume , I was mostly asked questions from there.</em></p><p>If you have any further questions , you can connect with me on <a href="https://www.linkedin.com/in/riddhi-dutta-698910129/">Linkedin</a> or <a href="https://www.instagram.com/code.blooded.voyager/">Instagram</a>.</p><p>Also checkout my <a href="https://www.youtube.com/channel/UCKyTTBdDH3I635HQMrPvz_A">YouTube Channel.</a></p><p>Hope it helps.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=81ff9ce28fbb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Calvin’s Game INOI problem fully explained with solution (EDITORIAL) (1D — DP)]]></title>
            <link>https://rite2riddhi.medium.com/calvins-game-inoi-problem-fully-explained-with-solution-editorial-1d-dp-dbad21025749?source=rss-7a4482d58c13------2</link>
            <guid isPermaLink="false">https://medium.com/p/dbad21025749</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[inoi]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[editorials]]></category>
            <category><![CDATA[codechef]]></category>
            <dc:creator><![CDATA[Riddhi Dutta]]></dc:creator>
            <pubDate>Fri, 22 May 2020 14:02:15 GMT</pubDate>
            <atom:updated>2020-12-23T20:43:00.780Z</atom:updated>
            <content:encoded><![CDATA[<h3>Calvin’s Game INOI problem fully explained with solution (EDITORIAL) (1D — DP)</h3><p><a href="https://www.codechef.com/INOIPRAC/problems/INOI1301"><strong>Problem in Short</strong></a><strong> :</strong></p><p>You are given an array a of length N. You start at position k. In the forward phase, you make jumps of size 1 or 2 towards the right. Then in the backward phase, you make jumps of size 1 of 2 towards the left till you reach position 1. Your score is the sum of the values in the array where you landed after each jump. What is the maximum score you can make?</p><p><strong>Explanation:</strong></p><p>Before starting reading the explanation I would suggest you to click on the problem link and read the full problem.</p><p>Cool, so let’s get started.</p><p><em>So , programmatically we can consider this as an 1-D array with index from 1 to N where each index represent a square.</em></p><p><strong>Throughout the problem assume 1 based indexing.</strong></p><p>From index K you can move forward 0 or more steps, and then you have to reach index 1 by taking backward step(s). Since we have to take the maximum sum possible so we have to choose the array elements in an optimal manner. The first thing that comes to our mind is to take all the positive numbers and skip the negative numbers.</p><p>Let’s say our array consists of 2 3 -5 7 -8 and we start from index 1. Therefore I will jump to index 2 ,then index 4 then come back to index 2 again finishing at index 1. Thus we get the sum 15 (3+7+3+2) which is the maximum sum possible.</p><p>But lets say we have an array 2 3 -5 -1 8 and start from index 1. Is it possible to take ONLY positive numbers? Yes obviously but in this case you will go to index 2 and and then come back to index 1 with sum = 5. But I can give you a greater sum. I will go to index 2 and then index 4 then index 5 come back to index 4, index 2 and eventually index 1 with a sum 14. So always taking ONLY positive number’s wont help. You can also assume a case where there are negative numbers only. So it seems that this approach won’t help.</p><p>So? Seems like there is no greedy solution to this and we have to try out each and every combination of choosing each step.</p><p>So at every step we have 4 options, either to go 1 step ahead or 2 steps ahead. We can also go 1 step back or 2 steps back, but <strong>once we start going backwards we cant move forward anymore.</strong></p><p>So let’s break down this problem into 2 parts.</p><p>Let’s find out that if we go forward from index ‘K’ what is the maximum sum possible to reach an index ‘i’ and also what is the maximum sum we can achieve in going back from index ‘i’ to 1.</p><p>For example say an array 5 3 -2 1 -1 and we start from index 1. So the maximum sum we can achieve starting from 1 is 4 and we end at index 4. So we will add 4 to maximum sum achieved if we go backwards from position 4.</p><p>So we will first think about the forward solution.</p><p>So at every point we have two choices, go 1 step ahead or go 2 steps ahead (obviously keeping the boundary in mind). and while choosing the current step out of these 2 options, I will take that step having maximum sum from these 2 steps.</p><p>We can sense we will need recursion, because we have to check for all possible combinations. But recursion will not pass all the test cases therefore we need to optimise it.</p><p>Now let’s see how can we do that.</p><p>Suppose I start from index 1 and go to index 2,3,4 updating the sum. From 4 we calculate the maximum sum that can be achieved if we go backwards from 4 to 1 and add that to our forward sum from index 1 to index 4 . Now for the same array if we try another combination say , we start from index 1 and go to index 3 then index 4(skipping index 2 this time), then again from index 4 we have to calculate the maximum sum that can be achieved if we go backwards from 4 to 1. So there is a repeated calculation. If we had somehow stored the result of maximum sum that can be achieved if we go backwards from index 4 to index 1 beforehand we could have saved the repeated calculation. Hence we need to first precompute that for every index ‘i’ what is the maximum sum achievable if we go backwards from index ‘i’ to 1 to save time. How do we do this?</p><p>We have to do this in the best way possible..Going by the constraints we have to come up with an 0(N) solution.</p><p>Now this is achievable. Let’s see how. If I am at index ‘i’ I have two choices, to go 1 step back or go 2 steps back. So the optimal choice at ‘i’ will be to either take a[i-1] and then add the maximum sum achievable from index i-1 to 1. Or take a[i-2] and then add the maximum sum achievable from index i-2 to 1. I will take the maximum of these two. Please note I will note add the current value i.e a[i] to backward[i] because if I got from index ‘i’ to index ‘j’ only score of index ‘j’ will be added to the total score. So maximum sum achievable from index ‘i’ to 1 can be calculated as,</p><p>backward[i] = max(a[i-1]+backward[i-1], a[i-2]+backward[i-2]) Please note that backward[i-1] and backward[i-2] will be computed beforehand when I will be calculating backward[i] and therefore I save repeated calculation by memoizing it. Again this backward[i] will be needed when I will be calculating for backward[i+1] and backward[i+2] states.</p><p>Now consider the base cases. Suppose I am at the first Index. In that case I have already reached my destination. Hence backward[1] will always be equals to 0. Also if I am at index 2, I have only 1 option, ie to go to index 1 and finish. Hence backward[1] = a[1]. I am calculating for index 1 and 2 separately just to ensure that array index doesn’t go out of bounds. More realistically when I am index 1 I have no option. And when I am at index 2 I have only one option i.e 1 step backward instead of 2 options.</p><p>So to sum up , I will calculate backward array like this</p><p>backward[1] = 0; if(n&gt;=2)</p><p>backward[2] = a[1]; for(i=3;i&lt;=N;i++)</p><p>backward[i] = max(a[i-1]+backward[i-1],a[i-2]+backward[i-2]);</p><p>Ok so what’s next?</p><p>Coming back to our forward move, now we have to make an optimal move in O(n) starting from index ‘k’. Again we have two choices , go 1 step ahead or go 2 steps ahead. But we have to also keep in mind we have to go backwards as well at some point of time from some index and can’t just keep moving forward only. Hence if we somehow keep another array like backward array say endForwardAtIndex where endForwardAtIndex[i] will denote the maximum sum achievable from index ‘k’ to index ‘i’ and with backward[i] stored we can easily figure out what is the maximum sum achievable if I finish my forward move at index ‘i’ starting from index ‘k’ and then move backwards all the way till 1. This will be achieved by endForwardAtIndex[i] + backward[i].</p><p>So if we have this endForwardAtIndex and backward array ready, How can we find the answer ? Well it will be max (endForwardAtIndex[i] + backward[i]) where ‘i’ will range from k to n.</p><p>How?</p><p>Because think for a moment, I just said endForwardAtIndex[i] + backward[i] denotes that if I end my forward move at index ‘i’ and with the maximum sum achievable from index ‘i’ to 1 by going backwards ready, I can find out what is the maximum sum achievable if I end my forward move at index ‘i’ and then going back to index 1. In short I can figure out what is the maximum sum if I end my forward move at index ‘i’.</p><p>Since I start from index ‘k’ the minimum index where I can end my forward move is at index ‘k’ itself.(this will denote a case where I don’t take any forward move at all and only go backwards). Similarly the maximum index I can end my forward move is at index ’n’ i.e last index. Hence maximum of all endForwardAtIndex[i] + backward[i] will give us the required answer where I = k to n. Because only within these indices I can end my forward move and once I have ended at index ‘i’ I have in store the maximum sum that can be achieved from index ‘i’ all the way to 1 in backward[i], therefore I can figure out that if I end my forward move at index ‘i’ what is the maximum sum achieved.</p><p>So if we can somehow calculate the endForwardAtIndex in O(n) we are done .</p><p>So what are the base cases?</p><p>Say we want to end our forward move at index K. (i.e we are not moving forward at all and only moving backward) the maximum sum achieved going in forward direction is 0. Hence total sum achieved = 0 + backward[k] .</p><p>Again if we want to end our forward move at index K+1 , the maximum sum achieved from index K to index K+1 can only be a[k+1]</p><p>Now for index k+2 onwards,</p><p>endForwardAtIndex[i] = a[i] + max(endForwardAtIndex[i-1],endForwardAtIndex[i-2])</p><p>Why? Because if we are ending at index ‘i’, we must consider the element at index ‘i’ and have two choices actually. I can either come to index ‘i’ from index i-1 or from index ‘i-2’. So which one I will add to a[i]? Obviously the maximum sum from these 2 ,isn’t it?. I will only add the maximum sum of these 2 paths to a[i].</p><p>In this way we can calculate endForwardAtIndex array.</p><p>There is one small thing to keep in mind: endForwardAtIndex[i] considers the current element whereas backward[i] doesn’t considers the current element. If you go and check the code of my backward[i] I am not adding a[i] to backward[i] but in endForwardAtIndex[i] I am adding a[i] to it. Why this is so?</p><p>Consider this array 2 4 5 7 1 and lets say I am checking the maximum sum achieved if I end my forward move at index 4 starting from index 2. endForwardAtIndex[4] = 5+7 = 12.Then I will add it with backward[4]. Now had I considered a[i] or current element in backward[i] , backward[4] would have yielded 18. And hence endForwardIndex[4] + backward[4] would have yielded 12 + 18 or rather 5 + 7 + 7 + 5 + 4 + 2. Check that 7 is being added 2 times but that should not be the case. Once I have reached index 4 and added 7 to my sum , I cant include 7 anymore if I am starting a backward move from it. Because if I go from index ‘i’ to index ‘j’ only the value of index ‘j’ gets added.</p><p>Therefore I wont consider a[i] in backward[i] as I have already considered the last element in endForwardAt[i].</p><p><strong>Algorithm</strong></p><p>n = size of the array a = array</p><p>// computing the backward array first</p><p>backward[1] = 0; if(n&gt;=2)</p><p>backward[2] = a[1]; for(i=3;i&lt;=n;i++)</p><p>backward[i] = max(a[i-1]+backward[i-1],a[i-2]+backward[i-2]);</p><p>//computing the endForwardAtIndex array endForwardAtIndex[k] = 0; if(k+1&lt;=n)</p><p>endForwardAtIndex[k+1] = a[k+1]; for(ll i=k+2;i&lt;=n;i++)</p><p>endForwardAtIndex[i] = a[i] + max(endForwardAtIndex[i-1],endForwardAtIndex[i-2]);</p><p>// computing the maximum with the help of 2 arrays</p><p>maximum =-INF; // lowest possible value for(i=k;i&lt;=n;i++)</p><p>maximum = max(maximum , endForwardAtIndex[i] +backward[i]);</p><p>print(maximum)</p><p>Since we calculated values based on pre computed values and saved repeated calculation, algorithm paradigm used here is Dynamic Programming. But I didn’t mention the word DP throughout this blog because I wanted to keep it simple and realistic. Often people get intimidated by this terms Dp, Graphs and all. So its a try to make them realise these things are very realistic and actually not that tough as we think it is.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*a3S-EHGb2wXKqm9h0cFaxA.jpeg" /></figure><p>If you like my post , do not hesitate to give a clap. It MATTERS and serves as a motivation to write more posts like these.</p><p>Also checkout my <a href="https://www.youtube.com/channel/UCKyTTBdDH3I635HQMrPvz_A">YouTube Channel.</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dbad21025749" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Decoding Cycles in an Array]]></title>
            <link>https://rite2riddhi.medium.com/decoding-cycles-in-array-34ce7d2d4a15?source=rss-7a4482d58c13------2</link>
            <guid isPermaLink="false">https://medium.com/p/34ce7d2d4a15</guid>
            <category><![CDATA[google]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Riddhi Dutta]]></dc:creator>
            <pubDate>Fri, 15 May 2020 17:49:31 GMT</pubDate>
            <atom:updated>2020-12-23T20:43:35.939Z</atom:updated>
            <content:encoded><![CDATA[<h3>Decoding Cycles in an Array !</h3><h4>CIRCULAR ARRAY LOOP , LEETCODE 457.( EXPLAINED WITH FULL WORKING CODE !)</h4><p>QUESTION</p><p>You are given a <strong>circular</strong> array nums of positive and negative integers. If a number <em>k</em> at an index is positive, then move forward <em>k</em> steps. Conversely, if it&#39;s negative (-<em>k</em>), move backward <em>k</em> steps. Since the array is circular, you may assume that the last element&#39;s next element is the first element, and the first element&#39;s previous element is the last element.</p><p>Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle&#39;s length &gt; 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.</p><p><strong>Example 1:</strong></p><pre><strong>Input:</strong> [2,-1,1,2,2]<br><strong>Output:</strong> true<br><strong>Explanation:</strong> There is a cycle, from index 0 -&gt; 2 -&gt; 3 -&gt; 0. The cycle&#39;s length is 3.</pre><p><strong>Example 2:</strong></p><pre><strong>Input:</strong> [-1,2]<br><strong>Output:</strong> false<br><strong>Explanation:</strong> The movement from index 1 -&gt; 1 -&gt; 1 ... is not a cycle, because the cycle&#39;s length is 1. By definition the cycle&#39;s length must be greater than 1.</pre><p><strong>Example 3:</strong></p><pre><strong>Input:</strong> [-2,1,-1,-2,-2]<br><strong>Output:</strong> false<br><strong>Explanation:</strong> The movement from index 1 -&gt; 2 -&gt; 1 -&gt; ... is not a cycle, because movement from index 1 -&gt; 2 is a forward movement, but movement from index 2 -&gt; 1 is a backward movement. All movements in a cycle must follow a single direction.</pre><p><strong>Note:</strong></p><ol><li>-1000 ≤ nums[i] ≤ 1000</li><li>nums[i] ≠ 0</li><li>1 ≤ nums.length ≤ 5000</li></ol><p><strong>Follow up:</strong></p><p>Could you solve it in <strong>O(n)</strong> time complexity and <strong>O(1)</strong> extra space complexity?</p><p>ASKED IN</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bmXikHcuHQ9_H2piIEGdEQ.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/281/1*j9JA7YhF9Uhv4QqXvzo8_Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/409/1*GYNJSrUXYq7gDoP-6QSDSw.png" /></figure><h3><strong>Explanation</strong></h3><p>So at first , we have to comprehend what are the factors that do not make a cycle in the array.</p><ol><li>The cycle must start and end at the same index of the array but the cycle length should be &gt; 1.</li></ol><p>Now what is cycle length ?</p><p>Cycle length is the number of elements present in the cycle.</p><p>For eg if the array is [ 2 , 1 , 1 ] , then the cycle consists of elements [ 2 , 1 ] and hence the cycle length is 2 which is a valid cycle.</p><p>So the only possible scenario where the cycle length can be 1 is</p><p>WHEN</p><p>arr[start] % arr.length == 0 ,</p><p>where ‘arr’ is the array and start is the start index of the cycle.</p><p>Let’s consider an example for this.</p><p>Let arr = [ 2 , 6, -1] . Here , if we start from index 1 ( consider 0 based indexing ) , then we end up at index 1 every-time , making our cycle length 1.</p><p>So all the indices having arr[index] % arr.length == 0 should be avoided.</p><p>2. The cycle should only proceed in one direction i.e either forward or backward.</p><p>This is pretty easy to understand.</p><p>Logically</p><p>if arr[start] &lt; 0 ,then , arr[index] should be &lt; 0 where index denotes all the</p><p>indices in the same cycle path from ‘start’ index.</p><p>OR</p><p>if arr[start] &gt; 0 ,then , arr[index] should be &gt;0 where index denotes all the</p><p>indices in the same cycle path from ‘start’ index</p><p>So we will write a function to check if a cycle is valid or not like below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/615/1*PacmJpr-kAIm0DaZqEMxSw.png" /><figcaption>Function to check whether a cycle is valid or not</figcaption></figure><p>3. A cycle must start and end at the same index. This condition is obviously not a big headache if we think a bit logically.</p><p>Let’s say we start from an index ‘i’ in the array , mark every node as visited ( in a boolean array named visited where visited[index] = true if it is already being visited) and if we again come across a visited node , then there is definitely a cycle with starting point equals to the node which is just being visited again. ( Just make sure the cycle conditions hold valid. i.e case 1 and 2).</p><p>But hang on.</p><p>When we hit a visited node , how are we sure that this node was visited in the current cycle ? It may also be the case that the node that I just visited again was visited before in a previous cycle traversal which I discarded because the cycle condition was not met. Hence only marking true or false in the visited array won’t be enough. We have to leave a mark of our starting node in every next node that we would visit by making visited[cur_index] = start_index , and if I visit an index where visited[cur_index] is already equals to start index , then I know that I have already visited this index before , and most importantly in my CURRENT cycle. An unvisited index can be set to INFINITY to mark it NOT visited initially. We won’t start our mission to find a cycle from any visited index as start index because that is practically of no use and would increase our time complexity as well .</p><p>A small observation : If the array contains only positive or negative elements and all the array elements % arr.length != 0 then , there will always be a cycle.</p><p>Now we are using an extra space of O(N) where N is the length of the array by using a visited array. This can be avoided by being a little smart and marking the indices in place (in the array itself).</p><p>How?</p><p>If we look carefully at the constraints , the maximum value that the array can contain is 1000 and the minimum value is -1000. So when we visit an index if we set the arr[index] to some value outside of this domain , then we will be able to understand that this index has already been visited. But we also need to find the start index from which it was visited. Hence , to mark an index visited</p><p>We set,</p><p>arr[index] = minDomain -start — 1 (if arr[index &lt; 0 ) ,</p><p>or</p><p>arr[index] = maxDomain + start + 1. (if arr[index] &gt; 0).</p><p>In this way we avoid taking the extra visited array and mark visited in place also leaving the trace of the start position of the current cycle. Along the path of the cycle we leave traces of the start of the current cycle so that when we hit a visited node we are sure that this node was visited from the current cycle itself.</p><p>If we visit a node which is already being visited but not a part of the current cycle then we can safely break out, as the path from there is already seen before and we know that does not lead to a valid cycle . Had it lead to a valid cycle we would have already returned ‘true’ by now and would not have been checking for the current cycle.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qQ0z_rPjdywJ9ASemBw1yw.png" /><figcaption>Full working code.</figcaption></figure><p>Time Complexity : O(N)</p><p>Space Complexity : O(1)</p><p>Please note that in line 27 of the above code , I have made nums[index] = nums[index] % n , where n is the length of the ‘nums’ array. This is done so that the array index does not go out of bounds when there are negative numbers.</p><p>Consider this case [- 5 , 1 ].</p><p>Here next index would be (0–5+2) % 2 = -1 which is not a valid index.</p><p>Check out the problem at this <a href="https://leetcode.com/problems/circular-array-loop/">link</a>.</p><p>Also checkout my <a href="https://www.youtube.com/channel/UCKyTTBdDH3I635HQMrPvz_A">YouTube Channel.</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=34ce7d2d4a15" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Decoding the Hare-Tortoise Algorithm for detecting loop in a Linked List in a very simpler fashion…]]></title>
            <link>https://rite2riddhi.medium.com/decoding-thehare-tortoise-algorithm-for-detecting-loop-in-a-linked-list-in-a-very-simpler-fashion-db491efa22b4?source=rss-7a4482d58c13------2</link>
            <guid isPermaLink="false">https://medium.com/p/db491efa22b4</guid>
            <category><![CDATA[linked-list-cycle]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[singly-linked-list]]></category>
            <category><![CDATA[floyd-warshall]]></category>
            <dc:creator><![CDATA[Riddhi Dutta]]></dc:creator>
            <pubDate>Fri, 08 May 2020 07:33:17 GMT</pubDate>
            <atom:updated>2020-12-23T20:42:07.465Z</atom:updated>
            <content:encoded><![CDATA[<h3>Decoding the Hare-Tortoise Algorithm for detecting a loop in a Linked List in a very simpler fashion and understanding it’s time complexity !</h3><p>For detecting a cycle in a linked list , we use the hare tortoise or the famous Floyd Warshall Algorithm.</p><p>The algorithm states that there will be two pointers.</p><p>A hare pointer and a tortoise pointer.</p><p>As the name suggests , the hare pointer will move twice the speed of the tortoise pointer at a single iteration(Check code snippet below).</p><p>If there exists a cycle in the linked list, they will always meet at a point in the cycle.</p><p>But ever thought why it always works?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*HFR593dq0xCUmvGT.PNG" /><figcaption>Node 0 is the starting point of the cycle of the linked list</figcaption></figure><p>So in the above diagram, 0 is the starting point of the loop.</p><p>The hare will run 2 times the distance of the tortoise. So when they meet ,</p><p>distance covered by the hare = 2 * distance covered by the tortoise.</p><blockquote><strong>Why will they always meet if there is a cycle ?</strong></blockquote><p>After the hare has entered the cycle it will lag behind the tortoise , but it will catch up soon, since at every traversal , it is catching up with the tortoise by one node i.e their distance difference is decreasing by 1 with every traversal.</p><p>Now let us think differently. Let us assume that the tortoise is standing still and the hare is coming to him at a speed of 1. So the hare will catch up eventually , right?</p><p>The same thing is happening here. If you are considering relative speed and distance , actually the hare is coming to the tortoise at a speed of 1 while the tortoise is standing still. It is the same scenario of the hare moving by 2 and the tortoise by 1.</p><p>Now the time complexity to check whether there exists a loop or not and to find it’s intersection point is O(N + K) ~ O(N) where K is the length of the cycle.</p><blockquote><strong>Why?</strong></blockquote><p>Let’s suppose K is the length of the cycle. So at a certain point , after both the hare and the tortoise have entered the cycle , there will always come a point when the hare is behind the tortoise and will do a catching up.</p><p>So as I just explained , imagine the situation like this that the hare is moving at a speed of 1 node per traversal and the tortoise is standing still (that’s the same as the hare moving by 2 nodes and the tortoise by 1). Then at most , the hare has to traverse a maximum of K -1 distance to catch up with the tortoise. And prior to that the hare has traversed the entire list. Hence complexity is O(N+K) ~ O(N).</p><blockquote><strong>Now finding the start of the cycle</strong>.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ZHQVysgAwDAQR4sK.png" /></figure><blockquote>So let’s suppose</blockquote><blockquote>Start of linked list(head) = A</blockquote><blockquote>start of cycle = C</blockquote><blockquote>Intersection point = H.</blockquote><p>AC = F</p><p>CH = a</p><p>HF = b</p><p>Distance traversed by the hare when they both meet = F + a + b + a.</p><p>Distance traversed by the tortoise when they both meet = F + a.</p><p>Now we know that the distance traversed by the hare is twice as the distance traversed by the tortoise.</p><p>2(F+a) = F + a + b + a</p><p>2F + 2a = F + 2a + b</p><p>F = b.</p><p>Therefore distance from the head to the start of the cycle of the linked list = distance from the intersection point to the start of the cycle of the linked list.</p><p>Hence if we have one pointer stationed at head and another one at intersection point and they both move at the same speed , then they will both meet at C (starting point of the cycle) as they have the same distance.</p><p>Now time complexity for finding the intersection point as discussed above = O(N)</p><p>Time complexity for finding the start of the cycle = O(f) or O(b)</p><p>Hence total time complexity = O(N) + O(f) ~ O(N).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*KiZCvYNdK-8w56iYgieV2Q.png" /><figcaption>Working Code</figcaption></figure><p>Hope it helps.</p><p>Feel free to connect with me over <a href="https://www.linkedin.com/in/riddhi-dutta-698910129/">LinkedIn </a>or <a href="https://www.instagram.com/code.blooded.voyager/">Instagram </a>for any further queries.</p><p>Also checkout my <a href="https://www.youtube.com/channel/UCKyTTBdDH3I635HQMrPvz_A">YouTube Channel.</a></p><p>Image Credits : Leetcode.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=db491efa22b4" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>