Dec. 30, 2017
Plan to study lecture notes again. Here is the link.
Showing posts with label Leetcode 72: edit distance. Show all posts
Showing posts with label Leetcode 72: edit distance. Show all posts
Saturday, December 30, 2017
Friday, October 20, 2017
Leetcode: Edit Distance - 30 minutes talk
Oct. 20, 2017
It is very interesting to spend time with my relative, a 22 year old in the city of Yichun. He is a computer science graduate from top universities in 2016, and he plans to take graduate admission test for a computer science master degree at the end of 2017.
I spent a few minutes to explain the possible deletion distance between two words "heat" and "hit". The minimum deletion distance is 3, including deletion of two chars ('e' and 'a') in the word "heat" and one deletion of chars ('i') in the word "hit".
The naive deletion distance 5 can be implemented by deletion of 3 chars in "heat" from second char to last char, and deletion of chars in "hit" from second char to last char.
I used two words "abc" and "defg" and explained the deletion distance of two words. The possible choice to delete a char each time is 2, and there are 7 choices, so it is 27.
Teaching was fun even though my nephew is a rookie in algorithm and data structure, he did not ask any question and surfed wechat while I was talking. He told me to continue and I was not sure if he understood the algorithm or not.
Introduction
30 minutes talk
I am very open to the new idea. What I have to do is to continue to support my nephew for Canada sponsor application and then also help him to build a career in computer science field.
It is very good for my nephew to get some skills to help his parents to manage a restaurant. I also prefer to encourage him to get more education instead of working in industry to work for some one else.
I did spent 30 minutes to test his coding skills, and practiced my lecturing skills during my vacation, this is the second chat. He was getting better, I still had no idea how he learns and what is his learning style.
Here are my notes I wrote on a piece of paper about the algorithm. The algorithm is documented in detail here.
Highlights of talk
The naive deletion distance 5 can be implemented by deletion of 3 chars in "heat" from second char to last char, and deletion of chars in "hit" from second char to last char.
I used two words "abc" and "defg" and explained the deletion distance of two words. The possible choice to delete a char each time is 2, and there are 7 choices, so it is 27.
Actionable Item
Teaching was fun even though my nephew is a rookie in algorithm and data structure, he did not ask any question and surfed wechat while I was talking. He told me to continue and I was not sure if he understood the algorithm or not.
Monday, September 11, 2017
Leetcode 72: Edit Distance
Sept. 11, 2017
It is one of classical algorithms related to recursive function and also memoization. I have practiced a few times and I am still learning the algorithm. My last practice is documented here, and all past practices are available through the search by Leetcode 72.
It was such great experience to be interviewed using the algorithm again. This is my thirdalgorithm practice, my last practice was more than one month ago. I still remembered the mistake I had and the advice I got from the peer.
Introduction
It was such great experience to be interviewed using the algorithm again. This is my third
Algorithm practice
Here is my C# code written in 30 minutes. I had a mocking experience starting from 10:00 pm.
I knew that I have to work hard to be an interviewer in order to get unlimited credit. I just started my new round of mocking practice. I could not memorize the algorithms, there are a lot of new issues coming out on this algorithm. I failed to do analysis of brute force solution, it should be 2(max(str1.Length, str2.Length)), because every time there is at most 2 choices. I was given the hint and then I took the hint to go from n * m to power of 2 analysis. In other words, the time complexity is lowered from polynomial time to quadratic time.
Assume that the worst case happens. In other words, the comparison of two chars are not equal, so one of them has to be deleted. There are two choices to do deletion, the minimum value of two choices will be recorded. For example, two strings are "abc" and "edfg". The total choices are at most 27. In mathematical term, the upper bound is 27 = 512. The dynamic programming using memoization will lower time complexity using jagged array memo[3][4], time complexity 3 * 4 = 12.
I also was told to make correction on the first line of the function, line 8. The checking is for the case of both strings are null or empty. Not at least one of them. I wrote || by the mistake.
9/12/2016
It is always good idea to write down the practice experience, what did I actually learn from the mocking? This time, 30 minutes coding passes all test cases, with one of corrections from the peer. But I was surprised to know that I need to grasp the basic algorithm analysis, as I shared my knowledge of Monte Carlo algorithm to a young graduate from a linguistic major, I have to explain the algorithm to myself. The most important is to know how to analyze instead of guessing.
If I have two choices to calculate distance, how should I make a decision? I have to go for the minimum one from the two choices. If I have a series of choices to make, then the combinations of choices will be 2n. To summarize, Leetcode 72 is the algorithm for me to teach myself how to understand the brute force solution with polynomial time complexity, know how to solve the problem first, and then apply dynamic programming, lower the time complexity to m * n using memoization, dynamic programming using bottom up solution.
It is interesting to know the memoization design, the best choice I know is to use jagged array, memo[][], the size of jagged array is str1.Length * str2.Length, that is how many intermediate result we have to hold. Assume that each of them is calculated to use a few simple steps which are O(1) time complexity.
I knew that I have to work hard to be an interviewer in order to get unlimited credit. I just started my new round of mocking practice. I could not memorize the algorithms, there are a lot of new issues coming out on this algorithm. I failed to do analysis of brute force solution, it should be 2(max(str1.Length, str2.Length)), because every time there is at most 2 choices. I was given the hint and then I took the hint to go from n * m to power of 2 analysis. In other words, the time complexity is lowered from polynomial time to quadratic time.
Assume that the worst case happens. In other words, the comparison of two chars are not equal, so one of them has to be deleted. There are two choices to do deletion, the minimum value of two choices will be recorded. For example, two strings are "abc" and "edfg". The total choices are at most 27. In mathematical term, the upper bound is 27 = 512. The dynamic programming using memoization will lower time complexity using jagged array memo[3][4], time complexity 3 * 4 = 12.
Related to a simple life choice
9/12/2016
It is always good idea to write down the practice experience, what did I actually learn from the mocking? This time, 30 minutes coding passes all test cases, with one of corrections from the peer. But I was surprised to know that I need to grasp the basic algorithm analysis, as I shared my knowledge of Monte Carlo algorithm to a young graduate from a linguistic major, I have to explain the algorithm to myself. The most important is to know how to analyze instead of guessing.
If I have two choices to calculate distance, how should I make a decision? I have to go for the minimum one from the two choices. If I have a series of choices to make, then the combinations of choices will be 2n. To summarize, Leetcode 72 is the algorithm for me to teach myself how to understand the brute force solution with polynomial time complexity, know how to solve the problem first, and then apply dynamic programming, lower the time complexity to m * n using memoization, dynamic programming using bottom up solution.
It is interesting to know the memoization design, the best choice I know is to use jagged array, memo[][], the size of jagged array is str1.Length * str2.Length, that is how many intermediate result we have to hold. Assume that each of them is calculated to use a few simple steps which are O(1) time complexity.
Sunday, July 30, 2017
Leetcode 72: Edit Distance
July 30, 2017
It is such great mocking experience for Julia to work on edit distance algorithm again in 30 minutes this afternoon around 4:00 pm. Since Julia was tired and kind of sleepy, she could not hear the peer because of her speaker was turned off. It took her 5 minutes to find out, both tried to login again. The fact is that if you are tired, your will have some issues to work on the small thing.
It is good to observe that when you are tired, the thing can go out of control once a while. Julia remembered last time that she was very tired and then she worked on week of code 34 over 5 hours and did not score anything. Always get ready for the mocking!
The algorithm is hard to write. Even though it is not the first time to write it. Her last practice is documented here.
The peer helped Julia to come out the idea to design the key for memoization. Julia worked on design by going through the simple case, "heat" to "hit", how to express distance("eat","it") using the key? Julia thought about loud, one way is to concatenate two keys like this "eat it", and she said that "it eat" should be the same as "eat it". Because Julia was too tired, she did not have a good idea. She was given a hint to use the array, use index of string, then she asked the idea using int[2] and define the comparer function.
The peer gave her hint to use jagged array memo[i][j], whereas i and j are the index of start position of substring.
C# practice code is here. The code runs with a test case and the result is correct. The peer reminded Julia line 71 and 72 having an issue. Julia forgot to increment one to the distance. At the end with a test case, the peer applaused Julia, and it was unbelievable 71 lines of code no bug.
I practiced again this algorithm through mocking interview, I met a senior developer who has very good managing experience. He asked me the time complexity about brute force solution, I stumbled on the question.
Based on the above experience, I did not learn the algorithm very well in theory. The dynamic programming is not easy to figure out. I need to relate to a simple life experience for this algorithm. I did one later on. Here is the blog link.
Introduction
It is such great mocking experience for Julia to work on edit distance algorithm again in 30 minutes this afternoon around 4:00 pm. Since Julia was tired and kind of sleepy, she could not hear the peer because of her speaker was turned off. It took her 5 minutes to find out, both tried to login again. The fact is that if you are tired, your will have some issues to work on the small thing.
It is good to observe that when you are tired, the thing can go out of control once a while. Julia remembered last time that she was very tired and then she worked on week of code 34 over 5 hours and did not score anything. Always get ready for the mocking!
The algorithm is hard to write. Even though it is not the first time to write it. Her last practice is documented here.
Design of Memoization
The peer helped Julia to come out the idea to design the key for memoization. Julia worked on design by going through the simple case, "heat" to "hit", how to express distance("eat","it") using the key? Julia thought about loud, one way is to concatenate two keys like this "eat it", and she said that "it eat" should be the same as "eat it". Because Julia was too tired, she did not have a good idea. She was given a hint to use the array, use index of string, then she asked the idea using int[2] and define the comparer function.
The peer gave her hint to use jagged array memo[i][j], whereas i and j are the index of start position of substring.
Algorithm practice
Editorial Notes:
9/22/2017I practiced again this algorithm through mocking interview, I met a senior developer who has very good managing experience. He asked me the time complexity about brute force solution, I stumbled on the question.
Based on the above experience, I did not learn the algorithm very well in theory. The dynamic programming is not easy to figure out. I need to relate to a simple life experience for this algorithm. I did one later on. Here is the blog link.
July 6 2023
I am working on Meta phone screen in two months, so I have chance to review Edit distance.
Wednesday, June 21, 2017
Leetcode 72: Edit Distance
June 21, 2017
Plan to work on Leetcode 72: Edit Distance again. The problem statement is here.
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.
Introduction
Algorithm study
Julia's C# practice is here.
Follow up
Dec. 10, 2019 10:49 PMThis definitely is a good practice question for dynamic programming.
Tuesday, December 27, 2016
Leetcode 72: Edit Distance (III)
Dec. 27, 2016
Review Leetcode: edit distance
Previous blog about edit distance:
1. http://juliachencoding.blogspot.ca/2015/06/leetcode-edit-distance.html
2. http://juliachencoding.blogspot.ca/2016/09/leetcode-72-edit-distance.html
Study the solution:
Study code review posts:
http://codereview.stackexchange.com/questions/142275/edit-distance-implementation
http://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings
Review Leetcode: edit distance
Previous blog about edit distance:
1. http://juliachencoding.blogspot.ca/2015/06/leetcode-edit-distance.html
2. http://juliachencoding.blogspot.ca/2016/09/leetcode-72-edit-distance.html
Study the solution:
Study code review posts:
http://codereview.stackexchange.com/questions/142275/edit-distance-implementation
http://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings
Sunday, September 18, 2016
HackerRank Stryker Code Sprint Grind (V) - The Hidden Message - 70%
Sept. 18, 2016
Problem statement
Julia's C# solution is here.
Here is the timeline Julia worked on the problem solving:
Section 1:
/* 7:08pm - start to read the problem statement
*
* 7:47pm start to write down her approach
* start position is increasing
* How to find word match?
*
* Time complexity -
* Data structure
* Space complexity:
*
* 7:55pm start to code
*
* 10:04pm start to conduct testing
*/
Section 2:
Copy the code from previous practice - substring search, using Boyer algorithm to speed up, avoid timeout issues.
/*
* 8:24pm
* copy code from blog:
* http://juliachencoding.blogspot.ca/2016/04/hackerrank-string-function-calculation_10.html
*
* 8:36 prepare to exit the function
*/
private static bool findUsingBoyerAlgo(string substring, string s, ref int start)
Section 3:
/*
* 9:02pm - start to code
* 9:43pm - still work on the calculation of cost
* - try to think about how many chars to be removed - second step
* 9:57pm use brute force solution first
*/
public static string calculateCost(IList<Match> data,
string message
)
Section 4:
/*
* 10:19pm
* Summary of submission:
* 40.80/60
* Wrong answer for test case: 11, 15
* Try to fix the bug
*/
Summary:
1. 40 minutes to read the problem statement
2. 2 hours coding - including eating a dinner - 20 minutes
55 minutes to work on calculation of cost, looked into interval algorithm, and then, figured out using brute force solution instead.
2. 10:04pm testing
Score 40.80/ 60
Decided to give up bug fix, and then, moved on next question.
Study C# submission - 60 out of 60
1. Use Trie
2. C#: use dynamic programming.
Related to Leetcode 72: "Edit Distance"
3. Study the blog: Levenshtein Distance wiki
4. Study Java 8 solution - use Rabin Karp algorithm search class, DP
5. C++ code - Learn from the best, competitive programmer
6. C++ - KMP algorithm, DP
7. The programmer - 5 Gold - rank 32/1700
a Googler, a blog.
Talk about Google code review - in Chinese, link is here.
Problem statement
Julia's C# solution is here.
Here is the timeline Julia worked on the problem solving:
Section 1:
/* 7:08pm - start to read the problem statement
*
* 7:47pm start to write down her approach
* start position is increasing
* How to find word match?
*
* Time complexity -
* Data structure
* Space complexity:
*
* 7:55pm start to code
*
* 10:04pm start to conduct testing
*/
Section 2:
Copy the code from previous practice - substring search, using Boyer algorithm to speed up, avoid timeout issues.
/*
* 8:24pm
* copy code from blog:
* http://juliachencoding.blogspot.ca/2016/04/hackerrank-string-function-calculation_10.html
*
* 8:36 prepare to exit the function
*/
private static bool findUsingBoyerAlgo(string substring, string s, ref int start)
Section 3:
/*
* 9:02pm - start to code
* 9:43pm - still work on the calculation of cost
* - try to think about how many chars to be removed - second step
* 9:57pm use brute force solution first
*/
public static string calculateCost(IList<Match> data,
string message
)
Section 4:
/*
* 10:19pm
* Summary of submission:
* 40.80/60
* Wrong answer for test case: 11, 15
* Try to fix the bug
*/
Summary:
1. 40 minutes to read the problem statement
2. 2 hours coding - including eating a dinner - 20 minutes
55 minutes to work on calculation of cost, looked into interval algorithm, and then, figured out using brute force solution instead.
2. 10:04pm testing
Score 40.80/ 60
Decided to give up bug fix, and then, moved on next question.
Study C# submission - 60 out of 60
1. Use Trie
2. C#: use dynamic programming.
Related to Leetcode 72: "Edit Distance"
3. Study the blog: Levenshtein Distance wiki
4. Study Java 8 solution - use Rabin Karp algorithm search class, DP
5. C++ code - Learn from the best, competitive programmer
6. C++ - KMP algorithm, DP
7. The programmer - 5 Gold - rank 32/1700
a Googler, a blog.
Talk about Google code review - in Chinese, link is here.
Sunday, September 4, 2016
Leetcode 72: Edit distance - code study
Sept. 4, 2016
First thing in the morning, this Sunday, labor long weekend, Julia read the book about "competitive programming. She read the book -
page 112,
6.3 String Processing with Dynamic Programming
6.3.1 string alignment - edit distance
Using Dynamic Programming, she was amazed that how good the solution is provided in the book. She read aloud the analysis and solution word by word, sentence by sentence, a few times. So enjoyable experience.
The book is detailed in the previous blog:
http://juliachencoding.blogspot.ca/2016/09/book-reading-competitive-programming.html
So, she looked up google and found the similar algorithm: Leetcode 72 - edit distance
Problem statement: (Hard)
First thing in the morning, this Sunday, labor long weekend, Julia read the book about "competitive programming. She read the book -
page 112,
6.3 String Processing with Dynamic Programming
6.3.1 string alignment - edit distance
Using Dynamic Programming, she was amazed that how good the solution is provided in the book. She read aloud the analysis and solution word by word, sentence by sentence, a few times. So enjoyable experience.
The book is detailed in the previous blog:
http://juliachencoding.blogspot.ca/2016/09/book-reading-competitive-programming.html
So, she looked up google and found the similar algorithm: Leetcode 72 - edit distance
Problem statement: (Hard)
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
b) Delete a character
c) Replace a character
Wednesday, June 17, 2015
Leetcode 72: edit distance
June 16, 2015
Problem statement:
72. Edit Distance
Code study:
One solution in Chinese, blog is here written by FightForYouDream.
Problem statement:
72. Edit Distance
Code study:
One solution in Chinese, blog is here written by FightForYouDream.
Stanford lecture note about edit distance, the pdf file is here.
Write down the feeling after the practice:
It is a two dimension dynamic programming. It took me a few hours to understand the algorithm. After a few month, I may totally forget the algorithm.
这个算法是2 dimensional dynamic programming. 读了好几个小时, 练习了代码, 理解了算法; 可能过几个月全忘了. 代码有一段容易出错,
Share the C# code, code is here.
Follow up
May 5, 2017
Review the algorithm after mocking experience on this algorithm in May 4, 2017.
Subscribe to:
Posts (Atom)