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

Leetcode 328: Odd Even Linked List (Easy)

February 8, 2016

328. Odd Even Linked List (Easy)
Julia's comment: think about O(N) space solution first (using array, and then, easy to go through), and then, work on O(1) space solution, the following blog helps:
http://www.cnblogs.com/EdwardLiu/p/5138199.html

To be continued.

Algorithm: reading blog

February 2, 2016

 Think about learning Python today, since Julia likes to read Python code and get some great ideas in the code. She starts to read the blogs from Leetcode question 331 to 1 in descending order.

  As a programmer, she spent over 6 months to learn Javascript in 2014, and then she loves to read Javascript code now. So, spend 10 - 20 minutes a day to learn Python, one day she will love to read Python code.

  Here is the blog she starts to read.

  http://bookshadow.com/leetcode/

  https://www.hrwhisper.me/leetcode-algorithm-solution/

  http://www.cnblogs.com/grandyang/p/4606334.html

  http://www.cnblogs.com/EdwardLiu/tag/Leetcode/

  http://www.jiuzhang.com/problem/

 Here is the log of her reading:

 Feb. 3, 2016
Leetcode: 331, 330, 329, 328, 327, 326

331. Verify Preorder serialization of a Binary Tree
idea: Use stack

330. Patching Array
Read the blog, understand the idea:
https://leetcode.com/discuss/82822/solution-explanation

329. Longest Increasing Path in a matrix
idea: go through each node in the matrix, BFS search, and get minimum one;

328. Odd Even Linked List (Easy)
Julia's comment: think about O(N) space solution first (using array, and then, easy to go through), and then, work on O(1) space solution, the following blog helps:
http://www.cnblogs.com/EdwardLiu/p/5138199.html

Feb. 4, 2016
327 Count of Range Sum
Still confused about the question, the example is also hard to understand.

324. Wiggle Sort II
Julia figured out the easy way to do it, O(n) time, O(1) space. So motivated. Next time, think about algorithm by yourself, start from brute force, and then, work towards requirement - efficient solution.

