Learning Interface through C# 2000 things

Nov. 6, 2017

Introduction

I got some advice to code to interface through the code review, so I plan to spend 2 hours to go over all interface things through C# 2000 things.

Here is the snapshot:

Code to Interface

It is so interesting to know that I enjoy to go over interface learning through C# 2000 things first. In order to understand the C# array and also IEnumerable interface, I need to go over the basics of C# first.

Actionable Items

Study Abstract class Array

Nov. 7, 2017


Actionable Item

Work on C# Array abstract class study

How many interfaces are derived from?

IClonable
IList
ICollection
IEnumerable
IStructuralComparable
IStructuralEquatable


Properties


IsFixedSize
IsReadOnly
IsSynchronize
Length
LongLength
Rank
SyncRoot

Method ( 10 methods a time)

AsReadOnly<T> (T[])
BinarySearch(Array, Int32, Int32, Object)  Use IComparable interface implemented by each element of the array and by the specified value.
BinarySearch(Array, Int32, Int32, Object, IComparer) Search a range of elements in a one-dimensional sorted array for a value, using the specified IComparer interface.
BinarySearch<T> (T[], T)
BinarySearch<T>(T[], T, IComparer<T>) Searches an entire one-dimensional sorted array for a value using the specified IComparer<T> generic interface.

BinarySearch<T>(T[], Int32, Int32, T) Searches a range of elements in a one-dimensional sorted array for a value, using the IComparable<T> generic interface implemented by each element of the Array and by the specified value.

BinarySearch<T>(T[], Int32, Int32, T, IComparer<T>) Searches a range of elements in a one-dimensional sorted array for a value, using the specified IComparer<T> generic interface.

Clear(Array, Int32, Int32) Sets a range of elements in an array to the default value of each element type.

Clone()
ConstrainedCopy(Array, Int32, Array, Int32, Int32) Copies a range of elements from an Array starting at the specified source index and pastes them to another Array starting at the specified destination index. Guarantees that all changes are undone if the copy does not succeed completely.

Start to read a question:
Why array implements IList?

IEnumerable vs IList

Nov. 8, 2017

What problem does IStructuralEquatable and IStructuralComparable solve?

Nov. 9, 2017
Read C# Array source code here. I found the link in the first few paragraphs of Array document.

Read C# SorterObjectArray - mscor.lib, the link is here. 

HackerRank - matrix rotation (Series 4 of 5)

Nov. 8, 2016

Plan to work on unfinished HackerRank algorithm related to array, try to score full score this time to celebrate new year 2017.

http://juliachencoding.blogspot.ca/2016/04/hackerrank-matrix-rotation-ii.html

Rotate array - HackerRank

problem statement:
https://www.hackerrank.com/challenges/matrix-rotation-algo

Write C# solution:

Review April, 2016 practice: 

another practice: (more than 1 hour, still having bugs, score 8.89/ wrong answer)
https://gist.github.com/jianminchen/57572227dafe939060f7cc81b193cd9b

Will come back very soon with the solution, hopefully score a hard algorithm perfectly. 

Dec. 6, 2016
Fix the bug on line 114, declare a new variable on line 114 actualSteps
C# solution - pass all test cases:
https://gist.github.com/jianminchen/6fabef7436097552e35633a549b0268a

There are over 100 C# solutions, Julia, let us have some fun; code review as many solutions as possible. 
Post C# solution here:

HackerRank - Spiral Message - NCR codesprint

Nov. 7, 2016

Problem statement

Julia spent over 4 hours to work on the solution, she made 15 submissions in the contest.

No. 1: first submission - score 4.49 of 20 (pass 4 of 14 test cases)


submission #2: (Score is 0.82 (full score is 20), pass 2 cases of 14 test cases.)


Julia's analysis after contest about the submission:
Submission #2 issues:

1. Repetition: Code is no good in structure, repetition code.
2. Structure issue: Counting mixes with string construction. Counting code duplicates 4 time. line 96 - 100
3. Base case: base case is not handled properly, one row, one column; one row will be counted twice.
4. Missing info: String split using # is avoided, just use count directly. But the spiral message is not correct.
5. Extra variables - row, col two variable can be avoided, using startX, startY, endX, endY to calculate.

No. 3 submission

code review after the contest:

1. The while loop - 115 - 119, but line 118, 119 redundant, part of first two lines.
2. Base case - one row, one column do not work - count twice
3. Add debug code - stringBuilder to tracker the string output - it is helpful, but unfortunately in the contest, Julia did not catch the error - starting point.
4. Missing start time/ end time for submission above function comment, need to track time spent.

line 49 - 59 test function: 

if the testing() function, the program does something like string.CompareTo("xaa##ar#rswx#aa") == 0 (line 209 - 210). and then, Julia would have found the start point should be lower left-hand instead of up left-hand in the contest.

No. 15. Julia's submission - score 6.7 of 20

Editorial Notes:

Think about the problem writing. Good problem writing gives out the important information, directly/ indirectly, more than once, twice.

There are 3 times to catch up spiral message starting point bug.
1. First, by following the diagrams closely.
2. Read the word by word
3. Sample test case spiral message result.

Base test case failed - bug, need to think about Math induction proof, starting from base case, and then, assuming N is correct, prove N+1 case based on N and base cases. Detail see book:
Page 15 - mathematical induction vs  programming technique of recursion

Design talk:
Spiral message - a matrix

start point matters,
choices: start from 4 corners.

Remove duplicates from Sorted Array

July 16, 2016

Problem statement:

Remove duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appears only once and return the new length.

Note that even though we want you to return the new length, make sure to change the original array as well in place

Do not allocate extra space for another array, you must do this in place with constant memory.

Example:
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

First practice:

https://gist.github.com/jianminchen/f7156b033b783b3a01c2ad2cb3d1b313

Array Class - C#, C++, JavaScript, Java

June 12, 2016

Memorize all API of array definitely will help performance, help to communicate and fast coding. Just invest time to read, memorize, and practice. More reading leads great coding experience.

Ask questions about design, why they share the same, what is difference. So, like bible verse, you will come out the API just in second when you have a problem to solve.

A small research about good programmer vs good googler:
http://juliachencoding.blogspot.ca/2016/06/good-programmer-or-just-good-googler.html

So, Julia starts to go over all API of Array class first:

in C#: (once a week, spend 30 minutes to go over all examples, memorize them all!)

https://msdn.microsoft.com/en-us/library/system.array(v=vs.110).aspx

It is an abstract class Array, implementing 6 interfaces:
   IConeable,
   IList,
   ICollection,
   IEnumerable,
   IStructuralComparable,
   IStructuralEquatable

Property:
IsFixedSize
IsReadOnly
IsSynchronize
Length
LongLength
Rank
SyncRoot

C# array method:
https://msdn.microsoft.com/en-us/library/system.array_methods(v=vs.110).aspx

40 methods:  (June 16, 2016, Go over them one by one, mark favorite ones)

AsReadOnly(T) (20 minutes June 19, 2016)
BinarySearch
Clear
Clone
ConstrainedCopy
ConvertAll
Copy
CopyTo
CreateInstance
Empty(T)


Exists(T)
Find(T)
FindAll(T)
FindIndex
FindLast(T)
FindLastIndex
ForEach(T)
GetEnumerator
GetLength
GetLongLength

GetLowerBound
GetUpperBound
GetValue
IndexOf
Initialize
LastIndexOf
Resize(T)
Reverse
SetValue
IList.Add

IList.Clear
IList.Contains
IList.IndexOf
IList.Insert
IList.Remove
IList.RemoveAt
IStructuralComparable.CompareTo
IStructuralEquatable.Equals
IStructuralEquatable.GetHashCode
TrueForAll(T)

Have to work on Enumerable 50 methods first:

System.Linq > Enumerable Class > Enumerable 50 Methods:

https://msdn.microsoft.com/en-us/library/bb342261(v=vs.100).aspx

Aggregate
All(TSource)
Any
AsEnumerable(TSource)
Average
Cast(TResult)
Concat(TSource)
Contains
Count
DefaultIfEmpty

Distinct
ElementAt(TSource)
ElementAtOrDefault(TSource)
Empty(TResult)
Except
First
FirstOrDefault
GroupBy
GroupJoin
Intersect

Join
Last
LastOrDefault
LongCount
Max
Min
OfType(TResult)
OrderBy
OrderByDescending
Range

Repeat(TResult)
Reverse(TSource)
Select
SelectMany
SequenceEqual
Single
SingleOrDefault
Skip(TSource)
SkpWhile
Sum

Take(TSource)
TakeWhile
ThenBy
ThenByDescending
ToArray(TSource)
ToDictionary
ToList(TSource)
ToLookup
Union
Where

JavaScript 
http://www.w3schools.com/jsref/jsref_obj_array.asp
https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/prototype (June 14, 2016 - go over 2 hours)
Array Methods - 25 methods

concat
copyWithin
every
fill
filter
findIndex
forEach
indexOf
isArray
join


lastIndexOf
map
pop
push
reduce
reduceRight
reverse
shift
slice
some


sort
splice
toString
unshift
valueOf


Study on June 13, 2016:
copyWithin - 3 arguments, target, start (required), end(required) (optional)

You should not use an array as associative arrays

http://andrewdupont.net/2006/05/18/javascript-associative-arrays-considered-harmful/

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from

Study:
compare to JavaScript Set object
Set

https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Set

Map

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map


JavaScript reference:

https://msdn.microsoft.com/en-us/library/yek4tbz0(v=vs.94).aspx

Array object:
https://msdn.microsoft.com/en-us/library/k4h76zbx(v=vs.94).aspx

JavaScript array study:  June 30, 2016

PROPERTY:
3 properties:

constructor,
length
prototype




constructor property:
https://msdn.microsoft.com/en-us/library/jj155291(v=vs.94).aspx


length:

array is sparse, so the array is not contiguous. The length is not necessarily the number of elements in the array.
https://msdn.microsoft.com/en-us/library/d8ez24f2(v=vs.94).aspx


Prototype:

https://msdn.microsoft.com/en-us/library/jj155285(v=vs.94).aspx


JavaScript array 29 methods:

Spend 10 minutes a time to memorize all the function names, and then, try to guess each api's task, what are the arguments, how it is designed.

write down:
Array.from   - copy array from, input argument is array.
isArray      - Array.isArray(arr)  input argument arr is array
of           - ? wild guess -
concat       - arr1.concat(arr2), concatenate the string
entries      - entries  - arguments: startIndex, endIndex, return subarray?

every        - iterator - go through each node in the array to check some logic?
fill         - fill - arr.fill(1), all the elements in the array are assigned to the same value
filter  
findIndex
foreach

indexof
join
keys
lastIndexOf
map

pop
push
reduce
reduceRight
reverse

shift
slice
some
sort
splice

toString
unshift
valueOf
values

challenges:
  Arguments:
  callback funciton -

  callback function syntax

  3 things Julia likes the JavaScript Array.fill function design:
   - start, end arguments are options
   - negative start, end arguments handling
   -
 
-- end of June 30, 2016 study --
-- End of JavaScript --

-----     Java ---
Java Array reference:
https://docs.oracle.com/javase/7/docs/api/java/lang/reflect/Array.html

Java Array

Method inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait

Method detail:
Array.newInstance

getLength
get  - Array.get(array, index)

getBoolean - Array.getBoolean(array, index)

getByte - Array.getByte(array, index)

getChar - Array.getChar(array, index)


getShort - Array.getShort(arrray, index)

getInt
getLong
getFloat
getDouble

