Re: [algogeeks] Re: arrays

[Abioy Sun]

Hello,

2010/12/29 Anand :
> if I already have a structure indicating the position of the element in the
> array. Then why do we need to sort. Question is to provide index of element
> in O(nlogn).

You do not have a structure before  preprocessing the data, whose
complexity  is O(nlogn) via qsort. Once you zip the zip the two array,
and sort the new array as @Wladimir and @juver++ mention, you can
provide each certain element's index in O(logn) via bsearch.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: arrays

[jai gupta]

for each element in the second array apply binary search in first array. ie,
For X[1] find 1 in first array with binary search.
Time Complexity=O(nlogn)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: arrays

[Anand]

if I already have a structure indicating the position of the element in the
array. Then why do we need to sort. Question is to provide index of element
in O(nlogn).



On Tue, Dec 28, 2010 at 2:20 PM, Wladimir Tavares wrote:

> Hi Anad,
>
> You can create a struct with this information
>
> typedef struct TArray{
> int value;
> int index;
> };
>
> TArray a[100];
>
>
>
> Wladimir Araujo Tavares
> http://www.si.ufc.br/~wladimir 
> "Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos."
>
>
>
>
>
> On Tue, Dec 28, 2010 at 1:57 PM, Anand  wrote:
>
>> Now the question boils down to how to sorted the array preserving its
>> index.
>>
>>
>> On Tue, Dec 28, 2010 at 12:27 AM, juver++  wrote:
>>
>>> Sort first array preserving the initial position of the elements.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: arrays

[Wladimir Tavares]

Hi Anad,

You can create a struct with this information

typedef struct TArray{
int value;
int index;
};

TArray a[100];



Wladimir Araujo Tavares
http://www.si.ufc.br/~wladimir 
"Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos."




On Tue, Dec 28, 2010 at 1:57 PM, Anand  wrote:

> Now the question boils down to how to sorted the array preserving its
> index.
>
>
> On Tue, Dec 28, 2010 at 12:27 AM, juver++  wrote:
>
>> Sort first array preserving the initial position of the elements.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Interview question amazon

[suhash]

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
> 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)][j-
> v[i]-k])
> This can be computed in a bottom up fashion for each node(each 'i')
> and for each possible sum(each 'j'). Hence, complexity is O(n*s*s).
>
> Now, if input is S (given sum value to find)
> Then, for each node 'i' if ok[i][S]=1, then a path exists with this
> node as root.
>
> After this, printing all paths can be done easily again similar to the
> first case.
>
> On Dec 26, 10:08 pm, MAC  wrote:
>
> > you are given a bst where each node has a int value , parent pointer , and
> > left and right pointers , write a function to find a path with a given sum
> > value. Path can go from left subtree tree , include root and go to right
> > tree as well . we need to find these paths also .
>
> >                                         5
> >            1                                                 10
> > 0                 2                                  6             11
>
> > so to find 16 we say it is 1 to 5 to 10
>
> > --
> > thanks
> > --mac

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Interview question amazon

[suhash]

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)][j-
v[i]-k])
This can be computed in a bottom up fashion for each node(each 'i')
and for each possible sum(each 'j'). Hence, complexity is O(n*s*s).

Now, if input is S (given sum value to find)
Then, for each node 'i' if ok[i][S]=1, then a path exists with this
node as root.

After this, printing all paths can be done easily again similar to the
first case.


On Dec 26, 10:08 pm, MAC  wrote:
> you are given a bst where each node has a int value , parent pointer , and
> left and right pointers , write a function to find a path with a given sum
> value. Path can go from left subtree tree , include root and go to right
> tree as well . we need to find these paths also .
>
>                                         5
>            1                                                 10
> 0                 2                                  6             11
>
> so to find 16 we say it is 1 to 5 to 10
>
> --
> thanks
> --mac

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Interview question amazon

