Hey what was the facebook question at IIT Roorkee? On Nov 5, 6:04 pm, saket <saket.ma...@gmail.com> wrote: > 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 <sunny816.i...@gmail.com> 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 <duman...@gmail.com> wrote: > > > is ur brute force O(1) for space? > > > > On Nov 4, 10:24 am, sunny agrawal <sunny816.i...@gmail.com> 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 algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
