C# Minimum Heap implementation

June 28, 2017

Introduction

There is a PriorityQueue class in Java for minimum heap, but in csharp programming language, there is no class. Julia has to figure out how to write one by herself.

Search the blog using minimum heap implementation, the link is here.

Algorithm study 

8:00 pm - 8:30 pm C# practice is here.

Julia met a peer who is a computer science Ph.D., and she was asked to simulate the minimum heap using Array, Array.Sort. Julia followed the hint and she did write one. It works and the solution is correct. But she likes to make her simulation better. There is only 30 minutes in mocking experience, Julia could not write a real minimum heap so she chose to use an array and then sort it using O(nlogn) algorithm.

She needs to look into C# books and figure out how to do it better in short future.

One of ideas is to use C# SortedSet class. Review previous practice on Leetcode 295: Median of stream.

Book reading: Essential C# 4.0

June 28, 2017

Introduction

It is the seventh year Julia works on C# programming on the current job in the city of Vancouver. Last 2 years Julia tried so hard to reinvent herself, she chose to work on Leetcode, coding blog, and focus on the basics.

Julia knows that it is so enjoyable to read a C# book in her spare time, she did today using 20 minutes, on the topic called "16 Building Custom Collections".

Book reading plan 

Actionable Item

Next book to read:
Effective C# 50 Specific Ways to Improve Your C#
Second Edition Scott Meyers

Book review is here.

Algorithm design talk

June 28, 2017

Introduction

It is very interesting to learn different issues to learn binary search algorithm. Most popular algorithm is a binary search algorithm. When is your last time to write a binary search algorithm?

In last 6 months, Julia wrote at least 5 times binary search algorithms, she had at least 5 peers to work on binary search algorithm. She knows so many ways to create bugs in binary search algorithm, but today's mocking experience the bug is new, the series are not convergent at all.

Binary search algorithm

It is a long journey to work on binary search tree algorithm in 2017. Julia struggled over a few hours on binary search tree algorithm in one of Hackerrank contest, she could not figure out why she failed on an issue and could not make significant improvement even after the contest.

Julia did over 80 mocking experience since March 2017. One thing she learned most is the binary search algorithm. She wrote a few times and also she watched how peers worked on binary search tree algorithm. It is most favorite algorithm Julia likes to practice again and again.

One thing Julia was so surprised is the design the peer gave out in binary search algorithm which cannot be convergent. (Mathematics series –convergent)

Mocking experience

Julia regularly attended the church but she never practiced algorithm and data structure with a peer from 2010 to 2015. Those five years Julia learned a lot through small group church activities.

Julia used to have one real experience in 2015 and then she did not have any mocking experience. In 2016 Julia only did 8 mocking experience and then she moved on. In 2017 March, Julia started to try to practice mocking, and then she did very well last few months.

As a hackerrank player, Julia can relate mocking experience learning to contest playing. At the very beginning, Julia studied a lot of hackerrank players through leaderboard and blogs they share, code in submissions. Until November 2016, Julia was lucky to start to get involved with code review community and learned a lot through asking questions. She asked help on code review and then she learned to solve hackerrank contest problems better and more understanding. 

Now Julia had 80 mocking experience since March 2017, she met so many peers and then she starts to look into possible topic for her short research. What Julia likes most in the algorithm problem solving?

Inorder successor binary search tree

June 27, 2017

Introduction

It is time to work on a few solutions on this binary search tree inorder successor. A simple idea is to go over the leetcode discussion on the algorithm, and study a few solutions.

Algorithm practice

May 20, 2017 C# practice is here. 

June 27, 2017 8:00 pm - 8:30 pm, 30 minutes practice is here.

The C# practice with test cases is here. More simple code is here.

July 4, 2017
Work on the solution without using parent node pointer.

Leetcode weekly contest 38

June 26, 2017

Introduction

It is a good idea for the summer day. Get up early one week day morning, like 6:00 am or 7:00 am, work on one Leetcode weekly contest and get some morning workout.

Here is the link of Leetcode weekly contest 38.

Algorithm practice 

N-th root of a number

June 26, 2017

Introduction 

Plan to work on N-th root of a number on geeksforgeeks.com.

Algorithm practice 

May 3, practice is here. 

