Continue after first blog on this problem:
http://juliachencoding.blogspot.ca/2016/07/leetcode-142-linked-list-cycle-ii.html
Java solution written in facebook code lab:
https://gist.github.com/jianminchen/cc0f97525e3eb68db23f4a07ec0b7e90
The code failed to pass some test cases.
Highlight problems on the first writing:
1. line 20,
normalRunner - one step a time, the variable name is too long; slow will be better.
2. line 21,
doubleRunner - the variable name is not so accurate; fast will be better.
problem 1: base case checking:
line 17: if(a == null)
return null
if the list is null or only has 1 node, then no cycle.
problem 2: doubleRunner and normalRunner is in the same list, and doubleRunner is ahead of normalRunner if there is no cycle; and if there is a cycle, two runners will run forever. In both cases, only need to check doubleRunner != null, if it is true, then normalRunner != null will be true as well.
In short, doubleRunner != null => normalRunner != null
The while checking has duplicate checking!
problem 3:
line 24: doubleRunner is not null <= it is duplicated with base case checking (line 17)!
While loop line 24, doubleRunner != null is duplicate with base case checking.
While loop design:
Let us check fast node can move 2 steps, next two nodes are not null;
if slow and fast node meets, then break the loop. <- make the logic checking positive, not negative (line 25)
problem 4:
while loop is not designed very well - easy to make bugs, hidden bugs.
line 25: negative checking - make the code more confusing
problem 5:
line 34: bug001 - if clause checking problem
line 35: doubleRunner != null => normalRunner != null
so if statement is not optimal
problem 6:
line 35: there is a hidden bug here - still cannot figure out.
problem 7:
line 38: extra variable - not necessary, reuse the old one, still in the scope.
line 40: not necessary
line 41: not necessary
Actionable item:
1. Document the mistakes made in the practice, learn from the experience.
2. Review code and figure out issues without any help.
Could not figure out bugs in the first practice
-> Failed facebook code lab test cases
-> Studied optimal solution
-> Ran optimal solution in facebook code lab
-> passed all test cases
-> then, started to find problems in the first practice
-> wrote down problems one by one
Train insane or remain the same - focus on training!
Train insane or remain the same 💪#progress #nopainnogain #mondaymotivation— Kristina Mladenovic (@KikiMladenovic) June 20, 2016
Séance de 1/2squat aujourd'hui😉 et vous? pic.twitter.com/K8tGiOXixC
No comments:
Post a Comment