[yq Zhang]

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 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.
>
> On Dec 26, 10:08 pm, MAC  wrote:
> > you are given a bst where each node has a int value , parent pointer ,
> and
> > left and right pointers , write a function to find a path with a given
> sum
> > value. Path can go from left subtree tree , include root and go to right
> > tree as well . we need to find these paths also .
> >
> > 5
> >1 10
> > 0 2  6 11
> >
> > so to find 16 we say it is 1 to 5 to 10
> >
> > --
> > thanks
> > --mac
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: arrays

[Anand]

Now the question boils down to how to sorted the array preserving its index.

On Tue, Dec 28, 2010 at 12:27 AM, juver++  wrote:

> Sort first array preserving the initial position of the elements.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: arrays

[Anand]

@ Wladimir

How do you get

(1,3)
(2,1)
(3,6)
(4,5)
(5,2)
(6,3)

B'cos once you sort the array you lose its original index.


On Tue, Dec 28, 2010 at 5:50 AM, Wladimir Tavares wrote:

> Consider your example:
>
>
> One is
>
> 2 5 1 6 4 3
>
> other is
>
> 1 2 3 4 5 6.
>
>
> After sorted the first array and keep the position you will have:
>
>
> (1,3)
> (2,1)
> (3,6)
> (4,5)
> (5,2)
> (6,3)
>
> O(n log n)
>
> for each value of the second array do  a binary search in the first array
> and discover the position
>
> O (log n)
>
> O (nlgn + lgn)
>
>
>
> On Tue, Dec 28, 2010 at 8:48 AM, Bhoopendra Singh  > wrote:
>
>> Is second array sorted?
>>
>>
>> On Tue, Dec 28, 2010 at 1:57 PM, juver++  wrote:
>>
>>> Sort first array preserving the initial position of the elements.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: arrays

[Wladimir Tavares]

Consider your example:

One is

2 5 1 6 4 3

other is

1 2 3 4 5 6.


After sorted the first array and keep the position you will have:


(1,3)
(2,1)
(3,6)
(4,5)
(5,2)
(6,3)

O(n log n)

for each value of the second array do  a binary search in the first array
and discover the position

O (log n)

O (nlgn + lgn)



On Tue, Dec 28, 2010 at 8:48 AM, Bhoopendra Singh
wrote:

> Is second array sorted?
>
>
> On Tue, Dec 28, 2010 at 1:57 PM, juver++  wrote:
>
>> Sort first array preserving the initial position of the elements.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Interview question amazon

[shanushaan]

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.

On Dec 26, 10:08 pm, MAC  wrote:
> you are given a bst where each node has a int value , parent pointer , and
> left and right pointers , write a function to find a path with a given sum
> value. Path can go from left subtree tree , include root and go to right
> tree as well . we need to find these paths also .
>
>                                         5
>            1                                                 10
> 0                 2                                  6             11
>
> so to find 16 we say it is 1 to 5 to 10
>
> --
> thanks
> --mac

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Interview Question

[suhash]

Sorry my mistake! But the general problem with more than 2 children
possible is more interesting! :)