https://segmentfault.com/a/1190000003783283
public class Solution { public void wiggleSort(int[] nums) { for(int i = 1; i < nums.length; i++){ // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1] if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } } }

322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html

这道题只让我们求出最小的那种，对于求极值问题，我们还是主要考虑动态规划Dynamic Programming来做，我们维护一个一维动态数组dp，其中dp[i]表示钱数为i时的最小硬币数的找零，递推式为：

dp[i] = min(dp[i], dp[i - coins[j]] + 1);

其中coins[j]为第j个硬币，而i - coins[j]为钱数i减去其中一个硬币的值，剩余的钱数在dp数组中找到值，然后加1和当前dp数组中的值做比较，取较小的那个更新dp数组

321. Find Maximum number 

https://www.hrwhisper.me/leetcode-create-maximum-number/

319 Bulb Switch 
http://www.cnblogs.com/grandyang/p/5100098.html

Analysis from the above blog:

那么我们来看这道题吧，还是先枚举个小例子来分析下，比如只有5个灯泡的情况，'X'表示亮，‘√’表示灭，如下所示：

初始状态：    X    X    X    X    X

第一次：      √    √    √    √    √

第二次：      √     X    √    X    √

第三次：      √     X    X    X    √

第四次：      √     X    X    √    √

第五次：      √     X    X    √    X

那么最后我们发现五次遍历后，只有1号和4号锁是亮的，而且很巧的是它们都是平方数，是巧合吗，还是其中有什么玄机。我们仔细想想，对于第n个灯泡，只有当次数是n的因子的之后，才能改变灯泡的状态，即n能被当前次数整除，比如当n为36时，它的因数有(1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同，括号中前面的数改变了灯泡状态，后面的数又变回去了，等于锁的状态没有发生变化，只有最后那个(6,6)，在次数6的时候改变了一次状态，没有对应其它的状态能将其变回去了，所以锁就一直是打开状态的。所以所有平方数都有这么一个相等的因数对，即所有平方数的灯泡都将会是打开的状态。

那么问题就简化为了求1到n之间完全平方数的个数，我们可以用force brute来比较从1开始的完全平方数和n的大小

February 7, 2-16
Please understand the question, if the problem is too complex, then the understanding may not be not correct. 

Leetcode 318: Maximum Product of Word Length 
Given a string array words, find the maximum value of length(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/

Solution 1:

直接看看每个字符串都包括了哪个字符，然后一一枚举是否有交集：

• 有交集，则乘积为0
• 无交集，乘积为 words[i].length() * words[j].length()

Solution 2:

其实因为全部都是小写的字母，用int 就可以存储每一位的信息。这就是位运算

• elements[i] |= 1 << (words[i][j] – ‘a’);   //把words[i][j] 在26字母中的出现的次序变为1
•  elements[i] & elements[j]    // 判断是否有交集只需要两个数 按位 与 （AND）运算即可

read the blog to understand bit operation, take some time to refresh the memory:
http://www.cnblogs.com/onlyac/p/5155881.html

在一个字符串组成的数组words中，找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母，在这里字符串由小写字母a-z组成的。

对于这道题目我们统计下words[i]的小写字母a-z是否存在，然后枚举words[i]和words[j]，找出max{Length(words[i]) * Length(words[j]) }。

小写字母a-z是26位，一般统计是否存在我们要申请一个bool flg[26]这样的数组，但是我们在这里用int代替，int是32位可以替代flg数组，用 与（&），或（1），以及向左移位（<<）就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111，“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000，这样两个进行与（&）得到0， 如果有相同的字母则不是0。

Algorithm: Merge two sorted singly linked list

February 2, 2016

Always work on simple problem. Enjoy the practice. Recursive function design is most important one. 


recursive solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list

Itearative solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list

http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/

Julia's practice:
Recursive solution:
https://github.com/jianminchen/AlgorithmsPractice/blob/master/MergeTwoSortedSinglyLinkedList.cs

Leetcode 109: convert sorted list to a binary search tree

Sept. 22, 2015

109 Convert sorted list to binary search tree (No. 109)

8/25/2015

Read the following blogs:

http://articles.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

C#, bottom up, time O(n), space O(log n) solution - best solution:

https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeB.cs

C#, top down, time O(n^2), space O(long n) solution - naive solution:

worked on code 2 times, first time, the calculation is kind of messy, then, worked on Leetcode question 108, get the idea to make it more simple; tips like len/2 only shows once, afterwards, use m instead. Just need to improve coding, think to make it more abstract, simple.

https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeC.cs

9/21/2015

Review the best solution, and then, totally forgot the bottom up solution idea. So, update the code with more comment.

Need to review more about bottom up/ top down solution in tree problems. Get more experience on bottom-up solution, read some articles about it. 

9/22/2015

Go over one example to build some muscle memory about this bottom up, O(1) solution to find the root node in subtree function.

Sorted List:

1->2->3->4->5->6->7,

How to convert the above sorted list to a binary search tree?

Thought process:

1.      First, get length of the list, which is 7 in the above list;

2.      Secondly, define a recursive function called

constructBST(ref  TreeNode head, int start, int end)

the above function definition, 3 arguments:

1.      First one is the reference of head node of sorted list,

2.      Start index of the list,

3.    End index of the list

In the function, first define the base case:

head is null, or start<end, return null

start==end, return head

then, call the recursive function for left subtree:

 head node is the same, start is the same, but end is len/2-1;

great tip comes in, the head node should move in the function, so that

root node can be accessed in the list using O(1), instead of starting from very beginning.

One more statement:

head = head.next;

TreeNode root = head;   // return this node as tree root node

Root.left = left subtree root node

Root.right = right subtree recursive function

       constructBST(ref  head.next, mid+1, end)

The tips to remember in the design, the recursive function should return the root node of the tree; secondly, input argument of linked list should use reference, and also head node moves in the recursive function, so it is O(1) to find the root node. 

Just cannot believe that only call .next function once in the recursive function! How to argue that the move is only once? Therefore, the total calls of .next should be length of list. Total recursive function calls is n, length of list. 

Debate why the recursive function has to return root node, and set up root node, connect its left/ right subtree root node. 

Debate why the linked list head node is moving. 

设计这个递归函数, 如何避免从链的头开始访问, 到中间点? 最关键是让链的头移动, 当需要设计树的根节点, 只要移动一步, 就是根节点. 画一个图, 帮助自己理解记忆; 看一篇文章, 开拓思路. 

The main point to understand the best solution using O(ln N) space, the left subtree has to be built first, and then, head node can be retrieved as .next method call, root node can be set up, and then, left subtree can be built. So, left subtree, then right subtree, then the tree with root node. Bottom up. 

Whereas sorted array to BST, the root node can be find right away, and then, tree can be set up top down. Julia is still confusing this top down / bottom up difference. :-) read more blogs. 

Blogs:

1. use global variable to remember the head node of linked list, great idea:

http://www.jiuzhang.com/solutions/convert-sorted-list-to-binary-search-tree/

2. another implementation using two pointers. Try it using C# later. 

https://siddontang.gitbooks.io/leetcode-solution/content/tree/convert_sorted_listarray_to_binary_search_tree.html

3. Java implementation, teach me how to use reference in Java or wrapper class. Good point!

http://rleetcode.blogspot.ca/2014/02/convert-sorted-list-to-binary-search.html

4. Time and space complexity analysis - think about it - very clear analysis 

http://blog.unieagle.net/2012/12/14/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Aconvert-sorted-list-to-binary-search-tree/

5. Three implementation discussions 

http://www.cnblogs.com/feiling/p/3267917.html

6. Great explanation - bottom up / top down, and in order traversal/ post order traversal

https://leetcodenotes.wordpress.com/2013/11/23/convert-sorted-list-to-binary-search-tree/

Implement the above 6 blogs using C#, and then, share the blog. After 1 month, check again and see if I can come out the bottom up solution in 5 minutes. If yes, stop; otherwise review again. 

Dec. 24, 2015

Review the solution again. 

How to recall the solution step by step?

1. Get list length <- travel the list once 

2. Design the recursive function with a list, start and end two position; use the position of start/end to boundary case checking; also the function returns the root node of the tree. 

3. Build left subtree

4. Find the middle of list as root <- how to get there? 

Cannot traverse the list again to half length if you want optimized solution, since it is in recursive function,  O(nlogn)

Every recursive call the list pointer will traverse once

5. Connect root node to left child

6. Move list pointer to next one 

7. Build right subtree

connect root node to right child as well. 

Recap the importance of function design: 

1. list with a pointer moving, starting from head

2. start, end position of linked list 

3. in the function build a tree

4. return root node of the tree