C# Minimum heap using SortedDictionary

August 4, 2018

Introduction

There is no C# class like Java PriorityQueue for minimum heap. I learned to write a minimum heap using SortedDictionary since I read the source code to study the problem solving of the algorithm called Merge k sorted lists recently.

I like to write a blog to document my experience.

Source code 

Here is C# source code to write a minimum heap using SortedDictionary. Also the folder is here to access my practice for the algorithm 23 Merge K sorted lists.

Challenge 

Here is the fact:

Julia, you spent 10 rounds of mock interviews from March 2017 to June 2018. You could not come out using SortedDictionary to write a simple minimum heap for K messed sorted array algorithm.

Give a few arguments to defend yourself:
I do not spend time to read SortedDictionary source code.
I do not know how SortedDictionary class is designed, why it is needed.
I do not try to memeorize all APIs from SortedDictionary.
I do not have chance to read the code using SortedDictionary to solve the problem.
I did search why C# does not provide PriorityQueue like Java, but I do not find alternatives with source code using SortedDictionary. 
I got so many choices to continue to study and improve. I just move on other problems to solve.


Give a few advice how to break through the problem:

Please provide a possible three solutions you can approach to come out a written solution like using SortedDictionary.

Follow up

March 26, 2019

I reviewed the solution written for union find algorithm, and then I will write new version using SortedDictionary as well.

Here is the folder to contain my practice.

Here is the union find algorithm using SortedDictionary

Follow up 

June 4 2020
I like to work on 215 Find kth largest element in the array using SortedDictionary. The idea is to write a solution using minimum heap.

Minimum Heap - C# practice

April 23, 2017

Introduction

A minimum heap C# code is needed for the Email everywhere algorithm in a booking woman in tech contest, so Julia googled and found the C# code. She put together with the algorithm and then she scored 30 points with a full score. Learning to use heap is a great mark for Julia, she knows that completely sorting is expensive, if only max and min value is needed, better to use binary tree, not binary search tree. Julia starts to learn using heap when she work on algorithm problem solving.

Code review 

C# code is here. Need to add some test case and do some code review.

Leetcode website and community

April 5, 2017

Introduction

Julia learned something from her mock interview yesterday. The interviewer shared his leetcode user id. So, Julia chose her study topic today - Leetcode website.

Julia likes to study what she can learn from mock interview. She likes to google it, and see there is a good topic on that.

Leetcode website 

Julia plans to read more leetcode discussion pages.

Here is the link of heap related posts search by tag - heap.


Study all tags - link is here.

Most reputable users - link is here.

Most popular - link is here.

Algorithm night (3)

January 21, 2016

Find 10 challenging algorithms questions, and then go over them one by one. It is fun, and also good learning experience.

She wishes that she could have more than 100 algorithm night, reviewed 1000 algorithms already, and each time, just so relax to go over different ideas how to solve them, by reading, and by good hints and teaching through blogs. At that time, she will be good thinker about algorithms. Wishful thinking, get back to reality (5 algorithms, 2 hours, a lot of headache, and could not figure out what is brute force solution.), work on 3rd algorithm night.

Be humble, be stupid, and learn from mistakes.

1. Leetcode 295: Find medium from data stream 

https://segmentfault.com/a/1190000003709954
https://gist.github.com/jianminchen/31572a64b2af48e3ccce


http://buttercola.blogspot.ca/2015/12/leetcode-find-median-from-data-stream.html


Julia, read Java priorityQueue class and get some ideas about the class design:
http://www.programcreek.com/2009/02/using-the-priorityqueue-class-example/

http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue

understand priority queue first, read the lecture notes:
http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf

2.  min stack
http://buttercola.blogspot.ca/2015/11/zenefits-mini-stack.html

3. 写一个函数float sumPossibility(int dice, int target)，就是投dice个骰子，求最后和为target的概率。因为总共的可能性是6^dice，所以其实就是combination sum，求dice个骰子有多少种组合，使其和为target。先用brute force的dfs来一个O(6^dice)指数复杂度的，然后要求优化，用dp，最后结束代码写的是两者结合的memorized search吧，

https://gist.github.com/diegozeng/6c964f623bbeaa716526