set - Array.set(array, index, Object value)

setBoolean
setByte
setChar   - Array (Object array, int index, char c)
setShort
setInt
setLong
setFloat
setDouble

Java 
Arrays

https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html

asList
binarySearch

copyOf
copyOfRange
deepEquals
deepHashCode
deepToString
equals
fill
hashCode
sort
toString

Methods inherited from class java.lang.Object

clone, equals, finalize, hashCode, notify, notifyAll, toString, wait.

blogs to read:
asList
http://stackoverflow.com/questions/20538869/what-is-the-best-way-of-using-arrays-aslist-to-initialize-a-list


copyOfRange:
http://www.tutorialspoint.com/java/util/arrays_copyofrange_short.htm

http://stackoverflow.com/questions/11001720/get-only-part-of-an-array-in-java

more than 2 ways:
   1. copyOfRange
   2. Arrays.asList(array).subList(index, array.Length)

 
http://stackoverflow.com/questions/19389609/array-vs-arraylist-in-performance

http://stackoverflow.com/questions/716597/array-or-list-in-java-which-is-faster

  notes: List   vs ArrayList   List is interface, whereas ArrayList is a concrete class to create object.

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html

HackerRank: Connected Cell in a Grid (III) - C# solution (III) - using recursive function

April 17, 2016

problem statement:

https://www.hackerrank.com/challenges/connected-cell-in-a-grid

Here is the code studied using DFS function with return value.

https://gist.github.com/jianminchen/bc2c399407a30181ca68292459a3c791

Julia likes to practice using same idea, write her own implementation.

Practice #1: 

https://gist.github.com/jianminchen/fd909c3545e2081cf2dd2b6daea5900f

Time spent:

Copy main function from previous implementation, and write recursive function - it takes less than 15 minutes.

First time write, no bug!

April 18, 2018

Here is another writing over 30 minutes:
Practice #2: 
https://gist.github.com/jianminchen/d434bcc59ebc8eb7c2cbb20c6f48ac06

The practice goal is to see if I can shorten the time to 10 minutes in writing. How good I can write.

But, surprisingly, the practice takes 30 minutes; and I found out the several issues:
1. Timeout - recursive calls, if/ while checking
2. Array.GetLength api

First, time out issue; read a row of '0' or '1', should be if, I put a while. <- it takes more than 10 minutes to find out. I pinpoint recursive call, because I have doubt, not 100% sure.

And then, I tried to avoid the recursive call to itself, and then, (dr, dc), mistakely I put (dr, dr); HackerRank shows wrong answers for 2 test cases.

Make one change a time, and see if I can shorten the time to 10 minutes.

Study Array.getLength()
https://msdn.microsoft.com/en-us/library/system.array.getlength(v=vs.110).aspx

Another version, it takes 14 minutes to write, without a bug:
Practice #3: 
https://gist.github.com/jianminchen/bd155e574b32ebb163455dad02fa76b1

Julia's performance is up and down, from 15 minutes to 30 minutes.
Again, all practices links:
#1
https://gist.github.com/jianminchen/fd909c3545e2081cf2dd2b6daea5900f
#2
https://gist.github.com/jianminchen/d434bcc59ebc8eb7c2cbb20c6f48ac06
#3
https://gist.github.com/jianminchen/bd155e574b32ebb163455dad02fa76b1

Work on speed and accuracy. Practice, more concentrated on writing. More alert on bug code. More knowledge about api, and basic things.

Learn Jagged Array -
http://stackoverflow.com/questions/597720/what-are-the-differences-between-a-multidimensional-array-and-an-array-of-arrays

HackerRank - Connected Cell In A Grid (II) - C# solution (II) using Queue

April 17, 2:50 - 3:25

Problem statement


First practice using C#,  solution written by Julia:

C# practice by Julia


Study the code: 1. Use Queue, instead of using recursive calls, using 2 dimension array, excellent code to study:

Study code 

