date:20120314

Re: [algogeeks] Array problem

2012-03-14 Thread Dheeraj Sharma

you have to calculate the sum of elements which are less than..that
particular element...this is not the question of calculating cumulative sum

On Wed, Mar 14, 2012 at 11:22 AM, sachin sabbarwal algowithsac...@gmail.com
 wrote:

 @gaurav popli:  how about this one??

 findsummat(int arr[],int n)
 {
int *sum ;
  sum =(int*)malloc(sizeof(int)*n);

 for(int i=0;in;i++)
   sum[i] = 0;

 for(int i=0;in;i++)
sum[i] = sum[i-1] + arr[i-1];
 //now print the sum array

 }

 it works very well
 plz tell me if anything is wrong with this solution.


 On Tue, Mar 13, 2012 at 12:03 PM, atul anand atul.87fri...@gmail.comwrote:

 @piyush : sorry dude , didnt get your algo . actually you are using
 different array and i get confused which array to be considered when.



 On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor pkjee2...@gmail.comwrote:

 1)First map the array numbers into the position in which they would be,
 if they are sorted,for example
 {30,50,10,60,77,88} --- {2,3,1,4,5,6}
 2)Now for each number ,find the cumulative frequency of index ( = the
 corresponding number in the map - 1).
 3)Output the cumulative frequency and increase the frequency  at the
 position (=the corresponding number in the map) by the number itself.
 Example
 {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
 Process the numbers now,
 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
 so output 0
Increase the frequency at index 2 to the number 3.
 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
Increase the frequency at index 3 to the number 5.
 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
 position 1 by 1.
 Similarly for others.


  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.




-- 
*Dheeraj Sharma*

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Array problem

2012-03-14 Thread sachin sabbarwal

now i get this!! i thought we have to calculate the sum upto (i-1)th index.
thanx for the clarifiacation.

On Wed, Mar 14, 2012 at 3:07 PM, Dheeraj Sharma dheerajsharma1...@gmail.com
 wrote:

 you have to calculate the sum of elements which are less than..that
 particular element...this is not the question of calculating cumulative sum


 On Wed, Mar 14, 2012 at 11:22 AM, sachin sabbarwal 
 algowithsac...@gmail.com wrote:

 @gaurav popli:  how about this one??

 findsummat(int arr[],int n)
 {
int *sum ;
  sum =(int*)malloc(sizeof(int)*n);

 for(int i=0;in;i++)
   sum[i] = 0;

 for(int i=0;in;i++)
sum[i] = sum[i-1] + arr[i-1];
 //now print the sum array

 }

 it works very well
 plz tell me if anything is wrong with this solution.


 On Tue, Mar 13, 2012 at 12:03 PM, atul anand atul.87fri...@gmail.comwrote:

 @piyush : sorry dude , didnt get your algo . actually you are using
 different array and i get confused which array to be considered when.



 On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor pkjee2...@gmail.comwrote:

 1)First map the array numbers into the position in which they would be,
 if they are sorted,for example
 {30,50,10,60,77,88} --- {2,3,1,4,5,6}
 2)Now for each number ,find the cumulative frequency of index ( = the
 corresponding number in the map - 1).
 3)Output the cumulative frequency and increase the frequency  at the
 position (=the corresponding number in the map) by the number itself.
 Example
 {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
 Process the numbers now,
 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is
 0. so output 0
Increase the frequency at index 2 to the number 3.
 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
Increase the frequency at index 3 to the number 5.
 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
 position 1 by 1.
 Similarly for others.


  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.


  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.




 --
 *Dheeraj Sharma*



  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread Sourabh Singh

@atul

Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time. :-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh singhsourab...@gmail.comwrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh singhsourab...@gmail.com
wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one
as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1]
) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma rahul23111...@gmail.com
wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread rahul sharma

@atul..plz tell me an example for square matrix...actually i faced it first
tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.comwrote:

