@ 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>
> > .
> > 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.