So, Julia did one more practice, and just wrote second implementation using idea in the above blog. 

Write C# code again using idea - 2 dimension array, queue, and also, mark the visited node using '2'. 
C# solution 1

Second Practice

It takes 30 minutes to write and fix bug, log interesting things happening in the practice:

1. First, fix the issue to read a row to a string, and then go over one char a time to get each node for the row.

   use Console.ReadKey()  first <- fatal error

2. use wrong local variable about key

3. Count should be 5 but 11 for one test case, count same thing more than once! - > add extra checking before counting. Or, set node is visited just before adding to the queue. 

Compare to the solution #1, two dimension array uses integer 1 or 0, my copy is using char '1', '0';
And also, the solution #1, every node sets visited true before adding to queue.
And my design, do not set, which causes problem. Same node is added to the queue more than once.

It is better to add unvisited node to the queue once.

Julia, you have to make sure that no bug in the code, it does not matter what idea you use. 

Third practice:

Write in 20 minutes, no bug:

3rd practice using C#


Again, 3 practices:

No. 1 - C# code

No. 2 - C# code

No. 3 - C# code

Leetcode 238: Product of Array except itself

July 24, 2015

 Introduction

I like to share the article talking about Google interview written in Chinese. The article is called "死理性派教你做谷歌面试题", the link is here. 

The experience of working on Leetcode is so challenging. I fully understand the solution but after a few days, I have no clue how it works. But there are so many good articles to read. 

Leetcode 238 in Chinese

  转载上面网页最后一段.

  不同于上面的“流传”，下面两道是已被确认了的google面试题。

第一题，给你一个长度为 N 的链表。N 很大，但你不知道 N 有多大。你的任务是从这 N 个元素中随机取出 k 个元素。你只能遍历这个链表一次，且必须保证取出的元素是完全随机的（出现概率均等）。

第二题，给你一个数组 A [ 1 .. n ] ，请你在 O ( n ) 的时间里构造一个新的数组 B [ 1 .. n ] ，使得 B [ i ] = A [ 1 ] * A [ 2 ] * ... * A [ n ]／A [ i ] 。你不能使用除法运算。

这两道题目看起来很专业，但有趣的是，即使没有学过信息学的人也可以想到答案。

第一题的意思就是有一大串物品，它们能且仅能逐个经过你眼前一次。你不知道它们的个数，要求你从中随机地抽取 k 个物品，同时必须保证取出的元素是完全随机的（出现概率均等）。

第二题给出了一个数列 A [ 1 .. n ] ，要求在较短的时间内不用除法构造一个新数列 B [ 1 .. n ] ，使得 B [i] = A [ 1 ] * A [ 2 ] * ... * A [ n ]／A [ i ] 。 n是这个数组的长度。而 O ( n ) 是评判计算方法速度的标准。如果一个解答方法在n任意变化的情况下，都能满足总共的计算次数相当于是 n 乘以一个常数C这个条件，那么就称这个解答方法是 O ( n ) 的；如果这个解答方法能满足总共的计算次数是 n ² 乘以常数C，那么这个解答方法就被称作是 O ( n ² ) 的。

第一题没有告诉我们物品的个数N，所以我们没法算出 k／N，连最基本的每样物品被选中的概率都不知道，还怎么继续操作呢？既然我们不知道一共有多少个物品，那我们就应该在所有的物品都经过我们眼前之后再做抉择。当每个物品经过我们眼前的时候，可以设法对应地给它生成一个 0 到 1 之间的随机数。等到我们见过了所有的物品之后，只需要选择对应的随机数最大的前 k 个物品就行了。

第二题不允许用除法增加了不少难度。 B [ i ] 不用除法来表示的话就是： B [ i ] = A [ 1 ] * ... * A [ i - 1 ] * A [ i + 1 ] * ... * A [ n ] 。若按照这个表达式进行计算，生成每个 B[ i ] 的时候要进行n - 1次乘法，这样一来完全生成 B [ 1 .. n ] 就需要 O ( n ² ) 的时间了。我们需要通过减少重复的运算来提高效率。

