@Enchantress: I'm assuming that you are talking about cheating by copying
from nearby students.
If this is not the first exam, based on prior grades, put the A students in
the back of the room, with the B students in front of the A students, the C
students in front of the B students, the D
No distinction has been amongst stduents. I think it is abt incraesing the
distance between any two students.
On Sun, Jul 28, 2013 at 10:45 AM, Dave dave_and_da...@juno.com wrote:
@Enchantress: I'm assuming that you are talking about cheating by copying
from nearby students.
If this is not
isnt the complexity should be o(m*n*n) instead of (n*n*n) as m can be
greater than n..plz comment
On Wed, Apr 10, 2013 at 10:11 PM, rahul sharma rahul23111...@gmail.comwrote:
http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
wat is complexity of
M is a matrix, not a number. M is NxN, so the algorithm is O(N^3) as
stated in the text.
On Apr 10, 4:19 pm, rahul sharma rahul23111...@gmail.com wrote:
isnt the complexity should be o(m*n*n) instead of (n*n*n) as m can be
greater than n..plz comment
On Wed, Apr 10, 2013 at 10:11 PM, rahul
M is number of rows n n is col..outer 2 loops are running n times and inner
is for kadane m tymes n for temp m times total 2m...so isnt it should be
n*n*m?
On Thursday, April 11, 2013, Don dondod...@gmail.com wrote:
M is a matrix, not a number. M is NxN, so the algorithm is O(N^3) as
stated in
Hope this helps :
space: o(n^2)
time: o(n^2)
#includeiostream
using namespace std;
inline int max(int a,int b)
{
if(ab)
return a;
else
return b;
}
int main()
{
char str[7]=hello;
int arr[3][3]={
{15,2,3},
{4,5,6},
# lengthy explanation give more attention
#here we are finding sums on all valid partition and storing all four
possible sums in variable a,b,c,d and and for all possible a,b,c,d we will
keep runninf max and min/
lets take an example parttion is done at row=0, coloumn=1
00 01| 02 03
@Hraday
worst case complexity of your algorithm comes out to be O(n^4)..
What I was thinking is precompute sums of all the rectangles in a sum
matrix ..using dynamic programming because I read some where that sum of
rectangles in a matrix has an optimal substructure property..
So we can get
Can any one help me with this ...Any DP solution?
On Sunday, 12 August 2012 17:48:07 UTC+5:30, sahil taneja wrote:
Divide 2D array into 4 parts. Compute sum of each partition and get max
value from the four of them. For all possible partitions get min value of
such max values computed.
--
@sahil Can you please explain your question with an example ?
--
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
Navin , your reply is correct.
On Sat, May 19, 2012 at 10:36 PM, Gene gene.ress...@gmail.com wrote:
The problem is not so clear, so you must make some assumptions to gat
an answer. Since we have water, we have to envision the histogram in
3d. Then assume that the distance between histogram
we need to find the amount of water stored on every bar of the histogram.
For this, we need to find two values :-
v1 :- the highest bar to the left - O(n)
v2:- the highest bar to the right - O(n)
amount of the water stored on the current bar is
Res= ( minimum of the two values(v1,v2) -
The problem is not so clear, so you must make some assumptions to gat
an answer. Since we have water, we have to envision the histogram in
3d. Then assume that the distance between histogram bars is 1 and bar
i has height H[i], 0=iN, zero width and unit depth, and the base
plane is at zero. Water
+1 @saurabh...:P
--
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
@gene
i think for 3 4 2 you need to start from left most element, and then make
substitutions one by one.
so it will be
3 4 2
2 4 3
2 3 4
@all i googled a bit, and found that O(n) solution is possible for it, any
idea ?
On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan
@shady : yes i guess this is what question says:-
so acc to this below algo work , i didnt execute it but i guess it will work
void nextSmaller(int arr[],int n)
{
s1 s;
int i,next,ele;
s.top=-1;
push(s,0);
for(i=1;in;i++)
{
next=arr[i];
if(isEmpty(s))
{
ele=pop(s);
while(arr[ele]
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com wrote:
@atul : it would be better for all to understand if you write the algo
instead of writing the code..
--
Amol Sharma
Third Year Student
Computer Science
http://www.geeksforgeeks.org/archives/8405
^ Similar Question.
On Mar 25, 4:49 pm, atul anand atul.87fri...@gmail.com wrote:
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com wrote:
@atul : it would be
http://www.geeksforgeeks.org/archives/8405
^ Similar question.
On Sun, Mar 25, 2012 at 5:19 PM, atul anand atul.87fri...@gmail.com wrote:
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com wrote:
@atul : it would
Urm. It's probably not the same. We could find the maximum element in the
array and use the trivial approach till we reach the max_element. After
that, all we need to do is to shift all the elements right of max_element
to the left by 1 and place max_element at the end. But again..this isn't
O(n).
i guess it can be done by modifying solution on
http://www.geeksforgeeks.org/archives/8405
my prev soln was based on the same..
instead of adding value to the stack...add index of that element.
in below code , line in bold are added
void nextSmaller(int arr[],int n)
{
s1 s;
int i,next,ele;
This problem isn't carefully defined. If you have 3,4,2 then 2 is the
first value smaller and of higher index than both 3 and 4. So which
to swap with?
On Mar 24, 10:01 am, Navin Kumar navin.nit...@gmail.com wrote:
Given an array of integers, for each index i, you have to swap the value at
i
@amol I was trying to put forward the point that the o/p need not be
sorted.If you check the difference between time of my and payal's message
it was a case of race condition.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Sun, Mar 25, 2012 at 6:54 AM,
n = x%2 ?
x can be any integer.
On Fri, Dec 2, 2011 at 5:19 PM, Don dondod...@gmail.com wrote:
(!x || !(x^1))
!(x1)
!((x|1)-1)
(x*x)==x
(x==(x==x))||(x==(x!=x))
etc.
On Nov 29, 9:07 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
*What are the different ways to say, the value of x
(!x || !(x^1))
!(x1)
!((x|1)-1)
(x*x)==x
(x==(x==x))||(x==(x!=x))
etc.
On Nov 29, 9:07 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
*What are the different ways to say, the value of x can be either a 0 or a
1.*
--
Nitin Garg
Personality can open doors, but only Character can keep them
Hi Geeks
Can anyone please comment on this.
Let me know if the problem description is not clear enough.
Thanks
Gopi
On Jul 9, 5:36 pm, Gopi kodaligopi...@gmail.com wrote:
Write code to move a set of elements (represented by start and end
indexed) in an array to a given destination location
@gopi: i didnt really understand what u want to say... what start,end and
destination denotes here??
u said it should start with 1 but in result it is starting with 9...plz
explain ur question again
On Sat, Jul 9, 2011 at 7:21 PM, Gopi kodaligopi...@gmail.com wrote:
Hi Geeks
Can anyone
Reverse elements of set from start to end
Reverse elements of set from end+1 to destination
Reverse elements of set from start to destination
DONE
O(n)
On Sat, Jul 9, 2011 at 7:25 PM, Yogesh Yadav medu...@gmail.com wrote:
@gopi: i didnt really understand what u want to say... what start,end
Hi Yogesh
start and end denote the indexes where the set that is to be moved
starts and ends in the given array.
Destination index denotes the index in the array where the given set
is to be moved. This needs some
rearrangement of the array elements as shown in the example before.
Hope that
@sunny
That's excellent. Thanks Sunny.
On Jul 9, 7:04 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Reverse elements of set from start to end
Reverse elements of set from end+1 to destination
Reverse elements of set from start to destination
DONE
O(n)
On Sat, Jul 9, 2011 at 7:25
If you allow for the following assumptions:
1. All numbers fit into a 32 bit or 64 bit integer.
2. The arrays are actually linked lists.
Time complexity: O(N)
Space complexity: O(1)
Solution:
1. Apply radix sort. (binary radix sort would probably do fine)
Note: You can make the sort stable
Yes I know I said it with regard to the current problem
On Tue, Jul 5, 2011 at 8:58 AM, Dave dave_and_da...@juno.com wrote:
@Saurabh: Nope. You can construct a heap in-place. But it is not O(n).
Dave
On Jul 4, 10:02 pm, saurabh singh saurab...@gmail.com wrote:
Again heap will require
@Dave bt the heap build operation is O(n) there is a proof fr this
On Tue, Jul 5, 2011 at 6:29 AM, saurabh singh saurab...@gmail.com wrote:
Yes I know I said it with regard to the current problem
On Tue, Jul 5, 2011 at 8:58 AM, Dave dave_and_da...@juno.com wrote:
@Saurabh: Nope. You can
http://www.cim.mcgill.ca/~langer/250/2010/lecture24.pdf
On Tue, Jul 5, 2011 at 12:37 PM, vaibhav agarwal vibhu.bitspil...@gmail.com
wrote:
@Dave bt the heap build operation is O(n) there is a proof fr this
On Tue, Jul 5, 2011 at 6:29 AM, saurabh singh saurab...@gmail.com wrote:
Yes I
yes Heap Build is O(n)
but after build it will be nlgn for comparision. isn't it ?
On Tue, Jul 5, 2011 at 10:07 PM, vaibhav agarwal vibhu.bitspil...@gmail.com
wrote:
@Dave bt the heap build operation is O(n) there is a proof fr this
On Tue, Jul 5, 2011 at 6:29 AM, saurabh singh
Lets conclude this post.Shall we?
.An o(n) seems infeasible without any significant extra memory
If extra memory is allowed,hash maps can be used to bring it down to
o(logn).But hash maps would eat up serious memory if numbers occupy a large
range.
--
You received this message because you
what abt this...
check length of the array if same then we make a min heap of both the
arrays which can be done in O(n) and call extraxtmin(). in this way we can
find whether they r equal.
othwersie nt equal.
correct me if i am wrong!!
On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh
Again heap will require extra space.
On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
vibhu.bitspil...@gmail.comwrote:
what abt this...
check length of the array if same then we make a min heap of both the
arrays which can be done in O(n) and call extraxtmin(). in this way we can
find
@saurabh bt we need only one extra array
On Mon, Jul 4, 2011 at 11:02 PM, saurabh singh saurab...@gmail.com wrote:
Again heap will require extra space.
On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
vibhu.bitspil...@gmail.com wrote:
what abt this...
check length of the array if same
@Vaibhav: Construction of a heap can be done in-place, but time
complexity is O(n log n).
Dave
On Jul 4, 9:55 pm, vaibhav agarwal vibhu.bitspil...@gmail.com wrote:
what abt this...
check length of the array if same then we make a min heap of both the
arrays which can be done in O(n) and call
@Saurabh: Nope. You can construct a heap in-place. But it is not O(n).
Dave
On Jul 4, 10:02 pm, saurabh singh saurab...@gmail.com wrote:
Again heap will require extra space.
On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
vibhu.bitspil...@gmail.comwrote:
what abt this...
check
I was thinking the same, BUT here the question is that we have two *SETS*
and that's the catch.
So, XORing all elements of SET A with SET B should result in ZERO only when
both the set have same elements.
Regards,
Sandeep Jain
On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal
@sandeep
SET A - {0,3,4,7}
SET B - {1,2,5,6}
xor of all elements is zero
sum of both the sets is same
no of elements in both are same
overall result : all Algorithm posted above Fails
On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain sandeep6...@gmail.com wrote:
I was thinking the same, BUT here
Agreed, BUT if you don't add a stipulation. You won't be able to reduce the
complexity.
For a 100% general solution, I don't think you can reduce the complexity
more than O(nLgn.)
There are variations of this question:
-- All numbers are non-zero and distinct.
-- All numbers belong to given range
But i don't think xor method will work at all for all of the cases above you
mentioned.
setA = {4,7}
setB = {5,6}
- all numbers in both set are nonzero and distinct
- all numbers are in some range :D
and for character parts it will similarly failby taking character set of
ascii values 4,5,6,7
there is no possible solution for this question in less than O(nlgn) time.
As by theorem given in cormen and solution is possible using xor
On Sun, Jul 3, 2011 at 2:27 PM, Sandeep Jain sandeep6...@gmail.com wrote:
For case1) yes XOR works,
for Well, for the other two cases hash-maps may come
Either you will have to use hashmaps which means extra storage or compromise
on time complexity as nlogn
I dont think there is any other possible workaround!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web
Hey,
what is the solution with XOR, methods mentioned above seem to
fail there any reference ?
On Sun, Jul 3, 2011 at 10:39 PM, Deoki Nandan deok...@gmail.com wrote:
there is no possible solution for this question in less than O(nlgn) time.
As by theorem given in cormen and
xor all the elements of both arrays ==0
sum of 1st array == sum of 2nd array
no. of elements in 1st == no. of elements in 2nd
if the above conditions are met, they have the same set.
m i missin sth?
On Jul 3, 1:23 am, mittal mohitm.1...@gmail.com wrote:
Given two arrays of numbers, find if each
xor will only result if corresponding elements are same . what if in both
the array set of integers are same but they arnt corresponding to each other
??
On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu duman...@gmail.com wrote:
xor all the elements of both arrays ==0
sum of 1st array == sum of 2nd
Dont think that the corresponding elements should be same.
XOR Should do it anyway.
Btw other question How would you find the second largest element in an
array using minimum no of comparisons?Any thing better than O(n).?
On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar
@mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont think
dat you can find second largest in less than O(n).
On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal mohitm.1...@gmail.com wrote:
Dont think that the corresponding elements should be same.
XOR Should do it anyway.
Btw other
@aditya. xor all elements mean that. take xor of each element of 1st array
store in a variable that take xor of variable and each element of the second
array if all elements are common then the variable will be 0 some where.
var = a[0];
for(i = 1; i sizeof(a)/sizeof(a[0]); i++)
var = var ^ a[i];
I think that the above algo will fail for the following two arrays:
a={2,2,3,3}
b={4,4,1,1}
sum(a)=sum(b);
a^b=0;
len(a)=len(b);
Correct me if i am wrong!
Pranav
On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa varunpahwa2...@gmail.comwrote:
@aditya. xor all elements mean that. take xor of each
but according to the question,ptr is pointing to the second node in this
case
On Fri, Apr 8, 2011 at 8:55 PM, Anurag atri anu.anurag@gmail.comwrote:
if innitially temp is pointing to A then there is no problem in deleting
the middle node ..
On Fri, Apr 8, 2011 at 4:49 PM,
for the second case it is possible only if the node contains the
previous node's address. Else there should be data movement
--
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
For the second case,
Consider,
A - B - C - NULL
Accor 2 me he has asked to reverse d list to make it as C - A by deleting
B, which can be done like this,
temp-next = temp-next-next; // A-C-NULL
temp-next-next = temp; //A-C-A
temp = temp-next; //C-A-C
temp-next-next = NULL; //C-A-NULL
Correct
hii,
Small correction
For the second case,
Consider,
A - B - C - NULL
Initially temp is pointing to A.
Accor 2 me he has asked to reverse d list to make it as C - A by deleting
B, which can be done like this,
temp-next = temp-next-next; // A-C-NULL
temp-next-next = temp; //A-C-A
temp =
if innitially temp is pointing to A then there is no problem in deleting the
middle node ..
On Fri, Apr 8, 2011 at 4:49 PM, murthy.krishn...@gmail.com
murthy.krishn...@gmail.com wrote:
hii,
Small correction
For the second case,
Consider,
A - B - C - NULL
Initially temp is pointing
Anyone here who can answer this question?
On Mon, Apr 4, 2011 at 9:18 PM, Umer Farooq the.um...@gmail.com wrote:
Hello friends,
The following question has appeared in two top companies of my city. I'd
appreciate if anyone is able to answer it.
Given a singly liked list comprising of three
@mac
Path always should be go through the root of the tree?
--
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
Why??? It doesn't help to solve problem. You are already have tree structure
with parent links. Taunt.
--
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
Tree structure already have parent node link. Even we reconstruct the tree
as linked list we are not allowed to achieve the goal. Path can be combined
using non-contigious (created from inorder traversal) elements. The only
solution is using DP with O(MAX_SUM_VALUE) extra space for each node.
On Mon, Jan 3, 2011 at 6:08 PM, juver++ avpostni...@gmail.com wrote:
Tree structure already have parent node link. Even we reconstruct the tree
as linked list we are not allowed to achieve
Normal tree node does not contain link to its parent. I am not saying
convert tree into linklist
On Tue, Jan 4, 2011 at 8:13 AM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
On Mon, Jan 3, 2011 at 6:08 PM, juver++ avpostni...@gmail.com wrote:
Tree structure already have parent node link. Even we reconstruct the tree
as linked list we are not allowed to achieve
Normal tree node
On Sun, Jan 2, 2011 at 8:30 PM, Akash Agrawal akash.agrawa...@gmail.comwrote:
I have written a kinda messed-up code for the same. Which is basically a
bottom-up approach.
Please find the same as attached. Some boundary conditions might be missed
and code can be written in a more decorated,
No , we had to find all the paths . Some paths could include the root .
On Tue, Dec 28, 2010 at 11:12 PM, yq Zhang zhangyunq...@gmail.com wrote:
I think the original question says Path can go from left subtree tree ,
include root and go to right tree as well. This should mean the path must
There are 3 paths exist in bst, post, pre and inorder.
store all these paths and find contiguous sum(and set of elements
which leads to this sum) and check if it equals to given sum, then
that is path.
On Dec 27, 6:48 pm, mohit ranjan shoonya.mo...@gmail.com wrote:
any hint for below question
Incorrect. Path can be combined from the several traversal algorithm's
output.
--
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
Not clear what path you are referring to.
Question. Should the path include root value always? (What is problem
with only left or only right path (not containing root))
In your example for 16 one more path can be 0 1 5 10 as
well. Should algo return all the paths or just first one.
I think the original question says Path can go from left subtree tree ,
include root and go to right tree as well. This should mean the path must
include the root.
On Tue, Dec 28, 2010 at 4:52 AM, shanushaan er.srivastavaro...@gmail.comwrote:
Not clear what path you are referring to.
And of course boundary cases(leaf nodes) are to be handled. For a leaf
node 'i', ok[i][j]=1(if j==v[i]), 0 otherwise!!!
On Dec 28, 11:04 pm, suhash suhash.venkat...@gmail.com wrote:
I think this can be solved using dp. Consider the subtree rooted at
node 'i'. Let ok[i][j] be a boolean (0 or 1)
Program is incorrect. Why does it output the following answer: point at (3,5
)size is 8???
--
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
How to solve the second question? it is different from the other question
posted where it requres only SQUARE sub matrix.
Sent from Nexus one
On Dec 25, 2010 11:00 AM, juver++ avpostni...@gmail.com wrote:
Try to search the answer before sumbitting the question here.
--
You received this
@ritesh..you dnt have to output v.. you have to output the minimum number of
flips so that your tree evaluates to v(v is either 0 or 1)
and if it alreday evaluates to v then return 0(no flips required)
if not possible return -1
On Wed, Aug 4, 2010 at 12:11 AM, RITESH SRIVASTAV
level of the tree is given or not ?
and where do we have to output V , just at the node we get it or at
the root ?
On Aug 3, 1:56 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a complete binary tree (either a node is a leaf node or has two
children)
every leaf node has value 0 or
write a recursive function getmin(node, value) that returns the least number
of flips necessary for the subtree rooted at node to give the result
value. recursive relations are easy to come up with, so I leave it as an
exercise :)
memorize the values calculated, so, never calculate a result more
I hope the value of V is 0 or 1. Is this right?
On Wed, Aug 4, 2010 at 12:48 AM, Manjunath Manohar manjunath.n...@gmail.com
wrote:
@above: i have little difficulty in perceiving the question... can u give
certain test cases..sample input/output ..
--
You received this message because you
4), which will vary the value of k for many times.
I think to cover up this problem..
1. we can store the starting and ending numbers for every K in another
file (with file name of every set) and then sort the file names
according to the starting values for every K set,
2. hence creating an
I like Terry's idea.
Let's say the 5000 numbers are: {1,2,...,5000}
For every 200 numbers you choose, create a 5000 bit string .. which
corresponds to 625 bytes
which is infact less than the 800 bytes you would require to store the
200 numbers as ints.
You don't store the 200 numbers explicitly,
I get what Terry means now. But it still uses 625/800 = 78% of the
naive method in terms of diskspace (or memory, whatever), so I think
the save is not big enough (the job interview is RD targeted, which I
assume they want to hear one with large saving).
Prateek's idea is to reduce the time of
I didn't fully get what you mean, but sounds not memory efficient: if
we need to store the 200 integers per set, and don't forget they say it
could be a lot of sets (even have to write to disk because memory does
not fit).
I think a better alternative could be to choose EVEN 5000 numbers
(taking mod of 2 of any number out of these can help to check whether
it can be in the set or not) and then make out set of 200 from these
5000 even numbers..
the set of 200 nos can be written on the disk in a sorted manner so
83 matches
Mail list logo
