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-with-Quadtrees-and-Hilbert-Curves > > 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.
