Some algorithms to study

May 13, 2016

Introduction

Here are some algorithm problems Julia likes to review, what she did is to spend 2 hours to go over Glassdoor.com and go over the interview questions on companies (A, F, L, M, G) from 2016 backward to January 2015.

As a software programmer, Julia knows the value of good thinker in algorithm, problem solving; and write readable, clean code to implement the idea using Java, C++, C#, JavaScript, learn through simple problem solving every day.

Algorithms to review

Put problems in the groups to help study:

Array:

1. Leetcode 23 - Merge K sorted array 

http://www.geeksforgeeks.org/merge-k-sorted-arrays/

-- read stack, queue, priority queue - definition - May 13, 2016

https://msdn.microsoft.com/en-us/library/4ef4dae9.aspx

read through priority queue API document, and understand more if I can.

2. Leetcode 215: Find the kth largest element in an array
http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

Tree problems:

1. Check if given binary tree is a mirror.  

2. Serialize and deserialize the tree

3. Get mirror image of a BST

4. Connect nodes at the same level in a binary tree  

    http://www.geeksforgeeks.org/connect-nodes-at-same-level/   (? bug)
   better one:
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree-using-constant-extra-space.html


Leetcode:

1. Leetcode -- 3 sum 

2. Leetcode 215  - Kth largest elment in the array (quick select)

Linked List:

1. If we have a linked list, and if I give you a number n, then first n node of the linked list should get reversed next n node should as it is, next n should get reversed like wise.

For example, n=3 

String:

1. Given an array of strings,  need to check every string in the array is a palindrome or not.  If it is, we have to print it.  

http://codereview.stackexchange.com/questions/73542/hashtable-implementation

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

2. Write a function to determine the longest palindromic substring of a given string.  

3. Find the minimum number of palindromes in a string. 

Sorting:

1. Write a merge sort 

Hashtable:

1. How do you implement a hash table? 

Dynamic Programming:

1. optimal coins

2. Ladder of height 100, u can use jumps {1,2,3} how many different ways can u reach 100.

DFS/ BFS/ Search:

1. Transform a [1,0] matrix grid into matrix grid of manhattan distance between closest 1's  

2. Given a certain number of tasks with specific start and end times, find the maximum number of jobs that can be 

done   

Misc:

1. Check whether rectangle overlap

2. Reverse a matrix in a given sequence

http://iwillgetthatjobatgoogle.tumblr.com/post/11352414963/implement-a-hash-table

3. There is a 9 digit number, you need to rearrange the number and make just bigger number then this one

    pivot element - google to find a solution

4. There are 9 buckets,Each bucket contains some chocolates(number of chocolates labeled on the bucket), a kid is there, He takes 1 second to eat all the chocolates of 1 bucket and as puts the bucket back, bucket gets filled again with the half chocolate then the original bucket had. kid has n second, find a way in which he can eat max chocolate in n seconds.

5. Find the next largest number.  

6. Solving the jigsaw puzzle. Input is the pieces of the puzzle and a method taking two pieces as input and returning true if they fit.

Leetcode 17: Phone Number - Practice using DFS/ Stack and BFS/ Queue

May 12, 2016

 Write two more practice using Queue/ BFS and DFS/ stack on this leetcode question:

Using Queue/ BFS
https://gist.github.com/jianminchen/5691a3488a2ef4f0660194502ae15f68

Using Stack/ DFS
https://gist.github.com/jianminchen/872bf70039fa8c61ff208b34a591c8ec

Previous blogs about practice:

April 21, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/04/window-sum.html

January 24, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/01/leetcode-17-letter-combinations-of.html


Question and Answer:

1. What is the difference using Queue and Stack on space usage?

For example, using Queue/ BFS, source code line:

