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)
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
@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 ..
@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
@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
@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.
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
@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
@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
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
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
@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
@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
13 matches
Mail list logo
