Being interviewee: Word count practice

April 25, 2018

Introduction

It is my favorite algorithm but also it is hard to write a complete solution in 30 minutes. The algorithm is to lower the sentence, remove special char \', and then split words by delimiters such as chars in the string " .:;,!", and then save the words to the dictionary, and then sort them by value. From the dictionary, apply the sentence word order, save words in the bucket to apply bucket sort, and then output in descending order of value.

Mock interview

I tried to write the code and pass test cases in 38 minutes, but I could not make it. After the mock interview, I spent over 20 minutes to debug and fix bugs in two places.

Here is C# code written in today's mock interview 8:00 PM. On line 48, I need to remove the statement: if(item.Length == 0), actually the statement: continue is deleted by cleaning process; and on line 106, the word may not be in the dictionary.


And here is C# code written after the mock interview to fix the bugs.

Chatting

It is such a nice experience to practice the algorithm with a software engineer from expedia.com. I was asked if I work for Microsoft since I choose to use C# programming language. I couldn't believe that the peer wrote the optimal solution quick and correctly. I just could not believe that I keep meeting a very talented programmer again, in an ordinary Wednesday. I spent 38 minutes on my algorithm, the peer spent less than 20 minutes on his algorithm meeting planner.

Action items

I need to design some drills for me to work on those algorithms similar to those mock inerview algorithm, play with the error message, so I can think about how to identify issues quickly once I read some error message.

Train myself to read the error message, and also get used to pinpoint the place by interpreting the error message correctly, specially for those error message without line of code information.

My ideal practice is to fix bugs in one minute. I should be able to quickly identify the code's issue.

Work count practice

March 28, 2018

Introduction

It is very challenge algorithm to work on in 30 minutes. I have worked on the algorithm more than 6 times, but I never had chance to complete the code and pass all test cases in less than 30 minutes.

Today I also read the problem statement, I need to write code to keep the original order of words in the same bucket.

Code practice

Here is the C# code I wrote in 30 minutes in the mock interview. After the mock interview, I spent at least 30 minutes to complete the code and pass all test cases. Here is the C# code to pass all test cases.

Here are highlights of my work after mock interview:

1. line 18, Punctuation chars: "., !:;?", I missed :, ;, ?
2. line 22, Add function argument totalCount
3. line 22, function argument should be replaced, not orignal string document.
4. line 27 - line 41, I fail to call string.Replace to replace ' using empty char, so replaceChar function is written.
5. comment out line 16
6. Still confuse ToLower() function call, should string.ToLower() or document.ToLower()
Argument: string is class, not an interface, so ToLower is member function of string class, not interface member function.
7, line 57 and line 58, index variable should be used instead of using variable i defined on line 49.

Word count practice

Feb. 18, 2018

Introduction

It is hard for me to master the algorithm called word count practice.  I have to work on the string manipulations, such as lower case, remove extra chars, and split string using regular expression, and then group by the value and sort by input string order.

One more practice

Here is one more practice I did on Feb. 17, 2018 10:00 PM mock interview, I wrote 20 minutes.

Word count algorithm practice

January 21, 2018

Introduction

It is another mock interview at 4:00 pm. I had to work on the algorithm called word count in a sentence. The task is to lower the char in sentence, replace ' using empty space, split into words using delimiter string ".!,", and then store words to Dictionary<string, int>, and then apply bucket sort, and then output to array.

30 minutes is the time limit for me to write. I could not finish it.

Please complete the code

Here is the code I wrote in 30 minutes in mock interview. I like to spend time to write today and complete it to pass all test cases on mock interview platform.

Follow up 

January 23, 2018

Here is C# code to pass all test case. I spent over 30 minutes to read Regular.Split and String.Split and figure out how to specify delimiters, how to specify multiple using +, using [ and ] to enclose all delimiters, and understand ( and ) meaning.

C# code is here.

Code review "LINQ and string.Split do it yourself practice" (II)

Oct. 27, 2017

Introduction

It is the first time I understand that the technical strength can only be trained by dedicated practice. Today I had chance to walk through those five lines of C# code, and explained to the peer how to apply those things in C++ code.

Will come back to document more about the experience as an interviewer. My last blog about the code review is here less than one month ago.

Algorithm talk 

The peer likes to write C++ but the complexity of code is beyond his expectation. 30 minutes is too short to come out the workable solution.

Here is the C# code written by code review on stackexchange.com:


Each step in the above C# code can be a small function written in C++ if the peer does not know the regular expression, or similar LINQ method. 3 or 4 years job experience does not help to train yourself to be a good C++ programmer. You need to train carefully.

Actionable Item

Plan to do some research about post vacation syndrome. I need to get out of relationships from the family back in China, less frequent using wechat to communicate family in China anymore, and get back to my normal work day in the city of Vancouver. One thing I choose to do after I overcome jet lag is to practice mock interview every day 10:00 PM. Need to meet new people and learn more about the industry and people.

Give myself a pat on my shoulder. Show my report of first mock interview after a month break.

Code review "LINQ and string.Split do it yourself practice"

Sept. 28, 2017

Introduction

It is time to review the algorithm again. I posted the question more than 5 month ago, the link is here.

Algorithm Practice

I had a mock interview and the peer chose to use C++ language. I did some research how to translate those four lines of C# code to C++ language.


I just could not believe that one day I can write a product using C# advanced feature like LINQ, write regular expression and groupby clause and where clause. I am so excited to set a small goal for my next project.

String search algorithm practice

August 7, 2017

Introduction

It is the British Columbia holiday and I booked another mocking practice at 12:00 pm. The practice hours is a very happy time to learn how to work on one algorithm.

Algorithm practice

