Saturday, April 8, 2017

Leetcode 554: Brick Wall - contest experience

April 8, 2017

Problem statement

Julia spent less than 90 minutes to work on the algorithm in Leetcode week contest 27, from 6:30 pm - 8:00pm. 


Her C# code in the contest is here. Need to work on more on this medium algorithm, Leetcode 554.

Actionable Item


3 medium algorithm, each takes 20 minutes. So, the code should be less than 50 lines for each algorithm.

Time just flies too quickly when Julia worked on Leetcode 554. She managed to work out the sample test case, but it does not pass Leetcode online judge.

Will work on improvements later. 


Analysis


Julia, you should think about using min heap to track line sweep algorithm, therefore no run time error, which is probably timeout.

Design flaw 

Her C# code in the contest is here.

Time complexity of algorithm Julia implemented, every node is visited more than once at least, upper bound is not sure, some node is visited multiple times; upper bound cannot be determined. 

Better to choose the algorithm only visits each row each brick wall once algorithm, the time complexity is deterministic.

Lesson learned

April 10, 2017 10:00pm

Julia did not notice that her choice of algorithm had timeout issue. The upper bound of the algorithm cannot be determined.

Actionable Item

April 10, 2017
Julia, you over engineering the algorithm. Make it simple and quick.

Julia, you have to measure the algorithm by your engineering power, determine which idea to go for it depending on time constraint. 20 minutes does not allow more than 50 lines of code, bug-free. It is impossible.

April 11, 2017
It should be your routine before you write any algorithm code, try to analyse time complexity.

No comments:

Post a Comment