May 30, C# practice is here. Root a number by power of n, for example, 0.001 - n = 3, root number is 0.1. 

June 26, C# practice is here. 

Julia did white boarding test on her own code, and then she found a bug on line 29 on test case 0.001, n = 3, search value 0.1. Julia tested her own code very carefully, and then find a bug on line 29. The peer asked the question to point out the bug on line 75, return integerValue/ 1000.0; not integerValue/ 1.0. At the end, there is a dead loop, so Julia put some debug code and traced down the bug on line 74, type conversion bug. 

Weight control project

June 25, 2017

Introduction

Summer is here in the city of Vancouver. One of goals in the summer is to play more sports, and also learn new skills to apply weight control.

Julia is busy working with hackerrank contests last 6 months, she also found out that she missed a lot of hours on tennis court. She used to spend a lot of summer time hours on tennis courts, play a lot of double matches, long hours to stay outdoor.

Weight control study 

Study BMI index again. Link is here. Plan to reduce the weight and get back to overweight, say goodbye to obesity weight. 

3000 algorithm practice

June 25, 2017

Introduction

It is estimated that a good software programmer should practice at least 3000 easy and medium algorithm based on her research on competitive programming. Right now, Julia had around 800 algorithm in her gist profile. It takes a while Julia adopts the idea called one algorithm a time based on her research on tennis coaching and mental strategies study. Never rush herself to finish algorithms. She used to study 10 algorithms in 3 hours, or 30 algorithms in one week, or tried to go over 70 algorithms in 3 or 4 hours.

It is better to learn one algorithm a time. Based on her study of the book "The art of competition programming", the book chapter the game plan of contest, Julia learned that it is also very helpful for her to go over each algorithm as many as possible ideas based on Leetcode discussion. She also learned that it is also very helpful to solve an expert level algorithm, in order to find a solution, Julia will quickly build up skills to do some research on algorithm, review the basics, and tries a few ideas.

Small research talk 

Read the blog again, link is here. Read the article again called "Competitive programming is a good use of time".

Review 3 advanced topics for competitive programming:

1. Fenwick tree
2. Max flow algorithm
3. Bitmask DP

Try to answer a few questions on Fenwick tree - binary index tree

One discussion on binary index tree is here on cs.stackexchange.com.

Second discussion on Fenwick tree is here on cs.stackexchange.com.

Study Hackerrank ProjectEuler+ leaderboard - link is here.

Codefights.com study

June 25, 2017

Plan to spend 30 minutes to study codefights.com website.

Game plan for a contest

June 23, 3017

Introduction

It is most enjoyable time to read a book chapter called "Game Plan for a contest", one chapter from book "The Art of Programming Contest".

Book chapter: Game Plan For a contest 

Julia likes to memorize classical problems for each classical algorithm. Here is the set of problems.

ACM ICPC world final problems - link is here. 

Leetcode 140: Word Break II

June 23, 2017

Introduction

Problem statement 


Plan to work on word break II algorithm sometime in short future.


Julia worked on Leetcode 139: Word Break I before, here is the blog.

Leetcode 55: Jump Game I

June 23, 2017

Introduction

Problem statement

Julia worked on the algorithm in 2015. Here is her C# practice.

Leetcode 45: Jump Game II

June 23, 2017

Introduction

It is one of hard level algorithm. The problem statement is here.

Julia worked on the algorithm in 2015. Here is her C# practice.

Algorithm 

Julia spent over 30 minutes to study one of greedy solution posted in the discussion, and then C# practice is here using greedy algorithm. 

Leetcode 72: Edit Distance

June 21, 2017

Introduction

Plan to work on Leetcode 72: Edit Distance again. The problem statement is here.

Algorithm study 

Julia's C# practice is here. 

Follow up

Dec. 10, 2019 10:49 PM

It is better to add code to the blog. Also I spent 10 minutes to review the code, there are three cases involved to build next iteration in dynamic programming, left, top, and left and top, first two the increment is 1, last one may be one or zero, depending on last char in two strings are the same or not.

This definitely is a good practice question for dynamic programming.

Can mock interview make difference? Continued II

June 20, 2017

Introduction

It is the first time Julia continuously works on mock interview experience starting from March 2017. Now she starts to understand the process better, and she starts to learn more things from the activities.