On Dec 28, 10:58 am, Terence  wrote:
> The description on internal nodes indicates this:
>
> > The value of an "AND" gate node is given by the logical AND of its TWO 
> > children's values.
> > The value of an "OR" gate likewise is given by the logical OR of its TWO 
> > children's values.
>
> On 2010-12-28 13:35, suhash wrote:
>
>
>
>
>
>
>
> > Your approach is for a binary tree, but the problem statement does not
> > say anything about it.
>
> > On Dec 28, 10:27 am, pacific pacific  wrote:
> >> here is my approach :
>
> >> Starting from the root node ,
> >> if root node need to have a 1 ...
> >> if root is an and gate :
> >>       flips  = minflips for left child to have value 1 + minflips for the
> >> right child to have value 1
> >> else
> >>       flips = minimum of ( minflips for left child to have value 1 , 
> >> minflips
> >> for right child to have value 1)
>
> >> For  a leaf node , return 0 if the leaf has the value needed else return
> >> INFINITY.Also if at any internal node if it is not possible return 
> >> INFINITY.
>
> >> On Tue, Dec 28, 2010 at 10:06 AM, Anand  wrote:
> >>> @Terence.
> >>> Could please elaborate your answer. Bottom up level order traversal helps
> >>> to get the final root value but how to use it to find minimum flips needed
> >>> to Obtain the desired root value.
> >>> On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
>  Using the same level order traversal (bottom up), calculating the minimum
>  flips to turn each internal node to given value (0/1).
>  On 2010-12-24 17:19, bittu wrote:
> > Boolean tree problem:
> > Each leaf node has a boolean value associated with it, 1 or 0. In
> > addition, each interior node has either an "AND" or an "OR" gate
> > associated with it. The value of an "AND" gate node is given by the
> > logical AND of its two children's values. The value of an "OR" gate
> > likewise is given by the logical OR of its two children's values. The
> > value of all of the leaf nodes will be given as input so that the
> > value of all nodes can be calculated up the tree.
> > It's easy to find the actual value at the root using level order
> > traversal and a stack(internal if used recursion).
> > Given V as the desired result i.e we want the value calculated at the
> > root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
> > to OR or OR to AND be required at internal nodes to achieve that?
> > Also for each internal node you have boolean associated which tells
> > whether the node can be flipped or not. You are not supposed to flip a
> > non flippable internal node.
> > Regards
> > Shashank Mani Narayan
> > BIT Mesra
>  --
>  You received this message because you are subscribed to the Google Groups
>  "Algorithm Geeks" group.
>  To post to this group, send email to algoge...@googlegroups.com.
>  To unsubscribe from this group, send email to
>  algogeeks+unsubscr...@googlegroups.com   .com>
>  .
>  For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
> >>>   --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algoge...@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com >>>  .com>
> >>> .
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Interview Question

[suhash]

@Terence: I like your explanation. Very short and crisp! :)

