703. Kth largest element in a stream

Oct. 27, 2018

Introduction

It is an easy level heap algorithm. I thought that I can write a solution using minimum heap quickly, but it took longer than one hour. I submitted more than four times and then finally I made it work.

My practice

Here is the post I shared on Leetcode discuss.

I like to write down very good experience to learn to design a minimum heap using SortedDictionary again, this time I also learned that time out issue, since I chose to count of minimum heap using SortedDictionary.Values.Count instead of keeping tracking of it by an variable actualSize.

What I did surprisingly is how to fix the timeout issue? Do SortedDictionary have issue with First() api related to time complexity?

I choose a good fight

One thing I like to do is to go for those easy level algorithms first, and also I like to show my problem solving skills.

First, I reviewed my past practice and I learned using SortedDictionary to write a minimum heap. I had rich experience to work on coding, since I have solved over 260 algorithms, I had experience to work on Merge k sorted lists, and I did study all C# submissions on Leetcode discuss.

Even though I have a lot of experience, but I still have to discipline myself again. I missed use case actualSize < size related to addNumberToHeap.

Most challenging thing is to solve timeout issue. I believe that SortedDictionary is based on binary tree to maintain the order, and I pinpointed the issue is related to check minimum heap's size. I decided to give it a try to track the size of heap by myself.

All those cases are really part of good workout for me to train myself, prepare myself for future challenge and exciting project to work.

K messed array using minimum heap using C#

August 11, 2018

Introduction

K messed array is the algorithm I practice over 10 times from March 2017 to August 2018 through mock interviews. I did not have chance to write one using minimum heap in C# since mock interview is only allowed 30 minutes for one algorithm.

Recently I practiced Leetcode 23: Merge k sorted lists. I had chance to learn to write a minimum heap using SortedDictionary.

K messed array

I spent 30 minutes to rewrite mock interview algorithm called K messed array using minimum heap. It is so excited to learn how to write a minimum heap using C# using less than 20 lines of code.

Here is the algorithm code written for K messed array.

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.

Order strings (II)

Nov. 14, 2017

Introduction

It is time for me to learn how to write a C# program and also review other's code. The second study code is written using SortedDictionary. DescendingComparer class and DescendingComparerI class are defined.

Code design talk 

Here is the C# code after I review the code.