@atul

Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time. :-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one
as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand
atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread atul anand

@rahul: i have alreday explained it in the provided link.
@sourbh : why it would not work for large dimension
On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

@atul..plz tell me an example for square matrix...actually i faced it
first tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time. :-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one
as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be
formed from any point taking that point as top left corner of max
rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand
atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at

Re: [algogeeks] Re: Microsoft Interview Question

2012-03-14 Thread atul anand

@umer : did interviewer told any one of the solution provided in the  given
link below or different?

http://www.geeksforgeeks.org/archives/1155


On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq the.um...@gmail.com wrote:

 Yes that is exactly what they wanted. I proposed BFS for this solution.
 Anyway, there was another problem that I was able to solve; but the
 interviewer brought up a much more efficient approach.

 The problem was:


- Given a linked a linked list with one pointer pointing to next,
another pointer pointing to any random pointer in the list. The random
pointer can be before or after the current pointer or it can even be at the
same node. Write a piece of code that can produce an exact copy of the
linked list.


 On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote:

 Yes that is exactly what they wanted. I proposed BFS for this solution.
 Anyway, there was another problem that I was able to solve; but the
 interviewer brought up a much more efficient approach.

 The problem was:

 Given a linked l


 On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:

 Since there is no mention of weights, you are looking for any spanning
 tree. Primm and Kruskal are for _minimum_ spanning tree. They are
 overkill for this problem.

 You can construct a spanning tree in any graph with DFS.  Just record
 every edge you find that reaches a vertex that has never been visited
 before.  This has to find every vertex, and since you are recording
 only the first edge used to arrive at each vertex, these edges must
 form a tree. This works even if there are cycles.  The algorithm is O(|
 E|).

 Note that in general a graph doesn't have a single root. So you'd
 search from all roots.  Another way to think about this:  introduce
 your own dummy root and edges to each vertex where there are no
 incident in edges.  Of course you don't report the dummy edges.

 On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote:
  i guess they were talking abt spanning tree , so you can use prism or
  kruskal algo to do the same.
 
 
 
 
 
 
 
  On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com
 wrote:
   Hello friends,
 
   I recently had an onsite MS interview. One of the questions that they
   asked was:
 
  - Given a directed graph, write a program that takes root of the
 graph
  and returns root of a tree which comprises of all the nodes of
 the graph in
  the same way as they appeared in the graph (the graph contains no
 cycles).
 
   --
   Umer
 
   --
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@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.

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.




 --
 Umer




 --
 Umer

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Re: Microsoft Interview Question

2012-03-14 Thread Umer Farooq

Well, the interviewer gave a hint to use hash-table.

The key of hash-table will be memory address of original node and value
will be the memory address of the new node.

On Wed, Mar 14, 2012 at 9:43 PM, atul anand atul.87fri...@gmail.com wrote:

 @umer : did interviewer told any one of the solution provided in
 the  given link below or different?

 http://www.geeksforgeeks.org/archives/1155


 On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq the.um...@gmail.com wrote:

 Yes that is exactly what they wanted. I proposed BFS for this solution.
 Anyway, there was another problem that I was able to solve; but the
 interviewer brought up a much more efficient approach.

 The problem was:


- Given a linked a linked list with one pointer pointing to next,
another pointer pointing to any random pointer in the list. The random
pointer can be before or after the current pointer or it can even be at 
 the