On Dec 28, 12:10 pm, Terence  wrote:
> Let cst[i][j] store the cost to flip node i to given gate j (0-'AND',
> 1-'OR').
> Then: cst[i][j] = 0,        if j==gate[i];
>        cst[i][j] = 1,        if j!=gate[i] and ok[i];
>        cst[i][j] = INFINITY, if j!=gate[i] and !ok[i];
>
> 1. To get value 1:
> 1.1 flip current gate to AND, and change all children to 1
> 1.2 flip current gate to OR, and change any child to 1.
> 2. To get value 0:
> 1.1 flip current gate to AND, and change any child to 0
> 1.2 flip current gate to OR, and change all children to 0.
>
> So for internal node i:
>       dp[i][0] = min(cst[i][0]+sum{dp[x][1] for each child x of i},
>                    cst[i][1]+max{dp[x][1] for each child x of i});
>       dp[i][1] = min(cst[i][0]+max{dp[x][0] for each child x of i},
>                    cst[i][1]+sum{dp[x][0] for each child x of i});
>     for leaf i:
>       dp[i][j] = (value[i]==j ? 0 : INFINITY)
>
> On 2010-12-28 13:32, suhash wrote:
>
>
>
>
>
>
>
> > This problem can be solved using dp in O(n), where 'n' is the number
> > of nodes in the tree.
> > Definitions:
> > Let gate[i] be a boolean denoting whether the gate at node 'i' is
> > 'AND' or 'OR'. (0-'AND' 1-'OR')
> > Let dp[i][j] store the minimum no. of swaps required to get a value of
> > 'j' (0 or 1), for the subtree rooted at 'i'.
> > Let ok[i] be a boolean which denotes whether a flip operation can be
> > performed at the i'th node or not.
> > Let i1,i2,i3.ik be the children of node 'i'
>
> > Now we have 2 cases:
> > case 1: ok[i] = 0 (means no flipping possible at node 'i')
> >              In this, we have many cases:
> >              case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
> > and j=1
> >                             this means all children should have a value
> > 1.
> >                             hence dp[i][j]=dp[i1][j]+dp[i2][j]
> > +.dp[ik][j]
> >              case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
> > and j=0
> >                             i will discuss this case in the end.
> >              case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
> > j=1
> >                             this one too, for the end
> >              case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
> > j=0
> >                             this means all children should have a value
> > 0.
> >                             hence dp[i][j]=dp[i1][j]+dp[i2][j]
> > +.dp[ik][j]
>
> > case 2: ok[i] = 1 (means flipping is possible at node 'i')
> >              We have 2 cases in this:
> >              case 2.1: we choose not to flip gate at node 'i'. This
> > reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
> >              case 2.2: we choose to flip gate 'i'. Again it is similar
> > to cases discussed above, except replacing 'AND' by 'OR' and vice
> > versa
> >                             and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
> > +.dp[ik][j]
>
> > Note: 1)Boundary cases for leaf nodes.
> >           2)Top down is easier.
> >           3)If it is impossible to get a value 'j' for subtree rooted
> > at 'i', then dp[i][j]=INF(some large value)
> >           4)Answer is dp[root][required_value(o or 1)]. If this
> > quantity is INF, then it is impossible to achieve this.
>
> > Now, lets discuss case 1.2:
> > We have an 'AND' gate and we want a result of 0.
> > So, atleast one of the children of node 'i' should be 0.
> > Now create 2 arrays x,y each of size 'k'
> > x[1]=dp[i1][0], y[1]=dp[i1][1]
> > x[2]=dp[i2][0], y[2]=dp[i2][1]
> > .
> > .
> > .
> > x[k]=dp[ik][0], y[k]=dp[ik][1]
>
> > Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
> > minimum element(x[h] is minimum)
> > Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]
>
> > The other cases are similar to this!
> > I can write a code and send if you have doubts.
>
> > On Dec 28, 9:36 am, Anand  wrote:
> >> @Terence.
>
> >> Could please elaborate your answer. Bottom up level order traversal helps 
> >> to
> >> get the final root value but how to use it to find minimum flips needed to
> >> Obtain the desired root value.
>
> >> On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
> >>> Using the same level order traversal (bottom up), calculating the minimum
> >>> flips to turn each internal node to given value (0/1).
> >>> On 2010-12-24 17:19, bittu wrote:
>  Boolean tree problem:
>  Each leaf node has a boolean value associated with it, 1 or 0. In
>  addition, each interior node has either an "AND" or an "OR" gate
>  associated with it. The value of an "AND" gate node is given by the
>  logical AND of its two children's values. The value of an "OR" gate
>  likewise is given by the logical OR of its two children's values. The
>  value of all of the leaf nodes will be given as input so that the
>  value of all nodes can be calculated up the tree.
>  It's easy to find the actual value at the root using level order
>  traversal

[algogeeks] Re: Interview question amazon

[juver++]

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 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Google Interview Question

[Terence]

Let cst[i][j] store the cost to flip node i to given gate j (0-'AND', 
1-'OR').

Then: cst[i][j] = 0,if j==gate[i];
  cst[i][j] = 1,if j!=gate[i] and ok[i];
  cst[i][j] = INFINITY, if j!=gate[i] and !ok[i];

1. To get value 1:
1.1 flip current gate to AND, and change all children to 1
1.2 flip current gate to OR, and change any child to 1.
2. To get value 0:
1.1 flip current gate to AND, and change any child to 0
1.2 flip current gate to OR, and change all children to 0.

So for internal node i:
 dp[i][0] = min(cst[i][0]+sum{dp[x][1] for each child x of i},
  cst[i][1]+max{dp[x][1] for each child x of i});
 dp[i][1] = min(cst[i][0]+max{dp[x][0] for each child x of i},
  cst[i][1]+sum{dp[x][0] for each child x of i});
   for leaf i:
 dp[i][j] = (value[i]==j ? 0 : INFINITY)


On 2010-12-28 13:32, suhash wrote:

This problem can be solved using dp in O(n), where 'n' is the number
of nodes in the tree.
Definitions:
Let gate[i] be a boolean denoting whether the gate at node 'i' is
'AND' or 'OR'. (0-'AND' 1-'OR')
Let dp[i][j] store the minimum no. of swaps required to get a value of
'j' (0 or 1), for the subtree rooted at 'i'.
Let ok[i] be a boolean which denotes whether a flip operation can be
performed at the i'th node or not.
Let i1,i2,i3.ik be the children of node 'i'

Now we have 2 cases:
case 1: ok[i] = 0 (means no flipping possible at node 'i')
 In this, we have many cases:
 case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
and j=1
this means all children should have a value
1.
hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]
 case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
and j=0
i will discuss this case in the end.
 case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
j=1
this one too, for the end
 case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
j=0
this means all children should have a value
0.
hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]

case 2: ok[i] = 1 (means flipping is possible at node 'i')
 We have 2 cases in this:
 case 2.1: we choose not to flip gate at node 'i'. This
reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
 case 2.2: we choose to flip gate 'i'. Again it is similar
to cases discussed above, except replacing 'AND' by 'OR' and vice
versa
and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
+.dp[ik][j]

Note: 1)Boundary cases for leaf nodes.
  2)Top down is easier.
  3)If it is impossible to get a value 'j' for subtree rooted
at 'i', then dp[i][j]=INF(some large value)
  4)Answer is dp[root][required_value(o or 1)]. If this
quantity is INF, then it is impossible to achieve this.

Now, lets discuss case 1.2:
We have an 'AND' gate and we want a result of 0.
So, atleast one of the children of node 'i' should be 0.
Now create 2 arrays x,y each of size 'k'
x[1]=dp[i1][0], y[1]=dp[i1][1]
x[2]=dp[i2][0], y[2]=dp[i2][1]
.
.
.
x[k]=dp[ik][0], y[k]=dp[ik][1]

Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
minimum element(x[h] is minimum)
Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]

The other cases are similar to this!
I can write a code and send if you have doubts.

On Dec 28, 9:36 am, Anand  wrote:

@Terence.

Could please elaborate your answer. Bottom up level order traversal helps to
get the final root value but how to use it to find minimum flips needed to
Obtain the desired root value.

On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:

Using the same level order traversal (bottom up), calculating the minimum
flips to turn each internal node to given value (0/1).
On 2010-12-24 17:19, bittu wrote:

Boolean tree problem:
Each leaf node has a boolean value associated with it, 1 or 0. In
addition, each interior node has either an "AND" or an "OR" gate
associated with it. The value of an "AND" gate node is given by the
logical AND of its two children's values. The value of an "OR" gate
likewise is given by the logical OR of its two children's values. The
value of all of the leaf nodes will be given as input so that the
value of all nodes can be calculated up the tree.
It's easy to find the actual value at the root using level order
traversal and a stack(internal if used recursion).
Given V as the desired result i.e we want the value calculated at the
root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
to OR or OR to AND be required at internal nodes to achieve that?
Also for each internal node you have boolean associated which tells
whether the node can be flipped or not. You are not supposed to flip a
non flippable internal node.
Regards
Shashank Mani Narayan
BIT Mesra

--
You received this message because you are subscribed to the Google Gr

[algogeeks] Re: DIVIDE TWO VARYING LENGTH NUMBERS.

[shanushaan]

The better option will be to shift and divide.
As you can store the arbitrary large number in a link list or int
array. Left shift the right array and subtract, this will give you a
better approach, rathar than just subtracting each time. Add them in
the end ..

On Dec 27, 1:47 am, Aniket  wrote:
> DIVIDE TWO VARYING LENGTH NUMBERS
> EX: ONE CAN BE UPTO 60 DIGIT AND OTHER 40 DIGIT
>
> Well,I thought of an approach.Store each digit of  each number in two
> separate integer arrays(From right to left).Then apply the subtraction
> method.Will it be feasible?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Google Interview Question

[Terence]

