ohh..I think my solution will work on square not on rectangles. On Sun, Oct 10, 2010 at 8:13 PM, Mridul Malpani <malpanimri...@gmail.com>wrote:
> @ ashish agarwal > > ur solution will not work on this : > > 10101 > 00000 > 11111 > 11000 > > > On Oct 10, 6:59 pm, ashish agarwal <ashish.cooldude...@gmail.com> > wrote: > > This question was asked in google interview > > one solution for this question is DP > > make a matrix p (all rows and columns are initialized to zero) > > if(a[i][j]==1]{ > > p[i][j]=min(p[i-1][j],p[i,j-1],p[i-1][j-1]]+1;} > > > > else p[i][j]=0; > > f > > find p[i][j] such that its has max value. > > > > On Sun, Oct 10, 2010 at 7:13 PM, Chi <c...@linuxdna.com> wrote: > > > Nevermind. I don't think Z-curve is a good solution for this problem. > > > This question was asked before, and somebody wrote a much simplier > > > solution. I wanted to show you only the quadtree or spatialindex. If > > > you have a quadtree-Key like this: 123123121212 > > > > > You can make a query like this: if ( $key = substr (0, 6, > > > "123123121212" ) then ... this will query all subsquares from index > > > "123123xxxxx". It is used by Google Maps and Microsoft Maps. > > > > > The problem with the quadtree is that overlapping square, or > > > rectangle would not be found. > > > > > From Wikipedia: > > > > > >The resulting ordering can equivalently be described as the order one > > > would get from a depth-first traversal of a quadtree; because of its > close > > > connection with quadtrees, the Z-ordering can >be used to efficiently > > > construct quadtrees and related higher dimensional data structures > > > > > >http://en.wikipedia.org/wiki/Z-order_%28curve%29 > > > > >http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-. > .. > > > > > On Oct 10, 2:04 pm, Harshal <hc4...@gmail.com> wrote: > > > > @Chi > > > > pls provide a link to learn z-curve implementation in such > problems.... > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> > > > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.