same node. Write a piece of code that can produce an exact copy of the
linked list.


 On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.comwrote:

 Yes that is exactly what they wanted. I proposed BFS for this solution.
 Anyway, there was another problem that I was able to solve; but the
 interviewer brought up a much more efficient approach.

 The problem was:

 Given a linked l


 On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:

 Since there is no mention of weights, you are looking for any spanning
 tree. Primm and Kruskal are for _minimum_ spanning tree. They are
 overkill for this problem.

 You can construct a spanning tree in any graph with DFS.  Just record
 every edge you find that reaches a vertex that has never been visited
 before.  This has to find every vertex, and since you are recording
 only the first edge used to arrive at each vertex, these edges must
 form a tree. This works even if there are cycles.  The algorithm is O(|
 E|).

 Note that in general a graph doesn't have a single root. So you'd
 search from all roots.  Another way to think about this:  introduce
 your own dummy root and edges to each vertex where there are no
 incident in edges.  Of course you don't report the dummy edges.

 On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote:
  i guess they were talking abt spanning tree , so you can use prism or
  kruskal algo to do the same.
 
 
 
 
 
 
 
  On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com
 wrote:
   Hello friends,
 
   I recently had an onsite MS interview. One of the questions that
 they
   asked was:
 
  - Given a directed graph, write a program that takes root of the
 graph
  and returns root of a tree which comprises of all the nodes of
 the graph in
  the same way as they appeared in the graph (the graph contains
 no cycles).
 
   --
   Umer
 
   --
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@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.

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.




 --
 Umer




 --
 Umer

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@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.




-- 
Umer

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread Sourabh Singh

@atul

1) it won't work for large dimention's coz their is a limit to size of
array we can declare on stack.
( which is typically 10^6 as far as i know :-) ).

2) the algo i m trying to find would work in linear time. while this one is
more then O(n^2)
fo rvery very large input this algo would be very very slow.. making it
impractial..

( it's like if u can find substring's in linear time then why use an O(n^2)
algo ;-) )

NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
on time to check implemention of your algo right now )

On Wed, Mar 14, 2012 at 9:07 AM, atul anand atul.87fri...@gmail.com wrote:

@rahul: i have alreday explained it in the provided link.
@sourbh : why it would not work for large dimension
On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

@atul..plz tell me an example for square matrix...actually i faced it
first tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

Also the histogram algo and algo given by you can't work on very very
big dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time.
:-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh singhsourab...@gmail.com
wrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand
atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy
one as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know
the whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be
formed from any point taking that point as top left corner of max
rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand atul.87fri...@gmail.com
wrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

--
You

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread Sourabh Singh

@rahul

may be this will help you..

/* Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.
   1. O(n^3) sol is very obvious
   2. O(n^2) sol [ this file]
   3. O(n)   sol [ possible but we need to know tucker matrix, etc advanced
set theory's]
*/


#includeiostream
#includeconio.h

int b[6][6];
using namespace std;
main()
{ int i,j,t;
  int a[6][6]=
  { 0,0,0,1,0,1,
0,1,1,1,0,0,
1,1,1,1,0,1,
0,1,1,1,1,0,
1,0,0,1,0,0,
0,1,0,1,1,0,};
  for(i=0;i6;i++)
  for(j=0;j6;j++)
  {   if(a[i][j]==1)
  {

b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
  }
  else
b[i][j]=0;
  }
  for(i=0;i6;i++)
  {   for(j=0;j6;j++)
  {printf( %d,a[i][j]);
  }
  printf(\n);
  }
  printf(\n\n\n\n\n);
  for(i=0;i6;i++)
  {   for(j=0;j6;j++)
  {printf( %d,b[i][j]);
  }
  printf(\n);
  }
  getch();
  return 0;
}


On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh singhsourab...@gmail.comwrote:

 @atul

 1) it won't work for large dimention's coz their is a limit to size of
 array we can declare on stack.
