As far as I have googled about the 'game of life' problem, of which this question is a variant ; no mathematical pattern/series emerges out of it ... but in this problem since the moves are defined in a 3*3 grids, I found some test cases where the board configurations do not change after certain k iterations. But I failed to generalize this. I have optimized the constant factor, by following a window strategy. In this we calculate the no. of black & whites for the first 3 rows, then keep them updating the count as you add the next row and remove the last row from the window. Improves the constant factor, but no change in complexity. I guess more than the complexity issue, FB people were interested in how well one can write a bug-free code & handle corner cases in given time. But, yeah if someone has a better solution than O(n^2), then it will be very nice.
On Nov 5, 12:06 am, sunny agrawal <[email protected]> wrote: > No,O(N^2) because all the flips happens simultaneously, it can be > reduce to O(2N) if each tile is represented using a single bit > > > > > > > > > > On Fri, Nov 4, 2011 at 11:12 PM, Dumanshu <[email protected]> wrote: > > is ur brute force O(1) for space? > > > On Nov 4, 10:24 am, sunny agrawal <[email protected]> wrote: > >> What can be a better solution than a Brute Force O(N^2* No of iteration) > > >> -- > >> Sunny Aggrawal > >> B.Tech. V year,CSI > >> Indian Institute Of Technology,Roorkee > > >> fb1_input.txt > >> < 1KViewDownload > > >> facebook.jpg > >> 119KViewDownload > > >> fb1_output.txt > >> < 1KViewDownload > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group > > athttp://groups.google.com/group/algogeeks?hl=en. > > -- > Sunny Aggrawal > B.Tech. V year,CSI > Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
