Friday, October 26, 2018

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.

No comments:

Post a Comment