( which is typically 10^6 as far as i know :-)  ).

 2) the algo i m trying to find would work in linear time. while this one
 is more then O(n^2)
 fo rvery very large input this algo would be very very slow.. making
 it impractial..

 ( it's like if u can find substring's in linear time then why use an
 O(n^2) algo ;-) )

 NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
 on time to check implemention of  your algo right now )



 On Wed, Mar 14, 2012 at 9:07 AM, atul anand atul.87fri...@gmail.comwrote:

 @rahul: i have alreday explained it in the provided link.
 @sourbh : why it would not work for large dimension
 On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

 @atul..plz tell me an example for square matrix...actually i faced it
 first tym...it executes...but explain plz..

 On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.com
  wrote:

 @atul

 Also the histogram algo and algo given by you can't work on very very
 big dimentions. say 10^5 x 10^5 matrix.
  but if we can find a DP then  we just need to keep 2 row's at a time.
 :-)



 On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 read it ..

 it's good but more or less like the histogram algo.. i wanted a DP.
 approach..

 here is some of wat i heard from a senior in colg..

 1. at every index we can keep 4 variable

 ht: height of max rectangle possible at index above current
  wt width  

  hl:height of max rectangle possible at index left of  current
 wl:   
 


 now problem is which one to take for current... index



 On Tue, Mar 13, 2012 at 10:52 AM, atul anand 
 atul.87fri...@gmail.comwrote:

 @ Sourabh: check solution i have posted in below link


 http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0



 On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @ ALL

  finding square matrix is quite a standard question and nw an easy
 one as everyone knows the reccussence atul has given.
  but  i wanted to find max rectangle..

 i know there is a DP for it. in O(n^2). for nxn matrix..don't know
 the whole approach .but  here is what i remember..

 1. aproach is simple to keep track of max rectangle which can be
 formed from any point taking that point as top  left corner of max
 rectangle and
 proceed further down .

 can someone suggest how can be proceed further..


 [ NOTE: problem occurs mainly when their are more than one
 rectangles which can be formed from same point ]

 plz.. don't suggest the histogram method it's just a dirty way of
 avoiding to work on getting this DP right. :-)


 On Mon, Mar 12, 2012 at 11:29 PM, atul anand 
 atul.87fri...@gmail.com wrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
 R[i,,j-1] ) );


 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma 
 rahul23111...@gmail.com wrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square sub-matrix
 with all 1s.

 For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0

 The maximum square sub-matrix with all set bits is

 1  1  1
 1  1  1
 1  1  1

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.

[algogeeks] Re: Novell - Interview (Round-3 Coding)

2012-03-14 Thread Gene

In case you want to play with this, here is a little program
that computes suffix trees with a simple brute force algorithm
and prints their sizes.  It looks like the actual growth is
O(m^2).  So my quick analysis was too conservative:

m=1 chars=0
m=3 chars=3
m=6 chars=11
m=10 chars=29
m=15 chars=67
m=21 chars=137
m=28 chars=254
m=36 chars=436
m=45 chars=704
m=55 chars=1082
m=66 chars=1597
m=78 chars=2279
m=91 chars=3161
m=105 chars=4279
m=120 chars=5672
m=136 chars=7382
m=153 chars=9454
m=171 chars=11936
m=190 chars=14879
m=210 chars=18337
m=231 chars=22367
m=253 chars=27029
m=276 chars=32386
m=300 chars=38504
m=325 chars=45452
m=351 chars=53302
m=378 chars=62129
m=406 chars=72011
m=435 chars=83029
m=465 chars=95267
m=496 chars=108812
m=528 chars=123754
m=561 chars=140186
m=595 chars=158204
m=630 chars=177907
m=666 chars=199397
m=703 chars=222779
m=741 chars=248161
m=780 chars=275654
m=820 chars=305372
m=861 chars=337432
m=903 chars=371954
m=946 chars=409061
m=990 chars=448879
m=1035 chars=491537

