Introduction
The sliding window algorithm is very challenge one even after I posted Find the smallest substring that contains some given subset of characters two months ago. Today 12 PM I had a mock interview and then I have to work on the similar algorithm with a peer from the United Kingdom. With the peer's help, I spent 50 minutes to go over the analysis and coding but still could not finish the algorithm writing, we had a chat about how to work on algorithm after we worked on both interviews 80 minutes. The peer asked a break, we took 20 minutes break to chat about algorithms. In last 5 minutes, I was asked by peer to finish the algorithm. I almost finished but timeout, time limit is 110 minutes. The fact is that I lost my writing on the platform.
I need to recall what I did about the coding, and then post the algorithm here. The peer had good advice for me to write the algorithm this time, the code will be different from the one I wrote before.
Coding
There are two issues in the code, first the input ["A"], search string "B", the result should be empty, not "B". Second issue is "Index was outside the bound of the array".
Continue to work on the bug fixing.
Now it is 12:35 AM. I fixed all the bugs. The function's arguments are not meaningful, so I mixed them together, one is arr, one is str. There are more than four places I mixed them in C# code here, line 26, arr[index] should be str[index], same as line 45, line 47. I changed them to meaningful name using char[] source, string search.
Lesson learned
Lesson learned: Always use meaningful name. Express the intent. I should change the variable's name to avoid the errors at the very beginning.
The C# code is here to look up.
Line 58
var isNeeded = dictionary[visit] > 0;
Actually I wrote first like this:
var isNeeded = Array.IndexOf(arr, visit);
And the peer asked me the time complexity of Array.IndexOf, it is O(m) and m is the length of the arr length. I should make it O(1) time instead. The peer worked very hard to help me, he followed my analysis of algorithm, time complexity O(n) where n is the length of search string instead of O(mn).
And the bugs are fixed to make the changes on the following lines.
Line 65 - add dictionary.ContainsKey(current) to avoid run time exception. The peer told me to move line 77 - 85 inside the while loop starting from 58 to 88, to make the code more simple to write.
ToDictionary using LINQ
var dictionary = arr.ToDictionary<char, int>();
And the peer was confused, and asked what I was writing. So, I wrote a for statement instead right away. I did not know that I have to write two mapping for key and value using LINQ statement in mock interview.
The LINQ learning is challenging, I should write
var dictionary = arr.ToDictionary(c => c, c => 1);
Discussion between two peers
It is the first time Julia learned that how good a peer can perform on the recursive algorithm, specially how to compose the test case quickly with the art of simplicity, and follow
Julia also learned that a programmer from other side of earth, North Ireland. Julia thought that the peer must work for Nokia before, but it ended up that Finland is far away from North Ireland. The peer corrected Julia on this.
The peer praised that Julia did very well on analysis of the algorithm, best one in last 5 or 6 peers worked on the algorithm. Julia gave honest response. It is all about hard work. Here is the code review about the algorithm on stackexchange.com, Julia worked on the algorithm over 2 weeks in 2015, and then she practiced mock interview on the algorithm over and over again. Here is the blog about over 5 or 6 mock interviews on the algorithm wrote in April 9, 2017.
Julia later looked up the university of North Ireland, Queen's University Belfast and talked to her roommate about Great Britain, compared to University of Victoria.
No comments:
Post a Comment