Introduction
It is more exciting to practice coding and attend contest in the weekends. Julia enjoys the contest and also likes to push herself to join the community and share what she can do. Here is the blog to show her ask code review on a hard level algorithm in Hackerrank world codesprint 10 recently.
Julia had a mocking experience tonight, she had a big surprise about learning a dynamic programming algorithm.
The problem is a very ordinary solution using dynamic programming, recursive solution.
The deletion distance of two strings is the minimum number of characters you need to delete in the two strings in order to get the same string. For instance, the deletion distance between
"meat" and "mit" is 3:- By deleting
'e'and'a'in"meat", and'i'in"mit", we get the string"mt"in both cases. - We cannot get the same string from both strings by deleting
2letters or fewer.
Less means more
How to analyse the above algorithm?
Use frog and dog as an example, we have two words, we like to linear scan two strings from left to right, all starts from the beginning. First chars of two strings are 'f' and 'd'. If they are equal, then both pointers go to next one. Otherwise, we have to move one of pointers. Both cases should be counted. In other words, 'd' is deleted, then continue to work on two strings: "og" and "frog"; or 'f' is deleted, then continue to work on two string: "dog" and "rog".
So far, the analysis is perfect. We cannot sort the string, because the order is important and has to be kept. The count of char does not help much. The brute force solution is not good since it will be O(n2), actually it is hard to find a brute force solution.
In other words, recursive function can be written in the following recurrence formula:
CalculateDeletionDistance(s1, s2) = CalculateDeletionDistance(s1.substring(1, length1 - 1), s2.substring(1, length2 - 1)) if s1[0] == s2[0];
Make it short, CalculateDeletionDistance is shorted as CDD, s11 is the substring of s1, s21 is the substring of s2.
CDD(s1, s2) = CDD(s11, s21) if s1[0] == s2[0],
CDD(s1, s2) = 1 + Math.Min(CDD(s1, s21), CDD(s11, s2)) if s1[0] != s2[0]
Basically the recursive function is depth first search, base case should be calculated the deletion distance. And then in order to save time, it is better using bottom-up solution, called dynamic programming method.
Previous practice on Leetcode 72 is here. Spend 20 minutes to review lecture note from standford again. Also plan to spend 30 minutes to review Leetcode discussion, link is here.
Julia was wondering if the dynamic programming is also solvable using DFS algorithm.
Plan to read the article on topcoder: Dynamic Programming - From novice to expert, the link is here.
Read the facebook engineering manager - Yi Huang's linkedin profile.
Take some notes from the recommendation:
In other words, recursive function can be written in the following recurrence formula:
CalculateDeletionDistance(s1, s2) = CalculateDeletionDistance(s1.substring(1, length1 - 1), s2.substring(1, length2 - 1)) if s1[0] == s2[0];
Make it short, CalculateDeletionDistance is shorted as CDD, s11 is the substring of s1, s21 is the substring of s2.
CDD(s1, s2) = CDD(s11, s21) if s1[0] == s2[0],
CDD(s1, s2) = 1 + Math.Min(CDD(s1, s21), CDD(s11, s2)) if s1[0] != s2[0]
Basically the recursive function is depth first search, base case should be calculated the deletion distance. And then in order to save time, it is better using bottom-up solution, called dynamic programming method.
Edit Distance Algorithm
Previous practice on Leetcode 72 is here. Spend 20 minutes to review lecture note from standford again. Also plan to spend 30 minutes to review Leetcode discussion, link is here.
Julia was wondering if the dynamic programming is also solvable using DFS algorithm.
Actionable Items
Plan to read the article on topcoder: Dynamic Programming - From novice to expert, the link is here.
Read the facebook engineering manager - Yi Huang's linkedin profile.
Take some notes from the recommendation:
Understand to build a hobby - writing code, solve problems on topcoders:
"Numerous times we turn to each other to discuss algorithm and optimization problems and every time I am impressed how insightful Yi can be. Yi has won countless programming awards and takes coding as a serious hobby. Yi has great enthusiasm in algorithm optimization. His hobby is to log into topcoder and attack one problem after another. He also has the great ability to apply research knowledge to actual programming. He is one of the few guys that will always think of how to turn research results into reality."
"Numerous times we turn to each other to discuss algorithm and optimization problems and every time I am impressed how insightful Yi can be. Yi has won countless programming awards and takes coding as a serious hobby. Yi has great enthusiasm in algorithm optimization. His hobby is to log into topcoder and attack one problem after another. He also has the great ability to apply research knowledge to actual programming. He is one of the few guys that will always think of how to turn research results into reality."
No comments:
Post a Comment