<?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 Just code every day on Medium]]></title>
        <description><![CDATA[Stories by Just code every day on Medium]]></description>
        <link>https://medium.com/@ellen31725?source=rss-62ecea7c166------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*ETRGlzOy1UyVE9Dj</url>
            <title>Stories by Just code every day on Medium</title>
            <link>https://medium.com/@ellen31725?source=rss-62ecea7c166------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 11:38:19 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@ellen31725/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[[LeetCode]Minimum Index of a Valid Split]]></title>
            <link>https://medium.com/@ellen31725/leetcode-minimum-index-of-a-valid-split-304fb5fa710d?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/304fb5fa710d</guid>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Fri, 28 Mar 2025 11:38:16 GMT</pubDate>
            <atom:updated>2025-03-28T11:38:16.841Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*hFdxPceb-FKwglV5" /><figcaption>Photo by <a href="https://unsplash.com/@aaronburden?utm_source=medium&amp;utm_medium=referral">Aaron Burden</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h4>Problem:</h4><p>You are given a list of numbers, like [1, 2, 2, 2, 3, 2].<br>There is one number that appears <strong>more than half</strong> the time — we call it the <strong>dominant number</strong>.</p><p>Your job is to find a place to split the list into two parts, like this:</p><ul><li>Left part: nums[0 to i]</li><li>Right part: nums[i+1 to end]</li></ul><p>The goal is to find the <strong>earliest index</strong> where you can split the list,<br> so that <strong>both parts still have the same dominant number</strong>.</p><h4>Example:</h4><p>Suppose you have this array:</p><pre>nums = [1, 2, 2, 2, 3, 2]</pre><p>In this array, the number <strong>2</strong> appears <strong>4 times</strong>.<br>The total length is 6, and 4 is more than half of 6 → so <strong>2 is the dominant number</strong>.<br>Now, we want to find the smallest index <strong>i<br></strong>such that:</p><ul><li>In the left part nums[0 to i], the number 2 is still the dominant number (it appears more than half the length)</li><li>In the right part nums[i+1 to end], 2 is also the dominant number</li></ul><p>For example, if we split at <strong>i = 2</strong>:</p><ul><li>Left part: [1, 2, 2] → 2 appears 2 times, length is 3 → 2 &gt; 1.5</li><li>Right part: [2, 3, 2] → 2 appears 2 times, length is 3 → 2 &gt; 1.5</li></ul><p>So this is a valid split!</p><h4>Summary</h4><ol><li>There is one number in the array that is the dominant number.</li></ol><p>2. Try to find a place to split the array, so that this number is still the dominant number in both left and right parts.</p><p>3. Return the earliest index where this kind of split is possible.</p><p>4. If no such split exists, return -1.</p><h4>Solution</h4><h4>Solution 1: Intuitive Thinking</h4><p>The problem guarantees that the entire array has one dominant number (a number that appears more than half of the array length).</p><p>So first, we need to find out which number is dominant .</p><p>Then, we try to split the array at each index<strong> </strong><strong>i</strong>, and check:</p><ul><li>Is the dominant number still dominant in the left part?</li><li>Is it also dominant in the right part?</li></ul><p>If both are true, we remember this index <strong>i</strong>.</p><p>This is a <strong>brute-force approach</strong>, but it’s not efficient because we have to <strong>recount both sides every time</strong>.</p><h4>Solution 2: Optimized Idea — Use the total count to scan only once</h4><p>We already know there is one dominant number in the whole array , and we can count how many times it appears in total — let’s call this totalCount.<br>For example:<br>If nums = [1, 2, 2, 2, 3, 2], the number 2 appears 4 times → totalCount = 4.</p><p>Now, as we go through the array from left to right, we keep track of how many times the dominant number appears on the left side — call this leftCount.</p><p>At position i, the number of times it appears on the right side is totalCount - leftCount.</p><p>We then check:</p><ul><li>Left length = i + 1, check if leftCount &gt; (i + 1) / 2</li><li>Right length = n - i - 1, check if rightCount &gt; (n - i - 1) / 2</li></ul><p>If both sides satisfy this, then we found a valid split — just return i.</p><pre>var minimumIndex = function(nums) {<br>    const countMap = new Map();<br><br>    // Count the frequency of each number<br>    for (let i = 0; i &lt; nums.length; i++) {<br>        const num = nums[i];<br>        countMap.set(num, (countMap.get(num) || 0) + 1);<br>    }<br><br>    // Find the dominant element<br>    const n = nums.length;<br>    let dominant = -1;<br>    for (const [key, value] of countMap.entries()) {<br>        if (value &gt; n / 2) {<br>            dominant = key;<br>            break;<br>        }<br>    }<br><br>    // Scan from left to right to find the minimum valid split index<br>    let leftCount = 0;<br>    const totalCount = countMap.get(dominant);<br><br>    for (let i = 0; i &lt; nums.length - 1; i++) {<br>        if (nums[i] === dominant) {<br>            leftCount++;<br>        }<br><br>        const leftLen = i + 1;<br>        const rightLen = n - leftLen;<br>        const rightCount = totalCount - leftCount;<br><br>        if (leftCount &gt; leftLen / 2 &amp;&amp; rightCount &gt; rightLen / 2) {<br>            return i;<br>        }<br>    }<br><br>    return -1; // No valid split found<br>};</pre><pre>from collections import Counter<br><br>def minimumIndex(nums):<br>    # Count the frequency of each number<br>    count_map = Counter(nums)<br><br>    # Find the dominant element<br>    n = len(nums)<br>    dominant = -1<br>    for num, count in count_map.items():<br>        if count &gt; n / 2:<br>            dominant = num<br>            break<br><br>    # Scan from left to right to find the minimum valid split index<br>    left_count = 0<br>    total_count = count_map[dominant]<br><br>    for i in range(n - 1):<br>        if nums[i] == dominant:<br>            left_count += 1<br><br>        left_len = i + 1<br>        right_len = n - left_len<br>        right_count = total_count - left_count<br><br>        if left_count &gt; left_len / 2 and right_count &gt; right_len / 2:<br>            return i<br><br>    return -1  # No valid split found</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=304fb5fa710d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Top Interview Questions on Arrays in LeetCode (III) — Jump Game、Jump GameII]]></title>
            <link>https://medium.com/@ellen31725/top-interview-questions-on-arrays-in-leetcode-iii-jump-game-jump-gameii-9f55b3c8e788?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/9f55b3c8e788</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[interview]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Fri, 27 Sep 2024 08:24:01 GMT</pubDate>
            <atom:updated>2024-09-27T08:28:31.268Z</atom:updated>
            <content:encoded><![CDATA[<h3>Top Interview Questions on Arrays in LeetCode (III) — Jump Game、Jump GameII</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ZNImqnyLkoA3NtX8" /><figcaption>Photo by <a href="https://unsplash.com/@camadams?utm_source=medium&amp;utm_medium=referral">Cam Adams</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>Jump Game</h3><p><a href="https://leetcode.com/problems/jump-game/">55. Jump Game</a></p><h4>problem:</h4><p>You are given an integer array called nums, where each element represents the maximum number of steps you can jump forward from that position. You start at the first index of the array, and your goal is to determine whether it&#39;s possible to reach the last index of the array.</p><p>To solve this, you need to check if, starting from the first index, you can jump through the array and eventually land on or go beyond the last index. If you can, return true; otherwise, return false.</p><h4>Example 1:</h4><p><strong>Input:</strong> nums = [2,3,1,1,4]<br><strong>Output:</strong> true<br><strong>Explanation:</strong><br>You start at index 0, where the value is 2, meaning you can jump up to 2 steps forward. From index 0, you jump 1 step to index 1, where the value is 3. From index 1, you can jump up to 3 steps forward, allowing you to reach the last index directly. Therefore, it is possible to reach the last index, so the result is true.</p><h4>Example 2:</h4><p><strong>Input:</strong> nums = [3,2,1,0,4]<br><strong>Output:</strong> false<br><strong>Explanation:</strong><br>You start at index 0, where the value is 3, so you can jump up to 3 steps forward. However, no matter how you jump, you will always end up at index 3 at some point. The value at index 3 is 0, meaning you can&#39;t jump any further. Since you&#39;re unable to reach the last index (index 4), the result is false.</p><h4>JavaScript Solution:</h4><pre>var canJump = function(nums) {<br>    let goal = nums.length - 1<br><br>    for(let i = nums.length - 1 ; i &gt;= 0; i--){<br>        if(nums[i] + i &gt;= goal){<br>            goal = i<br>        }<br>    }<br><br>    if(goal === 0){<br>        return true<br>    }else{<br>        return false<br>    }<br>};</pre><h4>Explanation:</h4><ol><li>goal:</li></ol><p>Initialize the goal to be the last index of the array (nums.length - 1). The goal is to check if you can reach this position from the start of the array.</p><p>2. for loop:</p><ul><li>Iterate through the array from the end (nums.length - 1) to the beginning (i &gt;= 0).</li><li>The condition nums[i] + i &gt;= goal checks if the current index i can jump to or beyond the current goal. nums[i] is the maximum jump you can make from index i, so nums[i] + i represents the farthest position you can reach from i.</li><li>If the current index i can reach the goal, update the goal to i, meaning the new goal is to reach this index now.</li></ul><p>3. After the loop:</p><ul><li>If goal equals 0, it means it&#39;s possible to reach the last index from the first index, so return true.</li><li>Otherwise, return false, indicating it&#39;s not possible to reach the last index from the start.</li></ul><h4>Time Complexity:</h4><p>The time complexity is <strong>O(n)</strong>, where n is the length of the nums array. This is because the loop iterates over the array once from the last index to the first.</p><h4>Space Complexity:</h4><p>The space complexity is <strong>O(1)</strong>, since the algorithm only uses a few extra variables (goal and i), regardless of the input size.</p><h3>How to Think?</h3><h4>1. <strong>Reverse Thinking (Checking from the End to the Start):</strong></h4><p>When checking if you can jump from the start to the end, starting from the first index is more complex as you must evaluate all possible jump paths. By reversing the process and checking from the last index backward, the goal progressively shrinks to reachable positions, avoiding unnecessary path exploration.</p><h4>Example:</h4><p>Consider the input nums = [2, 3, 1, 1, 4].</p><p><strong>From Start to End:</strong><br>Starting at index 0 (nums[0] = 2), you can jump to index 1 or 2. From index 1 (nums[1] = 3), you can jump to index 2, 3, or 4. You would need to check each possible path, which may lead to redundant checks.</p><p><strong>From End to Start (Reverse Thinking):</strong><br>Instead, set the goal to the last index (goal = nums.length - 1 = 4).</p><ul><li>Check if any previous index can jump to index 4. Since nums[3] = 1 can jump to 4, update the goal to 3.</li><li>Now check if any previous index can reach index 3. nums[2] = 1 can, so update the goal to 2.</li><li>Continue this process until you reach the start. If you can reach index 0, return true.</li></ul><h4>2. <strong>Solving the problem locally to reach the global goal</strong>:</h4><p>When moving backward, you only need to check if each index can jump to the current goal. If it can, update the goal to that index. This approach eliminates the need to explore every possible jump path, focusing only on the most forward index that can reach the goal.</p><h4>3.<strong>More time-efficient</strong>:</h4><p>This method requires only a single traversal of the array (O(n) time complexity). Each element is checked once to see if it can reach the goal, making it more efficient than brute-force approaches that check all possible jump combinations.</p><h4>4.<strong>Gradually shrinking the goal</strong>:</h4><p>When the goal is updated to the current index, it indicates that from this position, you can reach the end. If you can eventually reach the start, it means you can reach the final destination.</p><h4>5.<strong>Handling dead ends</strong>:</h4><p>If certain positions (like nums[i] == 0) can&#39;t jump forward, this method will detect them during the backward traversal. If no index before the dead end can reach the goal, the goal won&#39;t reach 0, and the function will return false.</p><blockquote>The difference between the two problems is that the first one only checks if it is possible to reach the last element of the array, while the second problem requires finding the minimum number of jumps needed to reach the last element. In the second problem, the goal is to minimize the number of jumps taken to reach the end of the array.</blockquote><p>Let’s take a look~</p><h3>Jump Game II</h3><p><a href="https://leetcode.com/problems/jump-game-ii/">45. Jump Game II</a></p><h4>Problem</h4><p>You are given a 0-indexed array nums, where each element nums[i] represents the maximum number of steps you can jump forward from that index. You start at nums[0] and need to reach the last index of the array, nums[n - 1]. Your task is to find the <strong>minimum number of jumps</strong> required to reach the last index.</p><h4>Example 1:</h4><p><strong>Input</strong>: nums = [2,3,1,1,4]<br><strong>Output</strong>: 2<br><strong>Explanation</strong>: Jump 1 step from index 0 to 1, then jump 3 steps to the last index.</p><h4>Example 2:</h4><p><strong>Input</strong>: nums = [2,3,0,1,4]<br><strong>Output</strong>: 2<br><strong>Explanation</strong>: Jump 1 step from index 0 to 1, then jump 3 steps to the last index.</p><h4>JavaScript Solution:</h4><pre>var jump = function(nums) {<br>    let res = 0<br>    let right = 0<br>    let left = 0<br><br>    while(right &lt; nums.length - 1){<br>        let farthest = 0<br><br>        for(let i = left; i &lt;= right ; i++){<br>           farthest = Math.max(farthest, i + nums[i])<br>        }<br><br>        left = right + 1<br>        right = farthest<br>        res++;<br>    }<br>    return res<br>};</pre><h4>Explanation:</h4><h4>Variable Definitions:</h4><ul><li>res: Keeps track of the number of jumps.</li><li>right: Tracks the current range within which you can jump, initially set to 0.</li><li>left: Represents the left boundary of the current jump range, also initialized to 0.</li></ul><h4>Logic Steps:</h4><ol><li><strong>Loop Condition</strong>: The loop continues as long as right has not reached or exceeded the last index of the array.</li><li><strong>Finding the Farthest Jump</strong>: For the current jump range (from left to right), calculate the farthest position you can jump to, which is i + nums[i]. The Math.max function is used to update the maximum distance you can jump in the current range.</li><li><strong>Update Jump Range</strong>: Once the farthest jump is determined, update the left boundary left to be right + 1 and the right boundary right to be farthest. This means the next jump can be made from this new range.</li><li><strong>Increment Jump Count</strong>: After updating the jump range, increment the jump counter res by 1.</li><li><strong>Exit Condition</strong>: When right reaches or exceeds the last element, exit the loop and return res, which represents the minimum number of jumps required to reach the last element.</li></ol><h3>How to Think?</h3><p>This solution uses a <strong>forward-thinking</strong> approach, starting from the first element and progressively exploring all possible jump ranges until reaching or exceeding the last element.</p><h4>Forward-thinking :</h4><ol><li><strong>Moves from start to end</strong>: The algorithm begins at the first element and expands the jump range (from left to right) each time, finding the farthest position reachable from the current range.</li><li><strong>Updates jump range continuously</strong>: After calculating the farthest jump, the right is updated, and the left is set to right + 1, meaning the next jump will start from the new range.</li><li><strong>Focuses on minimizing jumps, not just checking reachability</strong>: The solution continuously checks the farthest position that can be reached from the current range, rather than working backward from the end to the start. This helps find the minimum number of jumps efficiently.</li></ol><h4>Why Not Backward-thinking:</h4><ol><li><strong>Backward-thinking starts from the end</strong>: Typically, backward-thinking would start at the last element and work its way back to find the earliest index that can reach the target. It focuses on “can we reach” rather than “how many jumps to reach.”</li><li><strong>This problem emphasizes minimum jumps</strong>: The goal is to minimize the number of jumps, so it makes more sense to explore forward from the start and track the farthest possible jump, rather than working backward.</li></ol><h4>Time Complexity:</h4><p>The time complexity is <strong>O(n)</strong>, where n is the length of the nums array. This is because each index is processed once within the while loop and the inner for loop checks a limited range of elements in each iteration.</p><h4>Space Complexity:</h4><p>The space complexity is <strong>O(1)</strong>, as the algorithm only uses a fixed number of variables (res, right, left, farthest), regardless of the input size.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9f55b3c8e788" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Top Interview Questions on Arrays in LeetCode (Ⅱ)]]></title>
            <link>https://medium.com/@ellen31725/top-interview-questions-on-arrays-in-leetcode-%E2%85%B1-32daddb298e3?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/32daddb298e3</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[boyer-moore-algorithm]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[hashmap]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Thu, 26 Sep 2024 05:32:42 GMT</pubDate>
            <atom:updated>2024-09-26T05:36:17.912Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*aId24vpD5MFGrF8W" /><figcaption>Photo by <a href="https://unsplash.com/@ajaegers?utm_source=medium&amp;utm_medium=referral">Arnaud Jaegers</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Let’s first take a look at two problems related to finding the most frequent element in an array: one is a problem from LeetCode, and the other is a variation of the problem.</p><h3>Majority Element</h3><p><a href="https://leetcode.com/problems/majority-element/">169. Majority Element</a></p><h4>Problem:</h4><p>Given an array nums of size n, the task is to return the <strong>majority element</strong>. The majority element is defined as the element that appears more than ⌊n / 2⌋ times in the array. It is guaranteed that the majority element always exists in the array.</p><h4>Example 1:</h4><ul><li><strong>Input</strong>: nums = [3, 2, 3]</li><li><strong>Output</strong>: 3</li></ul><h4>Example 2:</h4><ul><li><strong>Input</strong>: nums = [2, 2, 1, 1, 1, 2, 2]</li><li><strong>Output</strong>: 2</li></ul><p>In both examples, the majority element appears more than half the time, and the solution returns that element.</p><h4>JavaScript Solution:</h4><pre>var majorityElement = function(nums) {<br>    let candidate <br>    let count = 0<br><br>    for(const num of nums){<br>        if(count === 0){<br>            candidate = num<br>        }<br>        <br>       count += (num === candidate) ? 1 : -1<br><br>    }<br><br>    return candidate<br>};</pre><p>Using the <strong>Boyer-Moore Majority Voting Algorithm</strong>, this solution can be explained using an election analogy. Imagine that each element in the array is a candidate running for office, and our goal is to identify the candidate with the majority of votes. Initially, we don’t have any candidate, and the vote count is set to zero. As we iterate through the array, when the vote count is zero, we choose the current element as the new candidate. Each time we encounter the same candidate again, we increase their vote count by one. If we come across a different candidate, we reduce the vote count by one. Whenever the vote count reaches zero, we switch to a new candidate and reset the vote count. By the end of the iteration, the remaining candidate is the one with the majority of votes, as they have garnered more than half of the total votes in the array.</p><h4>Step-by-Step Process (Using [2, 2, 1, 1, 1, 2, 2] as an example with the updated solution):</h4><ol><li><strong>First Iteration (num = 2)</strong>:</li></ol><ul><li>count = 0, so we set candidate to 2.</li><li>Since num === candidate, we increase count to 1.</li></ul><p><strong>2. Second Iteration (num = 2)</strong>:</p><ul><li>num is still 2, which matches the candidate, so we increase count to 2.</li></ul><p><strong>3. Third Iteration (num = 1)</strong>:</p><ul><li>num = 1, which is different from the candidate = 2. Therefore, we decrease count to 1.</li></ul><p><strong>4. Fourth Iteration (num = 1)</strong>:</p><ul><li>num = 1, which is different from the candidate, so we decrease count to 0.</li></ul><p><strong>5. Fifth Iteration (num = 1)</strong>:</p><ul><li>Since count = 0, we update candidate to 1.</li><li>Since num === candidate, we increase count to 1.</li></ul><p><strong>6. Sixth Iteration (num = 2)</strong>:</p><ul><li>num = 2, which is different from the candidate = 1, so we decrease count to 0.</li></ul><p><strong>7. Seventh Iteration (num = 2)</strong>:</p><ul><li>count = 0, so we switch the candidate to 2.</li><li>Since num === candidate, we increase count to 1.</li></ul><h4>Final Result:</h4><p>After iterating through all the elements, the final candidate is 2, which is the majority element because it appears more than half the time in the array.</p><h4>Explanation:</h4><p>Every time count reaches 0, it indicates that the current candidate no longer has majority support, so we switch to a new candidate. By the end of the process, the remaining candidate is the one that appears more than half the time in the array.</p><h4><strong>Time Complexity</strong>:</h4><p>O(n) — The algorithm iterates through the array once, so the time complexity is linear with respect to the size of the array.</p><h4><strong>Space Complexity</strong>:</h4><p>O(1) — The algorithm only uses a few variables (candidate and count), so the space complexity is constant, regardless of the input size.</p><h3>Find the Mode</h3><h4>Problem:</h4><p>Given an array of non-negative integers where all values fall within the range of 0 to 20, the task is to find and return the mode, which is the integer that appears most frequently in the array. You can assume that there is always a unique mode and no ties.</p><h4>Example 1:</h4><ul><li><strong>Input</strong>: [1, 2, 1, 3, 1]</li><li><strong>Output</strong>: 1</li></ul><h4>Example 2:</h4><ul><li><strong>Input</strong>: [6, 0, 8, 8, 10]</li><li><strong>Output</strong>: 8</li></ul><h4>Example 3:</h4><ul><li><strong>Input</strong>: [0, 2, 0, 1, 1, 20, 0]</li><li><strong>Output</strong>: 0</li></ul><p>In each case, the function should return the integer that appears most frequently in the list.</p><blockquote>At first glance, you might instinctively think this problem is no different from the previous one and decide to use the same solution. You might even pass the three test cases provided in the problem! However, when you submit your solution, you receive a “Wrong Answer.” Why? Because this approach is incorrect, and the two problems are not exactly the same. Let’s dive in and see why that is.</blockquote><p>On the surface, the “Majority Element” and “Mode” problems both seem to involve finding the element that appears the most times in an array. However, the two problems are fundamentally different, and therefore, the same solution, particularly the Boyer-Moore Majority Voting Algorithm, is not suitable for both.</p><h4>1. Majority Element</h4><p><strong>Problem Definition</strong>: In the “Majority Element” problem, we need to find the element that appears <strong>more than half</strong> of the time in the array. Specifically, in an array of length n, the majority element must appear at least ⌊n / 2⌋ + 1 times. This guarantees that the element will always take up more than half of the array.</p><p><strong>Why is the Boyer-Moore algorithm suitable for this problem?</strong></p><p>The core idea behind the Boyer-Moore Majority Voting Algorithm is “voting.” As we iterate through the array, we accumulate “votes” to determine the majority element. When the count reaches zero, we switch the candidate and continue the voting process. Since the majority element appears more than half the time, it will eventually dominate, even if there are some opposing votes along the way. In other words, this algorithm leverages the majority element&#39;s property to ensure that it becomes the final candidate, which is why Boyer-Moore efficiently solves the &quot;Majority Element&quot; problem.</p><h4>2. Mode</h4><p><strong>Problem Definition</strong>: In the “Mode” problem, we need to find the element that appears the most times in the array, but this element <strong>does not necessarily appear more than half the time</strong>. The mode is simply the most frequent element, regardless of whether its count exceeds half the array. For example, in the array [1, 2, 2, 3, 3, 3, 4], the mode is 3 because it appears the most frequently, even though it does not occupy more than half the array (it appears 3 times out of 7).</p><p><strong>Why is the Boyer-Moore algorithm not suitable for this problem?</strong></p><p>The Boyer-Moore Majority Voting Algorithm is designed specifically to find the majority element, assuming one element appears more than half the time. It works by canceling out different elements to filter out the majority element. However, the mode does not have this “more than half” guarantee. When there is no majority element, the Boyer-Moore algorithm cannot correctly identify the most frequent element.</p><ul><li><strong>Problem 1</strong>: The algorithm cancels out opposing “votes” instead of counting the frequency of each element. If the mode appears less frequently, it may be overlooked.</li><li><strong>Problem 2</strong>: In the mode problem, we need to count the occurrences of all elements and identify the one with the highest frequency. The Boyer-Moore algorithm focuses on identifying the element that appears more than half the time, which could lead to selecting an element that is not the most frequent.</li></ul><h4>JavaScript Solution:</h4><pre>function findMode(ns) {<br>    const map = new Map();<br>    let maxCount = 0;<br>    let mode = null;<br><br>    // Iterate through the array and record the occurrence of each number<br>    for (let i = 0; i &lt; ns.length; i++) {<br>        let num = ns[i];<br><br>        // If the number is already in the map, increment its count, otherwise set it to 1<br>        if (map.has(num)) {<br>            map.set(num, map.get(num) + 1);<br>        } else {<br>            map.set(num, 1);<br>        }<br><br>        // Update the max count and corresponding mode if the current number&#39;s count is greater<br>        if (map.get(num) &gt; maxCount) {<br>            maxCount = map.get(num);<br>            mode = num;<br>        }<br>    }<br><br>    return mode;<br>}</pre><h4>Explanation :</h4><p>This function finds the <strong>mode</strong> (the most frequently occurring number) in an array of numbers using a <strong>hash map (Map)</strong> to store the frequency of each number. The overall process can be described in the following steps:</p><ol><li><strong>Initialization</strong>:</li></ol><ul><li>A Map object is used to store the count of each number.</li><li>Two variables, maxCount and mode, are initialized to keep track of the highest count and the number that appears the most frequently.</li></ul><p><strong>2. Iteration</strong>:</p><ul><li>The function loops through the array ns. For each number, it checks whether the number is already present in the Map.</li><li>If it is, the function increments the count of that number.</li><li>If it isn’t, it adds the number to the Map and sets its count to 1.</li></ul><p><strong>3. Updating the Mode</strong>:</p><ul><li>During each iteration, the function checks whether the current number’s count has exceeded the maxCount. If it has, the maxCount is updated to reflect the new highest count, and the mode is updated to the corresponding number.</li></ul><p><strong>4. Return the Mode</strong>:</p><ul><li>After iterating through the entire array, the function returns the number that has the highest count, which is stored in the mode variable.</li></ul><h4><strong>Time Complexity</strong>:</h4><p>O(n) — The function iterates through the array once, and all operations (insertion and update in the Map) are done in constant time.</p><h4><strong>Space Complexity</strong>:</h4><p>O(n) — The Map stores up to n entries in the worst case, where n is the length of the array.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=32daddb298e3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Top Interview Questions on Arrays in LeetCode (Ⅰ)]]></title>
            <link>https://medium.com/@ellen31725/top-interview-questions-on-arrays-in-leetcode-%E2%85%B0-3ae6e65207c0?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/3ae6e65207c0</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[arrays]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Wed, 25 Sep 2024 11:31:32 GMT</pubDate>
            <atom:updated>2024-09-25T11:31:32.888Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0GPQOwnmTbsVPGPg" /><figcaption>Photo by <a href="https://unsplash.com/@goran_ivos?utm_source=medium&amp;utm_medium=referral">Goran Ivos</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>Problems involving the removal of duplicate elements from an array</h3><p>The following three problems all focus on removing duplicates from an array, but the key requirement is that the solution must be done <strong>in-place</strong>, meaning that the array should be modified directly without using extra space for another array or data structure.</p><h3>Remove Element</h3><p><a href="https://leetcode.com/problems/remove-element/">27. Remove Element</a></p><h4>Problem:</h4><p>Given an integer array nums and an integer val, remove all occurrences of val from nums <strong>in-place</strong>. The order of the elements may be changed. After removing the elements, return the number of elements in nums that are not equal to val.</p><p>You need to modify the array such that the first k elements contain only the values that are not equal to val, where k is the number of elements remaining in the array after removing all occurrences of val. The rest of the array beyond k is not important and can be left in any state. Your function should return k.</p><h4><strong>Examples:</strong></h4><ol><li><strong>Input:</strong> nums = [3,2,2,3], val = 3<br><strong>Output:</strong> k = 2, nums = [2,2,_,_]<br><strong>Explanation:</strong> Remove all 3s, leaving the first two elements as 2.</li><li><strong>Input:</strong> nums = [0,1,2,2,3,0,4,2], val = 2<br><strong>Output:</strong> k = 5, nums = [0,1,4,0,3,_,_,_]<br><strong>Explanation:</strong> Remove all 2s, leaving the first five elements as a mix of [0,1,3,4,0] in any order.</li></ol><h4>JavaScript solution：</h4><pre>var removeElement = function(nums, val) {<br>    let left = 0<br>    <br>    for(let right = 0 ;right &lt; nums.length ; right++){<br>        if(nums[right]!== val){<br>          nums[left]=nums[right]<br>          left++<br>        }<br>    }<br>    return left<br>        <br>};</pre><h4>Python solution：</h4><pre>def removeElement(nums, val):<br>    left = 0<br>    <br>    for right in range(len(nums)):<br>        if nums[right] != val:<br>            nums[left] = nums[right]<br>            left += 1<br>    <br>    return left</pre><h4>Explanation:</h4><p>I define two pointers, named left and right, both starting at index 0, which is the first element of the array. The left pointer acts like a passive anchor, only moving when the right pointer updates its value. The right pointer, on the other hand, actively traverses the array.</p><p>When the right pointer encounters a value equal to val (the value to be removed), no action is taken since I want to discard that value. However, when the right pointer finds a value that is <strong>not</strong> equal to val, I retain that value by assigning it to the position of the left pointer. After assigning, the left pointer moves forward to prepare for the next valid value.</p><p>This process repeats until the right pointer has traversed the entire array. By the end, the left pointer&#39;s index represents the count of elements in the array that are not equal to val, effectively marking the length of the modified array after removing all occurrences of val.</p><h4>Time Complexity:</h4><ul><li>The algorithm uses a single for loop that iterates through each element in the nums array exactly once. Therefore, the time complexity is <strong>O(n)</strong>, where n is the number of elements in the array nums.</li></ul><h4>Space Complexity:</h4><ul><li>The solution operates <strong>in-place</strong>, meaning it does not require any additional storage beyond a few variables (left and right). The array nums itself is modified directly. Hence, the space complexity is <strong>O(1)</strong>, or constant space, since no extra space is allocated that grows with the input size.</li></ul><h3>Remove Duplicates from Sorted Array</h3><p><a href="https://leetcode.com/problems/remove-duplicates-from-sorted-array/">26. Remove Duplicates from Sorted Array</a></p><p><strong>Problem:</strong></p><p>Given a sorted integer array nums in non-decreasing order, remove the duplicates <strong>in-place</strong> so that each unique element appears only once. The relative order of the elements must be maintained.</p><p>Your task is to modify the array such that the first k elements contain the unique elements in the original order they appeared in. The remaining elements in the array are not important and can be ignored. Finally, return k, which is the number of unique elements.</p><p><strong>Examples:</strong></p><ol><li><strong>Input:</strong> nums = [1,1,2]<br><strong>Output:</strong> k = 2, nums = [1,2,_]<br><strong>Explanation:</strong> The first two unique elements are 1 and 2.</li><li><strong>Input:</strong> nums = [0,0,1,1,1,2,2,3,3,4]<br><strong>Output:</strong> k = 5, nums = [0,1,2,3,4,_,_,_,_,_]<br><strong>Explanation:</strong> The first five unique elements are 0, 1, 2, 3, and 4.</li></ol><h4>JavaScript solution：</h4><pre>var removeDuplicates = function(nums) {<br>    let left = 1<br>    let right = 1<br><br>    while(right &lt; nums.length){<br>        if(nums[right] !== nums[right - 1]){<br>           nums[left] = nums[right]<br>           left++<br>        }<br>        right++<br>    }<br>    return left<br>};</pre><h4>Python solution：</h4><pre>def removeDuplicates(nums):<br>    if len(nums) == 0:<br>        return 0<br><br>    left = 1<br>    right = 1<br><br>    while right &lt; len(nums):<br>        if nums[right] != nums[right - 1]:<br>            nums[left] = nums[right]<br>            left += 1<br>        right += 1<br><br>    return left</pre><h4>Explanation:</h4><p>I initialize two pointers, named left and right, both starting at index 1 (the second element of the array). Since the first element doesn&#39;t have a value to compare with, it is guaranteed to be unique.</p><p>The left pointer acts as a passive anchor, only moving when the right pointer updates its value. The right pointer, on the other hand, traverses the array. The logic for determining whether to assign the value from the right pointer to the left pointer is different from the previous problem. In this case, when the current value of the right pointer is <strong>different</strong> from the value at the previous index (right - 1), it means a new unique value has been found. That value is then assigned to the position of the left pointer.</p><p>After assigning the value, the left pointer moves forward by one position, ready to receive the next unique value. This process continues until the right pointer has traversed the entire array. By the end, the left pointer’s index represents the total number of unique elements in the array.</p><h4>Time Complexity:</h4><p>Because of using a single while loop, the time complexity of the solution is <strong>O(n)</strong>.</p><h4>Space Complexity:</h4><p>The space complexity is <strong>O(1)</strong>, or constant space, as the solution modifies the array in-place using only a few variables, without needing extra memory for another data structure.</p><h3><strong>Remove Duplicates from Sorted Array II</strong></h3><p><a href="https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/">80. Remove Duplicates from Sorted Array II</a></p><h4><strong>Problem:</strong></h4><p>Given a sorted integer array nums in non-decreasing order, remove duplicates <strong>in-place</strong> so that each unique element appears at most twice. The relative order of the elements must remain the same.</p><p>You need to modify the array such that the first k elements contain the final result after removing the extra duplicates, with k being the number of elements left. It doesn&#39;t matter what values are left in the array beyond the first k elements.</p><p>You are not allowed to use extra space for another array, and the solution must have a space complexity of <strong>O(1)</strong>, meaning it should modify the input array directly. Finally, return k, the number of elements after the duplicates have been removed.</p><h4><strong>Examples:</strong></h4><ol><li><strong>Input:</strong> nums = [1,1,1,2,2,3]<br><strong>Output:</strong> k = 5, nums = [1,1,2,2,3,_]<br><strong>Explanation:</strong> The first five elements are [1, 1, 2, 2, 3], with duplicates limited to two per unique element.</li><li><strong>Input:</strong> nums = [0,0,1,1,1,1,2,3,3]<br><strong>Output:</strong> k = 7, nums = [0,0,1,1,2,3,3,_,_]<br><strong>Explanation:</strong> The first seven elements are [0, 0, 1, 1, 2, 3, 3], keeping at most two duplicates per unique element.</li></ol><h4>JavaScript solution：</h4><pre>var removeDuplicates = function(nums) {<br>    let left = 0<br>    let right = 0<br>    while(right &lt; nums.length){<br>      let count = 1<br>      while(right + 1 &lt; nums.length &amp;&amp; nums[right] == nums[right + 1]){<br>          count++<br>          right++<br>      }<br>      for(let i = 0; i &lt; Math.min(2,count); i++){<br>          nums[left] = nums[right]<br>          left++<br>      }<br>      right++<br>    }<br>  return left<br>};</pre><h4>Python solution：</h4><pre>def removeDuplicates(nums):<br>    left = 0<br>    right = 0<br>    <br>    while right &lt; len(nums):<br>        count = 1<br>        while right + 1 &lt; len(nums) and nums[right] == nums[right + 1]:<br>            count += 1<br>            right += 1<br>        <br>        for i in range(min(2, count)):<br>            nums[left] = nums[right]<br>            left += 1<br>        <br>        right += 1<br>    <br>    return left</pre><h4>Explanation:</h4><p>I initialize two pointers, named left and right, to remove duplicates in a sorted array while allowing each unique element to appear at most twice.</p><ol><li>Both pointers start at index 0. The right pointer traverses the array to identify duplicates.</li><li>For each element, it counts how many times it repeats using a while loop.</li><li>After determining the count of duplicates, the solution ensures that each unique element is kept at most twice by using a for loop and assigning the element to the position of the left pointer.</li><li>The left pointer moves forward, and the right pointer continues to traverse the array until all elements are processed.</li><li>Finally, the function returns left, which represents the length of the array after duplicates are removed while keeping at most two of each element.</li></ol><h4>Time Complexity:</h4><p>The time complexity is <strong>O(n)</strong>, where n is the length of the array. Both pointers traverse the array once, and the inner loop runs at most twice, so the overall complexity is linear.</p><h4>Space Complexity:</h4><p>The space complexity is <strong>O(1)</strong>, as the solution modifies the array in-place using only a few variables without extra memory allocation.</p><h3>Problems involving rotating the elements of an array</h3><p>The following problem involves rotating, not removing duplicates, but similarly requires in-place modification.</p><h3>Rotate Array</h3><p><a href="https://leetcode.com/problems/rotate-array/">189. Rotate Array</a></p><h4><strong>Problem:</strong></h4><p>Given an integer array nums, rotate the array to the right by k steps, where k is a non-negative integer. The rotation should be done in-place without using extra space for another array.</p><h4><strong>Examples:</strong></h4><ol><li><strong>Input:</strong> nums = [1,2,3,4,5,6,7], k = 3<br><strong>Output:</strong> [5,6,7,1,2,3,4]<br><strong>Explanation:</strong> Rotating the array 3 steps to the right results in [5,6,7,1,2,3,4].</li><li><strong>Input:</strong> nums = [-1,-100,3,99], k = 2<br><strong>Output:</strong> [3,99,-1,-100]<br><strong>Explanation:</strong> Rotating the array 2 steps to the right results in [3,99,-1,-100].</li></ol><h4>JavaScript solution：</h4><pre>var rotate = function(nums, k) {<br>   k = k % nums.length<br><br>   if(k === 0){<br>      return nums<br>   }<br><br>   if(k &gt; 0){<br>     const removed = nums.splice(nums.length - k)<br>     nums.unshift(...removed)<br>   }<br><br>   return nums<br>};</pre><h4>Python solution：</h4><pre>def rotate(nums, k):<br>    k = k % len(nums)<br>    <br>    if k == 0:<br>        return nums<br>    <br>    if k &gt; 0:<br>        removed = nums[-k:]  # Get the last k elements<br>        nums[:] = removed + nums[:-k]  # Modify the array in-place by combining the removed part with the rest<br>    <br>    return nums</pre><h4>Explanation:</h4><p>If the value of k is larger than the length of the array, I first take k modulo the array length to get the actual number of rotations needed, because rotating more than the length of the array is equivalent to looping back around.</p><p>Next, I move the last k elements to the front of the array and concatenate the remaining elements to get the rotated result.</p><p>The reason I don’t use push and unshift one by one is that this approach is less efficient. The unshift operation requires shifting all elements backward, which can be time-consuming for large arrays, increasing the time complexity. Using slicing and concatenating is more efficient because it rearranges the elements in a single operation, rather than moving them individually, resulting in better performance.</p><h4>Time Complexity:</h4><p>The time complexity is <strong>O(n)</strong>, where n is the length of the array. Both splice() and unshift() involve moving up to k elements, resulting in an overall time complexity of <strong>O(n)</strong>.</p><h4>Space Complexity:</h4><p>The space complexity is <strong>O(k)</strong> since splice() creates a new array to store k elements.</p><blockquote>Note:</blockquote><blockquote><strong>Difference between </strong><strong>splice() and </strong><strong>slice() in Arrays:</strong></blockquote><blockquote>splice(): This method <strong>modifies the original array</strong> by adding, removing, or replacing elements in place. It directly affects the array and returns the removed elements, if any.</blockquote><blockquote>slice(): This method <strong>does not modify the original array</strong>. Instead, it returns a shallow copy of a portion of the array, without changing the original data.</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3ae6e65207c0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implementing Bull Queue for Efficient Task Management in Healthcare Systems: A Technical Overview]]></title>
            <link>https://medium.com/@ellen31725/implementing-bull-queue-for-efficient-task-management-in-healthcare-systems-a-technical-overview-9f92138bb567?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/9f92138bb567</guid>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Tue, 24 Sep 2024 16:00:36 GMT</pubDate>
            <atom:updated>2024-09-24T16:00:36.953Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*CUZ2xVWj75psg7H5" /><figcaption>Photo by <a href="https://unsplash.com/@tnygarcia?utm_source=medium&amp;utm_medium=referral">Tony Garcia</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>In today’s article, I took some time to document the queue system implemented in the platform I’m developing. Recently, I’ve been focusing on how to optimize patient flow across healthcare institutions. This led me to reflect on the key technologies I depend on to ensure smooth operations. Bull Queue has become an integral part of the infrastructure, managing tasks efficiently and providing real-time updates in a way that is both straightforward and powerful.</p><h3>What is Bull Queue?</h3><p>Bull is a lightweight, powerful, and fast Redis-based task queue for Node.js. It is designed to manage and process jobs, which are essentially tasks that need to be executed. Bull Queue enables developers to handle background tasks, delays, retries, and job prioritization with ease. The fact that Bull is based on Redis allows it to take advantage of Redis’ efficient in-memory data structures, making it fast and scalable.</p><h3>How Bull Queue Works</h3><p>At its core, Bull Queue operates by creating a queue where jobs can be added and processed asynchronously. A job can be a piece of code or a function that you want to run, but you don’t need it to block the main process. This makes Bull Queue particularly useful for offloading tasks like sending emails, processing files, or managing complex workflows that need to run in the background without interfering with the main application.</p><p>Bull Queue is built on Redis, which functions as a persistent data store for the queue. Every job that is added to the queue is stored in Redis until it is processed. Each job can have various states, such as “waiting”, “active”, “failed”, or “completed”, and Bull provides tools to handle retries, job priorities, and even delayed jobs. Here’s a brief overview of its workflow:</p><ul><li><strong>Job Creation</strong>: When a task is submitted to Bull, it is added to a Redis-backed queue.</li><li><strong>Job Processing</strong>: Bull workers pick up the jobs from the queue and execute them based on predefined logic.</li><li><strong>Retries and Failures</strong>: If a job fails, Bull supports retry mechanisms with custom retry intervals and failure handling.</li><li><strong>Completion</strong>: Once a job is processed, Bull marks it as completed and can trigger any further processing based on predefined rules.</li></ul><h3>Bull Queue vs. Kafka and RabbitMQ</h3><p>When considering other messaging or queue systems like Kafka and RabbitMQ, there are key differences:</p><ul><li><strong>Kafka</strong>: Kafka is designed for handling high-throughput data streams, making it ideal for event streaming and log aggregation. It’s more suitable for situations where large amounts of data need to be processed in real-time, like financial transactions or sensor data. Kafka is a distributed system with a focus on ensuring message durability and scalability across many nodes, but it may be overkill for tasks that simply need job processing rather than complex data pipelines.</li><li><strong>RabbitMQ</strong>: RabbitMQ is a general-purpose message broker that supports multiple messaging protocols and patterns, such as pub-sub, message acknowledgment, and routing. It is excellent for distributed systems requiring guaranteed message delivery but can be more complex to configure compared to Bull Queue. RabbitMQ excels in flexibility but might be heavier for simpler job-processing tasks.</li><li><strong>Bull</strong>: Unlike Kafka and RabbitMQ, Bull is specifically optimized for job queueing and processing in Node.js environments. It integrates deeply with Redis, providing lightweight job processing, retries, and delays out of the box. For many Node.js applications that require background job processing, Bull is simpler to implement, easier to scale, and sufficiently powerful for common use cases like handling tasks with time constraints.</li></ul><h3><strong>Why Choose Bull over Other Queues?</strong></h3><p>For developers working in a Node.js environment who need a simple yet powerful task management system, Bull is often the preferred choice. The decision to choose Bull Queue stems from several reasons:</p><p><strong>1.Ease of Use</strong>: Bull is easier to set up and use in Node.js applications compared to more complex systems like Kafka or RabbitMQ. It has a straightforward API and excellent documentation, making it accessible for developers.</p><p><strong>2.Built-in Redis Support</strong>: Bull leverages Redis for both job persistence and queue management, meaning that Redis’ robust in-memory data storage makes job retrieval and processing highly efficient.</p><p><strong>3.Advanced Job Management</strong>: Bull has built-in support for features like delayed jobs, retries, job prioritization, and concurrency management, which are essential for creating a reliable task processing system.</p><p><strong>4.Real-time Monitoring</strong>: Bull also integrates with third-party dashboard tools like bull-board, allowing administrators to monitor job queues, inspect failed jobs, and manage workflows visually.</p><h3>What Does It Mean That Bull Is Based on Redis?</h3><p>Redis is an in-memory data store that excels in performance and scalability, making it ideal for real-time applications. When we say that Bull Queue is based on Redis, it means that Redis handles the queuing logic. Jobs in Bull are stored in Redis lists and sets, which makes job addition and retrieval extremely fast. Redis also handles job persistence, ensuring that jobs aren’t lost if the system crashes.</p><p>Additionally, Redis allows Bull to efficiently manage job states, priorities, and delayed tasks. Redis is central to Bull’s architecture, providing not just job storage but also reliability and fast retrieval, which are crucial for systems where performance is key.</p><h3>The Application of Bull Queue in Healthcare Institutions: Patient Flow Optimization</h3><p>I am using Bull Queue to manage various stages of patient flow in a healthcare institution. A typical patient journey includes:</p><ul><li><strong>Registration and Waiting for Consultation</strong>: After registering, a patient will wait to see a doctor. This waiting time can vary depending on the queue and the doctor’s availability.</li><li><strong>Consultation and Waiting for Treatment/Examination</strong>: After the consultation, the patient may need to wait for one or more treatments or lab tests.</li><li><strong>Collecting Medicine</strong>: After receiving prescriptions, the patient heads to the pharmacy department, where they may wait to collect their medicine.</li></ul><p>Each of these stages involves some level of waiting time, and the goal is to optimize and manage these times effectively. For every stage in the process, specific time thresholds are defined that represent an acceptable waiting time. If a patient exceeds this threshold, the system flags it as a delay.</p><h3>How Bull Queue Operates in This Scenario</h3><p>Here’s how Bull Queue plays a role in managing the patient flow:</p><ol><li><strong>Tracking Patient Status</strong>: As a patient progresses through the different stages of their visit, Bull Queue tracks their current status (waiting for a doctor, undergoing examination, waiting for medication, etc.). Each status update triggers the creation of a job in Bull Queue, which holds the patient’s current stage and the corresponding waiting time.</li><li><strong>Handling Time Thresholds</strong>: For each stage (e.g., waiting for a consultation, waiting for medication), specific time thresholds are defined. Bull Queue monitors these thresholds by setting delayed jobs.If a patient has been waiting longer than the defined limit, a delayed job is executed, and Bull Queue triggers an alert.</li><li><strong>Real-time WebSocket Notifications</strong>: Bull Queue works in conjunction with WebSockets to push real-time notifications to medical staff. If the system detects that a patient has been waiting too long in any stage, it sends an immediate notification, ensuring that staff can respond to the delay and improve patient flow.</li><li><strong>Improving Efficiency</strong>: By providing real-time insights into patient statuses and potential delays, Bull Queue helps medical staff to react more effectively. This improves overall efficiency in the patient journey, reduces waiting times, and enhances the quality of care provided.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9f92138bb567" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Basic Python Interview Questions]]></title>
            <link>https://medium.com/@ellen31725/basic-python-interview-questions-d967513a63b8?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/d967513a63b8</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Mon, 23 Sep 2024 16:52:53 GMT</pubDate>
            <atom:updated>2024-09-23T16:52:53.101Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*VVZ6paxNUW4SRlVo" /><figcaption>Photo by <a href="https://unsplash.com/@goran_ivos?utm_source=medium&amp;utm_medium=referral">Goran Ivos</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h4>1. How do you create multi-line comments in Python?</h4><p>In Python, there isn’t a dedicated syntax for multi-line comments, but there are several ways to achieve similar functionality.</p><ol><li><strong>Using consecutive single-line comments (</strong><strong>#)</strong>: This is the most common approach. You can place a # symbol at the beginning of each line you want to comment out.</li></ol><pre># This is an example of a multi-line comment<br># Each line is preceded by a `#`<br># This makes it easy to comment out multiple lines</pre><p><strong>2. Using multi-line strings (</strong><strong>&quot;&quot;&quot; or </strong><strong>&#39;&#39;&#39;)</strong>: Multi-line strings are primarily used for string literals, but if they are not assigned to any variable, they can act as temporary multi-line comments. This is particularly useful when you want to add large descriptive comments in your code.</p><pre>&quot;&quot;&quot;<br>This is an example of using triple quotes<br>to create a multi-line comment.<br>Technically, this is a string literal,<br>but it can serve as a comment if left unassigned.<br>&quot;&quot;&quot;</pre><blockquote><strong>Note</strong>: While using triple quotes as comments can be convenient, it is not the formal way to comment in Python. Multi-line strings will still be treated as strings and may occupy memory during runtime if not optimized by the interpreter.</blockquote><p>3. <strong>Using docstrings for functions or classes</strong>: Although not technically comments, you can use docstrings (&quot;&quot;&quot;) to document functions, classes, or modules. Docstrings are executed and stored as metadata, so they are not meant for general code commenting, but they are useful for providing descriptions of how a function or class works.</p><pre>def example_function():<br>    &quot;&quot;&quot;<br>    This is a docstring.<br>    It describes what this function does.<br>    It can span multiple lines.<br>    &quot;&quot;&quot;<br>    pass</pre><h4>2. What is the difference between is and == in Python?</h4><p>In Python, the difference between is and == lies in <strong>what they compare</strong>:</p><ol><li><strong>== compares the values of two variables</strong>. It checks if the content stored in the variables is the same, regardless of whether they are distinct objects in memory. For example, two separate lists or strings with the same content will be considered equal when using ==.</li><li><strong>is compares the identity of two variables</strong>. It checks if the two variables point to the exact same object in memory. Thus, is will return True only if both variables reference the same object.</li></ol><h4>Example:</h4><pre>a = [1, 2, 3]<br>b = [1, 2, 3]<br><br># == compares values (content)<br>print(a == b)  # True, because both lists have the same content<br><br># is compares identities (memory location)<br>print(a is b)  # False, because they are two distinct objects in memory</pre><h4>Additional Example with Integers:</h4><p>For immutable data types like integers or strings, Python may cache small values, making is return True for those specific cases. However, this behavior can be inconsistent for larger numbers or more complex objects.</p><pre>x = 1000<br>y = 1000<br><br>print(x == y)  # True, because the values are the same<br>print(x is y)  # False, because they are different objects<br><br># Python caches small integers (-5 to 256)<br>a = 10<br>b = 10<br>print(a is b)  # True, because Python caches small integers</pre><h4>Usage of is with None:</h4><p>One of the most common uses of is is to check if a variable is None. This is because None is a singleton in Python, meaning there is only one instance of None in memory. Therefore, using is ensures that you are checking the identity of the object, not just its value.</p><pre>x = None<br>if x is None:<br>    print(&quot;x is None&quot;)</pre><h4>3. What is the use of pass in Python?</h4><p>In Python, pass is a <strong>placeholder</strong> that indicates a section of code with no implementation. It is used when you want to define a block of code but don&#39;t have the logic ready yet. This allows you to maintain the structure of your program without causing syntax errors, enabling the code to run correctly while you leave space for future functionality.</p><h4>Example:</h4><pre>def my_function():<br>    pass  # Function to be implemented later</pre><p>The pass statement can be used in several situations, including:</p><ol><li><strong>Defining functions, classes, or conditional statements without implementation</strong>: Sometimes, you might want to outline the structure of your program without providing the details immediately. pass lets you do this without raising any errors.</li></ol><pre>class MyClass:<br>    pass  # Class definition to be implemented later</pre><pre>def my_function():<br>    pass  # Function logic will be added later</pre><p><strong>2. Using as a placeholder in loops or conditionals</strong>: When writing a loop or an if statement, you may want to skip the body for the moment and come back to it later. Instead of leaving it empty (which would cause an error), you can use pass.</p><pre>if condition_met:<br>    pass  # Handle the condition later<br>else:<br>    print(&quot;Condition not met&quot;)</pre><pre>for i in range(10):<br>    pass  # Placeholder for future loop logic</pre><h4>4. How to Use Global Variables in a Function?</h4><p>In Python, if you want to use a global variable inside a function, you must declare it using the global keyword. This tells Python that you are referencing or modifying a variable that exists in the global scope, rather than creating a new local variable inside the function.</p><h4>Example:</h4><p>Let’s say we have a global variable count initially set to 0. In the function increment, we use the global keyword to inform Python that we want to modify the global count variable, not create a new local one. After calling increment, the value of count is increased by 1. When we print count, the output will be 1.</p><pre>count = 0  # This is a global variable<br><br>def increment():<br>    global count  # Tells Python to use the global &#39;count&#39; variable<br>    count += 1<br><br>increment()<br>print(count)  # Output: 1</pre><h4>Key Points:</h4><ul><li><strong>Using the </strong><strong>global keyword</strong>: This keyword allows the function to access and modify the global variable instead of creating a local copy.</li><li>Without the global keyword, Python would assume that any variable assignment within the function is creating a new local variable.</li></ul><h4>Example Without global:</h4><p>If you don’t use the global keyword, Python will treat count as a local variable, and the global count will remain unchanged.</p><pre>count = 0<br><br>def increment():<br>    count = 1  # This only creates a local variable &#39;count&#39;<br><br>increment()<br>print(count)  # Output: 0 (the global &#39;count&#39; remains unchanged)</pre><pre>config_mode = &quot;development&quot;  # Global configuration variable<br><br>def switch_mode():<br>    global config_mode<br>    config_mode = &quot;production&quot;  # Modify the global variable<br><br>switch_mode()<br>print(config_mode)  # Output: productio</pre><h4>5. What is Negative Indexing in a List? Can you give an example?</h4><p>Negative indexing in a list allows you to access elements starting from the <strong>end of the list</strong>. In Python, the index -1 refers to the <strong>last element</strong> in the list, -2 refers to the <strong>second-to-last element</strong>, and so on. This provides an intuitive way to access elements from the end of the list without needing to calculate the exact positive index.</p><h4>Example:</h4><pre>my_list = [10, 20, 30, 40, 50]</pre><pre># Access the last element<br>print(my_list[-1])  # Output: 50 (the last element of the list)</pre><pre># Access the second-to-last element<br>print(my_list[-2])  # Output: 40 (the second-to-last ele</pre><h4>Why Use Negative Indexing?</h4><p>Negative indexing is especially useful when you want to access elements from the end of the list but do not want to calculate the exact position of those elements based on the list’s length. It simplifies the process of working with lists, particularly when dealing with unknown or dynamically changing list sizes.</p><h4>Additional Example:</h4><pre>numbers = [5, 15, 25, 35, 45, 55]<br><br># Access the last three elements using negative indexing<br>print(numbers[-1])  # Output: 55<br>print(numbers[-3])  # Output: 35複製程式碼</pre><p>You can also use negative indexing in <strong>slicing</strong>, which allows you to retrieve a portion of the list by specifying a range of indices:</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d967513a63b8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Technical Interview Notes for Software Engineers: Commonly Asked Questions on Fundamental Website…]]></title>
            <link>https://medium.com/@ellen31725/technical-interview-notes-for-software-engineers-commonly-asked-questions-on-fundamental-website-69e70a9c16ef?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/69e70a9c16ef</guid>
            <category><![CDATA[website-operations]]></category>
            <category><![CDATA[fundamental-concepts]]></category>
            <category><![CDATA[tech]]></category>
            <category><![CDATA[software]]></category>
            <category><![CDATA[interview]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Sun, 22 Sep 2024 04:03:51 GMT</pubDate>
            <atom:updated>2024-09-22T04:05:08.482Z</atom:updated>
            <content:encoded><![CDATA[<h3>Technical Interview Notes for Software Engineers: Commonly Asked Questions on Fundamental Website Operations</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*KRF24hErvoxyO7DI" /><figcaption>Photo by <a href="https://unsplash.com/@walls_io?utm_source=medium&amp;utm_medium=referral">Walls.io</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h4>Interviewer🧔‍♂️: To assess your understanding efficiently, please answer the following questions within one to two minutes. Feel free to provide concise but clear explanations, highlighting key points relevant to your experience.</h4><h4>1. Interviewer🧔‍♂️: Please describe in as much detail as possible the process that occurs behind the scenes when a user enters a URL in a browser and ultimately views a webpage.</h4><h4>Candidate👨‍🦱:</h4><p>When a user enters a URL in the browser, the process can be broken down into the following steps:</p><ol><li><strong>DNS Lookup</strong>: The browser first sends a request to the <strong>Domain Name System (DNS)</strong> server, which acts like a directory, mapping domain names to their corresponding <strong>IP addresses</strong>. The DNS server returns the IP address of the server that hosts the requested domain.</li><li><strong>Establishing a Connection</strong>: After receiving the IP address, the browser initiates a connection with the server. This is done through a process known as the <strong>TCP three-way handshake</strong>, ensuring that a stable connection is established between the client and server.</li><li><strong>Secure Communication</strong>: Once the connection is established, the browser uses encryption protocols like <strong>SSL </strong>or <strong>TLS</strong> to secure the data being transmitted. This ensures that any data exchanged between the client and server remains encrypted and protected from third-party interception.</li><li><strong>Load Balancing</strong>: If the server setup includes a <strong>load balancer</strong>, the incoming request is routed to an appropriate server within a pool, based on predefined algorithms (e.g., <strong>round-robin</strong> or <strong>least connections</strong>). This ensures efficient distribution of traffic across multiple servers.</li><li><strong>Server Response</strong>: The selected server processes the request and generates a response. This response typically includes files like <strong>HTML, CSS</strong>, and <strong>JavaScript</strong>, which will be used to build the webpage. The response is sent back to the load balancer and forwarded to the browser.</li><li><strong>Dynamic Content Handling</strong>: If the webpage includes dynamic content, such as user-specific data or search results, the server may interact with <strong>application servers</strong> or <strong>database servers</strong> to fetch or compute the necessary information. The final response is then returned to the browser.</li><li><strong>Rendering the Page</strong>: Upon receiving the response, the browser parses the <strong>HTML</strong> file to structure the page, applies <strong>CSS</strong> to style it, and executes <strong>JavaScript</strong> to add interactivity. Once these processes are complete, the browser displays the fully rendered webpage to the user.</li></ol><h4>2. Interviewer🧔‍♂️: In modern web development, handling resources across different domains is often necessary. Can you explain what CORS (Cross-Origin Resource Sharing) is, and how it enables cross-origin communication? Additionally, could you describe how you would configure CORS in a typical web application?</h4><h4>Candidate👨‍🦱:</h4><p>CORS (Cross-Origin Resource Sharing) is a security mechanism implemented by web browsers to allow servers to specify which origins (domains) are permitted to access their resources. This is important because, by default, the <strong>Same-Origin Policy</strong> restricts browsers from making requests to domains different from the one that served the web page, to prevent malicious websites from accessing sensitive data.</p><h4>How to Enable Cross-Origin Communication:</h4><ol><li><strong>Set Server Response Headers</strong>:<br>To allow cross-origin requests, the server must include the Access-Control-Allow-Origin header in its response. This header specifies which origins are allowed to access the resource. For instance, to allow any origin, it can be set to *, or it can be restricted to specific origins like:</li></ol><pre>Access-Control-Allow-Origin: https://example.com</pre><p><strong>2. Handle Preflight Requests</strong>:<br>When a request involves modifying data (e.g., POST, PUT, DELETE) or uses custom headers, the browser sends an OPTIONS preflight request to check if the actual request is allowed. The server must respond with appropriate headers, such as Access-Control-Allow-Methods to specify allowed HTTP methods and Access-Control-Allow-Headers for allowed custom headers:</p><pre>Access-Control-Allow-Methods: GET, POST, PUT<br>Access-Control-Allow-Headers: Content-Type, Authorization</pre><p>3.<strong>Allow Credentials</strong>:<br>If the cross-origin request needs to include <strong>cookies</strong> or <strong>authentication</strong> information, the server should set the Access-Control-Allow-Credentials header to true. However, in this case, Access-Control-Allow-Origin cannot be set to *; it must specify an explicit origin:</p><pre>Access-Control-Allow-Credentials: true<br>Access-Control-Allow-Origin: https://example.com</pre><h4>3. <strong>Interviewer🧔‍♂️:</strong> Can you explain the key characteristics of the HTTP communication protocol?</h4><h4>Candidate👨‍🦱:</h4><p>HTTP (Hypertext Transfer Protocol) is an application layer communication protocol primarily used for data transmission between browsers and servers. It has several key characteristics:</p><ol><li><strong>Statelessness</strong>:<br>HTTP is a stateless protocol, meaning each request is independent, and the server does not retain any information about previous requests. If state needs to be maintained (e.g., for <strong>login sessions</strong>), technologies like <strong>cookies </strong>or <strong>sessions</strong> are used.</li><li><strong>Request-Response Model</strong>:<br>HTTP operates based on the <strong>request-response</strong> model. The client (usually a browser) sends a request to the server, which processes it and sends back an appropriate response. This model is simple but effective for web communication.</li><li><strong>Support for Static and Dynamic Content</strong>:<br>HTTP can transmit both <strong>static</strong> resources (e.g., images, CSS files) and <strong>dynamic</strong> content (e.g., server-generated HTML pages). This flexibility allows it to support both static websites and dynamic web applications.</li><li><strong>Multiple Request Methods</strong>:<br>HTTP supports various request methods, each serving a specific purpose. For instance, GET is used to retrieve data, POST to submit data, PUT to update existing resources, and DELETE to remove resources.</li><li><strong>Support for Various Data Formats</strong>:<br>HTTP allows the transmission of different data formats through the Content-Type header, including plain text, <strong>JSON</strong>, <strong>XML</strong>, <strong>images</strong>, and more. This versatility makes it suitable for a wide range of applications.</li><li><strong>Extensibility</strong>:<br>HTTP is highly extensible through headers, which can be used to customize the behavior of the protocol. Headers can manage <strong>authentication</strong>, <strong>caching</strong>, and more, enhancing the flexibility of HTTP for different use cases.</li></ol><h4>4. <strong>Interviewer🧔‍♂️:</strong> Can you explain the specific differences between the HTTP GET and POST methods?</h4><h4>Candidate👨‍🦱:</h4><p>The GET and POST methods are both used in HTTP, but they serve different purposes and have distinct characteristics:</p><ol><li><strong>Purpose</strong>:</li></ol><ul><li>GET is used to retrieve data from a server. It requests data from a specified resource without modifying any data on the server.</li><li>POST, on the other hand, is used to send data to the server to create or update a resource. It’s commonly used for submitting forms, uploading files, or sending complex data.</li></ul><p><strong>2. Data Transmission</strong>:</p><ul><li>In a GET request, the data is appended to the <strong>URL</strong> as query parameters (e.g., ?key=value). This makes the data visible in the URL, which is not ideal for sensitive information like passwords.</li><li>In a POST request, the data is sent in the <strong>request body</strong>, making it more secure for sensitive data transmission as it’s not exposed in the URL.</li></ul><p><strong>3. Caching</strong>:</p><ul><li>GET requests are <strong>cacheable</strong>, meaning the browser or intermediary proxies can store responses for faster retrieval if the same request is made again.</li><li>POST requests are <strong>not cacheable</strong> by default because they modify data or send new data, so each request is considered unique.</li></ul><p><strong>4. URL Length and Data Size</strong>:</p><ul><li>GET requests have limitations on the amount of data that can be sent because URLs have a length limit, which varies by browser but is generally around 2048 characters.</li><li>POST requests do not have this limitation since the data is sent in the body, allowing for much larger payloads, including files or large datasets.</li></ul><p><strong>5. Idempotency</strong>:</p><ul><li>GET requests are<strong> idempotent</strong>, meaning calling the same request multiple times will not change the server’s state — it simply retrieves the same data.</li><li>POST requests are <strong>not idempotent</strong>; sending the same request multiple times can result in the creation of multiple resources or repeated actions on the server.</li></ul><p><strong>6. Visibility</strong>:</p><ul><li>Since GET data is part of the URL, it’s visible to anyone who can see the URL (in history, logs, etc.), making it less secure for sensitive data.</li><li>POST hides data within the request body, providing better privacy for sensitive information.</li></ul><h4>5. <strong>Interviewer🧔‍♂️:</strong> In what scenarios are 4xx and 5xx status codes typically used?</h4><h4>Candidate👨‍🦱:</h4><p>The <strong>4xx</strong> and <strong>5xx</strong> status codes represent client-side and server-side errors, respectively, in HTTP communications. Here’s a breakdown of each:</p><h4>4xx Status Codes:</h4><p>4xx status codes indicate client-side errors. This means that the client’s request has some issues, preventing the server from processing it. Common scenarios include:</p><ol><li><strong>400 Bad Request</strong>:<br>This indicates that the request from the client is malformed or contains invalid parameters, making it impossible for the server to understand or process it.</li><li><strong>401 Unauthorized</strong>:<br>This code is returned when the request lacks valid <strong>authentication credentials</strong>. It is typically seen in situations where the user needs to log in or provide authorization to access a resource.</li><li><strong>403 Forbidden</strong>:<br>Even though the client has authenticated, this code is returned when they do not have permission to access the requested resource, often due to insufficient access rights.</li><li><strong>404 Not Found</strong>:<br>This means the server could not find the requested resource. It’s common when a user tries to access a webpage or API endpoint that doesn’t exist.</li><li><strong>429 Too Many Requests</strong>:<br>This indicates the client has sent too many requests in a short period, often triggered by <strong>rate-limiting</strong> policies, especially in APIs.</li></ol><h4>5xx Status Codes:</h4><p>5xx status codes indicate server-side errors, meaning the server failed to process a valid request due to an internal issue. Common scenarios include:</p><ol><li><strong>500 Internal Server Error</strong>:<br>This is a generic error indicating something went wrong on the server’s side, such as a code bug or database connection failure.</li><li><strong>502 Bad Gateway</strong>:<br>This happens when a server, acting as a gateway or proxy, receives an invalid response from an upstream server, often due to connectivity issues between servers.</li><li><strong>503 Service Unavailable</strong>:<br>This means the server is temporarily unable to handle the request, possibly due to server overload or maintenance. It’s usually a temporary issue.</li><li><strong>504 Gateway Timeout</strong>:<br>This occurs when a server, acting as a gateway or proxy, takes too long to receive a response from the upstream server. It can happen when the upstream server is slow or unreachable.</li></ol><h4>6. <strong>Interviewer🧔‍♂️:</strong> What are the key differences between the WebSocket and HTTP communication protocols?</h4><h4>Candidate👨‍🦱:</h4><p>WebSocket and HTTP are two distinct communication protocols, primarily differing in their communication patterns and use cases.</p><p>First, HTTP is based on a <strong>request-response</strong> model, meaning that whenever a client (typically a browser) sends a request, the server responds, and once the communication is complete, the connection is closed. If the client needs to send another request, a new connection must be established. This makes HTTP suitable for applications like static websites or scenarios where resources need to be fetched from the server, as it works well for <strong>short, one-time requests</strong>.</p><p>In contrast, WebSocket is a <strong>full-duplex</strong> protocol, meaning that after the connection is established, data can flow continuously and <strong>bidirectionally</strong> between the client and server without the need to repeatedly establish connections. This makes WebSocket ideal for use cases that require frequent, <strong>real-time</strong> data exchanges, such as <strong>instant messaging</strong>, <strong>online gaming</strong>, or stock trading systems, where maintaining real-time synchronization is critical.</p><h4>7. <strong>Interviewer🧔‍♂️:</strong> Can you explain the concept of caching? How have you applied it in your projects?</h4><h4>Candidate👨‍🦱:</h4><p>Caching is a technique used to improve system performance and reduce latency by temporarily storing frequently accessed or computationally expensive data in a faster medium, such as memory. This allows the system to retrieve data directly from the cache rather than recalculating or fetching it from a slower backend source, such as a database or external API. By storing data closer to where it’s needed — whether in memory, disk, or a distributed cache — subsequent requests can be served much faster, reducing the time and resources required for future retrievals.</p><h4>How I’ve Applied Caching in My Projects:</h4><p>In one of my recent projects, I implemented <strong>Redis</strong> to cache <strong>precomputed statistical data</strong> for a <strong>statistics center</strong>. The system often performed resource-intensive computations to generate reports and analytics based on historical data. To improve response times, I cached precomputed data along with other frequently accessed information. The caching process worked as follows:</p><ul><li><strong>Data Retrieval</strong>: For any request, the system first checks the Redis cache for the required precomputed data.</li><li><strong>Cache Miss</strong>: If the data isn’t in the cache (cache miss), the system performs the necessary calculations, and the result is stored in Redis for future use.</li><li><strong>Cache Hit</strong>: On subsequent requests, the data is fetched directly from the cache, significantly reducing computation time and response delays.</li></ul><p>This reduced <strong>computation time</strong> and improved performance by about <strong>35%</strong>, especially during peak usage.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=69e70a9c16ef" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implementing a Web Server System without Third-Party Libraries or Frameworks]]></title>
            <link>https://medium.com/@ellen31725/implementing-a-web-server-system-without-third-party-libraries-or-frameworks-d16f333f280b?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/d16f333f280b</guid>
            <category><![CDATA[socketserver]]></category>
            <category><![CDATA[sockets]]></category>
            <category><![CDATA[web]]></category>
            <category><![CDATA[tcp]]></category>
            <category><![CDATA[https]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Fri, 10 May 2024 05:47:13 GMT</pubDate>
            <atom:updated>2024-05-10T05:49:55.016Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*E_JS6QmLlUltfluM" /><figcaption>Photo by <a href="https://unsplash.com/@fabioha?utm_source=medium&amp;utm_medium=referral">fabio</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Implementing a web server system from scratch can help us better understand how networking programs work at a low level. When writing network applications, we often rely on established tools that provide foundational infrastructure. However, the small implementation in this article, which builds a simple server and client from scratch, will help us understand how they interact with each other. So, let’s dive in!</p><h3>Using socketserver</h3><p>Python’s socketserver module provides a straightforward way to implement TCP servers. Here&#39;s how you can create a simple TCP server and client using this module.</p><h4>Server Implementation</h4><p>The following code demonstrates a basic TCP server that listens for incoming connections and responds with a predefined message:</p><pre># Write a TCP server<br>import socketserver<br><br># Custom handler class inheriting from BaseRequestHandler<br>class Handler(socketserver.BaseRequestHandler):<br>    def handle(self):<br>        # Receive data from the client<br>        data = self.request.recv(10240).strip().decode(&quot;utf-8&quot;)<br>        print(&quot;Received:\n&quot; + data)<br>        response = &quot;Response from server&quot;<br>        # Send response back to the client<br>        self.request.sendall(response.encode(&quot;utf-8&quot;))<br><br># Instantiate the server<br>with socketserver.TCPServer((&quot;localhost&quot;, 9999), Handler) as server:<br>    server.serve_forever()</pre><h4>Client Implementation</h4><p>To interact with this TCP server, we can write a simple client program that sends a message to the server and receives a response:</p><pre># Client implementation<br>import socket<br><br>with socket.create_connection((&quot;localhost&quot;, 9999)) as sock:<br>    # Send a message to the server<br>    sock.sendall(&quot;Message from client&quot;.encode(&quot;utf-8&quot;))<br>    # Receive the server&#39;s response<br>    response = sock.recv(10240).decode(&quot;utf-8&quot;)<br>    print(&quot;Received:\n&quot; + response)</pre><h4>How It Works</h4><ol><li>Handler Class: The Handler class inherits from socketserver.BaseRequestHandler and processes incoming requests.</li><li>handle Method:</li></ol><ul><li>The handle method is invoked for every client request.</li><li>Data received from the client is decoded using UTF-8 and printed to the console.</li><li>The server replies with a predefined message.</li></ul><h3>Using socket</h3><p>Now, let’s rewrite the same server and client using the lower-level socket module.</p><h4>Server Implementation</h4><pre># TCP server using socket<br>import socket<br><br>HOST = &quot;localhost&quot;<br>PORT = 9999<br><br># Create the server socket<br>with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as server_socket:<br>    # Bind and listen for incoming connections<br>    server_socket.bind((HOST, PORT))<br>    server_socket.listen(5)  # Listen for up to 5 connections<br>    print(f&quot;Server listening on {HOST}:{PORT}&quot;)<br><br>    while True:<br>        # Accept a new client connection<br>        client_socket, client_address = server_socket.accept()<br>        with client_socket:<br>            print(f&quot;Connected by {client_address}&quot;)<br>            data = client_socket.recv(10240).decode(&quot;utf-8&quot;).strip()<br>            print(f&quot;Received:\n{data}&quot;)<br>            response = &quot;Response from server&quot;<br>            # Send a response back to the client<br>            client_socket.sendall(response.encode(&quot;utf-8&quot;))</pre><h4>Client Implementation</h4><pre># TCP client using socket<br>import socket<br><br>HOST = &quot;localhost&quot;<br>PORT = 9999<br><br># Create the client socket and connect to the server<br>with socket.create_connection((HOST, PORT)) as client_socket:<br>    # Send a message to the server<br>    client_socket.sendall(&quot;Message from client&quot;.encode(&quot;utf-8&quot;))<br>    # Receive the server&#39;s response<br>    response = client_socket.recv(10240).decode(&quot;utf-8&quot;)<br>    print(f&quot;Received:\n{response}&quot;)</pre><h4>How It Works</h4><ol><li>Server Socket Setup:</li></ol><ul><li>Create a socket using socket.socket.</li><li>Bind it to a specific address and port using bind.</li><li>Set up a listening queue using listen.</li></ul><p>2. Accept Connections:</p><ul><li>Accept an incoming client connection using accept.</li><li>Receive and send data using recv and sendall.</li></ul><p>3. Client Implementation:</p><ul><li>Create a socket and connect to the server using create_connection.</li><li>Send and receive data using sendall and recv.</li></ul><h3>Differences Between socket and socketserver</h3><ol><li>Level of Abstraction:</li></ol><ul><li>socket is a low-level API that provides direct access to network sockets.</li><li>socketserver is a higher-level framework that simplifies writing network servers.</li></ul><p>2. Concurrency:</p><ul><li>socket requires explicit concurrency handling (e.g., threading or multiprocessing).</li><li>socketserver provides built-in concurrency support via mix-in classes like ThreadingMixIn or ForkingMixIn.</li></ul><p>3. Ease of Use:</p><ul><li>socket provides complete control over the networking behavior.</li><li>socketserver simplifies server implementations by handling socket management and requests.</li></ul><p>4. Customization:</p><ul><li>socket allows fully custom implementations and behavior.</li><li>socketserver provides a structure that makes server creation faster and easier but with some trade-offs in customization.</li></ul><h3>What is a Communication Protocol?</h3><p>A communication protocol defines the rules for data exchange between systems. Protocols can be categorized based on their characteristics, such as connection-based vs. connectionless, or text vs. binary.</p><h3>TCP Protocol</h3><p>The Transmission Control Protocol (TCP) is a connection-oriented protocol that ensures reliable, ordered delivery of data. It is ideal for applications that require accuracy, like web browsing or email.</p><h3>HTTP Protocol</h3><p>The Hypertext Transfer Protocol (HTTP) operates on top of TCP and defines the format for communication between web clients and servers. It is stateless, meaning each request-response pair is independent of others.</p><h3>Relation to a TCP Server</h3><ol><li>A TCP server listens on a port and handles incoming connections.</li><li>An HTTP server is a TCP server that interprets incoming data according to the HTTP protocol.</li><li>Libraries like socket.io build upon TCP or WebSocket to provide high-level features like broadcasting.</li></ol><h3>For Example: HTTP Server Built on TCP Server</h3><pre>import socketserver<br><br># Basic HTTP response<br>HTTP_RESPONSE = &quot;&quot;&quot;\<br>HTTP/1.1 200 OK<br>Content-Type: text/plain<br><br>Hello, World!<br>&quot;&quot;&quot;<br><br># Custom handler class inheriting from BaseRequestHandler<br>class HTTPHandler(socketserver.BaseRequestHandler):<br>    def handle(self):<br>        # Receive data from the client<br>        request = self.request.recv(1024).strip().decode(&quot;utf-8&quot;)<br>        print(&quot;Received Request:\n&quot; + request)<br>        # Send a basic HTTP response back to the client<br>        self.request.sendall(HTTP_RESPONSE.encode(&quot;utf-8&quot;))<br><br># Instantiate the server<br>with socketserver.TCPServer((&quot;localhost&quot;, 9999), HTTPHandler) as server:<br>    print(&quot;HTTP Server running on http://localhost:9999&quot;)<br>    server.serve_forever()</pre><h4>How It Works</h4><ol><li>Handler Class:</li></ol><ul><li>The HTTPHandler class processes incoming requests.</li><li>It reads the client request data, prints it to the console, and sends back a basic HTTP response.</li></ul><p>2. Server Setup:</p><ul><li>The TCPServer listens on port 9999 and handles incoming connections using the custom HTTPHandler class.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d16f333f280b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Interesting and Practical Programming Questions(Largest Integer、Second Largest Integer、Greatest…]]></title>
            <link>https://medium.com/@ellen31725/interesting-and-practical-programming-questions-largest-integer-second-largest-integer-greatest-b62688aa6e60?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/b62688aa6e60</guid>
            <category><![CDATA[second-largest-integer]]></category>
            <category><![CDATA[greatest-common-divisor]]></category>
            <category><![CDATA[least-common-multiple]]></category>
            <category><![CDATA[largest-integer]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Fri, 26 Apr 2024 03:51:06 GMT</pubDate>
            <atom:updated>2024-04-26T03:54:11.948Z</atom:updated>
            <content:encoded><![CDATA[<h3>Interesting and Practical Programming Questions(Largest Integer、Second Largest Integer、Greatest Common Divisor、Least Common Multiple）</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*cZ-hytiXGQjpRvy-" /><figcaption>Photo by <a href="https://unsplash.com/@charlesdeluvio?utm_source=medium&amp;utm_medium=referral">charlesdeluvio</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h4>1. Find the Largest Integer</h4><p>Given an array/list containing at least one integer, find and return the largest integer.</p><p>Input Example 1: [1, 3, 3, 2, 5, -2]<br>Return: 5</p><p>Input Example 2: [-5, -10, -8, -1, -2]<br>Return: -1</p><p>Input Example 3: [0, 2, 2]<br>Return: 2</p><pre>function findLargestInteger(numbers) {<br>    return Math.max(...numbers);<br>}</pre><ul><li>This JavaScript function uses the Math.max method, which finds the maximum value in a list of numbers.</li><li>The spread syntax (...) is used to pass all the elements of the array as individual arguments to Math.max.</li></ul><p>Time Complexity:</p><p>O(n), where n is the number of elements in the numbers array. This is because the Math.max() function needs to iterate over each element of the array once to find the maximum value.</p><p>Space Complexity:</p><p>It’s O(1) because the algorithm doesn’t use any additional space that scales with the size of the input.</p><h4>2. Find the Second Largest Integer</h4><p>Given an array/list containing at least two different integers, find and return the second largest integer.</p><p>Input Example 1: [1, 3, 3, 2, 5, -2]<br>Return: 3</p><p>Input Example 2: [-5, -10, -8, 1, -1]<br>Return: -1</p><p>Input Example 3: [0, 2]<br>Return: 0</p><pre>function findSecondLargest(numbers) {<br>    let uniqueNumbers = [...new Set(numbers)]; // Remove duplicates<br>    uniqueNumbers.sort((a, b) =&gt; b - a); // Sort descending<br>    return uniqueNumbers[1]; // Return the second element<br>}</pre><ul><li>This JavaScript function first removes duplicates from the array using a Set, then sorts the unique numbers in descending order.</li><li>The second element of the sorted array is returned as it represents the second largest number.</li></ul><p>Time Complexity:</p><ol><li>Removing Duplicates: The operation of removing duplicates using a Set has a time complexity of 𝑂(𝑛), where 𝑛 is the number of elements in the original array. This is because each element needs to be checked and inserted into the Set.</li><li>Sorting: Sorting the elements using the .sort() method typically has a time complexity of 𝑂(𝑛log⁡𝑛), where 𝑛 now refers to the number of unique elements after duplicates are removed.</li></ol><p>Space Complexity:</p><ol><li>The space complexity is also 𝑂(𝑛) in the worst case, which occurs when all elements are unique, requiring space to store each element in the Set.</li><li>Space complexity depends on the specific sorting algorithm used; most modern browsers implement sorting algorithms that generally require 𝑂(log⁡𝑛) additional space.</li></ol><p>Overall:</p><ul><li>Time Complexity: 𝑂(𝑛log⁡𝑛), dominated by the sorting step.</li><li>Space Complexity: 𝑂(𝑛), primarily due to the storage needed for the Set to eliminate duplicates.</li></ul><h4>Note: Dive Into the Space Complexity of “uniqueNumbers.sort((a, b) =&gt; b — a)”</h4><p>The space complexity of uniqueNumbers.sort((a, b) =&gt; b - a), primarily depends on the sorting algorithm that the JavaScript engine implements. Most modern JavaScript engines like V8 (used in Google Chrome and Node.js) employ a combination of sorting algorithms depending on the array&#39;s size. Typically, these include QuickSort and Insertion Sort.</p><p>For QuickSort, which is commonly used for larger arrays, the average and worst-case space complexity is 𝑂(log⁡𝑛). This space complexity arises because QuickSort is a recursive algorithm, and 𝑂(log⁡𝑛) space is required to maintain the stack used by the recursive calls.</p><p>However, for small arrays, some JavaScript engines switch to Insertion Sort, which has a space complexity of 𝑂(1), meaning it uses a constant amount of additional space.</p><p>Thus, for the code uniqueNumbers.sort((a, b) =&gt; b - a);:</p><ul><li>If the engine uses QuickSort due to the array’s size, the space complexity will generally be 𝑂(log⁡𝑛).</li><li>If the engine uses Insertion Sort for a small array, the space complexity will be 𝑂(1).</li></ul><h4>3. Find the Greatest Common Divisor</h4><p>Create a function that takes in two positive integers and returns the greatest common divisor (GCD) of these two numbers.</p><p>Input Example 1: 6 and 4<br>Return: 2</p><p>Input Example 2: 5 and 16<br>Return: 1</p><p>Input Example 3: 12 and 6<br>Return: 6</p><pre>function findGreatestCommonDivisor(a, b) {<br>    while(b !== 0) {<br>        let t = b;<br>        b = a % b;<br>        a = t;<br>    }<br>    return a;<br>}</pre><p>This function uses the Euclidean algorithm, which is an efficient method for computing the greatest common divisor (GCD) of two numbers. The algorithm repeatedly applies the operation of replacing the pair of numbers (a, b) with (b, a mod b) until b becomes zero. The resulting non-zero element, a, is the GCD.</p><p>Time Complexity:</p><p>The time complexity of the Euclidean algorithm is 𝑂(log⁡(min⁡(𝑎,𝑏))), where a and b are the input numbers. This is because in each step, the algorithm reduces the size of one of the numbers by at least half (in the worst-case scenario), leading to a logarithmic number of steps.</p><p>Space Complexity:</p><p>The space complexity is 𝑂(1) because the algorithm only needs a fixed amount of space for the variables used, regardless of the size of the input numbers.</p><h4>Note: The Euclidean Algorithm Explained with an Example</h4><p>The Euclidean algorithm is a classical method for finding the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers also divides their difference. ( This “difference” can also be the result of repeatedly subtracting the smaller number multiple times, which is equivalent to the result of the modulo operation. )</p><p>Follow these steps to apply the algorithm:</p><pre>1. Take two numbers, a and b.<br><br>2. If b is 0, then the GCD is a.<br><br>3. Otherwise, replace a with b and b with the remainder of a divided by b.<br><br>4. Repeat the process until b becomes 0.</pre><p>Here’s an example:</p><p>Let’s find the GCD of 48 and 18:</p><pre>Step 1: <br>48 % 18 = 12 (So we replace 𝑎 with 18 and 𝑏 with 12)<br><br>Step 2:<br>18 % 12 = 6 (Now 𝑎 is 12 and 𝑏 is 6)<br><br>Step 3:<br>12 % 6 = 0 (Finally, 𝑎 is 6 and 𝑏 is 0)<br><br>Result:<br>The GCD of 48 and 18 is 6</pre><h4>BTW, Another Note: Division by Zero and Zero Divided by a Number</h4><ul><li>Any Number Divided by 0:</li></ul><p>Division by zero is undefined in mathematics, which means that you cannot divide any number by zero. In most programming languages, trying to divide by zero will result in an error or an undefined result.</p><ul><li>0 Divided by Any Number:</li></ul><p>Zero divided by any non-zero number is always zero. In mathematical terms, 0 % 𝑛 = 0 for any integer 𝑛 that is not zero.</p><h4>4. Find the Least Common Multiple</h4><p>The function should take two positive integers as input and return the Least Common Multiple (LCM) of these two integers.</p><p>Input Example 1: 6 and 4<br>Return: 12</p><p>Input Example 2: 5 and 16<br>Return: 80</p><p>Input Example 3: 12 and 6<br>Return: 12</p><p>To compute the LCM of two numbers, we can utilize the relationship between the Greatest Common Divisor (GCD) and LCM.</p><p>And we just practice how to find the Greatest Common Divisor (GCD) of two positive integers in Question 3 above.</p><p>The LCM of two numbers a and b can be calculated using the formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/402/1*FgmhgqqiWmjKsJuuuSPqGQ.png" /></figure><pre>function gcd(a, b) {<br>    // Continue taking the remainder until b becomes zero<br>    while (b !== 0) {<br>        let temp = b;<br>        b = a % b;<br>        a = temp;<br>    }<br>    return a;<br>}<br><br>function lcm(a, b) {<br>    return Math.abs(a * b) / gcd(a, b);<br>}</pre><ol><li>The gcd function calculates the greatest common divisor using the Euclidean algorithm. It repeatedly replaces the larger number by its remainder when divided by the smaller number until one of the numbers becomes zero. The other number at that point is the GCD.</li><li>The lcm function then calculates the LCM using the formula mentioned above. It multiplies the two numbers and divides by their GCD to get the LCM. The Math.abs ensures the result is positive.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b62688aa6e60" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding Binary Heaps: Definitions, Comparisons, Implementations, and Applications]]></title>
            <link>https://medium.com/@ellen31725/understanding-binary-heaps-definitions-comparisons-implementations-and-applications-94d5f95c1ecf?source=rss-62ecea7c166------2</link>
            <guid isPermaLink="false">https://medium.com/p/94d5f95c1ecf</guid>
            <category><![CDATA[datastrucutre]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[heap]]></category>
            <dc:creator><![CDATA[Just code every day]]></dc:creator>
            <pubDate>Wed, 24 Apr 2024 14:45:24 GMT</pubDate>
            <atom:updated>2024-04-24T14:45:24.440Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*EZKA1ur7CENnh67z" /><figcaption>Photo by <a href="https://unsplash.com/@markusspiske?utm_source=medium&amp;utm_medium=referral">Markus Spiske</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h4>1. What is a Binary Heap?</h4><p>A binary heap is a complete binary tree data structure where each node of the tree has a value that is either greater than (in the case of a max heap) or less than (in the case of a min heap) the values of its children. This property makes binary heaps useful for implementing priority queues, where the order of objects is determined by their priority.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XZ6DD3HlTlXjMElExkvfag.png" /><figcaption>Not a Binary Heap</figcaption></figure><p>In a binary heap, every parent node must adhere to a specific ordering with respect to its children:</p><ul><li>In a max heap, every parent node must have a value that is greater than the values of its children.</li><li>In a min heap, every parent node must have a value that is less than the values of its children.</li></ul><h4>2. Min Heaps vs. Max Heaps: Characteristics and Examples</h4><p>Binary heaps are primarily classified into two types: min heaps and max heaps.</p><p>The key difference between them lies in the node arrangement:</p><ul><li>Min Heap: In a min heap, the value of each node is less than the values of its children, but there are no guarantees between sibling nodes. The smallest value is always at the root, making it ideal for quickly finding and removing the minimum element.</li></ul><p>For example, in a task scheduling system, tasks could be prioritized by shortest duration first, using a min heap to quickly access the next task.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cGQEtycW-s1c8382ze219Q.png" /><figcaption>Min Heap</figcaption></figure><ul><li>Max Heap: Conversely, in a max heap, each node’s value is greater than its children’s values, with the largest value at the root. And there are no guarantees between sibling nodes.</li></ul><p>This structure is suitable for applications where quick access to the maximum element is needed, such as in a streaming service that prioritizes the highest quality streams.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*q9mnr2EH9nroF0QSxLD9BQ.png" /><figcaption>Max Heap</figcaption></figure><h4>3. Implementing Basic Methods on Heaps</h4><p>The basic operations that define the functionality of heaps include insertion, extraction, and heapification:</p><ul><li>Insertion: To insert a new element, it is added at the end of the tree (maintaining the complete tree property), and then it “bubbles up” to restore the heap property. This process involves swapping the added element with its parent until the correct order is restored.</li><li>Extraction: Removing the root element (the min in a min heap or the max in a max heap) involves replacing the root with the last element in the tree and then “bubbling down” this element to restore the heap order.</li><li>Heapify: This method is used to convert a random collection of elements into a heap. Starting from the last non-leaf node, the heap property is enforced by pushing down elements that violate the heap property.</li></ul><h4>4. JavaScript Implementation of a Min Heap</h4><ol><li>Insertion<br>To insert a new element into a min heap, we’ll add the element at the end of the array (heap) and then “bubble it up” until the heap property is restored.</li></ol><pre>function bubbleUp(heap, index) {<br>    let parentIndex;<br>    while (index &gt; 0) {<br>        parentIndex = Math.floor((index - 1) / 2);<br>        if (heap[parentIndex] &gt; heap[index]) {<br>            // Swap parent and current index<br>            [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];<br>            index = parentIndex;<br>        } else {<br>            break;<br>        }<br>    }<br>}<br><br>function insert(heap, element) {<br>    heap.push(element);<br>    bubbleUp(heap, heap.length - 1);<br>}</pre><p>2. Extraction<br>To remove the root (minimum element in a min heap), we swap it with the last element, remove the last element, and then “bubble down” the new root to restore the heap order.</p><pre>function bubbleDown(heap, index) {<br>    let leftChildIndex, rightChildIndex, smallestChildIndex, len = heap.length;<br><br>    while ((leftChildIndex = 2 * index + 1) &lt; len) {<br>        rightChildIndex = leftChildIndex + 1;<br>        smallestChildIndex = leftChildIndex;<br><br>        if (rightChildIndex &lt; len &amp;&amp; heap[rightChildIndex] &lt; heap[leftChildIndex]) {<br>            smallestChildIndex = rightChildIndex;<br>        }<br><br>        if (heap[smallestChildIndex] &lt; heap[index]) {<br>            // Swap smallest child and current index<br>            [heap[index], heap[smallestChildIndex]] = [heap[smallestChildIndex], heap[index]];<br>            index = smallestChildIndex;<br>        } else {<br>            break;<br>        }<br>    }<br>}<br><br>function extract(heap) {<br>    if (heap.length === 0) {<br>        return null;<br>    }<br><br>    let minElement = heap[0];<br>    heap[0] = heap[heap.length - 1];<br>    heap.pop();<br>    bubbleDown(heap, 0);<br>    return minElement;<br>}</pre><p>3.Heapify<br>This function transforms an unstructured array into a heap, starting from the last non-leaf node down to the root node.</p><pre>function buildHeap(elements) {<br>    let heap = [...elements];<br>    for (let i = Math.floor(heap.length / 2) - 1; i &gt;= 0; i--) {<br>        bubbleDown(heap, i);<br>    }<br>    return heap;<br>}</pre><p>For example:<br>1. Heapify the Array [5, 3, 8, 4, 2, 6, 9, 7]</p><p>Initial array representation as a complete binary tree:</p><pre>        5<br>       / \<br>      3   8<br>     / \ / \<br>    4  2 6  9<br>   /<br>  7</pre><ul><li>Start from the last non-leaf node.</li><li>Apply bubbleDown on each node as required.</li></ul><p>Final heap after heapifying:</p><pre>        2<br>       / \<br>      3   6<br>     / \ / \<br>    4  5 9  7<br>   /<br>  8</pre><p>2. Insertion of Element 1</p><ul><li>Add 1 at the end, then bubble it up.</li></ul><pre>Before bubbling up:<br><br>        2<br>       / \<br>      3   6<br>     / \ / \<br>    4  5 9  7<br>   / \<br>  8   1</pre><pre>After Bubble Up:<br><br>        1<br>       / \<br>      2   6<br>     / \ / \<br>    4  5 9  7<br>   / \<br>  8   3</pre><p>3.Extraction from a Min Heap</p><ul><li>Swap root 1 with last element 3, remove 1.</li></ul><pre>After removing 1 and before bubbling down:<br>        3<br>       / \<br>      2   6<br>     / \ / \<br>    4  5 9  7<br>   /<br>  8</pre><pre>After Bubble Down:<br>        2<br>       / \<br>      3   6<br>     / \ / \<br>    4  5 9  7<br>   /<br>  8</pre><h4>5. Real-World Applications and Derived Data Structures</h4><p>Heaps find extensive applications in various fields:</p><ul><li>Priority Queues: Commonly used in algorithms like Dijkstra’s algorithm for shortest paths, event-driven simulation, and operating systems for managing processes.</li><li>Heapsort Algorithm: A comparison-based sorting algorithm that uses binary heaps to sort elements efficiently.</li><li>Graph Algorithms: Many graph algorithms use priority queues internally, and heaps provide an efficient way of implementing these queues.</li></ul><p>Derived data structures from heaps include:</p><ul><li>Heap-Ordered Trees: Variants like leftist trees, binomial heaps, and Fibonacci heaps, which are optimized for specific operations, such as decrease-key operations in network optimization algorithms.</li><li>Priority Queue Implementations: Heaps can be used to implement double-ended priority queues by combining the features of min heaps and max heaps.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=94d5f95c1ecf" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>