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.

C# Minimum Heap implementation

June 28, 2017

Introduction

There is a PriorityQueue class in Java for minimum heap, but in csharp programming language, there is no class. Julia has to figure out how to write one by herself.

Search the blog using minimum heap implementation, the link is here.

Algorithm study 

8:00 pm - 8:30 pm C# practice is here.

Julia met a peer who is a computer science Ph.D., and she was asked to simulate the minimum heap using Array, Array.Sort. Julia followed the hint and she did write one. It works and the solution is correct. But she likes to make her simulation better. There is only 30 minutes in mocking experience, Julia could not write a real minimum heap so she chose to use an array and then sort it using O(nlogn) algorithm.

She needs to look into C# books and figure out how to do it better in short future.

One of ideas is to use C# SortedSet class. Review previous practice on Leetcode 295: Median of stream.

Leetcode 295 Median of stream

May 31, 2017

Leetcode 295. Find median from data stream - discussion panel is here.

C# solution using SortedSet. The C# code to study is here.

C# solution using MinHeap/ MaxHeap - self defined. The study code is here.

Read blog about the discussion again - link is here - the blog on ardendertat.com

Question 69: Median of a stream (Julia's ranking:  10 out of 10  March 31, 2017), book: Code interviews, Harry He. 

Follow up 

June 6, 2017

Julia C# practice using SortedSet, the code is here. 

Julia C# practice using self-defined Heap, the code is here. 

June 29, 2017
Review SortedSet implementation, the code is here. 

Actionable Items

Google search "SortedSet C# example leetcode", work on related algorithm, try to get more practice on SortedSet. 

Messed array k step away small talk

April 15, 2017

Introduction

Julia was busy with Hackerrank week code #31 this morning starting from 8:00 am and she had some issues about her attitude to test cases, last night she stayed up to 1 am to work on coding with test cases. She failed 50% test case of minimum spanning tree, and she thought that this Saturday morning time is the wonderful time to learn how to strength her test skills, she tried to fix those failed test cases today.

Last night 10:00 pm she had a mocking experience but she felt kind of disappointed, because she liked to get more mocking comment. Last night she did not get optimal solution. She could not think freely to reach optimal solution.

But today 10:00 am mocking experience is a very good experience, best of 8 mocking experience. She spent over 10 minutes to work on time complexity analysis, O(k²) -> O(klogk) -> O(k), she stopped before she thought about O(1), she knew that it is not so good to find minimum value using O(k) time. She asked for a hint, and then she was given to think heap sort. She got it right away, O(1) to get the minimum value if minimum heap is used to store k elements. Because all k numbers does not need to be sorted, only minimum value is needed.

Using O(k) time to get minimal is not optimal, use space to trade time, use a binary tree - a data structure to store k element, minimum value is the root of binary tree, that will be O(1) time. Actually it is named minimum heap.

Small talk about messed array 

The 30 minutes mocking experience is here with transcript, thought process, hint given and C# code.

Actionable Item

This is the first time in last 8 experience Julia got rate of 7 for her code. 30 minutes is long time for a conversation. Writing code was to write down what she described in the test case. Even though Julia worked on first 10 minutes without coming out using heap sort, she understood the solution and how to approach the problem by going through a simple test case [1, 2, 3, 4, 5].

"Really familiarize yourself with the sorting algorithms. You definitely understand them but get to a place where you can recall them more intuitively."

Facts

The problem is so subtle and then Julia did not come out using heap sort, even though she wrote about the algorithm of search medium using O(1) about a data structure a few days ago. 

Follow up 

June 28, 2017  8:00 pm - 8:30 pm
C# practice code 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