Line 31: IList<string> list = letterCombination("234"); // test result: "abc", "def", so 3x3 = 9 cases. If the string is "2345678", 7 digits string, then, when first string is added to the list, on line 86, the queue's count is around 3^7 = 9 * 9 * 9 * 3, more than 2000 records in the queue. However, using Stack/ DFS, source code line 31, the string is "2345678", when the first phone number is added to the list, the stack size is around 3*7 = 20, around 20 records in the stack. So, it takes more space to use queue/ BFS on this problem solving, not efficient on space usage.

2. Please look into string, stringBuilder on this problem solving.
Read more blogs on this discussion:

Algorithm: Rotate array by one element

May 11, 2016

Quickly find out the blogs related to "Rotate array by one element", look for optimal solution. Julia, it is not so important to show optimal solution, but  at least, never waste the opportunity to show that you are a hacker, willing to solve any problem.

Anything about rotate two dimensional array:

1.
http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array

2.
https://blogs.msdn.microsoft.com/oldnewthing/20080902-00/?p=21003

3.
http://geekswithblogs.net/cwilliams/archive/2008/06/16/122906.aspx

4. Matrix transpose
https://en.wikipedia.org/wiki/Transpose

Question and answer:
1. How many hours do you spend to work on this problem?
Reading 2 hours +. 

Leetcode 48: rotate image

May 11, 2016

Julia likes to study the algorithm: rotate image

http://fisherlei.blogspot.ca/2013/01/leetcode-rotate-image.html

http://shunrang.blogspot.ca/2015/10/rotate-image-and-spiral-matrix.html

Leetcode 239: sliding window maximum

May 11, 2016

Study two blogs. The first one is written in Chinese, link is here. And the second one is here.

Read the blog, link is here.

Julia, please write down your C# practice:

Question and Answer:
1. How long do you study the problem? What do you learn?

Julia spent over 30 minutes on this question. And she learns that deque is excellent data structure to achieve optimal time complexity and complete the task.

2. Can  you tell the concrete the example and show how to solve the problem?

Just think like a greedy algorithm. Make the special data structure like Java Deque data structure, every node is added to the deque once and also removed once. Keep the deque as small as possible, in other words, if the element cannot be the maximum of sliding window, then it should be removed from deque right away.

So, time complexity is O(N).

Also, make it greedy, inside the deque, all elements are sorted by descending order from left to right.

For example, windows size with 4, [1, 3, -1, 2], no matter what next numbers are, 1 and -1 are never going to be a maximal as the window moving. The queue should like [3,2].

So, to maintain the queue in order.
add node in queue from right side only; but remove nodes from both end, just before a node is added.

3. Time complexity analysis:
For those solutions - you can come out:
A. Use heap, or other solutions, time complexity can up to O(nlogn).
w - window size
n - array size
Building a heap, time complexity O(wlogW)
...
so, if w<<n, close to O(n), but if w = 3/n or 4/n, the running time goes up to O(nlogn).
B. ?

4. Learn Java Dequeue class, and C# linkedList:
   API:

   First:
   getFirst
   RemoveFirst
 
   Last:
   addLast
   getLast
   removeLast

   isEmpty

Leetcode 317 - shortest distance from all building - a warm up practice (Part 3)

May 11, 2016

Julia spent time to rewrite the algorithm on Leetcode 317.

Here is her last practice on January, 2016. The blog is top 3 most visited blog - 138 visit up to May 11, 2016. So, she is encouraged to rewrite the code.

Her practice after 4 months is here.

She likes to do more writing on this algorithm, try to figure out ways to improve the performance.

HackerRank – Connected Cell in a Grid - Warm up with Five Practices (V)

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016:

http://juliachencoding.blogspot.ca/2016/04/hackerrank-connected-cell-in-grid.html

Fifth practice, using stack instead of recursive function, implement the DFS algorithm:

https://gist.github.com/jianminchen/11725341e9474e0503950616c9ad1848

Question and Answer:

1. What do you like the approach - using stack, DFS algorithm? 

