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.