@ pacific:
Also consider the choice of flipping the node itself.
And if an internal node cannot be flipped, it is still possible to flip 
its value, only the above choice is not taken into consideration..


On 2010-12-28 13:27, pacific pacific wrote:

here is my approach :

Starting from the root node ,
if root node need to have a 1 ...
if root is an and gate :
 flips  = minflips for left child to have value 1 + minflips for 
the right child to have value 1

else
 flips = minimum of ( minflips for left child to have value 1 , 
minflips for right child to have value 1)


For  a leaf node , return 0 if the leaf has the value needed else 
return INFINITY.Also if at any internal node if it is not possible 
return INFINITY.


On Tue, Dec 28, 2010 at 10:06 AM, Anand > wrote:


@Terence.

Could please elaborate your answer. Bottom up level order
traversal helps to get the final root value but how to use it to
find minimum flips needed to Obtain the desired root value.




On Fri, Dec 24, 2010 at 1:56 AM, Terence mailto:technic@gmail.com>> wrote:

Using the same level order traversal (bottom up), calculating
the minimum flips to turn each internal node to given value
(0/1).



On 2010-12-24 17:19, bittu wrote:


Boolean tree problem:

Each leaf node has a boolean value associated with it, 1
or 0. In
addition, each interior node has either an "AND" or an
"OR" gate
associated with it. The value of an "AND" gate node is
given by the
logical AND of its two children's values. The value of an
"OR" gate
likewise is given by the logical OR of its two children's
values. The
value of all of the leaf nodes will be given as input so
that the
value of all nodes can be calculated up the tree.
It's easy to find the actual value at the root using level
order
traversal and a stack(internal if used recursion).

Given V as the desired result i.e we want the value
calculated at the
root to be V(0 or 1) what is the minimum number of gates
flip i.e. AND
to OR or OR to AND be required at internal nodes to
achieve that?

Also for each internal node you have boolean associated
which tells
whether the node can be flipped or not. You are not
supposed to flip a
non flippable internal node.


Regards
Shashank Mani Narayan
BIT Mesra


-- 
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.


--
You received this message because you are subscribed to the Google Groups "Algorithm 
Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Find all the subset of an array whose sum is equal to some number

[shanushaan]

Thanks , I need to learn sml now :).
I was looking for the conversation over algo development and hints to
do that.

On Dec 25, 10:04 pm, Puneet Ginoria  wrote:
> This attachment contains the code for the above program in SML language and
> it uses lambda calculus.
>
>
>
>
>
>
>
> On Sat, Dec 25, 2010 at 9:18 PM, juver++  wrote:
> > What you need to get for the answer - amount of such subsets or display
> > them?
> > First problem can be solved using DP.
> > Second - brute force.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Find all the subset of an array whose sum is equal to some number

[shanushaan]

On what basis we will divide the array.
(Eg 1. Sort and divide them on positive negative )

On Dec 25, 10:52 pm, radha krishnan 
wrote:
> This s similar to the problemhttps://www.spoj.pl/problems/SUBSUMS/
> we have to split the array into 2 arrays
> say A,B
> generate all subsets of each array(both A and B) and another
> array(A1,B1) to store the sum of each subset
> now take each element of A1 and binarysearch B1 to achieve this sum
> assume k=2^(n/2)
> overall complexity is (2*(2^(n/2)) + 2*(k(lgk)) +k lgk)
> 2^(n/2) for each subset  so 2*(2^(n/2))
> k(lg k) -- sorting so 2*(k lg k)
> k(lgk)--binary search
>
> On Sat, Dec 25, 2010 at 10:38 PM, Puneet Ginoria
>
>
>
>
>
>
>
>  wrote:
> > sorry i forgot to attach here it is
>
> > On Sat, Dec 25, 2010 at 10:34 PM, Puneet Ginoria 
> > wrote:
>
> >> This attachment contains the code for the above program in SML language
> >> and it uses lambda calculus.
>
> >> On Sat, Dec 25, 2010 at 9:18 PM, juver++  wrote:
>
> >>> What you need to get for the answer - amount of such subsets or display
> >>> them?
> >>> First problem can be solved using DP.
> >>> Second - brute force.
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algoge...@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Google Interview Question

