Thursday, February 16, 2017

Leetcode 317: Shortest distance from all buildings (Part 4)

Feb. 16, 2017

Introduction

Julia was trying to find a good one to ask code review on stackexchange.com, and the she noticed that her blog is coming to a landmark 100,000 views. So, she likes to celebrate her hard work, she saw one of visitor was from search result using keyword: Leetcode 317 in last 7 days. So, the user of the blog solved her problem - find a nice algorithm to review. She worked on the algorithm before, she did twice. 

Her first practice is more than 12 months, she reviewed the blog in January 2016In May 11, 2016, she practised again the algorithm. Her practice code is here. Through her practice, she likes to track her progress. She likes to say just so so, coding is like tennis sport, she has to learn from best - Roger Federer.

Workout

Julia likes to rewrite the C# code based on last practice in January, 2016. And here are the highlights of change.

To challenge herself, she designed several classes to track intermediate result, for example, empty land and building distance, building key and empty land position should also be recorded, so she can test the API first.

Because there is no concern about timeout or space limitation, Julia likes to design a few APIs, and also learn how to write code to follow S.O.L.I.D. principles.

In C# code, function WalkFromBuildingBFS is set as public API, and also a test case is added. Make sure that BFS search algorithm is working fine.

Here is the C# practice ready for review. Here is the code review link

Read some posts about SOLID principles on stackoverflow.com first.

Feb. 17, 2017 10:15pm 
Read the post about SOLID principles, the link is here.

Feb. 18, 2017 11:05am 
1. Update the question of Leetcode 317 to make it more instructional - the breadth first search, including some research I did on community challenge. 

2. Study the community challenge question code review, Rainfall challenge.
     Study Java code implementation first, and then write a C# one to ask for review.


Feb. 20, 2017
Read leetcode solution discussion, one of discussion is to expedite the search, great idea I read first time:
I also tested the other three C++ solutions posted so far, they took 340-1812 ms. I think mine is faster because I don't use a fresh "visited" for each BFS. Instead, I walk only onto the cells that were reachable from all previous buildings. From the first building I only walk onto cells where grid is 0, and make them -1. From the second building I only walk onto cells where grid is -1, and I make them -2. And so on.



No comments:

Post a Comment