C# practice code is here. I spent over 10 minutes to fix so many compile errors, but I stopped after running into the execution errors.

After the practice, I found the two problems, one is null pointer error (4 lines of code are added from line 44 to 47), second one is missing a loop (a for loop is added on line 58), I fixed them after mocking practice.

Weakness

There are two issues in my writing in mocking interview. First one is null pointer issue. Second one is to separate the collection from one single item. Need to go over each item in collection, and append each of them.

Plan to do some research on common mistakes in C# code. Using strong typing is a good tip to allow the compiler to help, avoid error in run time checking.

Fraudulent Activity Notification - OpenBracket Code Sprint - HackerRank

Oct. 20, 2016

Julia spent over 8+ hours to work on this algorithm, and finally, at the end of day, she knew that she had to read problem statement again and figured out a new idea. She found the solution and scored 40 of 40.

But, Julia likes to write down her journey, and reminds herself to be smart, be able to find optimal solution in first time.

Here is the problem statement:

https://www.hackerrank.com/contests/openbracket/challenges/fraudulent-activity-notifications

And then, her submissions:

1. First submission:
pass 2 test cases, 5 test cases - runtime error
https://gist.github.com/jianminchen/ed96f667ca20d4ce6e5da61315e17cd5

Over 3 hours work,
1. timeout issue - use binary search to replace linear search, and see if the timeout issue can be solved.
2. Add position/ remove position - try to implement O(1) insertion O(1) deletion algorithm
code has flaws, insert position (p1) / remove position (p2),
p1 >= p2 or p1 < p2.
3. Look into C# bulk copy, Array.Copy, not sure if Array.Copy can be O(1) instead of O(n), using bulk copy, look up stack overflow a few times.

2. Find bugs, and continue to write new code.

https://gist.github.com/jianminchen/3beb1b21d99a62eb607f9f3b40a61bee

add new function called binarySearchAdd

function customizedArrayCopy (line 181 - line 190) - try to fix bugs
discuss different cases - 90 lines of code, hard to write without a bug, and so many cases,
think about cyclomatic complexity, or execution path, how many execution path with this design.

Julia spent hours on this function customizedArrayCopy, and it is hard to spot error/ fix error
on this function.

(Oct. 26, 2016, customizedArrayCopy function - If two case (line 267 - line 288), else, there are
3 nested statement: if/else if/else (line 289 - line 342); so, in total, 5 cases, line 252 - line 346;
This function is breaking SRP - single responsibility principle. The function spanning almost 96 lines
of code, Julia has to take more than 6 hours to write/ debug/ reason. This is not the code for
HackerRank contest!)

..., continuously submitted 9 times, score 0.

9th submission:
https://gist.github.com/jianminchen/0b7fe2b10b324e710066128682992c74

10th submission:  score 40 out of 40, using bucket sort.
https://gist.github.com/jianminchen/5e85135f68bc9be02be7f7390647ae00

Timeline analysis:

7:45am             - start to read problem statement
9:00am - first submission, pass 2 test cases, but timeout on other 5 test cases,
       Binary search can improve time complexity from O(n) to O(logn)
Work on binary search algorithm

10:11am   reviewed binary search function code
10:24am   found bugs related to Add position vs Remove position
10:40am look up Java AddRange, C# bulk copy

...  (Julia likes to play with Array.Copy, and other things - logic thinking if/ else. But to be a competitive programmer, Julia has to learn to sharpen her thoughts, work on optimal solution instead.)

12:00 - 9:30pm - work on the coding, try to write bug-free code, mess with ideas using Array.Copy, naively thinking about bulk copy - Time Complexity O(1)

9:30pm - gave up all the solutions, read problem statement and find a new idea:
9:30pm - 10:07 write a bucket sort algorithm, without too much effort, succeed.

Time complexity:

O(N^2) -> O(NlogN) -> O(N), N is the number of days.

Previous work on distribution sort, bucket sort:

1. Leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm
http://juliachencoding.blogspot.ca/2015/06/leetcode-maximum-gap-no-164.html

2. Radix Sort - a distribution sort
http://juliachencoding.blogspot.ca/2016/05/radix-sort-distribution-sort.html

3. Leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm
http://juliachencoding.blogspot.ca/2015/06/leetcode-distribution-sort-algorithm.html

Encouraging ending notes:
Can you give out a summary for the practice?

Answer:
10th submission:  score 40 out of 40, using bucket sort.
https://gist.github.com/jianminchen/5e85135f68bc9be02be7f7390647ae00

line 141 and line 142:

int SIZE = 201; int[] dPriorDays = new int[SIZE]; Just use space to trade off time, reduce time complexity from two loops on n - number of days to one loop on n (2*10^5), and one loop on SIZE (201) which is also constant tim O(1). Basic facts: n^2 will be around 4*10^10, it will be around 40 billion. The time complexity is shortened to 1 of 1000. Things to work on: Spend 2 hours to read this mentoring business in IT business - http://www.theeffectiveengineer.com/blog/secret-to-growing-software-engineering-career http://www.theeffectiveengineer.com/blog/five-key-skills-of-successful-programmers

leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm

Here is the leetcode link I am reading in the morning on April 4, 2015.

http://yucoding.blogspot.ca/2014/12/leetcode-question-maximum-gap.html

And then, find out myself to read this article from the following links, try to find readable explanation about the algorithms related to distribution sort algorithms.

https://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

May 22, 2016   (30 minutes at least)

Review the solution on this blog:

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/164.maximum-gap.java

Read blogs talking about algorithm first, 

https://ask.julyedu.com/question/213

Distribution Sort - 分布排序

Radix Sort - 基数排序

Actionable Items:

Spend 4 hours + work on code implementation, Java, C++ -> C# code.