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 wrote:
> @Enchantress: I'm assuming that you are talking about cheating by copying
> from nearby students.
>
> If this is not the first exam, base
@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 st
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 wrote:
> M is a matrix, not a number. M is NxN, so the algorithm is O(N^3) as
> stated in the text.
>
> On Ap
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 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 sharma 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 sharma wrote:
>
> http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
>
> wat is complexity of thisn3 or mn2
>
Hope this helps :
space: o(n^2)
time: o(n^2)
#include
using namespace std;
inline int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
char str[7]="hello";
int arr[3][3]={
{15,2,3},
{4,5,6},
@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 sum
# 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
@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
algogeeks+unsubscr..
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.
>
Navin , your reply is correct.
On Sat, May 19, 2012 at 10:36 PM, Gene 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 bars is 1 and bar
> i
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<=i wrote:
> Imagine that you have an histogram stored in an array. No
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) - heigh
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;
s.top=
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).
http://www.geeksforgeeks.org/archives/8405
^ Similar question.
On Sun, Mar 25, 2012 at 5:19 PM, atul anand wrote:
> wont work for all cases...ignore
> i will post the algoonce i fix it
> On 25 Mar 2012 17:06, "Amol Sharma" wrote:
>
>> @atul : it would be better for all to understand if you
http://www.geeksforgeeks.org/archives/8405
^ Similar Question.
On Mar 25, 4:49 pm, atul anand wrote:
> wont work for all cases...ignore
> i will post the algoonce i fix it
> On 25 Mar 2012 17:06, "Amol Sharma" wrote:
>
>
>
>
>
>
>
> > @atul : it would be better for all to understand if you
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, "Amol Sharma" 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 and Engineering
@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;i next)
{
swap(arr,ele,i);
next=arr[ele];
if(isEmpty(&s)
@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 wrote:
> +1 @saurabh...:P
>
+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 t
@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, Ge
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 wrote:
> Given an array of integers, for each index i, you have to swap the value at
> i with the first value
n = x%2 ?
x can be any integer.
On Fri, Dec 2, 2011 at 5:19 PM, Don wrote:
> (!x || !(x^1))
> !(x>>1)
> !((x|1)-1)
> (x*x)==x
> (x==(x==x))||(x==(x!=x))
>
> etc.
>
> On Nov 29, 9:07 pm, Nitin Garg wrote:
> > *What are the different ways to say, the value of x can be either a 0 or
> a
> > 1.*
>
(!x || !(x^1))
!(x>>1)
!((x|1)-1)
(x*x)==x
(x==(x==x))||(x==(x!=x))
etc.
On Nov 29, 9:07 pm, Nitin Garg 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 open"
--
You r
@sunny
That's excellent. Thanks Sunny.
On Jul 9, 7:04 pm, sunny agrawal 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 PM, Yogesh Ya
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 clari
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 wrote:
> @gopi: i didnt really understand what u want to say... what start,end and
> destination d
@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 wrote:
> Hi Geeks
>
> Can anyone please comment on this
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 wrote:
> Write code to move a set of elements (represented by start and end
> indexed) in an array to a given destination location (denoted by
> destinatio
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 on
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 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 wrote:
>
>> Yes I know I said it w
http://www.cim.mcgill.ca/~langer/250/2010/lecture24.pdf
On Tue, Jul 5, 2011 at 12:37 PM, vaibhav agarwal 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 wrote:
>
>> Yes I know I said it with regard to the current
@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 wrote:
> Yes I know I said it with regard to the current problem
>
> On Tue, Jul 5, 2011 at 8:58 AM, Dave wrote:
>
>> @Saurabh: Nope. You can construct a heap in-place. But it is no
Yes I know I said it with regard to the current problem
On Tue, Jul 5, 2011 at 8:58 AM, Dave 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 wrote:
> > Again heap will require extra space.
> >
> > On Tue, Jul 5, 2011
@Saurabh: Nope. You can construct a heap in-place. But it is not O(n).
Dave
On Jul 4, 10:02 pm, saurabh singh wrote:
> Again heap will require extra space.
>
> On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
> wrote:
>
>
>
>
>
> > what abt this...
> > check length of the array if same then we m
@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 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 extraxtmin(). in this w
@saurabh bt we need only one extra array
On Mon, Jul 4, 2011 at 11:02 PM, saurabh singh 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 then we m
Again heap will require extra space.
On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
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 extraxtmin(). in this way we can
> find whether they r equal.
> othwe
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 wrote:
> Let
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 are
I guess this question is similar to anagram.
On Mon, Jul 4, 2011 at 1:07 AM, Arpit Sood wrote:
> 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 wrote:
>
>> there is no possibl
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 wrote:
> there is no possible solution for this question in less than O(nlgn) time.
> As by theorem given in cormen and solution is possib
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
may be we can add condition that sum of squares and cubes be same.
On Sun, Jul 3, 2011 at 1:09 PM, Deoki Nandan wrote:
> 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:
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 wrote:
> For case1) yes XOR works,
> for Well, for the other two cases hash-maps may come in handy. :)
>
>
> R
For case1) yes XOR works,
for Well, for the other two cases hash-maps may come in handy. :)
Regards,
Sandeep Jain
On Sun, Jul 3, 2011 at 1:48 PM, sunny agrawal wrote:
> 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}
>
>
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,
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
@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 wrote:
> I was thinking the same, BUT here the question is tha
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 wrote:
> I think
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 wrote:
> @aditya. xor all elements mean that. take xor of each element of 1st array
> st
@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];
@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 wrote:
> Dont think that the corresponding elements should be same.
> XOR Should do it anyway.
>
> Btw other question "How wou
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
wrote:
> xor will only res
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 wrote:
> xor all the elements of both arrays ==0
> sum of 1st array == sum of 2nd array
> no. of elem
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 wrote:
> Given two arrays of numbers, find if each of the two arrays have
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 wrote:
> 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 <
>
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 te
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
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
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 u
Anyone here who can answer this question?
On Mon, Apr 4, 2011 at 9:18 PM, Umer Farooq 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 nodes
>
> Dele
@mac ..ACTUAL QUESTION IS like this
Given a binary tree and a number, return true if the tree has a root-
to-leaf path such that adding up all the values along the path equals
the given number. Return false if no such path can be found.
so given tree is like this
12so possible co
@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
algogeeks+unsubscr...@
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
On Tue, Jan 4, 2011 at 8:13 AM, rahul patil
wrote:
>
>
> On Mon, Jan 3, 2011 at 6:08 PM, juver++ 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
On Mon, Jan 3, 2011 at 6:08 PM, juver++ 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 directly. I want to say tha
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 Sun, Jan 2, 2011 at 8:30 PM, Akash Agrawal wrote:
> 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, beautiful fashion.
>
>
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, beautiful fashion.
Logic:
- start from the root,
- keep the nodes value in an
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 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
> include the root.
>
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 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) denoting whether you can
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) denoting whether you can
achieve a sum of 'j', with the subtree rooted at node 'i', and node
'i' is chosen in the path.
Hence, ok[i][j] = max((k=0 to (j-v[i])) ok[left(i)][k]&ok[right(
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 wrote:
> Not clear what path you are referring to.
>
> Question. Should the path includ
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.
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
al
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 wrote:
> any hint for below question ?
>
> Mohit
>
>
>
>
>
>
Check it once again. There is no submatrix with 8 1's in it.
--
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...
Hi ,
the program outputs the co-ordinate of bottom-right of the largest
1*1 rectangular submatrix and the size is total number of elements in that
matrix.
On Mon, Dec 27, 2010 at 7:31 PM, juver++ wrote:
> Program is incorrect. Why does it output the following answer: point at
> (3,5 )s
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
Hi Guys ,
I have coded the first part soon i will come with the
solution of part 2 :---
Let me know if u find any error case (hope u will find none)
public class Largestsubmatrix {
public point [][] a;
int [][] binmatrix;
public point loc;
public Largestsubmatrix(int [][] a) {
t
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++" wrote:
> Try to search the answer before sumbitting the question here.
>
> --
> You received this message because you a
Try to search the answer before sumbitting the question here.
--
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..
@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
wrote:
> level of
I hope the value of V is 0 or 1. Is this right?
On Wed, Aug 4, 2010 at 12:48 AM, Manjunath Manohar 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 are subscribed to the
@above: i have little difficulty in perceiving the question... can u give
certain test cases..sample input/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 unsubscri
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 mo
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 wrote:
> given a complete binary tree (either a node is a leaf node or has two
> children)
> every leaf node has value 0 or 1.
> every internal node
I forgot to mention that we choose nos from 0 to 4999
--~--~-~--~~~---~--~~
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
To represent each no. by 1 bit, for 5000 nos , we require 5000 bits.
Since an integer has 32 bits. A set can be represented by an 156 integr
array.In array each bit corresponding to no. in set is set. Thus is
set1 contains no. k. Let i=k/32, pos=k%32. Then for set1, pos LSB of
ith element of arra
" 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
Kevin wrote:
> 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 R&D targeted, which I
> assume they want to hear one with "large" saving).
>
> Prateek's idea
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 R&D targeted, which I
assume they want to hear one with "large" saving).
Prateek's idea is to reduce the time of
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 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
that
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).
as we are given the numbers to be chosen , choose any consecutive 5000
integers or 5000 integers with constant difference then map it on to a
array of size 5000.
Store the numbers in the set by arr[no in set ]=1;
Then you can store them in an array and the above operation can be
done in o(1).
Wh
98 matches
Mail list logo