[Terence]

The description on internal nodes indicates this:

The value of an "AND" gate node is given by the logical AND of its TWO 
children's values.
The value of an "OR" gate likewise is given by the logical OR of its TWO 
children's values.


On 2010-12-28 13:35, suhash wrote:

Your approach is for a binary tree, but the problem statement does not
say anything about it.

On Dec 28, 10:27 am, pacific pacific  wrote:

here is my approach :

Starting from the root node ,
if root node need to have a 1 ...
if root is an and gate :
  flips  = minflips for left child to have value 1 + minflips for the
right child to have value 1
else
  flips = minimum of ( minflips for left child to have value 1 , minflips
for right child to have value 1)

For  a leaf node , return 0 if the leaf has the value needed else return
INFINITY.Also if at any internal node if it is not possible return INFINITY.

On Tue, Dec 28, 2010 at 10:06 AM, Anand  wrote:

@Terence.
Could please elaborate your answer. Bottom up level order traversal helps
to get the final root value but how to use it to find minimum flips needed
to Obtain the desired root value.
On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:

Using the same level order traversal (bottom up), calculating the minimum
flips to turn each internal node to given value (0/1).
On 2010-12-24 17:19, bittu wrote:

Boolean tree problem:
Each leaf node has a boolean value associated with it, 1 or 0. In
addition, each interior node has either an "AND" or an "OR" gate
associated with it. The value of an "AND" gate node is given by the
logical AND of its two children's values. The value of an "OR" gate
likewise is given by the logical OR of its two children's values. The
value of all of the leaf nodes will be given as input so that the
value of all nodes can be calculated up the tree.
It's easy to find the actual value at the root using level order
traversal and a stack(internal if used recursion).
Given V as the desired result i.e we want the value calculated at the
root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
to OR or OR to AND be required at internal nodes to achieve that?
Also for each internal node you have boolean associated which tells
whether the node can be flipped or not. You are not supposed to flip a
non flippable internal node.
Regards
Shashank Mani Narayan
BIT Mesra

--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

  --
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.


--
You received this message because you are subscribed to the Google Groups "Algorithm 
Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: arrays

[Bhoopendra Singh]

Is second array sorted?

On Tue, Dec 28, 2010 at 1:57 PM, juver++  wrote:

> Sort first array preserving the initial position of the elements.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Find all the subset of an array whose sum is equal to some number

[shanushaan]

Well All the subsets, not the number

On Dec 25, 8:48 pm, juver++  wrote:
> What you need to get for the answer - amount of such subsets or display
> them?
> First problem can be solved using DP.
> Second - brute force.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Interview question amazon

[master007]

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
>
>
>
>
>
>
>
> On Sun, Dec 26, 2010 at 10:38 PM, MAC  wrote:
> > you are given a bst where each node has a int value , parent pointer , and
> > left and right pointers , write a function to find a path with a given sum
> > value. Path can go from left subtree tree , include root and go to right
> > tree as well . we need to find these paths also .
>
> >                                         5
> >            1                                                 10
> > 0                 2                                  6             11
>
> > so to find 16 we say it is 1 to 5 to 10
>
> > --
> > thanks
> > --mac
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] 10 Most Frequent Search Text

[juver++]

We don't know how many elements in the stream. All decisions should be done 
at online.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: arrays

[juver++]

Sort first array preserving the initial position of the elements.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Interview Question

[suhash]

Btw...another observation in case 1.2:

I wrote:
Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
minimum element(x[h] is minimum)
Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]

Here, just setting dp[i][j]=v will do (athough the complexity is same
in both the cases)
because for all (f!=h), atleast one of x[f], y[f] will be 0. (by not
performing any swaps, and just evaluating the value at the node)

hence dp[i][j]=min(x[1],x[2],x[3],.x[k])

