Leetcode 212: Word Search II

June 13, 2017

Problem statement

Introduction

Trie is the kind of tree data structure and easy to save space with common prefix. Julia spent over 5 hours to work on one of trie algorithm and posted a code review on stackexchange.com called prefix neighbor. She went through the trie and learned that the trie can be in any form.

This time Julia had to relearn trie again. She had the weakness of data structure Trie, she could not figure out how to solve test case 36 and 37 two test cases timeout issue.

Code practice 

It is the hard level algorithm.

Julia worked on the Leetcode 212 word search.

Her first submission failed last 2 test cases from 36 - 37. Timeout issue. Julia did not know that she needs to use trie, she just used recursive function. The code is here.

Here is the C# code.

She studies the discussion written by a Googler - Yavinci, and wrote second practice. Still work on the code for more testing. Here is the C# code.

Julia continued to work on the trie and here is the C# code passing leetcode online judge.

Algorithm talk - learn Trie again

It is interesting to learn how data structure Trie to help solving timeout issues. For example, there are a lot of words like "aaaa", "aaab", "aaac", ...,"aaaz", Julia was so naive on June 13, 2017. She just goes over each word in the dictionary, and try to find each word using depth first search (DFS) recursive calls.

However the last 2 test case of 37 test cases time out. But Julia did not have idea how to solve it.

Julia needs to take a data structure coaching lesson again. so great to catch the opportunity.

As we can see, those words have same prefix "aaa", and the fourth char or last char is a to z. How to save the time to search, for example, if the path is the prefix of one word, then we need to continue to search.

