C# SortedSet talk

June 30, 2017

It is a great idea to learn C# programming language using Leetcode. Julia searches Google using keyword "C# SortedSet Leetcode", and then she finds the following algorithms to work on:

Leetcode  23  Merge K Sorted Lists
Leetcode  57  Insert Intervals
Leetcode 128 Longest Consecutive Sequence
Leetcode 220 Remove Duplicate III
Leetcode 239 Sliding Window Maximum
Leetcode 295 Median of Streams


It takes a few hours to study those algorithm written using C# SortedSet.

Window minimum

April 21, 2016

Try to get some algorithm reading and then find a similar algorithm in HackerRank, and get some workout on coding.

It is called Window minimum.

Problem statement from the geeksforgeeks website

Given an array of size N, a window of size W slides over it by increment of slide S. If the window reaches to the end, we should stop there. Find a formula in form of N, S, W so that we can find the number of valid windows. Write a program to find minimum in every window and print it. Optimize it.

e.g. {1,2,3,4,5}, W=2, S=1
first window: {1,2} min=1
second window(increment by S=1): {2,3}, min=2

…

last window: {4,5}, min=4

The array might not be sorted. I have taken sorted array for simplicity.

or in Chinese, 

滑动窗口求最小:

 给了一个ArrayList：4, 2, 12, 11, -5，窗口size为2，返回的ArrayList为：2, 2, 11, -5。这里窗口size是一个参数。

Leetcode 239: Sliding window maximum

Read one of solutions using Java:
Java solution 

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