<?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 Yiming Qu on Medium]]></title>
        <description><![CDATA[Stories by Yiming Qu on Medium]]></description>
        <link>https://medium.com/@yimingqu256?source=rss-dca40af24860------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*d8kMIpPLFHv0zaRbR-SbbA.jpeg</url>
            <title>Stories by Yiming Qu on Medium</title>
            <link>https://medium.com/@yimingqu256?source=rss-dca40af24860------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 10:23:42 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@yimingqu256/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[Solution to Fish]]></title>
            <link>https://medium.com/@yimingqu256/solution-to-fish-38a86f246776?source=rss-dca40af24860------2</link>
            <guid isPermaLink="false">https://medium.com/p/38a86f246776</guid>
            <category><![CDATA[codility]]></category>
            <dc:creator><![CDATA[Yiming Qu]]></dc:creator>
            <pubDate>Wed, 27 Nov 2024 10:15:56 GMT</pubDate>
            <atom:updated>2024-11-27T10:22:30.175Z</atom:updated>
            <content:encoded><![CDATA[<h3>Task description</h3><p>You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.</p><p>The fish are numbered from 0 to N − 1. If P and Q are two fish and P &lt; Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.</p><p>Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:</p><ul><li>0 represents a fish flowing upstream,</li><li>1 represents a fish flowing downstream.</li></ul><p>If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P &lt; Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:</p><ul><li>If A[P] &gt; A[Q] then P eats Q, and P will still be flowing downstream,</li><li>If A[Q] &gt; A[P] then Q eats P, and Q will still be flowing upstream.</li></ul><p>We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.</p><p>For example, consider arrays A and B such that:</p><p>A[0] = 4 B[0] = 0 A[1] = 3 B[1] = 1 A[2] = 2 B[2] = 0 A[3] = 1 B[3] = 0 A[4] = 5 B[4] = 0</p><p>Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.</p><p>Write a function:</p><blockquote><em>int solution(vector&lt;int&gt; &amp;A, vector&lt;int&gt; &amp;B);</em></blockquote><p>that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.</p><p>For example, given the arrays shown above, the function should return 2, as explained above.</p><p>Write an efficient algorithm for the following assumptions:</p><ul><li>N is an integer within the range [1..100,000];</li><li>each element of array A is an integer within the range [0..1,000,000,000];</li><li>each element of array B is an integer that can have one of the following values: 0, 1;</li><li>the elements of A are all distinct.</li></ul><h3>Solution</h3><pre>#include &lt;stack&gt;<br><br>// you can write to stdout for debugging purposes, e.g.<br>// cout &lt;&lt; &quot;this is a debug message&quot; &lt;&lt; endl;<br><br>int solution(vector&lt;int&gt; &amp;A, vector&lt;int&gt; &amp;B) {<br>    // Implement your solution here<br>    std::stack&lt;int&gt; downStream;<br>    int upStreamCount = 0;<br>    int n = A.size();<br><br>    for(int i = 0; i &lt; n; i++){<br>        if (B[i] == 1){<br>            downStream.push(A[i]);<br>        }else { <br>            while((!downStream.empty()) &amp;&amp; (downStream.top() &lt; A[i])){<br>                downStream.pop();<br>            }<br>            if(downStream.empty()){<br>                upStreamCount++;<br>            }<br>        }<br>    }<br><br>    int number = upStreamCount + downStream.size();<br>    return number;<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=38a86f246776" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solution for EquiLeader]]></title>
            <link>https://medium.com/@yimingqu256/solution-for-equileader-e777337aae65?source=rss-dca40af24860------2</link>
            <guid isPermaLink="false">https://medium.com/p/e777337aae65</guid>
            <category><![CDATA[code]]></category>
            <category><![CDATA[codility]]></category>
            <dc:creator><![CDATA[Yiming Qu]]></dc:creator>
            <pubDate>Sat, 24 Feb 2024 21:22:18 GMT</pubDate>
            <atom:updated>2024-02-24T22:33:04.645Z</atom:updated>
            <content:encoded><![CDATA[<h3>Task description</h3><p>A non-empty array A consisting of N integers is given.</p><p>The <em>leader</em> of this array is the value that occurs in more than half of the elements of A.</p><p>An <em>equi leader</em> is an index S such that 0 ≤ S &lt; N − 1 and two sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N − 1] have leaders of the same value.</p><p>For example, given array A such that:</p><p>A[0] = 4, A[1] = 3, A[2] = 4, A[3] = 4, A[4] = 4, A[5] = 2</p><p>we can find two equi leaders:</p><ul><li>0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.</li><li>2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.</li></ul><p>The goal is to count the number of equi leaders.</p><p>Write a function:</p><p><em>class Solution { public int solution(int[] A); }</em></p><p>that, given a non-empty array A consisting of N integers, returns the number of equi leaders.</p><p>For example, given:</p><p>A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2</p><p>the function should return 2, as explained above.</p><p>Write an efficient algorithm for the following assumptions:</p><ul><li>N is an integer within the range [1..100,000];</li><li>each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].</li></ul><h3>Solution:</h3><p>To solve this problem, we should recognize that the <em>leader</em> of the two sub-arrays is the same as that of the entire array. That is because firstly, according to the definition of <em>leader,</em> the <em>leader</em> of the entire array is unique. Secondly, given that the <em>leader</em> of the two sub-arrays is not the same as that of the entire array, and that means there is another <em>leader </em>in the two sub-arrays, denoting it as <em>leader_1 </em>while<em> </em>the entire array’s<em> leader </em>donated as<em> leader_0. </em>Suppose that <em>leader_0 </em>occurs <em>left_0</em> times in the left sub-array and <em>right_0</em> times in the right sub-array. Similarly, Suppose that <em>leader_1 </em>occurs <em>left_1</em> times in the left sub-array and <em>right_1</em> times in the right sub-array. According to the definition of <em>leader</em>, obviously, <em>left_1 &gt; left_0, right_1 &gt; right_0</em>, which means the occurrence of <em>leader_1</em> is greater than that of <em>leader_0</em> in the entire array, contradicting the fact that the <em>leader</em> of the entire array is unique. Therefore, <em>leader_1 == leader_0.</em></p><p>The following step is to count the occurrence of the left sub-array and right sub-array in each loop. To solve this, initially, we should find the total occurrence count of the <em>leader </em>in this entire array.</p><pre>def solution(A):<br>    # STEP 1: Find the leader of the entire array<br>    # The entire array, left sub-array, and right sub-array<br>    # share the same leader.<br>    elements_dict = {}<br>    leader = -1<br>    for i in A:<br>        elements_dict[i] = 0<br>    for i in A:<br>        elements_dict[i] += 1<br>        if elements_dict[i] &gt; int(len(A)/2):<br>            leader = i<br>    <br>    # STEP 2: Count the number of occurrences of &#39;Leader&#39;.<br>    leader_count = A.copy()<br>    count = 0<br>    for i in range(len(A)):<br>        if A[i] == leader:<br>            count += 1<br>        # leader_count[i] represents the number of occurrences of &#39;Leader&#39; <br>        # when iterating through the i-th element of the entire array.<br>        leader_count[i] = count <br><br>    equi_leader_number = 0<br>    <br>    # STEP 3: Count the number of equi leader<br>    for i in range(len(leader_count) - 1):<br>        left_length = i + 1<br>        right_length = len(leader_count) - left_length<br><br>        left_count = leader_count[i]<br>        right_count = count - left_count<br><br>        if left_count &gt; int(left_length/2) and right_count &gt; int(right_length/2):<br>            equi_leader_number += 1<br><br>    return equi_leader_number</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e777337aae65" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solution for MinAvgTwoSlice]]></title>
            <link>https://medium.com/@yimingqu256/solution-for-minavgtwoslice-97594643ddea?source=rss-dca40af24860------2</link>
            <guid isPermaLink="false">https://medium.com/p/97594643ddea</guid>
            <dc:creator><![CDATA[Yiming Qu]]></dc:creator>
            <pubDate>Mon, 06 Nov 2023 17:47:05 GMT</pubDate>
            <atom:updated>2023-11-06T21:42:40.086Z</atom:updated>
            <content:encoded><![CDATA[<h3>Task description</h3><p>A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P &lt; Q &lt; N, is called a <em>slice</em> of array A (notice that the slice contains at least two elements). The <em>average</em> of a slice (P, Q) is the sum of A[P] + A[P + 1] + … + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + … + A[Q]) / (Q − P + 1).</p><p>For example, array A such that:</p><p>A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8</p><p>contains the following example slices:</p><ul><li>slice (1, 2), whose average is (2 + 2) / 2 = 2;</li><li>slice (3, 4), whose average is (5 + 1) / 2 = 3;</li><li>slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.</li></ul><p>The goal is to find the starting position of a slice whose average is minimal.</p><p>Write a function:</p><blockquote><em>def solution(A)</em></blockquote><p>that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.</p><p>For example, given array A such that:</p><p>A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8</p><p>the function should return 1, as explained above.</p><p>Write an efficient algorithm for the following assumptions:</p><ul><li>N is an integer within the range [2..100,000];</li><li>each element of array A is an integer within the range [−10,000..10,000].</li></ul><h3>Analysis:</h3><p>The key to solve this task is these two patterns:</p><p>(1) All the longer slices are built up with these 2-element and/or 3-element small slices.<br>(2) There must be some slices, with length of <strong>2</strong> or <strong>3</strong>, having the minimal average value among all the slices.</p><p>According to the task description, (1) is very easy to understand. Let’s talk about (2).</p><p>First, we are <strong>NOT</strong> denying that, 4-or-more-element slices have the global minimal average. However, in a 4-or-more-element slice, you can find a 2-or-3-element slice that also has the global minimal average and it is obvious that a 4-or-more-element slice composed of 2-or-3-element slices. Let’s suppose that the number of 2-element slices is <em>p</em>, and the number of 3-element slices is <em>q.</em></p><pre>def solution(A):<br>    # Implement your solution here<br>    min_2 = 10001<br>    pos_2 = 0<br><br>    min_3 = 10001<br>    pos_3 = 0<br><br>    n = len(A)<br><br>    for i in range(n):<br>        if i &lt;= n-2:<br>            avg_2 = (A[i] + A[i+1])/2<br>            if min_2 &gt; avg_2:<br>                min_2 = avg_2<br>                pos_2 = i<br>        <br>        if i &lt;= n-3:<br>            avg_3 = (A[i] + A[i+1] + A[i+2])/3<br>            if min_3 &gt; avg_3:<br>                min_3 = avg_3<br>                pos_3 = i <br>    <br>    min_avg = min(min_2,min_3)<br><br>    pos = pos_2 if min_2 == min_avg else pos_3<br><br>    return pos</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=97594643ddea" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solution for CountDiv]]></title>
            <link>https://medium.com/@yimingqu256/solution-for-countdiv-9125688e3192?source=rss-dca40af24860------2</link>
            <guid isPermaLink="false">https://medium.com/p/9125688e3192</guid>
            <dc:creator><![CDATA[Yiming Qu]]></dc:creator>
            <pubDate>Sat, 04 Nov 2023 17:10:10 GMT</pubDate>
            <atom:updated>2023-11-04T17:10:10.800Z</atom:updated>
            <content:encoded><![CDATA[<h3>Task description</h3><p>Write a function:</p><blockquote><em>def solution(A, B, K)</em></blockquote><p>that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:</p><blockquote><em>{ i : A ≤ i ≤ B, i mod K = 0 }</em></blockquote><p>For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.</p><p>Write an efficient algorithm for the following assumptions:</p><ul><li>A and B are integers within the range [0..2,000,000,000];</li><li>K is an integer within the range [1..2,000,000,000];</li><li>A ≤ B.</li></ul><p>Solution:</p><pre>def solution(A, B, K):<br>    # Implement your solution here<br>    # divpoint: the point that is divisible by K<br>    start_flag = True if A%K == 0 else False <br>    start = A//K<br><br>    end_flag = True if B%K == 0 else False<br>    end = B//K<br><br>    <br>    if start_flag == False &amp; end_flag == False:<br>    # if both A and B are not the divpoint<br>        return end - start<br>    else:<br>    # if either A or B is the divpoint<br>        return end - start + 1</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9125688e3192" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solution for PassingCars]]></title>
            <link>https://medium.com/@yimingqu256/solution-for-passingcars-2604f5cc0857?source=rss-dca40af24860------2</link>
            <guid isPermaLink="false">https://medium.com/p/2604f5cc0857</guid>
            <dc:creator><![CDATA[Yiming Qu]]></dc:creator>
            <pubDate>Fri, 03 Nov 2023 15:58:08 GMT</pubDate>
            <atom:updated>2023-11-03T15:58:08.625Z</atom:updated>
            <content:encoded><![CDATA[<h3>Task description</h3><p>A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.</p><p>Array A contains only 0s and/or 1s:</p><ul><li>0 represents a car traveling east,</li><li>1 represents a car traveling west.</li></ul><p>The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P &lt; Q &lt; N, is passing when P is traveling to the east and Q is traveling to the west.</p><p>For example, consider array A such that:</p><p>A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1</p><p>We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).</p><p>Write a function:</p><blockquote><em>def solution(A)</em></blockquote><p>that, given a non-empty array A of N integers, returns the number of pairs of passing cars.</p><p>The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.</p><p>For example, given:</p><p>A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1</p><p>the function should return 5, as explained above.</p><p>Write an efficient algorithm for the following assumptions:</p><ul><li>N is an integer within the range [1..100,000];</li><li>each element of array A is an integer that can have one of the following values: 0, 1.</li></ul><p>Solution:</p><pre>def solution(A):<br>    # Implement your solution here<br>    length = len(A)<br>    end = length - 1<br>    init_sum = 0<br>    zero_count = 0<br><br>    for i in range(length):<br>        if A[i] == 0:<br>  # for each &#39;0&#39; in A, suppose all the succissive elements are &#39;1&#39;<br>            init_sum += (end - i)#(end - i) pairs<br>            zero_count += 1 #count the number of &#39;0&#39;<br><br>    excessive_sum = 0<br>  # for example,if [0,1,1,1,1] is changed to [0,1,0,1,1], we should subtract one pair<br>  # if [0,1,1,1,1] is changed to [0,1,0,0,1], we should subtract 1+2 pairs<br>  # because when &#39;1&#39; is replaced by &#39;0&#39;, all the &#39;0&#39; will lose a pair<br>  # for the first time, lose one pair, and the second time, lose two pairs.<br>    for i in range(0, zero_count):<br>        excessive_sum += i<br><br>    sum = init_sum - excessive_sum# subtract excessive value<br><br>    if sum &lt;= 1000000000 and sum &gt;= 0:<br>        return sum<br>    else:<br>        return -1</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2604f5cc0857" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solutions for MissingInteger]]></title>
            <link>https://medium.com/@yimingqu256/solutions-for-missinginteger-e85c5e2b5a67?source=rss-dca40af24860------2</link>
            <guid isPermaLink="false">https://medium.com/p/e85c5e2b5a67</guid>
            <dc:creator><![CDATA[Yiming Qu]]></dc:creator>
            <pubDate>Thu, 02 Nov 2023 10:59:02 GMT</pubDate>
            <atom:updated>2023-11-02T10:59:02.526Z</atom:updated>
            <content:encoded><![CDATA[<h3>Task description</h3><p>Write a function:</p><blockquote><em>def solution(A)</em></blockquote><p>that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.</p><p>For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.</p><p>Given A = [1, 2, 3], the function should return 4.</p><p>Given A = [−1, −3], the function should return 1.</p><p>Write an efficient algorithm for the following assumptions:</p><ul><li>N is an integer within the range [1..100,000];</li><li>each element of array A is an integer within the range [−1,000,000..1,000,000].</li></ul><p>Solutions:</p><pre>def solution(A):<br>    # Implement your solution here<br>    arr = [i for i in A if i &gt; 0]<br><br>    if len(arr) == 0:<br>    #if all elements in A are less than 1, <br>    #the smallest positive integer is 1<br>        return 1<br><br>    max_val = max(arr)<br><br>    arr_dict = {}<br><br>    for i in arr:<br>        arr_dict[i] = 0<br><br>    for i in range(1,max_val+1): #Traverse from 1 to the largest number in A<br>        if i not in arr_dict.keys():<br>            return i<br>    <br>    return max_val + 1</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e85c5e2b5a67" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solutions for MaxCounters]]></title>
            <link>https://medium.com/@yimingqu256/solutions-for-maxcounters-0f8934b6d436?source=rss-dca40af24860------2</link>
            <guid isPermaLink="false">https://medium.com/p/0f8934b6d436</guid>
            <dc:creator><![CDATA[Yiming Qu]]></dc:creator>
            <pubDate>Wed, 01 Nov 2023 17:09:44 GMT</pubDate>
            <atom:updated>2023-11-02T10:59:43.839Z</atom:updated>
            <content:encoded><![CDATA[<h3>Task description</h3><p>You are given N counters, initially set to 0, and you have two possible operations on them:</p><ul><li><em>increase(X)</em> − counter X is increased by 1,</li><li><em>max counter</em> − all counters are set to the maximum value of any counter.</li></ul><p>A non-empty array A of M integers is given. This array represents consecutive operations:</p><ul><li>if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),</li><li>if A[K] = N + 1 then operation K is max counter.</li></ul><p>For example, given integer N = 5 and array A such that:</p><p>A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4</p><p>the values of the counters after each consecutive operation will be:</p><p>(0, 0, 1, 0, 0) (0, 0, 1, 1, 0) (0, 0, 1, 2, 0) (2, 2, 2, 2, 2) (3, 2, 2, 2, 2) (3, 2, 2, 3, 2) (3, 2, 2, 4, 2)</p><p>The goal is to calculate the value of every counter after all operations.</p><p>Write a function:</p><blockquote><em>def solution(N, A)</em></blockquote><p>that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.</p><p>Result array should be returned as an array of integers.</p><p>For example, given:</p><p>A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4</p><p>the function should return [3, 2, 2, 4, 2], as explained above.</p><p>Write an efficient algorithm for the following assumptions:</p><ul><li>N and M are integers within the range [1..100,000];</li><li>each element of array A is an integer within the range [1..N + 1].</li></ul><p>SOLUTION:</p><pre>def solution(N, A):<br>    # Implement your solution here<br>    arr = [0 for i in range(N)]<br>    max_item = 0<br>    base = 0 #recorde &#39;base&#39;<br>    for i in A:<br>        if i &lt; N+1:<br>            if arr[i-1] &lt;= base:<br>                arr[i-1] = base + 1<br>            else:<br>                arr[i-1] += 1<br>            if max_item &lt; arr[i-1]:<br>                max_item = arr[i-1]<br>        <br>        else:<br>            base = max_item #update base<br><br>    for i in range(len(arr)):#update items that less than base<br>        if arr[i] &lt; base: <br>            arr[i] = base<br>    <br>    return arr</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=0f8934b6d436" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>