Think about time complexity. My original solution (the C# code) is to go over each word, and then start to search board using DFS; so time complexity is related to how many words, each word is searched through board using DFS. If 26 words all starting from same prefix "aaa", then "aaa" will be searched in the board over 26 times.

The idea of using Trie, and then go over each element in the board, and then do DFS search against the Trie tree.

So preparation is the key, store all words to a prefix tree first.

Trie 

Plan to read Trie wiki article, review time complexity advantage of using Trie data strucutre.

A trie has a number of advantages over binary search tree. A trie can also be used to replace a hash table.

Topcoder using Trie - the article link is here.
Hackerearth tutorial about Trie - the article link is here.
Read 10 pages lecture notes about Trie - CMU lecture notes is here.

Max Score - RookieRank 3

May 6, 2017


Plan to work on the algorithm: Max Score in next 1 - 2 hours. Time is 5/6/2017, 12:53 pm.

Follow up 

May 7, 2017 9:20am

C# code in the contest is here, scored 3.5 out of 35.

Follow up 

Study the discussion about the solution, the link is here.

1. The following implementation uses memoization, backtracking, and backward processing:

C# practice code is here which passes all test cases.

2. Continue to work on my code submission, change the key of memoization, relax to the sum instead of the string concatenated by various array's element.
Score 14 out of 30, timeout test cases 7 - 10.
C# practice code is here.

3. Bit mask - pass all test cases
C# practice code is here.

Bit manipulation 4 things to review

1. Get integer 2ⁱ:
//use left shift i times,
bitToCheck = 1 <<  i

2. Check ith bit is 1:
// int bitmask
bitmask & bitToCheck

3. Get ith bit:
bitmask |= bitToCheck,

4. Unmask the ith bit:
// backtracking
bitmask &= ~bitToCheck


4. Bit mask - replace the integer using int[], size of array is 20.
May 11, 2017
Timeout on test cases from 6 to 10. Score 10.50 out of 30.
C# practice code is here.
string.Join(",", bitmask) takes too much time.

Julia learned the lesson. Take some time to write bit manipulation instead of using int[]. Bit manipulation expedites the process, use int instead of int[].

5. Continued to work on code written in the contest,
May 12, 2017 11:11 pm
C# practice code is here. Score 10.50, pass test case 0 - 5, and timeout on test case 6 - 10.

Learn when to do memorization, it should be out-of-for-loop, memo on the used HashSet<int>, actually encode all used indexes of the array to a string. Move the memoization from inside for-loop to outside for-loop.

Algorithm analysis

It is most important to come out the recurrence formula for the algorithm. Try to work backwards instead of starting from the first number and forward.

The maximum score of k problem can be solved by choosing any number as the last kth number, and then work on the maximum score of k - 1 problem. Use bitmask as key to do memoization.

Actionable Items

Review previous practice, and find some cases to use bitmask.

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union        
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

2. Hackerearth.com dynamic programming and bit masking, article link is here.

HackerRank - university code sprint - Array construction - code review

Dec. 25, 2016

Introduction
A few of facts about the algorithm:
1. In contest, spent over 10 hours to work on
2. The algorithm is advanced one
3. Score 8 out of 80
4. The algorithm is really a challenging one
5. Spent over 10 hours to work on after the contest, studied C# code


http://juliachencoding.blogspot.ca/search/label/array%20construction%20%28series%201%20of%205%29

Workout 

1. Plan to write a code review request on stackexchange.com.
2. Need to study how to post a good code review on stackexchange.com
3. Be careful that do not get down vote, off-topic
4. Put down ideas why to ask code review
5. Julia also learned through the code review, how to write better English, her grammar mistakes.


Code Review Link

Case study:
http://meta.codereview.stackexchange.com/a/1035/123986

http://meta.codereview.stackexchange.com/users/11974/user1131146-account-abandoned

HackerRank codesprint - Array construction - after contest (series 2 of 5)

Nov. 14, 2016

Problem statement:
https://www.hackerrank.com/contests/university-codesprint/challenges/array-construction/submissions/code/7825209

Study C# submissions:
1. perfect solution with full score 80
https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

Julia spent more than one hour to read code, but she could not understand the design. So, she decided to work on debugging, add output text info to figure out the design.

Here are workout she did and then figured out the algorithm:

Study more than 2 hours on one of solutions, using recursive solution; but Julia still are not clear about the solution. Need to work on more! Do not give up! Try it every day 10 minutes. It should be easy! 

Julia's work (3+ hours) Try very hard to understand the clever solution by debugging 

-  From the above C# solution:

https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

-->   add some debug information to understand the algorithm 

add debugging information to the source code 

https://gist.github.com/jianminchen/48616cdb58a96264eb6e17ce8b177005

-> Here is the log file to understand the algorithm design:

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

Question 1:

Use your own words to guess how to design the algorithm through debugging process?

Answer:

still confused about line 118, line 119:

118  int newSum     = sum + i * (n - p);

119  int newDiffSum = diffsum + (i * p - sum) * (n - p);

Question 2: What does (n-p) stand for? Can you explain it in one sentence?

Let us work on one more change first:

https://gist.github.com/jianminchen/48616cdb58a96264eb6e17ce8b177005

so, decided to track n-p value on line 118.

C# code with debug info (stage II):

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

debug text info:

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

Actionable Items:

1. Run test cases, and compare the time difference 

First, comment out code on line 36, time out on test case 4.

https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

Write a new blog on this testing adventure.

http://juliachencoding.blogspot.ca/2016/11/hackerrank-university-codesprint-array_18.html

2. Study all C# solutions:

2.1. perfect solution with full score 80

https://gist.github.com/jianminchen/49f45acc69b4d87c51d02c81a788fbc9

2.2. perfect solution with full score 80

https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

2.3. score half score 40

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

3. understand one term: constructive algorithm

Constructive algorithm: (preprocessing, and then, lookup)

(HackerRank - array construction is a constructive algo.)

https://www.quora.com/What-does-the-constructive-algorithms-tag-mean-at-Codeforces 

Great idea to push hard - cannot get it wrong! that is the attitude for advanced level algorithm involved mathematical analyse.

Don't practice 'til you get it right. Practice 'til you can't get it wrong. #tennis #motivation pic.twitter.com/GNpWdF372B

— Tennis Coaching™️ (@tennisdothow) August 20, 2015

HackerRank: string function calculation - string algorithm - Brute Force Solution

April 10, 2016

  Problem statement:

https://www.hackerrank.com/challenges/string-function-calculation

  Time spent: 2:40pm - 3:35pm 20 minutes to think, 20 minutes to write down in C#

Understand the problem, so, here are her thoughts:

Brute force solution:

pass one test case: aaaaaa, return 12,

failed test case:
abcabcddd,
wrong answer - Easy fix, index error on the loop

score 8.89/ 80

one test case: wrong answer
All other test cases time out

https://gist.github.com/jianminchen/09c77ba32b156f765b4debb2bccba0c8

Need to work on KMP, or Boyer-Moore algorithm, see how to make HackerRank happy, score more points.

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html

blog:
http://juliachencoding.blogspot.ca/search/label/string%20functions%20review