"It takes a village to raise a child". Julia knows that she could not do something alone and one day she is expert on algorithm and data structure. It is the great learning experience to work on the same algorithm together with a peer and learn from each other. 

Recently a computer science undergraduate student asked Julia what advice she has, because the peer likes to get more professional interviews from refdash.com. 

Julia learned a few things through the conversation. Julia was told that interviewbit.com is very popular site to practice coding.

Research talk 

Julia had her first professional mock interview experience in May 2017, and she got the comment like the following:

"Pretty solid interview overall. Algorithms and problem comprehension was on a pretty high level. Coding was good as well, but got a bit sloppy at times when we got to details (very minor edge cases)."

Can mock interview make difference? Continued

June 20, 2017

Introduction

"It takes a village to raise a child". Related to improve algorithm and data structure, Julia learned that it also takes the hundred people to help her learn depth first search using recursive function.

As a classical depth first search algorithm, Julia worked on the Sudoku algorithm in 2015, she collected over 10 solutions; She thought that she mastered the sudoku algorithm in 2015, actually not! How did Julia find out the fact?

Julia practised Sudoku solver in April and May of 2017. First experience is in April, the peer complained that Julia forgot to write a base case in her first writing and gave a rating of 3 with comment "Do not know how to write code", and then second one is in May, the peer coached Julia to set base case first thing in the design, do not write any small function, keep it short as possible, quick as possible. From those two hours to work with two different people, Julia learned to stay humble, learn and quickly fix her learning issues. With those two mock interview experience, Julia learned the Sudoku solver in totally surprising ways. Learn from people from recent graduate and senior developer, recent graduate explained what to work on through Google onsite experience, and the senior developer showed her later in second meeting with more tips.

June 18 and 19 weekend, Julia worked on the expert level algorithm called path matching, she scored 0.46 out of maximum score 100, she worked on over 5 hours but she learned depth first search again through the problem solving. Julia likes to solve the problem first, it does not matter if she scored less than 0.5%. She likes to get expert level algorithm problem solved first.

Julia starts to meet a person a day to work on algorithm problem solving, she also pays attention to peer's curiosity level on algorithm and problem solving, how good the peer can influence her through one hour conversation. Today she was surprised that the peer shared her link to solve C# problem from stackoverflow.com. Also the peer also typed the test case for her, and then Julia found out that her code had a bug, wrong output.

Julia learns how to do whiteboard testing and she did one today as well. But she missed the bug. So she felt that the peer is much better a tester and maybe she is a project manager working somewhere. It is the second time Julia worked on the algorithm.

A research talk 

The mocking experience is short, only one hour, the peer chose to turn off the video. But the quality of the work is very impressing, Julia found out that she is lacking of this kind of preparation for the mocking experience. 

Julia worked on extra 10 minutes to use Microsoft visual studio to find the bug. It is an excellent experience. 

C# code is here. 

In the line of 44, the new variable should be declared for each key value pair of dictionary. It is called nextPrefix. Do not change the function argument prefix, based on the least astonishment principle.

So share the advice Julia got today.

-very good communication, i liked how you explained your thought process thoroughly -got to the answer fast but still made sure to test before writing code

it's ok to ask the interviewer if you can look up inbuilt/library functions for the language if you need to, that might be helpful sometimes.

Can Leetcode weekly contest make difference?

June 20, 2017

Introduction

It is a ritual to do small research every day. Today Julia chooses a topic called "Can Leetcode weekly contest make difference?"

The reason Julia chose the topic is that she found out her last leetcode weekly contest reminded her to work on the basics - linear scan array more efficiently. The blog is called Leetcode 605: Can place flowers.  Julia found a very short solution through Leetcode discussion after she spent 48 minutes in the contest, she learned to solve the problem using 5 minutes. Only 10% of time, she learned the basics of linear scan an array, looping first.

On June 19, Julia noticed that she performed better on mocking experience of algorithm Leetcode 151 compared to her last one more than one month ago.

The argument is that "Leetcode weekly contest makes difference".

Performance talk 

Leetcode.com is so helpful because it attracts million players to share ideas, compared to code review on stackexchange.com, Julia found out that Leetcode.com is a good place to find excellent ideas to solve a Leetcode algorithm, but codereviwe.stackexchange.com is an excellent place for Julia to practice good writing and learn how to share her learning. 

