[algogeeks] Re: Facebook Campus Test Question
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.
[algogeeks] Re: Facebook Campus Test Question
plz post a samle input output.. 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Campus Test Question
i/p o/p files are attached in the post, see carefully :-o On Fri, Nov 4, 2011 at 6:23 PM, Dumanshu duman...@gmail.com wrote: plz post a samle input output.. 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 at http://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.
[algogeeks] Re: Facebook Campus Test Question
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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Campus Test Question
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 at http://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.