public class SuffixTreeProblem {

// We store strings implicitly. If there is an a child,
// there is an a edge out of the node.  If dollar is
// true then this node marks the end of a suffix.
static class Node {
Node a = null, b = null;
boolean dollar = false;
}

// Produce a string that requires a big suffix tree.
byte [] genString(int n) {
byte [] s = new byte [1 + n + n * (n + 1) / 2];
int i = 0;
for (int in = n; in  0; in--) {
s[i++] = 'b';
for (int j = 0; j  in; j++) {
s[i++] = 'a';
}
}
s[i] = '$';
return s;
}

// Brute force: Build the tree counting characters used.
int suffixTreeChars(byte [] s) {
Node tree = new Node();
int n = 0;
for (int iStart = s.length - 1; iStart = 0; --iStart) {
Node p = tree;
for (int i = iStart; ; ++i) {
if (s[i] == '$') {
p.dollar = true;
break;
}
else if (s[i] == 'a') {
if (p.a == null) {
p.a = new Node();
++n;
}
p = p.a;
}
else {
if (p.b == null) {
p.b = new Node();
++n;
}
p = p.b;
}
}
}
return n;
}

void test() {
for (int n = 0; n  50; ++n) {
byte [] s = genString(n);
int m = s.length;
System.out.println(m= + m +  chars= +
suffixTreeChars(s));
}
}

public static void main(String [] argv) {
new SuffixTreeProblem().test();
}
}

On Mar 14, 1:06 am, Gene gene.ress...@gmail.com wrote:
 Let's try

 { reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } .

 Note that m = n(n+1)/2 + n = O(n^2)

 Think about adding suffixes to the tree from shortest to longest.

 So suppose you are now adding something of the form

   reverse( $ X a^L Y )

 where L is the length of the longest run of a's and X and Y are what
 comes before and after.  Well we know the length of Y is at most L
 and the length of X must be L(L-1)/2+(L-1) = L(L+1)/2 - 1 . What's
 already in the tree will match no more than 2L characters before a new
 branch occurs. The new branch will therefore have at least
 L(L+1)/2 - 1 - 2L characters.  This is O(L^2).

 You should do the math more rigorously, but roughly you will be
 getting for the total of all branches added,

 sum_{L=0,1,..n} O(L^2) = O(n^3) = O(m ^ 1.5)

 with one character per branch.  This is super-linear.

 On Mar 13, 12:47 am, reynald reni reni.reyn...@gmail.com wrote:







  Construct an infinite family of strings over a fixed alphabet, where
  the total length of the edge-labels on their suffix tree grows faster
  than O(m), where 'm' is the length of the string. [That is, show that
  linear time suffix tree algorithm would be impossible if edge-labels
  were written explicitly on the edges.]

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread saurabh singh

On 3/15/12, Sourabh Singh singhsourab...@gmail.com wrote:
 @rahul

 may be this will help you..

 /* Given a binary matrix, find out the maximum size square sub-matrix with
 all 1s.
1. O(n^3) sol is very obvious
2. O(n^2) sol [ this file]
3. O(n)   sol [ possible but we need to know tucker matrix, etc advanced
 set theory's]
 */


 #includeiostream
 #includeconio.h

 int b[6][6];
 using namespace std;
 main()
 { int i,j,t;
   int a[6][6]=
   { 0,0,0,1,0,1,
 0,1,1,1,0,0,
 1,1,1,1,0,1,
 0,1,1,1,1,0,
 1,0,0,1,0,0,
 0,1,0,1,1,0,};
   for(i=0;i6;i++)
   for(j=0;j6;j++)
   {   if(a[i][j]==1)
   {

 b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
   }
   else
 b[i][j]=0;
   }
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,a[i][j]);
   }
   printf(\n);
   }
   printf(\n\n\n\n\n);
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,b[i][j]);
   }
   printf(\n);
   }
   getch();
   return 0;
 }


 On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh
 singhsourab...@gmail.comwrote:

 @atul

 1) it won't work for large dimention's coz their is a limit to size of
 array we can declare on stack.