10 steps to master dynamic programming (step II)

June 19, 2017


Plan to work on interviewbit.com dynamic programming tutorial. Here is the link of dynamic programming algorithms.

First Gold Medal on Hackerrank

June 19, 2017

It is time to celebrate first gold medal on Hackerrank. Julia won her first gold medal on hackerrank, she played week of code 33, and then she worked hard and then she was in top 4% ranking.

Here is the image she likes to show the medal to celebrate. It is not easy, after more than 12 months, she finally made it happen.

Here is julia's hackerrank profile link.

Julia likes to play hackerrank contest, and also she works hard on basics through Leetcode algorithm practice.

Here are the contests she attended and she likes the failure and also likes the progress to gain skills to perform better. It took her six months to get her first gold medal in 2017.

She still remembered in April she played this contest called world codesprint 10, she documented that the huge difference between top 10 players and Julia's performance. The blog link is here.

In April, Julia set a goal for a gold medal. Here is the blog called "Talent small talk".

Psalm 126: 5 Those who sow with tears will reap with songs of joy.

Leetcode 76: Minimum Windows Substring

June 18, 2017

Problem Statement

First step Julia spent over 60 minutes to write and then failed several times, she finally passed first 267 test cases, and last test case failed with timeout error. C# code is here.

A lot of failed test case in her practice:

1. A lot of out-of-boundary index error, "abc", "a"
line 57 and 58, search[left] - make sure that left is in the boundary of the array

2. "a", "aa", need to check counts as well.

Knight Covering - codeChef

June 18, 2017

Introduction

It is very good learning experience to play contest on codeChef. Julia is a rookie to play short contest, 2.5 hours. She started to choose to read chinese version of problem statement, here is the problem statement.

She also did some google search, and found the similar algorithm, N x N board instead. She spent 10 minutes to read the algorithm. Link is here.

Leetcode: Number of Connected Components in an Undirected Graph

June 17, 2017

Introduction

Julia has to work hard on expert level algorithm, she plans to work on the algorithm called "Path Matching" in the week of code 33. Julia needs to find some topics to study in order to come out a working idea to solve partial the algorithm.

One of her studies is about network, n nodes with n - 1 edges, what implies to this graph? Julia likes to find path for any two nodes. What should be included for a good consideration before she comes out the idea to search a pattern.

Algorithm study

Read the blog written by Grandyang, the blog link is here.

Leetcode: Number of Islands II

June 17, 2017

Introduction

Julia has to work hard on expert level algorithm, she plans to work on the algorithm called "Path Matching" in the week of code 33. Julia needs to find some topics to study in order to come out a working idea to solve partial the algorithm.

One of her studies is about network, n nodes with n - 1 edges, what implies to this graph? Julia likes to find path for any two nodes. What should be included for a good consideration before she comes out the idea to search a pattern.

Algorithm study

Plan to read a blog written by jcliBlogger, the link is here. 

Leetcode number of islands II, the link is here. 

Leetcode: Graph Valid Tree

June 17, 2017

Introduction

Julia has to work hard on expert level algorithm, she plans to work on the algorithm called "Path Matching" in the week of code 33. Julia needs to find some topics to study in order to come out a working idea to solve partial the algorithm.

One of her studies is about network, n nodes with n - 1 edges, what implies to this graph? Julia likes to find path for any two nodes. What should be included for a good consideration before she comes out the idea to search a pattern.

Algorithm study 

One blog written in Chinese called grandyang is here.  It is now 9:15pm, Julia likes to go over the algorithm 15 minutes before she moves on to the Leetcode discussion session for broad discussion. 

Plan to study the code in the blog, and write a C# version. UnionFind using array is very good practice. 

Hidden message algorithm code review

June 17, 2017

Introduction

The algorithm "hidden message" is the medium algorithm in stryker contest in 2016. Julia decided to review the algorithm based on her blog since she likes to get more idea on how a trie data structure to solve the string search algorithm very well. Recently Julia noticed that she could not figure out using trie to solve a timeout issue on Leetcode algorithm 212 Word Search, she knows that her training has some issues, she needs to emphasis more on trie. 

Algorithm code review 

The C# code is here to review.

Leetcode 572: subtree of another tree

June 17, 2017

It is time to review one of blogs written for the algorithm. The blog link is here.

