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.
No comments:
Post a Comment