http://www.labnol.org/internet/github-gist-tutorial/28499/

4. Possible triangle
http://www.geeksforgeeks.org/find-number-of-triangles-possible/

http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers

Argue about how to reduce time complexity from O(N^3) to O(N^2), how exactly i, j, k three variable, k is only from 0 to n-1 once for each i, nothing to do with j. So, it is time for i - from 1 to N, and time for j from 1 to N two loops, and then for i - N, and k from 1 to N ( skip j - big point! Cannot figure out easily. )

5.  Top K int in a large stream (This can be done in O(n))
http://stackoverflow.com/questions/185697/the-most-efficient-way-to-find-top-k-frequent-words-in-a-big-word-sequence

6. Leetcode solutions - blog reading
Just read as many solution and see if there are something new to write down here:

http://www.cnblogs.com/grandyang/p/4606334.html  ( No. 1 - No. 280)

Review Leetcode questions 1 - 20 (January 24, 2016)

So, here are some notes about DFS - backtracking problem solving:

1. DFS vs BFS, DFS usually involves backtracking as well. So, remember backtracking.
2. How to design the DFS function?
    A. return result - one of arguments:
   IList<string> res
    is a good idea, also, it can be member variable of class Solution.
    B. Convert a char to integer '1' -> 1
         quickest way is c - '0'
    C. Backtracking is the key to ensure the bug free
    D. Java, C# using stringBuilder to construct string, append

Review solutions:
http://codesniper.blogspot.ca/2015/03/sticky-post-all-of-my-published.html

Java solution:  Leetcode 1 - 120

Leetcode 239: sliding window maximum

August 7, 2015

Julia spent 20-30 minutes to think about solution first, and read the following blogs, write some code as well. She practised three time using C# and here are the details.

C# practices

Here are 3 practice Julia did using LinkedList, List and SortedList. 

1. C# LinkedList

C# code implementation

2. C# List<int>

C# practice code

3. C# SortedList

C# practice code

More detail

Double ended queue is implemented using C# LinkedList class, here is Julia's C# practice code: C# code implementation

Julia chose to study the blog on Leetcode: sliding window maximum

C# code implementation (C# does not have deque class, so using C# List<int>, 

convert Python code implementation to C#, time limit exceeded)

Good workout on C# List<int>, Julia experienced different style on removing head element if out of sliding window. 

C# practice code 

Julia chose to read the blog on geekforgeek.com called "maximum of all subarrays of size k". 

Method A: naive solution, time complexity O(nw)
C# practice code is here. 

Method B: using Self-Balancing Tree (Time complexity: O(nk), need to write c# code)

C# practice code is here. 

4. blog:

http://yuanhsh.iteye.com/blog/2190852

http://n00tc0d3r.blogspot.ca/2013/04/sliding-window-maximum.html

Good comment about Deque:

We can use a Deque which allow insertions/deletions on both ends. For a Deque implemented by Circular Array/Buffer or Double Linked List, the basic insert/delete operations run in constant time.

discussion of using heap: 

 The first thought might be heap.

By maintaining a heap for all numbers in the window can give us a O(nlogw)-time solution, where

• building up a heap for initial window takes time O(wlogw)
• when window moves to the next number, each insertion and deletion take time O(logw) and there are n-w moves in total.
• after updating the heap, findMax only takes time O(1) since we know the top of heap is the largest.
•  

So, if w << n, the performance of this solution is good, close to O(n); but if w is not that small, say w = n/3 or n/4, the running time goes up to O(nlogn).

5. blog:   C++ code 

using C++ multiset in the above solution, so try to convert it to C# class using SortedList

C# practice code

6. blog:
http://www.mamicode.com/info-detail-927510.html

Convert Java Script code to C#; I spent over 12 months to try to be expert on Java Script, so much fun to read the Java Script code again, and enjoyed the blog about the analysis. 

Others:
https://github.com/jianminchen/slidingWindowMaximum/blob/master/slidingWindowMaximu5.cs

http://www.cnblogs.com/grandyang/p/4656517.html

http://techinpad.blogspot.ca/2015/05/lintcodeleetcode-sliding-window-maximum.html