( which is typically 10^6 as far as i know :-)  ).

 2) the algo i m trying to find would work in linear time. while this one
 is more then O(n^2)
 fo rvery very large input this algo would be very very slow.. making
 it impractial..

 ( it's like if u can find substring's in linear time then why use an
 O(n^2) algo ;-) )

 NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
 on time to check implemention of  your algo right now )



 On Wed, Mar 14, 2012 at 9:07 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @rahul: i have alreday explained it in the provided link.
 @sourbh : why it would not work for large dimension
 On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

 @atul..plz tell me an example for square matrix...actually i faced it
 first tym...it executes...but explain plz..

 On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.com
  wrote:

 @atul

 Also the histogram algo and algo given by you can't work on very very
 big dimentions. say 10^5 x 10^5 matrix.
  but if we can find a DP then  we just need to keep 2 row's at a time.
 :-)



 On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 read it ..

 it's good but more or less like the histogram algo.. i wanted a DP.
 approach..

 here is some of wat i heard from a senior in colg..

 1. at every index we can keep 4 variable

 ht: height of max rectangle possible at index above current
  wt width  

  hl:height of max rectangle possible at index left of  current
 wl:   
 


 now problem is which one to take for current... index



 On Tue, Mar 13, 2012 at 10:52 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @ Sourabh: check solution i have posted in below link


 http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0



 On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @ ALL

  finding square matrix is quite a standard question and nw an easy
 one as everyone knows the reccussence atul has given.
  but  i wanted to find max rectangle..

 i know there is a DP for it. in O(n^2). for nxn matrix..don't know
 the whole approach .but  here is what i remember..

 1. aproach is simple to keep track of max rectangle which can be
 formed from any point taking that point as top  left corner of max
 rectangle and
 proceed further down .

 can someone suggest how can be proceed further..


 [ NOTE: problem occurs mainly when their are more than one
 rectangles which can be formed from same point ]

 plz.. don't suggest the histogram method it's just a dirty way of
 avoiding to work on getting this DP right. :-)


 On Mon, Mar 12, 2012 at 11:29 PM, atul anand 
 atul.87fri...@gmail.com wrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
 R[i,,j-1] ) );


 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma 
 rahul23111...@gmail.com wrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square sub-matrix
 with all 1s.

 For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0

 The maximum square sub-matrix with all set bits is

 1  1  1
 1  1  1
 1  1  1

  --
 You received this message because you are subscribed to

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread saurabh singh

@sourabhThere are O(n^2) elements in the matrix of size nXn. Yes
we can find patterns in a substring with n elements in O(n) but can
you do that in O(sqrt(n)) (To complete your analogy),
Beside's can you allocate a 10^6X10^6 matrix in an array?


On 3/15/12, saurabh singh saurab...@gmail.com wrote:
 On 3/15/12, Sourabh Singh singhsourab...@gmail.com wrote:
 @rahul

 may be this will help you..

 /* Given a binary matrix, find out the maximum size square sub-matrix
 with
 all 1s.
1. O(n^3) sol is very obvious
2. O(n^2) sol [ this file]
3. O(n)   sol [ possible but we need to know tucker matrix, etc
 advanced
 set theory's]
 */


 #includeiostream
 #includeconio.h

 int b[6][6];
 using namespace std;
 main()
 { int i,j,t;
   int a[6][6]=
   { 0,0,0,1,0,1,
 0,1,1,1,0,0,
 1,1,1,1,0,1,
 0,1,1,1,1,0,
 1,0,0,1,0,0,
 0,1,0,1,1,0,};
   for(i=0;i6;i++)
   for(j=0;j6;j++)
   {   if(a[i][j]==1)
   {

 b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
   }
   else
 b[i][j]=0;
   }
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,a[i][j]);
   }
   printf(\n);
   }
   printf(\n\n\n\n\n);
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,b[i][j]);
   }
   printf(\n);
   }
   getch();
   return 0;
 }


 On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh
 singhsourab...@gmail.comwrote:

 @atul

 1) it won't work for large dimention's coz their is a limit to size of
 array we can declare on stack.