To write using stack is similar to using queue, but the search is DFS instead of BFS. Julia does not have time to build a test case to compare the order of visited nodes this time. 

HackerRank – Connected Cell in a Grid - Warm up with Five Practices (IV)

May 11, 2016

Warm up an algorithm like tennis sports, work on different strokes before she plays matches. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016:

http://juliachencoding.blogspot.ca/2016/04/hackerrank-connected-cell-in-grid.html

Fourth practice, using DFS – recursive function, but use an argument – reference int to track value

     https://gist.github.com/jianminchen/589f05f5c87bb6e018de0a472d8a3b6f

Question and Answer:

1. What do you like the approach - DFS, recursive function, use an argument - reference to track the count? 

Julia likes to use an argument to track the count, and let the recursive function return void. 

HackerRank – Connected Cell in a Grid - Warm up with Five Practices (III)

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016:

http://juliachencoding.blogspot.ca/2016/04/hackerrank-connected-cell-in-grid.html

Third practice, use DFS – recursive function, which also returns the count.

         https://gist.github.com/jianminchen/2279967c64a712fb138355b69a6201dd

Question and Answer:

1. What do you like this approach? DFS using recursive function, which returns the count? 

It is easy to write, less error prone; most efficient in time consumption. 

HackerRank – Connected Cell in a Grid - Warm up with Five Practices (II)

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016:

http://juliachencoding.blogspot.ca/2016/04/hackerrank-connected-cell-in-grid.html

Warmup coding: 

Her practice, using queue, but use jagged array:  (20 minutes to write), using queue, jagged array, 

https://gist.github.com/jianminchen/9cf4702b56dc7a57ec6b699449b89593

Question and answer: 

1. How is the warmup experience? 

Because this is the second one, after 1 hour writing, debugging the code in first practice using dimensional array/ queue, this one is much easy. Just replace the dimension array using jagged array. 

HackerRank – Connected Cell in a Grid - Warm up with Five Practices

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016.

First practice, it takes her close to 60 minutes to write, fix issues.  Use dimensional array, use queue to do BFS – breadth first search.

C# code 

Here are mistakes:

      1. Forget to add boundary check function, do boundary check (source code: line 108)

      2. Forget to introduce neighbor_X, neighbor_Y  (source code: line 90, 91)

      3. Neighbor_X is mistakenly written as neighbor_Y, so wrong answer;

          Debug the code and find the issue. It takes more than 20 minutes, a lot of stress. (source code: line 96)

So, it is excellent chance to learn and improve the performance.

Write a small function to debug the code, figure out the wrong answer issue – testRoutine, source code: line 36.

C# code with an extra debug function

Second practice, using queue, but use jagged array:  (20 minutes to write)

C# code using jagged array

          

Third practice, use DFS – recursive function, which also returns the count.

C# code using DFS, recursive function

         

Fourth practice, using DFS – recursive function, but use an argument – reference int to track value

C# code using reference integer in function argument     

Fifth practice, using stack instead of recursive function, implement the DFS algorithm:

C# code using stack

Question and answer:

      1. What do you learn through the warm up? Do you learn some better ways to fix the bugs?

It is better to write down the functions needed to help the task, this way, you will be more efficient.

Here are 4 tasks:

     1. Calculate the key

     2. Boundary check 

     3. Maximum value search

     4. Using queue to do search

     2.  Why do you do warm up this time? What are the advantages?

Julia still remembers the favorite tip to work on the tasks:

1.    Just mark the visited node as 0 from value 1

2.    Update node value from 1 to 0 before it is added to the queue

3.    Use key = row * 10 + col, since row < 10, col < 10 to track each node in the queue

Julia likes to write code and do some warm up, therefore, she can get more experience; she tries to improve performance to 20 minutes for this kind of DFS, BFS, matrix, search algorithm.

3. Do you reproduce the experience of high stress to trouble shooting and work on bug fix? 