Leetcode 459: repeated substring patterns

June 17, 2017

Problem statement

Leetcode 44: wildcard matching

June 17, 2017

Problem statement

It is hard level algorithm. Julia tried the algorithm a few times in mocking experience, she used the algorithm a few time to interview and also was interviewed.

Now it is 9:36 am, Julia likes to read some discussion. Plan to spend 20 - 30 minutes.

First, Julia was advised in mocking experience to use recursive function to make the code more easy to write.

Special test cases are looked into:

1. ?*, any character repeated multiple time, ? represents any character, * means repeating multiple times.

2. If string is finished, but the pattern string is not, it is still possible to match. Pattern string ?*, a* or a*b* etc.

3. Some challenging matching, like "aaa" to match "a*a", how to wisely calculate a* pattern to match first two chars instead of all three characters.

Study code using DP solution - link is here.

Path Matching - week of code 33

June 17, 2017

Problem statement

Research and study plan 

It is the expert level algorithm. As a hackerrank player, Julia is still learning how to solve the expert level algorithm partially. What she likes to do is to dedicate a few hours, think about ideas, study related topic, and most important is to go over related algorithms in Leetcode, topcoder, hackerearth, and read some lecture notes.

After a few hours study, Julia starts to come out some idea to solve basic sample test cases first, leave timeout and performance issues as is until she comes out the great idea to solve the issue.

1. Leetcode 44 - wildcard matching - 20 - 30 minutes research and study, documented in the blog:
wildcard matching.

2. Review string search algorithm KMP, Rabin algorithm on topcoder. Link is here.

3. Review KMP and other string search algorithm on Julia's coding blog as well. Now it is 10:11am.

4. Review "the hidden message" algorithm on hackerrank contest. The blog is here.

5. Leetcode: Graph Valid Tree - the coding blog of grandyang is here.

Time is 9:07 pm, June 17, 2017
It is hard to figure out the idea to solve the path between two nodes. Julia likes to study some good algorithm.

She googled n nodes n - 1 edges meaning - no cycle in the graph, a tree?

6. Read lecture notes about union find data structure - lecture notes by Princeton is here. Now it is 9:55 pm.

Follow up after the contest

The code submitted in the contest is here. Score 0.47 out of maximum score 100.

Plan to study the Java code written by Salmur - score 100, link is here.

Plan to study the discussion provided by one of players. Link is here.

Bonnie and Cylde - week of code 33

June 16, 2017

Introduction

It is the expert level algorithm and Julia likes to work on the algorithm. 

Expert Level

Julia chooses to work on the expert level algorithm, Bonnie and Cylde. She chooses to study graph algorithm for a few hours, and then tries to find a solution. 

First, she reads the topcoder graph blogs. Blog link is here. 

Next, she will search all graph algorithm in Leetcode marking hard level, she will quickly go over 5 - 10 of them. 

Third, undirected graph lecture notes - link is here. 

Fourth, detect cycle in directed graph, link is here. Detect cycle in undirected graph, link is here. 

Fifth step, go over graph algorithms on geeksforgeeks.org website. The link is here. 

One of graph algorithms, "Print all paths from a given source to a destination". The blog is here. 

"Competitive Programming" authored by - Graph

Union find algorithm on hackerearth - link is here. 

Progress Report

Now it is 8:44 am Saturday morning, Julia has to review her submission result. The interesting part of expert level algorithm is that Julia has to go over a lot of content about graph, a lot of reading, and then she decided to use one of algorithms to solve the problem. 

The idea to solve the problem was original wrong, and then she made a minor change to make sense on second sample test case. 

The another interesting fact to write code for expert level algorithm is that Julia does not have a lot of code to write. The idea is quiet simple, but a few test cases timeout. It is hard to find the right idea. Julia has to do time analysis for the algorithm and see which one can survive the time limit. 

Follow up after the contest

Julia submitted the code in the contest and score 25% of maximum score, 22.86 out of maximum score 80. Julia just used union find algorithm and then used another idea to apply union find second time to exclude one of two source nodes. Code is here. 

Leetcode 516: Longest palindromic subsequence

June 15, 2017


Work on Leetcode 516: longest palindromic subsequence

Julia's C# practice is here.

Palindromic table - week of code 33

June 15, 2017



