<?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 Ze on Medium]]></title>
        <description><![CDATA[Stories by Ze on Medium]]></description>
        <link>https://medium.com/@zeyuanli?source=rss-7961156ac0f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*lC9fJtSDm0n_dxNg4k10fw@2x.jpeg</url>
            <title>Stories by Ze on Medium</title>
            <link>https://medium.com/@zeyuanli?source=rss-7961156ac0f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 12:44:44 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@zeyuanli/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[Sorted Data Structure in C# for Your Coding Questions]]></title>
            <link>https://medium.com/@zeyuanli/sorted-data-structure-in-c-for-your-coding-questions-3008bf16a2bc?source=rss-7961156ac0f------2</link>
            <guid isPermaLink="false">https://medium.com/p/3008bf16a2bc</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[c-sharp-programming]]></category>
            <category><![CDATA[priority-queue]]></category>
            <category><![CDATA[coding-question]]></category>
            <category><![CDATA[dotnet]]></category>
            <dc:creator><![CDATA[Ze]]></dc:creator>
            <pubDate>Fri, 31 Mar 2023 16:49:45 GMT</pubDate>
            <atom:updated>2023-03-31T17:26:07.515Z</atom:updated>
            <content:encoded><![CDATA[<h4>.NET 6 releases its version of PriorityQueue in C#(finally). Here is everything you need to know about the C# sorted data structures in coding question practice, including PriorityQueue, SortedDictionary, SortedList, and SortedSet</h4><p>Practicing coding questions is a key part preparing technical interviews for junior, mid senior developers. I often got confused looking at various unreliable stack overflow answers. Here, we will talk about how to choose between them, how to write custom comparers and a common data structure combination for coding interview.</p><h3>Abstract data type vs Data structure</h3><p>Let’s talk about basics.</p><p>You will encounter a lot of big works like Heap, Priority queue, TreeMap, etc. What are the differences?</p><p>First of all priority queue is a <strong>abstract data type</strong>, which is a high-level description of a data type that specifies its behavior and properties, while a <strong>data structure</strong> is a specific implementation of that data type in a particular programming language.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/642/1*1U84PIC_NCARPZ2Sjm6NGQ.png" /></figure><p>In practice, a priority queue can be implemented using a variety of data structures, including heaps, binary search trees, and arrays. What makes it confusing for some, that C# implementation of heap data structure is called `PriorityQueue&lt;TElement,TPriority&gt;`</p><p>Let’s dive into details of those data structures.</p><h3>SortedDictionary, SortedList, and SortedSet</h3><p>None of them support duplicate keys or items on sorting.</p><h4>SortedDictionary&lt;TKey, TValue&gt;</h4><ul><li>Collection of KeyValuePair&lt;TKey, TValue&gt;</li><li>Sorted on key in ascending order</li><li>It is the TreeMap equivalent in C#</li><li>Implemented with balanced binary search tree, so has O(log n) for retrieval, insertion and removal operations</li></ul><pre>SortedDictionary&lt;int, string&gt; sdict = new SortedDictionary&lt;int, string&gt;(); <br>sdict.Add(4, &quot;k&quot;);<br>sdict.Add(1, &quot;2&quot;);<br>sdict.Add(2, &quot;3&quot;);                <br>sdict.Add(3, &quot;4&quot;);<br><br>Console.WriteLine(sdict.Values.First()); //2<br>Console.WriteLine(sdict.Keys.First());   //1<br><br>Console.WriteLine(sdict.Values.Last());  //k<br>Console.WriteLine(sdict.Keys.Last());    //4 or  dict.Last().Key;<br><br>Console.WriteLine(sdict.Keys.ElementAt(0));  //access by index by Enumerable<br>Console.WriteLine(sdict.Values.ElementAt(0));<br><br>//customized comparator - sort in descending order<br>SortedDictionary&lt;int, string&gt; sdict = new SortedDictionary&lt;int, string&gt;(<br>  Comparer&lt;int&gt;.Create((a, b) =&gt; b - a)<br>);<br><br>//Methods<br>public void Add (TKey key, TValue value); // O(logn)<br>public bool ContainsKey (TKey key); // O(logn)<br>public bool ContainsValue (TValue value); // O(n)<br>public bool Remove (TKey key); // O(logn)<br><br>//An efficient way to retrieve values when a program frequently tries keys that are not in the dictionary<br>public bool TryGetValue (TKey key, out TValue value); // O(logn)</pre><h4>SortedList&lt;TKey, TValue&gt;</h4><ul><li>Collection of KeyValuePair&lt;TKey, TValue&gt;</li><li>Sorted on key in ascending order</li><li>Implemented with two sorted arrays, so has O(log n) for retrieval, but O(n) for insertion and removal operations</li><li>It uses less memory than SortedDictionary and is faster to popularize from sorted data, also supports efficient indexed retrieval of keys and values through Keys and Values collections properties..</li></ul><pre>SortedList&lt;int, int&gt; sl = new SortedList&lt;int, int&gt;();<br>// Add some sample data<br>sl.Add(6, 20);<br>sl.Add(1, 11);<br>sl.Add(11, 99);<br>sl.Add(7, 3);<br><br>// get min key in sorted list<br>Console.WriteLine(sl.Keys[0]); // 1<br><br>// get max key in sorted list<br>Console.WriteLine(sl.Keys[sl.Count - 1]); // 11<br><br>//Share the common methods with SortedDictionary</pre><h4>SortedSet&lt;T&gt;</h4><ul><li>Sorted in ascending order</li><li>It is the TreeSet equivalent in C#</li><li>Implemented with balanced binary search tree, so has O(log n) for retrieval, insertion and removal operations</li><li>It has properties of Min and Max. Retrieving min and max value is O(1).</li><li>Changing the sort values of existing items is not supported and leads to a lot of weird behaviors when updating! You have to remove it from the set, then add it back, which I’ll provide an example in next Mapped Priority Queue topic.</li></ul><pre>//Properties <br>public int Count { get; }<br>public T? Max { get; }<br>public T? Min { get; }<br><br>//Methods<br>public bool Add (T item);<br>public virtual void Clear (); //O(n)<br>public bool Remove (T item); //O(logn)<br>public bool TryGetValue (T equalValue, out T actualValue);<br><br>//Union with another collection<br>public void UnionWith (System.Collections.Generic.IEnumerable&lt;T&gt; other); <br><br>//Returns a view of a subset - inclusive<br>//This method does not copy elements from the SortedSet&lt;T&gt; <br>//but provides a window into the underlying SortedSet&lt;T&gt; itself<br>public virtual System.Collections.Generic.SortedSet&lt;T&gt; GetViewBetween (T? lowerValue, T? upperValue);<br><br><br>//Example<br>// List all the avi files.<br>SortedSet&lt;string&gt; aviFiles = mediaFiles1.GetViewBetween(&quot;avi&quot;, &quot;avj&quot;);<br>foreach (string avi in aviFiles)<br>{<br>    Console.WriteLine($&quot;\t{avi}&quot;);<br>}</pre><h3>PriorityQueue</h3><ul><li>PriorityQueue&lt;TElement,TPriority&gt; is the implementation of a heap in C#.</li><li>Sorted on priority in ascending order by default(min heap).</li><li>Unlike other sorted data structure in C#, it allows duplicate priorities, but it does not follow FIFO.</li></ul><p>Implemented with a balanced binary search tree with the lowest priority on top.</p><ul><li>This has the advantage of retrieving a minimal element with O(1).</li><li>It also has O(log n) for enqueue and dequeue an element.</li><li>It takes O(n) time to search an element.</li></ul><p>Below is a max heap representation in an index tree, the elements are stored in an array.</p><ul><li>Every new element inserted, is inserted into the next empty spot, to make the heap valid once again, which is moving the element to the next element (top to bottom, left to right) and swapping it with its parents until the element is in its right place.</li><li>In max heaps, every element is larger than the elements below them.</li><li>In min heaps, every element is smaller than the elements below them.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*TqWx9-B8DXBq3Tas" /><figcaption>Credit to the YouTube video that I watched and forgot the name of it..</figcaption></figure><pre>//minheap - default<br>var pq = new PriorityQueue&lt;int, box&gt;(Comparer&lt;box&gt;.Create((a, b) =&gt; a.x - b.x));<br><br>//Methods<br>//Removes and returns the minimal element from<br>public TElement Dequeue (); // O(logn)<br><br>//Removes the minimal element <br>//Copies it and its priority to the arguments.<br>public bool TryDequeue (out TElement element, out TPriority priority);<br><br>//Add a element<br>public void Enqueue (TElement element, TPriority priority); // O(logn)<br><br>//Add a element and return the minimal element<br>public TElement EnqueueDequeue (TElement element, TPriority priority);<br><br>//Returns the minimal element without removing it.<br>public TElement Peek ();<br><br>//Returns a value that indicates whether there is a minimal element<br>//if one is present, copies it and its priority to the arguments. <br>//The element is not removed <br>public bool TryPeek (out TElement element, out TPriority priority);</pre><h3>Mapped Priority Queue</h3><p>As mentioned, there are good and bad between SortedDictionary/SortedSet and PriorityQueue.</p><p>SortedDictionary/SortedSet(TreeMap/TreeSet):</p><ul><li>Only sort on keys, not allowing duplicates.</li><li>Has O(log n) for item retrieval</li><li>SortedSet has Min/Max as properties(O(1)).</li></ul><p>PriorityQueue:</p><ul><li>Allow duplicate sorting and O(1) for min/max</li><li>Has O(n) for retrieval.</li></ul><p>Solving certain coding problems needs to make some tweaks in the existing data structure for our needs.</p><p><strong>Mapped Priority Queue: HashMap+TreeSet(Dictionary + SortedSet with a custom comparator)</strong> — a combination of two data structures provides us with:</p><blockquote>The Dictionary&lt;TKey,TValue&gt; generic class provides a mapping from a set of keys to a set of values — HashMap</blockquote><ol><li>Able to handle duplicates sorting with custom comparator</li><li>O(log n) for item retrieval</li><li>O(1) for Min/Max</li></ol><p>For example in a common question — Top K frequent words, we need to access top k most frequent words. It requires performing many insert operations. Maintaining a PQ will cost O(n), we want to optimize to O(k), and if we choose SortedDictionary, it sorts on the key, not on its frequency(value).</p><p>Maintain k size SortedSet + n size Dictionary, can handle both: keep track of all counts(in Dictionary) and the a custom comparator(in SortedSet) sorts based on the counts.</p><p>One important thing in C# SortedSet, “Changing the sort values of existing items is not supported and may lead to unexpected behavior.”, in this case, if we want to update count values in the dictionary the sorting is based on, we must remove the element in the sorted set first, then update and add the element back to the set.</p><p>Here is an example with <a href="https://leetcode.com/problems/longest-repeating-character-replacement/">longest repeating character replacement</a>:</p><pre>public class Solution {<br>//https://leetcode.com/problems/longest-repeating-character-replacement/<br>    public int CharacterReplacement(string s, int k) {<br>        Dictionary&lt;char, int&gt; map = new Dictionary&lt;char, int&gt;();<br>        SortedSet&lt;char&gt; set = new SortedSet&lt;char&gt;(Comparer&lt;char&gt;.Create(<br>            (a, b) =&gt;<br>            map[a] == map[b] ? (int)(a - b) : map[a] - map[b] <br>  //must handle queal values<br>        ));<br><br>        int res = 0, slow = 0;<br>        for (int fast = 0; fast &lt; s.Length; fast++)<br>        {<br>            char curt = s[fast];<br>            if (map.ContainsKey(curt))<br>            {<br>                set.Remove(curt);//remove the element in set<br>                map[curt]++;<br>            }<br>            else<br>            {<br>                map[curt] = 1;<br>            }<br>            set.Add(curt);//add back<br><br>            while (fast - slow + 1 - map[set.Max] &gt; k)<br>            {<br>                char slowchar = s[slow];<br>                set.Remove(slowchar); //remove the element in set<br>                if (map[slowchar] == 1)<br>                {<br>                    map.Remove(slowchar);<br>                }<br>                else<br>                {<br>                    map[slowchar]--;<br>                    set.Add(slowchar);<br>                }<br>                slow++;<br>            }<br><br>            res = Math.Max(res, fast - slow + 1);<br>        }<br><br>        return res;<br>    }<br>}</pre><h3>Conclusion</h3><p>Facing coding questions during the interview, we need to make quick judgments on which data structure to adopt. Here are few tips on sorted data structure within C#:</p><ul><li>Prioritize SortedDictionary over SortedList if there is frequent insertion, update or removal operation.</li><li>SortedList has index retrieval for its keys and values.</li><li>In updating SortedSet, first remove the element in the set, update it, then add it back.</li><li>In custom comparator, must handle when elements are equal.</li><li>PQ is bad at updating existing elements and priorities, choose MappedPriorityQueue(Dictionary + SortedSet) for frequent updates.</li><li>if you call Peek() in a much higher frequency, PQ could be better</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/932/1*BWWUZt-6QXM6ogayvNGzyg.png" /></figure><p>Reference:</p><ul><li><a href="https://medium.com/@lifei.8886196/sorted-data-structure-in-c-an-introduction-to-sorteddictionary-sortedlist-and-sortedset-19a69fe184e0">Sorted Data Structure in C#: An Introduction to SortedDictionary, SortedList, and SortedSet</a></li><li><a href="https://medium.com/@dorlugasigal/c-10-priorityqueue-is-here-5067e2628470">C# 10 PriorityQueue is here !</a></li><li><a href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sorteddictionary-2?view=net-7.0">SortedDictionary&lt;TKey,TValue&gt; Class</a></li><li><a href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedlist-2?view=net-7.0">SortedList&lt;TKey,TValue&gt; Class</a></li><li><a href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedset-1?view=net-7.0">SortedSet&lt;T&gt; Class</a></li><li><a href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2?view=net-7.0">PriorityQueue&lt;TElement,TPriority&gt; Class</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3008bf16a2bc" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>