Julia reproduced the issue of high stress, she could not fix the bug on her first practice. So, she wrote a small debug function try to figure out; actually, it is a mistake in writing. 

Next time, reexamine every line of code, every variable, every executable path, when the code is executed. Do not depend on debugging, running the code, because stress level is high. 

External merge sort - Duplicate Elements of An Array

March 10, 2016

External merge sort, distributed algorithm discussion. Very good topic, and enjoy the reading.

External merge sort article:
http://goo.gl/wbwAi8

More reading:

https://en.wikipedia.org/wiki/External_sorting

http://www-inst.eecs.berkeley.edu/~cs186/sp08/notes/08-Sorting.pdf

Write down some notes, and tell what you learn through the study.

Common mistakes in code writing

May 9, 2016

  Julia likes to do some research on common mistakes in code writing.

  Here are the articles she chooses to read:

1. https://www.quora.com/What-are-the-common-mistakes-made-by-beginner-competitive-programmers
2. https://www.quora.com/How-do-you-debug-your-code-quickly-in-programming-contest-environments
3. https://www.quora.com/What-are-some-macros-that-are-used-in-programming-contests
4. https://www.quora.com/What-was-the-biggest-mistake-you-made-while-practicing-for-a-programming-contest
5. https://www.quora.com/What-are-some-cool-C++-tricks-to-use-in-a-programming-contest
6. http://www.cprogramming.com/tips/

Favorite tips:
  1. be aware of loop invariants
  2. passing array elements to functions

Common mistakes in interviews:

6. http://www.geeksforgeeks.org/top-5-common-mistakes-in-technical-on-site-interviews/

7. http://warrington.ufl.edu/graduate/gbcs/docs/50jobinterviewmistakes.pdf

8. http://skillcrush.com/2016/02/16/common-tech-job-interview-mistakes/

9. http://www.thegeekstuff.com/2013/11/interview-mistakes/

HackerRank: Greedy Algorithms

May 9, 2016

Work on easy algorithms in Greedy category:

1. Grid Challenge

2. Beautiful Pairs

3. Jim and the Orders

4. Mark and Toys

HackerRank: Search algorithms

May 9, 2016

Work on a few of search algorithms:

1. Ice Cream Parlor

2. Maximise Sum

3. Missing Numbers

HackerRank: Algorithms > Sorting

May 9, 2016

Work on Sorting Challenges:

Value the easy question. Write your own code, and then, study other's submission. Rewrite the code again and again, learn how to stay focus, and avoid common mistakes in writing.

1. Insertion Sort - Part 1 (Easy)

2. Insertion Sort - Part 2 (Easy)

3. Correctness and the Loop Invariant

4. Running Time of Algorithms

5. Quicksort 1 - Partition

6. Quicksort 2 - Sorting

7. Quicksort In-Place

Height of a tree

May 9, 2016

problem statement:
https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree

Julia's practice:
https://gist.github.com/jianminchen/18de7257b29bf6ccbab63cdc93d4077f

Reverse print

Problem statement:
https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list-in-reverse

Reverse print:
https://gist.github.com/jianminchen/91e8dfeac0e962307b30f4afd0bb6f98

Submission reading: 10 - 20 minutes.
https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list-in-reverse/leaderboard

Compare two linked list

May 9, 2016

Problem statement:
https://www.hackerrank.com/challenges/compare-two-linked-lists

Compare two linked list:
https://gist.github.com/jianminchen/904a955b78a56ece032f5b9a681f91fc

Submission code to study:
https://www.hackerrank.com/challenges/compare-two-linked-lists/leaderboard

Iterative solution:
https://goo.gl/vyGJkW

Merge two sorted linked list

May 9, 2016
Problem statement:
https://www.hackerrank.com/challenges/merge-two-sorted-linked-lists

Merge two sorted linked list
https://gist.github.com/jianminchen/c09df676896e938d7f6c3819e301545c