On Dec 28, 10:32 am, suhash  wrote:
> This problem can be solved using dp in O(n), where 'n' is the number
> of nodes in the tree.
> Definitions:
> Let gate[i] be a boolean denoting whether the gate at node 'i' is
> 'AND' or 'OR'. (0-'AND' 1-'OR')
> Let dp[i][j] store the minimum no. of swaps required to get a value of
> 'j' (0 or 1), for the subtree rooted at 'i'.
> Let ok[i] be a boolean which denotes whether a flip operation can be
> performed at the i'th node or not.
> Let i1,i2,i3.ik be the children of node 'i'
>
> Now we have 2 cases:
> case 1: ok[i] = 0 (means no flipping possible at node 'i')
>             In this, we have many cases:
>             case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
> and j=1
>                            this means all children should have a value
> 1.
>                            hence dp[i][j]=dp[i1][j]+dp[i2][j]
> +.dp[ik][j]
>             case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
> and j=0
>                            i will discuss this case in the end.
>             case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
> j=1
>                            this one too, for the end
>             case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
> j=0
>                            this means all children should have a value
> 0.
>                            hence dp[i][j]=dp[i1][j]+dp[i2][j]
> +.dp[ik][j]
>
> case 2: ok[i] = 1 (means flipping is possible at node 'i')
>             We have 2 cases in this:
>             case 2.1: we choose not to flip gate at node 'i'. This
> reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
>             case 2.2: we choose to flip gate 'i'. Again it is similar
> to cases discussed above, except replacing 'AND' by 'OR' and vice
> versa
>                            and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
> +.dp[ik][j]
>
> Note: 1)Boundary cases for leaf nodes.
>          2)Top down is easier.
>          3)If it is impossible to get a value 'j' for subtree rooted
> at 'i', then dp[i][j]=INF(some large value)
>          4)Answer is dp[root][required_value(o or 1)]. If this
> quantity is INF, then it is impossible to achieve this.
>
> Now, lets discuss case 1.2:
> We have an 'AND' gate and we want a result of 0.
> So, atleast one of the children of node 'i' should be 0.
> Now create 2 arrays x,y each of size 'k'
> x[1]=dp[i1][0], y[1]=dp[i1][1]
> x[2]=dp[i2][0], y[2]=dp[i2][1]
> .
> .
> .
> x[k]=dp[ik][0], y[k]=dp[ik][1]
>
> Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
> minimum element(x[h] is minimum)
> Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]
>
> The other cases are similar to this!
> I can write a code and send if you have doubts.
>
> On Dec 28, 9:36 am, Anand  wrote:
>
> > @Terence.
>
> > Could please elaborate your answer. Bottom up level order traversal helps to
> > get the final root value but how to use it to find minimum flips needed to
> > Obtain the desired root value.
>
> > On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
> > > Using the same level order traversal (bottom up), calculating the minimum
> > > flips to turn each internal node to given value (0/1).
>
> > > On 2010-12-24 17:19, bittu wrote:
>
> > >> Boolean tree problem:
>
> > >> Each leaf node has a boolean value associated with it, 1 or 0. In
> > >> addition, each interior node has either an "AND" or an "OR" gate
> > >> associated with it. The value of an "AND" gate node is given by the
> > >> logical AND of its two children's values. The value of an "OR" gate
> > >> likewise is given by the logical OR of its two children's values. The
> > >> value of all of the leaf nodes will be given as input so that the
> > >> value of all nodes can be calculated up the tree.
> > >> It's easy to find the actual value at the root using level order
> > >> traversal and a stack(internal if used recursion).
>
> > >> Given V as the desired result i.e we want the value calculated at the
> > >> root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
> > >> to OR or OR to AND be required at internal nodes to achieve that?
>
> > >> Also for each internal node you have boolean associated which tells
> > >> whether the node can be flipped or not. You are not supposed to flip a
> > >> non flippable internal node.
>
> > >> Regards
> > >> Shashank Mani Narayan
> > >> BIT Mesra
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email