注意到 B [ i ] 可以看作是两个部分的乘积， A [ 1 ] * ... * A [ i - 1 ] 和 A [ i + 1 ] * ... * A [ n ] 。同理 B [ i + 1 ] 就由 A [ 1 ] * ... * A [ i - 1 ] * A [ i ] 和 A [ i + 2 ] * ... * A [ n ] 组成。计算 B [ i ] 时的许多乘法在计算 B [ i + 1 ] 的时候又进行了一遍，因此可以重复利用上一次运算的结果，以避免无谓的运算。从这点出发，我们构造两个新的数列：

S [ i ] = A [ 1 ] * ... * A [ i – 1 ]
T [ i ] = A [ i + 1 ] * ... * A [ n ]

因为生成完整的 S [ 1 .. n ] 和 T [ 1 .. n ] 都能在 O ( n ) 的时间内完成，那么根据 B [ i ] = S [ i ] * T [ i ] 这条式子，生成整个 B [ 1 .. n ] 便也能够在 O ( n ) 的时间内完成了。

不得不说，谷歌是个很爱玩的公司。它曾在MIT校园内到处张贴着一份密码，据说，这份密码包含了一个Google Jobs的电话号码，解开密码的人可以通过此电话留下自己的个人信息，进入谷歌工作。各位读者，你能解开这个密码吗？如果有漂亮的解答，我会在这里贴出来。

Leetcode Question No. 53: Maximum subarray sum

July 6, 2015

problem statement:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Study the code:
http://joycelearning.blogspot.ca/2013/10/leetcode-maximum-subarray.html

C# code:

https://github.com/jianminchen/MaximumSubArray/blob/master/Program.cs

https://github.com/jianminchen/MaximumSubArray_Space/blob/master/Program.cs

More reading: 

1. Keyword lookup: 

DP problem: Kadane's algorithm, maximum subarray sum

2. Write a program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

January 3, 2015

Review the question. 

Here is the link of C# solution:

https://github.com/jianminchen/Leetcode_C-/blob/master/53MaximumSubArray1.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/53MaximumSubArray2.cs

study code:

http://joycelearning.blogspot.ca/2013/10/leetcode-maximum-subarray.html


https://github.com/xiaoxq/leetcode-cpp/blob/master/src/MaximumSubarray.cpp

Leetcode: word search

July 6, 2015

Problem statement:

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

The problem can be solved using backtracking, recursive solution. 

Share C# implementation:

https://github.com/jianminchen/wordSearch-/blob/master/Program.cs

Leetcode 54: Spiral Matrix | Code review | 2015 - 2023 | Long journey

June 11, 2015

Problem Statement

Recursive solution

The first study code is here. The second is here.

Iterative solution

The first study code is here. The second one is here. 

C# code to pass Leetcode online judge:

Julia's C# code practice in 2015

Follow up 

May 23, 2017

C# practice passes all test case. The code is here. Put one row and one column checking inside the for loop statement. Code is here.

Feb. 13, 2018

It is the early day I started to write coding blog to document my code practice. At that time, I was so shy and also afraid to write down my thinking process. I do not know myself even it is just three years ago.

I just wrote down two sentences, even the sentence is not complete. I chose to study two solutions and then I practiced one of them.

One thing I can tell now is that I did not pay attention to myself, how I think as a programmer, most likely I thought that coding is more important and also challenge.

The blogs I chose in 2015

Those algorithm blogs are well-written. I am surprised that I did not practice one by one in 2015.

The recursive solution is saved in the gist. Here is the link.
The solution based on directions is saved in the gist. Here is the link.
The solution based on directions and range is here.

Follow up 

July 4, 2023

I am so lucky to have chance to prepare for another phone screen from Meta in short future. I have chance to review my work history on this algorithm.