Reverse a doubly linked list:

May 9, 2016

Problem statement:
https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list

Reverse a doubly linked list:
https://gist.github.com/jianminchen/5bdf999c91964e87788e0d010eb52e53

Linked List: print list

More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1



print list
https://gist.github.com/jianminchen/cd219738d812605e0c6ced926d2e488c

Insert a node at tail of a linked list

More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1


Insert a node at tail of a linked list
https://gist.github.com/jianminchen/957d2025fd310a9e59fb88fe8766e0de

Insert a node at the head of a linked list

More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1



Insert a node at the head of a linked list
https://gist.github.com/jianminchen/79dd121f3135769d57088c7d2e9e51fe

Insert a node at a specific position in a linked list

More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1


Insert a node at a specific position:
https://gist.github.com/jianminchen/5b357be38d6bad427e885c7b7343c19b

Linked List: Delete a node

More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1


Delete a node:
https://gist.github.com/jianminchen/d0a360f5a5a4be3b6d94e09d6bd0f266

Reverse a linked list

More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1

Reverse a linked list:
https://gist.github.com/jianminchen/2c0203cebd076ae329a10e870c414219

HackerRank: Linked List - Get Node value

More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1

Get Node value:
https://gist.github.com/jianminchen/d4da2ec82876d93bcd1920927054702d

HackerRank: Insert a node in a double linked list

May 8, 2016


Problem statement:
https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list


Julia spent over 30 minutes to work out a solution:

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

A few of mistakes in first writing:
1. If the list is empty, add a new node, forget to return the node;
2. Insert a node, 3 possible positions:
   before the head,
   in the middle of list,
   at the end of list <-  edge case -> forget the edge case first time

Review other submissions:

Question and answer:

1. What do you learn through the study?

Julia learns to write an iterative solution for the problem. And also she fixed all the bugs and then complete the task.

The solution Julia takes is not the best one, she uses dummy head node to help, and then, use iterative solution to the do work. Need more practice.

She learned that she needs more ideas, in order to complete it in less than 10 minutes.

Also, the linked list - the simple problem is also very helpful to learn how to think recursively.

2. This is a solution to study - use recursive function, much short code, less time to write:

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

Before Julia reads the code in detail, she wrote her own recursive solution. It is fast, no dummy head need, and also much easy to read:

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

Forget to add one more line: after line 30, before line 31.
(head->next)->prev=head;

Let us talk about the idea using recursive function - how to design the function? 

Test case: 2->4->6, insert a value 1, 
First, deal with the case that the list is empty: create a new node, and then return;
Second, if the inserted value is less than head's value, then create a new head with value 1, 
link it to the head; 
Otherwise, the first node is processed, and the next node of it is the value of recursive call. 
It saves time to write recursively here.


3. What are the common issues you find in the submissions?

https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/leaderboard

--
More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1

Get Node value:
https://gist.github.com/jianminchen/d4da2ec82876d93bcd1920927054702d

Reverse a doubly linked list:
https://gist.github.com/jianminchen/5bdf999c91964e87788e0d010eb52e53

Merge two sorted linked list
https://gist.github.com/jianminchen/c09df676896e938d7f6c3819e301545c

Compare two linked list:
https://gist.github.com/jianminchen/904a955b78a56ece032f5b9a681f91fc

Reverse a linked list:
https://gist.github.com/jianminchen/2c0203cebd076ae329a10e870c414219

Reverse print:
https://gist.github.com/jianminchen/91e8dfeac0e962307b30f4afd0bb6f98

Delete a node:
https://gist.github.com/jianminchen/d0a360f5a5a4be3b6d94e09d6bd0f266

Insert a node at a specific position:
https://gist.github.com/jianminchen/5b357be38d6bad427e885c7b7343c19b

Insert a node at the head of a linked list
https://gist.github.com/jianminchen/79dd121f3135769d57088c7d2e9e51fe

