@ashish: I should try your solution. On Oct 10, 3: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]{if ( $key = substr (0, 6, "123123121212" ) > 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> > > . > > 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.