Here is the progress report of the algorithm at 10:05 pm.

Now it is 10:41 pm, Julia checked the edge case:

1. A single digit is a valid palindrome.
2. Note that a sequence of only  element can contain , but  is invalid as it contains a leading zero.

Julia fixed the bug related to edge case, now she scored 60 out of maximum score 60. Very good, Julia started to go over the problem statement and found the bug. She checked that scores on leader board from 50.00, 51.67, 53.3, 56.66, 58.33, 60.00.  Last time she scored 50.00. So she tried to find small edge cases, but she found all of them. 

Progress report

One thing Julia learned through the algorithm is that she has to take care all small edge cases, she failed test case 40 and 41, and then she figured out the edge case and submitted on June 16, 2017. 

Now it is 8:53 am. And Julia had one test case with timeout issue, she has no idea to solve the issue. 

To play the contest, Julia learns a few things, one thing is to write down test cases for small edge cases. Think carefully. 

Follow up after the contest 

Here is the code submitted in the contest, which passed all test cases except timeout on test case 30. 

Hackerrank week of code 33

June 15, 2017

Week of code 33 on Hackerrank

It is so exciting to play hackerrank week of code 33. Julia likes to check her progress through the contest.

Here is the progress report on June 15, 2017, 10:08 pm.

Now it is 10:59 pm, Julia scored 60 maximum score on the algorithm "Palindromic table". Her ranking moved up to 431. 

There are 2 more expert level algorithms to go for the week of code 33. Now it is 11:15 pm, Julia checked the leader board in Canada. Here is the progress report:

Now it is Sunday, June 18, 2017, 8:15 am. Julia likes to ensure that she can get a gold medal, stay in the top 4%. So she plans to do more study and write some code for the algorithm. 

Here is the comparison to one of top players. 

Leetcode 300: Longest increase subsequence

June 15, 2017

Introduction

Plan to review the longest increasing subsequence algorithm again. It is getting much easy to work on the algorithm on Leetcode, the discussion of Leetcode 300 is Julia's favorite. Most of important job in the practice is to go over different ideas and seek the inspiration to solve the problem. It is the great to know one more idea, one more tip to solve the problem, and also go over different language.

There are over 70,000 accepted submissions, look at the statistics, Julia found out that it is a really home to the algorithm. Just dive in, get 30 - 60 minutes first round study. Do some research.

Algorithm problem solving

Julia's C# solution using binary search is here.

Julia's C# solution using dynamic programming is here.

Actionable Items

Work on Leetcode 516: longest palindromic subsequence

Julia's C# practice is here.

Transform to Palindrome - week of code 33

June 14, 2017

Introduction

Problem statement is here. It is a medium level algorithm, it is related to subsequence, it is about palindrome, and it is also to find the longest possible palindromic subsequence.

Code preparation in the contest

June 15, 2017 10:05 pm

Here is the progress report of the algorithm:

Follow up after the contest

The code submitted in the contest is here.

Binary tree root to leaf path minimum path value with the path

June 14, 2017

Introduction

   

It is very interesting to practice binary tree path sum with the same value. Julia did the practice in 2016. Today she did practice twice, first she rewrote the algorithm better to represent her understanding the algorithm - the recursive function.

And then she practice mocking experience, she wrote an extended algorithm to find the minimum path sum from root to leaf, the return value is the minimum path sum and also return the path.

 

 

Code practice 

 

3 practices: 

 July 28, 2016, C# practice

 June 14, 2017, C# practice

June 14, 2017 9:49pm  - C# practice

In 3rd practice, Julia was asked to extend the algorithm in the mocking experience, add the minimal sales path to the output as well. 

It is again the opportunity to practice how DFS works, use a string variable to track all the nodes in the path. 

 

Leetcode 79: Word Search

June 13, 2017

Problem statement


Julia's C# practice is here. The code passes all test cases of Leetcode online judge.

Work on basics

June 13, 2017

Introduction

It is better to work on the basics instead of taking new technology as part of arsenal. Julia likes to work on Http protocol learning, CSS foundation, JavaScript foundation, work on more and then start to explore new technologies. She still remembered that back to in 2014 she spent over 5 months to learn JavaScript every day. She decided to learn a function language and then she followed the book called JavaScript the definitive guide.

What to work on 

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.