Insert a node at tail of a linked list
https://gist.github.com/jianminchen/957d2025fd310a9e59fb88fe8766e0de

print list
https://gist.github.com/jianminchen/cd219738d812605e0c6ced926d2e488c

Trees:
Problem statements:
https://www.hackerrank.com/domains/data-structures/trees

height of tree:
https://gist.github.com/jianminchen/18de7257b29bf6ccbab63cdc93d4077f

Top view:
problem statement:
https://www.hackerrank.com/challenges/tree-top-view
https://gist.github.com/jianminchen/f7742a123f3524c1d0fbd98e71c8f516

Level Order Traversal:
https://gist.github.com/jianminchen/a3194f885fc542a7f5827cbcdc92a3f5

HackerRank: Linked List - Find Merge Point of two linked list

May 8, 2016

Problem statement:
https://www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists

Cpp solution:

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

Value simple, easy question, solve the problem, learn from other submissions. From the simple ones, build up skills, feel more comfortable to solve moderate, difficult one later.

Submissions:
https://www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists/leaderboard

Julia's favorite code:
1. define a few functions, very well written:
length, position, common - use recursive function, very short function - 3 lines of code each function
https://gist.github.com/jianminchen/2ab387360a0ff2ef41c10c67219fd1c1
source:
https://goo.gl/J5WK7y

2. unbelievable short - only use for loop to do things:
https://gist.github.com/jianminchen/9d14ff515146af193c4bee660b0a6fb8

Question and answer:
1. What do you learn through the problem solving? Code submission study?

Julia likes to document the problems she found when she reads first 100 solutions, in order to improve the speed, accuracy, and avoid bugs - avoid repetition of same logic:

1. Best code she found so far:
https://gist.github.com/jianminchen/2ab387360a0ff2ef41c10c67219fd1c1

2. One is to use brute force, go through each node in the first list, compare to each node in the second list; The algorithm is not optimal.

3. Shortest time to write the code, in less than 20 lines:
https://gist.github.com/jianminchen/9d14ff515146af193c4bee660b0a6fb8

3. Repeat same code twice - if/else statement - avoid two cases, simplify to one case.

4. Same code as Julia does, but better code:
https://goo.gl/NXTurm

HackerRank: Delete duplicate value nodes from a sorted linked list

May 6, 2016

Easy question - Linked List

Problem statement:
https://www.hackerrank.com/challenges/delete-duplicate-value-nodes-from-a-sorted-linked-list

Julia's solution:

https://gist.github.com/jianminchen/9013539e71764a018f3745c514da9d91

Most favorite solution:

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


