alonsovidales / facebook-programming-challenges

This is a compilation of possible questions to be solved in order to be hired by Facebook
159 stars 54 forks source link

better optimized solution to staves #6

Closed La-comadreja closed 9 years ago

La-comadreja commented 9 years ago

This approach to the staves problem takes a different tactic to identifying the staves initially, compared to @alonsovidales' very interesting approach. @alonsovidales calculates all combinations of staves, saves the full staves in a dict and checks each pair for overlap, then balance. My staves.py identifies the full set of non-overlapping staves by start position and extracts them as substrings immediately before the check for whether they are balanced. It calculates the stave balance of the longest staves first, and terminates if a balanced pair is found.

There are several advantages to this approach: (1) There is no need for the extra dict data structure. (2) If longer staves are found, the program can return the result and skip the calculations to identify the shorter staves. (3) No comparisons are performed between overlapping staves. (4) There is only one calculation to find the stave values in the branch, per stave.

I also made the method and variable names more self-explanatory.

alonsovidales commented 9 years ago

Perfect, Thanks a lot for the contribution!