( which is typically 10^6 as far as i know :-)  ).

 2) the algo i m trying to find would work in linear time. while this one
 is more then O(n^2)
 fo rvery very large input this algo would be very very slow.. making
 it impractial..

 ( it's like if u can find substring's in linear time then why use an
 O(n^2) algo ;-) )

 NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit
 short
 on time to check implemention of  your algo right now )



 On Wed, Mar 14, 2012 at 9:07 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @rahul: i have alreday explained it in the provided link.
 @sourbh : why it would not work for large dimension
 On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

 @atul..plz tell me an example for square matrix...actually i faced it
 first tym...it executes...but explain plz..

 On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh
 singhsourab...@gmail.com
  wrote:

 @atul

 Also the histogram algo and algo given by you can't work on very very
 big dimentions. say 10^5 x 10^5 matrix.
  but if we can find a DP then  we just need to keep 2 row's at a
 time.
 :-)



 On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 read it ..

 it's good but more or less like the histogram algo.. i wanted a DP.
 approach..

 here is some of wat i heard from a senior in colg..

 1. at every index we can keep 4 variable

 ht: height of max rectangle possible at index above current
  wt width  

  hl:height of max rectangle possible at index left of  current
 wl:   
 


 now problem is which one to take for current... index



 On Tue, Mar 13, 2012 at 10:52 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @ Sourabh: check solution i have posted in below link


 http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0



 On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @ ALL

  finding square matrix is quite a standard question and nw an easy
 one as everyone knows the reccussence atul has given.
  but  i wanted to find max rectangle..

 i know there is a DP for it. in O(n^2). for nxn matrix..don't know
 the whole approach .but  here is what i remember..

 1. aproach is simple to keep track of max rectangle which can be
 formed from any point taking that point as top  left corner of max
 rectangle and
 proceed further down .

 can someone suggest how can be proceed further..


 [ NOTE: problem occurs mainly when their are more than one
 rectangles which can be formed from same point ]

 plz.. don't suggest the histogram method it's just a dirty way of
 avoiding to work on getting this DP right. :-)


 On Mon, Mar 12, 2012 at 11:29 PM, atul anand 
 atul.87fri...@gmail.com wrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
 R[i,,j-1] ) );


 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma 
 rahul23111...@gmail.com wrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square
 sub-matrix
 with all 1s.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread atul anand

@Sourabh : here we are talking abt 2 different problems in this post..which
are little bit similar.

1) original question says find max subset of matix contaning '1' and '0'

we knw recurrence to solve this problem , as posted above.

2) now your question is to find max subset of matrix which contain +ve or
-ve numbers , not necessarily only '1' or '0'

so in my solution , you need to give some input to solve this problem
and that input is say matrix m[][].
if you check my solution then in just modifies input matrix to find
solution , its space complexity is O(1).

On Thu, Mar 15, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.comwrote:

@atul

1) it won't work for large dimention's coz their is a limit to size of
array we can declare on stack.
( which is typically 10^6 as far as i know :-) ).

2) the algo i m trying to find would work in linear time. while this one
is more then O(n^2)
fo rvery very large input this algo would be very very slow.. making
it impractial..

( it's like if u can find substring's in linear time then why use an
O(n^2) algo ;-) )

NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
on time to check implemention of your algo right now )

On Wed, Mar 14, 2012 at 9:07 AM, atul anand atul.87fri...@gmail.comwrote:

@rahul: i have alreday explained it in the provided link.
@sourbh : why it would not work for large dimension
On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

@atul..plz tell me an example for square matrix...actually i faced it
first tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.com
wrote:

@atul

Also the histogram algo and algo given by you can't work on very very
big dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time.
:-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand
atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy
one as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know
the whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be
formed from any point taking that point as top left corner of max
rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one
rectangles which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand
atul.87fri...@gmail.com wrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

--
You received this message

Re: [algogeeks] Array problem

Re: [algogeeks] Array problem

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Re: Microsoft Interview Question

Re: [algogeeks] Re: Microsoft Interview Question

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

[algogeeks] Re: Novell - Interview (Round-3 Coding)

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

13 matches

Site Navigation

Mail list logo

Footer information