/*
  Remove all duplicate elements from a sorted linked list
  Node is defined as
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* RemoveDuplicates(Node *head)
{
    Node *cur = head;
    int last_seen = cur->data;
    while(cur->next) {
        if(cur->next->data == last_seen) {
            cur->next = cur->next->next;
        }else {
            cur = cur->next;
            last_seen = cur->data;
        }
    }
    return head;
}

Question and Answer: 
1. What do you learn through the practice? How long do you take?

Julia spent more than 30 minutes to work on this question; She wrote a two nested loops, and then, came cross time out issue; She tried to direct a pointer to correct position, like 1->1->1->2, she likes to set up first node with value 1's next point to 2. She was in hurry, tried to do it once to make it work in nested second loop. Actually, she figured out the solution just be lazy to let first node with value 1 to point to third node with value 1 first.

Then, she came out this solution using one loop only:

https://gist.github.com/jianminchen/9013539e71764a018f3745c514da9d91

2. What do you learn through studying other submissions?

Julia learned that through the problem solving, she read first 20 submissions, 80% of them should get rid of two loops, or reduce code length to less than 10 lines; one loops is enough to take care of the business; But, people stop when the code works.

Julia knows that value of excellent code. She has to push herself, train herself to discipline herself. 

She found the favorite solution, 
https://gist.github.com/jianminchen/a13738b4ab32decb8601f29777172209

Her new strategy:
Write the code, finish the coding; and then, delete the code, write again. Stop on the best one. And then, try to sort out if there is a bug in the code, test cases etc. And then, discuss or present the code.

Because when the code is short and clean, it shortens time to do code review, bug fixes.

Another concern is that there are so many solutions to solve a problem, only if the solution is short and concise, people can easily follow and tell the correctness.

Statistics and Comment:

1. Read 200 submissions, around 5-10 using recursive function, 80% more than 10 lines of code, over 10 of them use two nested loops.

2. Enjoy the reading; thinking about myself as interviewer, and see how many of them are impressive; I do not see more than 10 of them.

https://www.hackerrank.com/challenges/delete-duplicate-value-nodes-from-a-sorted-linked-list/leaderboard

one more readable code to follow:
https://gist.github.com/jianminchen/b46755065e4d17c82ad793889e2c911b


3. Time spent: reading code submissions - 2+ hours

Look into those:

https://www.hackerrank.com/contests/programming-interviews-practice-session/challenges

https://www.hackerrank.com/contests/algorithms-practice-match-2/challenges

https://www.hackerrank.com/contests/regex-practice-2/challenges

https://www.hackerrank.com/contests/basic-ds-quiz-2/challenges

https://www.hackerrank.com/basic-ds-quiz-2

https://www.hackerrank.com/countercode
https://www.hackerrank.com/accel-contest

Courses to check:
https://www.coursera.org/learn/algorithmic-thinking-1

https://www.coursera.org/learn/algorithmic-thinking-2#

https://www.coursera.org/maestro/api/certificate/get_certificate?verify-code=V5LZ37UU7P


Quizes:
https://www.hackerrank.com/challenges/basic-algo-quiz-1

https://www.hackerrank.com/challenges/data-structures-quiz-2


Find some interesting problems on the link - hackerRank:
https://www.hackerrank.com/roaclark

https://www.hackerrank.com/epiccode

https://www.hackerrank.com/contests/codesprint-practice/challenges

https://www.hackerrank.com/cherry_su

https://www.hackerrank.com/dotgc

Try quick sort in place on HackerRank - 3 questions

HackerRank: article reading

May 3, 2016

http://blog.hackerrank.com/step-0-before-you-do-anything/

very good article - favorite:

Designing Challenges that Gauge Depth of Thinking, and also, talk about hurdles, how senior people can overcome a few of them once. 

http://blog.hackerrank.com/design-impactful-code-challenges/

http://blog.hackerrank.com/setting-expectations-warming-your-candidates/


Julia's favorite quote:
"Gauging not only their intelligence but also how much they value fundamentals through algorithm and data structure questions are strong instruments to find the best engineering talent"


http://blog.hackerrank.com/how-amazon-web-services-surged-out-of-nowhere/

Leetcode 323: Number of connected components

May 1, 2016

https://asanchina.wordpress.com/2015/12/29/323-number-of-connected-components-in-an-undirected-graph/

http://massivealgorithms.blogspot.ca/2015/12/leetcode-323-number-of-connected.html

http://leetcode0.blogspot.ca/2016/02/323-number-of-connected-components-in.html

Leetcode 261: graph-valid-tree

May 1, 2016

http://happycoding2010.blogspot.ca/2015/11/leetcode-261-graph-valid-tree.html

http://www.cnblogs.com/yrbbest/p/5018217.html

Read the blog to entertain, figure out how to improve practice:
http://home.cnblogs.com/u/yrbbest/

Leetcode 133: clone graph

May 1, 2016

Problem statement and solutions:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-clone-graph.html

http://www.cnblogs.com/springfor/p/3874591.html


C# code:
Easy to read - Node class
https://gist.github.com/jianminchen/c328dbc4391cb03a9ab8665b3ab54966
Fit into leetcode online judge
https://gist.github.com/jianminchen/bf0821320af0e549b486997faf11b358

Question and answer:

1. What do you learn through the practice? Can you write down your own words with your experience of learning?

1. Let us talk about a small test case, undirected graph {0,1,2#1,2#2,2}, here is the graph:

So, in Julia's practice, undirected graph node is defined in class Node:
class Node
{
    public int label;
    public List<node> neighbors;

    public Node(int x)
  {
         label = x;
         neighbors = new List<Node>();
   }
}

The above graph, 3 nodes are declared, node0, node1, node2,
3 edges in the graph:
 0 -- 1,
 0 -- 2
the above 2 edges are saved in node0's neighbors - a list;

edge 1--2
the third edge is saved in node1's neighbors;

edge 2--2 - a loop to itself
the fourth edge is saved in node2's neighbors - a list containing node2 itself.

Here is the expression to parse the graph: {0,1,2#1,2#2,2}

Any edge in the graph is only saved once in the list named in neighbors. <- It is good! 

Julia likes to catch up some reading about graph, so she spent 10 minutes to read:
http://algs4.cs.princeton.edu/41graph/

2. Need to review graph search, DFS vs. BFS, in the above C# practice, queue is used, so it should be BFS - breadth first search.

So, cloneGraph(Node node) function is designed to do BFS - breadth first search. If node0 is passed, then we can go over the steps what should do:

Main idea is to put input argument - a node into queue, copy the node to a first node in cloned graph, denoted as newHead.
Also, in the Dictionary - a map, add one entry - node, newHead.

Next, get into a loop with queue length checking > 0:
dequeue the node from the queue, and then,
check its neighbors, go through the iteration loop one by one.

If the neighbor node is not in the dictionary, then,
    it is not in cloned graph, what we need to do, is to add a new node in cloned graph,
    and also add a new entry in the dictionary,
    and update cloned graph neighbors list as well.
If the neighbor node is in the dictionary, then
    update cloned graph with current node's mapping - add one entry in neighbor list. (*)
<- (*) Need to figure out when this executable path will be executed! 

So, node0 is passed in as an argument, walk through steps:
node0 has two neighbors, node1 and node2, 
go through one by one, 
node1 is not in the dictionary, create a copy for node1, 
add an entry {node1, copy} into the dictionary,
also bind copy to newHead's neighbor. 
add node1 into queue. 

node2 is visited, and then, ...
add node2 into queue

when node1 is dequeued from queue, node1's neighbors are examined:
only one neighbor, node2. 
But node2 is already in the dictionary, <- need to debug the code to verify

when node0 is dequeued from queue, 
node1 and node2 are added to queue, 
two edges are added to clonedGraph, 
ditionary is updated with node1 and node2. 

when node1 is dequeued, need to add edge 1->2. 

change C# code: 
https://gist.github.com/jianminchen/35f3efda39c30d1e993a16a89d14308d

Make the code more flat, remove if/else in previous version. 
foreach (Node aNeighbor in currNeighbors)
                {
                    bool containing = map.ContainsKey(aNeighbor); 

                    // 1.update queue 
                    if (!containing)
                        queue.Enqueue(aNeighbor); 

                    // 2. update map 
                    if (!containing)
                    {
                        Node copy = new Node(aNeighbor.label);
                        map.Add(aNeighbor, copy); 
                    }

                    // 3. update neighbors for cloned graph 
                    // definitely, map.ContainsKey[aNeighbor]                   
                    map[curr].neighbors.Add(map[aNeighbor]);                    

                }

Comment: 
1. The explanation is kind of tricky, not so clear! Improve it later. 

2. Look into issues about else statement, Julia makes mistakes when she write if/else, and do not pay attention to else condition. <- basic logic checking...
Next time, try to put all true case in one statement. Your cognitive ability is in a standard level, only thing to improve is to discipline yourself, write code with more disciplines, simplify!