date:20130312

Re: [algogeeks] java

2013-03-12 Thread manish untwal

according to my understanding the super class object have limited function
like for example
Class - animal : methods/behavior : roam() and eat()
and a sub class hippo : method/behavior : roam(),eat() and swim()
so a hippo is a animal then according to the polymorphic property of java
a reference of animal can refer to object of class hippo and animal but
still the reference can call only the behavior of class animal i.e : animal
A = new hippo() is legal but you can't call A.swim() because it refer to
the animal property of class hippo ie roam and eat...not swim. and also u
can't do this as hippo H = new animal() as this means animal should have
all the property of hippo because it is referred by a hippo reference do
H.swim() should not be a NULL.reply if you get it or not.
P.S :  I tried to explain it through an example

On Tue, Mar 12, 2013 at 8:51 PM, sulekha metta wrote:

> what ever data members,member functions present in super class are
> applicable to subclass...subclass may contain more additional
> featuresso its obvious that size of subclass object is more than
> superclass object...now lets take an analogy of float(4 bytes) and double(
> 8 bytes) float can be implicitly converted into double( as float size is
> less when compared to double) but not vice versathen why is this not
> applicable to superclass object and subclass object(as size of superclass
> object is less when compared to subclass)? please tell if am wrong!
>
>
> On Tue, Mar 12, 2013 at 7:37 PM, subramony mahadevan 
> wrote:
>
>> i think its just a logical reason  take animal as superclass bird as
>> subclass ... since we are talking about inheritance it is " is a
>> relationship " ie bird is a animal not vice versa hence we cannot
>> implicitly convert to subclass
>>
>>
>> On Sat, Mar 2, 2013 at 6:18 PM, sulekha metta wrote:
>>
>>> Q) why super class object can't be  implicitly converted to subclass? is
>>> there any specific reason?
>>> Thanks in advance!
>>>
>>> --
>>> sulekha metta
>>> B.E computer science
>>> osmania university
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> sulekha metta
> B.E computer science
> osmania university
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
With regards,
Manish kumar untwal
Indian Institute of Information Technology
Allahabad (2009-2013 batch)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Query on a tree again!

2013-03-12 Thread Nguyễn Thành Danh

Hi Shashank,
It could be. But if the tree has only 2 branches, and A, B lie as two leaf
nodes on each branch, there won't be any more leaf position for C. Thus, C
has to lie on the path between A and B. Could you give me some hint to find
C in O(lgN) though?

On Mon, Mar 4, 2013 at 3:19 PM, BackBencher wrote:

> Hi Danh , shouldn't  be C will farthest leaf node from given A  and B ?
>
> Thanks
> Shashank
>
> On Sunday, January 13, 2013 7:43:23 AM UTC+5:30, Danh Nguyen wrote:
>>
>> Hi everyone,
>>
>> I'm trying to solve this problem, but I have no idea to 
>> begin.
>> I really need some hints for it:
>>
>>-
>>
>>Given a tree of N nodes, and Q queries. (1 <= N, Q <= 100,000)
>>-
>>
>>Each query has 2 arbitrary nodes on that tree (let's call them A and
>>B).
>>-
>>
>>We define that the distance from another node (let's say C) to A and
>>B is the minimum of {the distance from C to A, the distance from C to B}.
>>-
>>
>>To answer each query, find C so that the distance from C to A and B
>>are as large as possible.
>>
>> I don't think it's possible to do do each query in O(N). It should be
>> O(lgN).
>>
>> Please help me! Thanks a lot in advance!
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Questions

2013-03-12 Thread rohit jangid

these questions were asked for software dev. in amazon ? which round .
looks like straight easy questions...


On Sun, Mar 10, 2013 at 5:58 PM, Nishant Pandey <
nishant.bits.me...@gmail.com> wrote:

> Ans to *Boundary traversal of a tree. Write the code.
>
> *1) you need to for preoder oder for left most tree with flag and post
> order traversal for right most tree with flag.
> 2) the role of flag would be to decide wther to print or not like in case
> of left subtree ,flag would be tree as u knw that
> in preorder traversal left element would be boundary and once u go
> right make it false .. same for right subtree:
>
> Code snippet would look like this :
>
> void printleft (struct node *root, bool flag) {
>   if (!root) return;
>   if (flag || (!root->left && !root->right)) {
> cout<< root->data;
>   }
>   printleft(root->left, true);
>   printleft(root->right, false);
> }
>
> this is preorder for left subtree , do post order for right subtree like :
>
> void printright (struct node *root, bool flag) {
>   if (!root) return;
>   printright(root->left, false);
>   printright(root->right, true);
>   if (flag || (!root->left && !root->right)) cout<< root->data;
>
> }
> *
> *let me knw if anything seems confusing.
>
> On Sun, Mar 10, 2013 at 4:59 PM, Nishant Pandey <
> nishant.bits.me...@gmail.com> wrote:
>
>> i have few questions regarding ur problems pratik :
>>
>> 1) A tree with only parent pointer, how to find LCA?
>> Doubt : do u mean only root of the tree is given , i am assuming root
>> along with two nodes address whose lca need to
>>  find too is given , i am right ?
>>
>> 2) Find top k searched elements from a continuous stream of data.
>> Doubt : what do u mean by top k search element can u please explain
>> little bit with exmple.
>>
>>
>> I would love to post solution for you provided clear my doubts 
>> may i knw which Amazon's round questions are they ?
>>
>>
>> On Mon, Feb 18, 2013 at 1:28 AM, Tushar  wrote:
>>
>>> It looks as if you have just pasted some Amazon interview questions on
>>> this forum.
>>> These are pretty common questions.
>>> Try to come up with your own answers.
>>> Do some research on google and previous posts on this forum. You'll get
>>> answers to all of them.
>>>
>>> If you have some idea and want to discuss that, then post different
>>> posts for each questions as arun recommended along with your understanding
>>> of the question and your approach.
>>>
>>> All the best
>>>
>>>
>>> On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:

 Hi All,
 I need ur help in solving few questions.

 Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
 BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*


 *
 *

  *a. Kadane’s Algo.*

  *
 *

 *b. Linked-list intersection point.*

 *
 [A tree with only parent pointer, how to find LCA?]
 *

 *

 *

 *
 c. Design a stack which can perform findMax in O(1).
 *

 *

 *

 *d. Set of stocks for each day have been given. Need to find the days
 on which I buy and sell share to earn max profit, alongwith finding the max
 profit.*


 *
 e. Find top k searched elements from a continuous stream of data.
 *

 *

 *

 *f. Given a linked-list and 2 integers k & m. Reverse the linked-list
 till k elements and then traverse till m elements and repeat.*

 *Write production quality code.*

 *
 *

 *g. An array of elements have been given. Find for each element, first
 max element to its right.*

 *
 *

 *h. Boundary traversal of a tree. Write the code.*


 Please help me out...

 Thanks in advance...

 Thanks & Regards,
 Pratik Mayur Mehta.

>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] java

2013-03-12 Thread sulekha metta

what ever data members,member functions present in super class are
applicable to subclass...subclass may contain more additional
featuresso its obvious that size of subclass object is more than
superclass object...now lets take an analogy of float(4 bytes) and double(
8 bytes) float can be implicitly converted into double( as float size is
less when compared to double) but not vice versathen why is this not
applicable to superclass object and subclass object(as size of superclass
object is less when compared to subclass)? please tell if am wrong!


On Tue, Mar 12, 2013 at 7:37 PM, subramony mahadevan wrote:

> i think its just a logical reason  take animal as superclass bird as
> subclass ... since we are talking about inheritance it is " is a
> relationship " ie bird is a animal not vice versa hence we cannot
> implicitly convert to subclass
>
>
> On Sat, Mar 2, 2013 at 6:18 PM, sulekha metta wrote:
>
>> Q) why super class object can't be  implicitly converted to subclass? is
>> there any specific reason?
>> Thanks in advance!
>>
>> --
>> sulekha metta
>> B.E computer science
>> osmania university
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
sulekha metta
B.E computer science
osmania university

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] java

2013-03-12 Thread manish untwal

didn't understand your question please specify the question with an example.

On Sat, Mar 2, 2013 at 6:18 PM, sulekha metta wrote:

> Q) why super class object can't be  implicitly converted to subclass? is
> there any specific reason?
> Thanks in advance!
>
> --
> sulekha metta
> B.E computer science
> osmania university
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
With regards,
Manish kumar untwal
Indian Institute of Information Technology
Allahabad (2009-2013 batch)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] java

2013-03-12 Thread subramony mahadevan

i think its just a logical reason  take animal as superclass bird as
subclass ... since we are talking about inheritance it is " is a
relationship " ie bird is a animal not vice versa hence we cannot
implicitly convert to subclass


On Sat, Mar 2, 2013 at 6:18 PM, sulekha metta wrote:

> Q) why super class object can't be  implicitly converted to subclass? is
> there any specific reason?
> Thanks in advance!
>
> --
> sulekha metta
> B.E computer science
> osmania university
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Cyclic sorting problem

2013-03-12 Thread sourabh jain

Hi all ,

if an array is given in random order , you have to output the minimum
number of swaps required to convert into cyclic sorted array.

e.g. array given is 3 5 4 2 1

so the first swap will be 5<-->4   result : 3 4 5 2 1
second swap will be  2<-->1  result : 3 4 5 1 2 (final)

output : 2





-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] ORDER OF A PERMUTATION

2013-03-12 Thread Danh Nguyen



We all know that the order of a permutation is the Least Common Multiples 
of its disjoint cycles' lengths. Also, we know that an involution is a 
permutation whose order is at most 2. The number of involutions of length n 
can be obtained from this recurrence relation: F[n] = F[n - 1] + (n - 1) * 
F[n - 2]

I'm just wondering whether we have any formula to count the number of 
permutations of length n whose orders are at most k (k >= 2)?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Questions

2013-03-12 Thread Nishant Pandey

i have few questions regarding ur problems pratik :

1) A tree with only parent pointer, how to find LCA?
Doubt : do u mean only root of the tree is given , i am assuming root along
with two nodes address whose lca need to
 find too is given , i am right ?

2) Find top k searched elements from a continuous stream of data.
Doubt : what do u mean by top k search element can u please explain
little bit with exmple.


I would love to post solution for you provided clear my doubts 
may i knw which Amazon's round questions are they ?

On Mon, Feb 18, 2013 at 1:28 AM, Tushar  wrote:

> It looks as if you have just pasted some Amazon interview questions on
> this forum.
> These are pretty common questions.
> Try to come up with your own answers.
> Do some research on google and previous posts on this forum. You'll get
> answers to all of them.
>
> If you have some idea and want to discuss that, then post different posts
> for each questions as arun recommended along with your understanding of the
> question and your approach.
>
> All the best
>
>
> On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:
>>
>> Hi All,
>> I need ur help in solving few questions.
>>
>> Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
>> BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*
>>
>>
>> *
>> *
>>
>> *a. Kadane’s Algo.*
>>
>> *
>> *
>>
>> *b. Linked-list intersection point.*
>>
>> *
>> [A tree with only parent pointer, how to find LCA?]
>> *
>>
>> *
>>
>> *
>>
>> *
>> c. Design a stack which can perform findMax in O(1).
>> *
>>
>> *
>>
>> *
>>
>> *d. Set of stocks for each day have been given. Need to find the days on
>> which I buy and sell share to earn max profit, alongwith finding the max
>> profit.*
>>
>>
>> *
>> e. Find top k searched elements from a continuous stream of data.
>> *
>>
>> *
>>
>> *
>>
>> *f. Given a linked-list and 2 integers k & m. Reverse the linked-list
>> till k elements and then traverse till m elements and repeat.*
>>
>> *Write production quality code.*
>>
>> *
>> *
>>
>> *g. An array of elements have been given. Find for each element, first
>> max element to its right.*
>>
>> *
>> *
>>
>> *h. Boundary traversal of a tree. Write the code.*
>>
>>
>> Please help me out...
>>
>> Thanks in advance...
>>
>> Thanks & Regards,
>> Pratik Mayur Mehta.
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] find out all pairs of numbers a,b such that a^2+b^2 = N

2013-03-12 Thread Nishant Pandey

some thing like would work.


int find(int x ) {
int p = sqrt(x/2);
int total=0;
float y;
for( int i=0;i<=p;i++) {
  y=sqrt(x*x-i*i);
  if( y(int) == y) total++;
}
return total;

}



find(
}

On Thu, Feb 14, 2013 at 10:22 AM, Shachindra A C wrote:

> Guneesh,
>
> Thanks for the reply.
> I interpret ur answer as follows:
>
> If N = say, 50
>
> the two combinations are (1,7) and (5,5).
>
> Acc to you, first find sqrt(50) = 7
>
> fill in 1,4,9,16,25,36,49 in an array.
>
> Then have min = 0, max = 6 and get all combinations in one pass over the
> array, right?
>
> So, the complexity would be O(n^0.5), right?
>
> Can you think of any solution making use of complex domain? Just curious
> to know...
>
> On Wed, Feb 13, 2013 at 10:28 PM, Guneesh Paul Singh 
> wrote:
>
>> Replace all elements of array by its square.and sort it
>> Now question is to find two  nos in the array such that their sum is N.
>> For this take two pointers min and max
>> Initialize min to 0 and max to n-1(n-size of array)
>> 1.find the sum a[min]+a[max]
>> 2.if sum>N max=max-1
>> if sum> if sum==N we have a sol
>>
>> Now in case of nonunique values all possible pairs must be displayed
>> eg for 2 2 3 3 N =5
>> min=0,max 3 is a sol but u need to display all combination of 2 and 3 for
>> that i used tempmin=position till which we have a value a[min] and temp max
>> postion till which we have a value a[max] and display
>> all possible combinations.
>>
>> P.S. This was asked to me in Amazon
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> Regards,
> Shachindra A C
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: FInd unique element.

2013-03-12 Thread Nishant Pandey

i think what aditya suggested is cool but in that instead of going for
largest element we need to search smallest value and its index would he
number we are looking for.

On Sun, Feb 24, 2013 at 7:45 PM, Dave  wrote:

> @Marti: If you know m and k, and if m is even and k is odd, then xoring
> the elements of the array will give the integer that occurs k times. But
> this is not a general algorithm for arbitrary m and k.
>
> Dave
>
> On Sunday, February 24, 2013 1:24:23 AM UTC-6, marti wrote:
>
>> A hint is to use XOR for linear time..but how?
>>
>> On Friday, February 22, 2013 12:58:07 AM UTC+5:30, marti wrote:
>>>
>>> How do I Find the Unique Element that Appears exactly k Times in an
>>> Array?
>>>  the problem is given an integer array, only one integer appears* k* times,
>>> all the other integers appears *m* times in the array (*k*<*m*). Find
>>> out that integer.
>>>
>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Print tree node which sum

2013-03-12 Thread vamshi palakurti

Conver your BST  to a doubly linked list by doing an inorder traversal. Now
do the normal find sum procedure

Sorry but i have no idea about normal tree case.


On Tue, Mar 5, 2013 at 9:08 PM, Dave  wrote:

> @Marti: I'm not quite sure if you mean that there are two problems, one
> with a BST and the other with an ordinary tree, or if you mean that one of
> the summands comes from a BST and the other comes from an ordinary tree.
>
> If both values come from a BST, do two simultaneous inorder traversals,
> one forwards (from left to right), and the other backwards (from right to
> left). If the sum of the two current elements is less than the value,
> advance the forward traversal, while if the sum is greater than the value,
> advance the backward traversal. Quit when equality is reached or when the
> two traversals reach the same element. O(n) time and O(log n) space if the
> BST is reasonably balanced, although the space can be as large as O(n) if
> the BST is severly unbalanced (as in case it has degenerated into a linked
> list).
>
> In order to do two simultaneous traversals, use two stacks to keep track
> of the state, as recursion won't allow you to do them.
>
> Dave
>
> On Tuesday, March 5, 2013 1:54:30 AM UTC-6, marti wrote:
>
>> Given a value , print two nodes that sum to the value in a BST and normal
>> tree.. time:O(n), space O(logn).
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Questions

2013-03-12 Thread Nishant Pandey

Ans to *Boundary traversal of a tree. Write the code.

*1) you need to for preoder oder for left most tree with flag and post
order traversal for right most tree with flag.
2) the role of flag would be to decide wther to print or not like in case
of left subtree ,flag would be tree as u knw that
in preorder traversal left element would be boundary and once u go
right make it false .. same for right subtree:

Code snippet would look like this :

void printleft (struct node *root, bool flag) {
  if (!root) return;
  if (flag || (!root->left && !root->right)) {
cout<< root->data;
  }
  printleft(root->left, true);
  printleft(root->right, false);
}

this is preorder for left subtree , do post order for right subtree like :

void printright (struct node *root, bool flag) {
  if (!root) return;
  printright(root->left, false);
  printright(root->right, true);
  if (flag || (!root->left && !root->right)) cout<< root->data;

}
*
*let me knw if anything seems confusing.
On Sun, Mar 10, 2013 at 4:59 PM, Nishant Pandey <
nishant.bits.me...@gmail.com> wrote:

> i have few questions regarding ur problems pratik :
>
> 1) A tree with only parent pointer, how to find LCA?
> Doubt : do u mean only root of the tree is given , i am assuming root
> along with two nodes address whose lca need to
>  find too is given , i am right ?
>
> 2) Find top k searched elements from a continuous stream of data.
> Doubt : what do u mean by top k search element can u please explain
> little bit with exmple.
>
>
> I would love to post solution for you provided clear my doubts 
> may i knw which Amazon's round questions are they ?
>
>
> On Mon, Feb 18, 2013 at 1:28 AM, Tushar  wrote:
>
>> It looks as if you have just pasted some Amazon interview questions on
>> this forum.
>> These are pretty common questions.
>> Try to come up with your own answers.
>> Do some research on google and previous posts on this forum. You'll get
>> answers to all of them.
>>
>> If you have some idea and want to discuss that, then post different posts
>> for each questions as arun recommended along with your understanding of the
>> question and your approach.
>>
>> All the best
>>
>>
>> On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:
>>>
>>> Hi All,
>>> I need ur help in solving few questions.
>>>
>>> Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
>>> BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*
>>>
>>>
>>> *
>>> *
>>>
>>>  *a. Kadane’s Algo.*
>>>
>>>  *
>>> *
>>>
>>> *b. Linked-list intersection point.*
>>>
>>> *
>>> [A tree with only parent pointer, how to find LCA?]
>>> *
>>>
>>> *
>>>
>>> *
>>>
>>> *
>>> c. Design a stack which can perform findMax in O(1).
>>> *
>>>
>>> *
>>>
>>> *
>>>
>>> *d. Set of stocks for each day have been given. Need to find the days
>>> on which I buy and sell share to earn max profit, alongwith finding the max
>>> profit.*
>>>
>>>
>>> *
>>> e. Find top k searched elements from a continuous stream of data.
>>> *
>>>
>>> *
>>>
>>> *
>>>
>>> *f. Given a linked-list and 2 integers k & m. Reverse the linked-list
>>> till k elements and then traverse till m elements and repeat.*
>>>
>>> *Write production quality code.*
>>>
>>> *
>>> *
>>>
>>> *g. An array of elements have been given. Find for each element, first
>>> max element to its right.*
>>>
>>> *
>>> *
>>>
>>> *h. Boundary traversal of a tree. Write the code.*
>>>
>>>
>>> Please help me out...
>>>
>>> Thanks in advance...
>>>
>>> Thanks & Regards,
>>> Pratik Mayur Mehta.
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] help with o/p why 0 comes???

2013-03-12 Thread vivekanandan r

The output of the below code is also zero ,
key reason is floating point number are stored as *mantissa, exponent. *

float dec=1.00;
printf("\n dec=%d , float =%f",dec,dec);



On Fri, Mar 1, 2013 at 12:05 PM, Karthikeyan V.B wrote:

> O/p will not be 0.
>
> 1.00 is the result which when read as %d takes the decimal value of
>  stored in memory - it will not be 1.00 or 0.
>
> Since float is not stored as direct binary in memory as integer is stored,
> instead there's a separate procedure for storing float as binary in memory
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Print tree node which sum

2013-03-12 Thread sourabh jain

take two stacks of O(logn) space use one to traverse as left - > root->
right (inorder) and other as right->root-> left(reverse inorder) like

while (true){

 a=top(s1);
b=top(s2);
if(a+b==sum ) break;
if(a+b  sum) pop(s2);
}

if(s1 && s2 are empty) no solution
else result = top(s1) and top(s2);

On Tue, Mar 5, 2013 at 1:24 PM, marti  wrote:

> Given a value , print two nodes that sum to the value in a BST and normal
> tree.. time:O(n), space O(logn).
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] java

2013-03-12 Thread sulekha metta

Q) why super class object can't be  implicitly converted to subclass? is
there any specific reason?
Thanks in advance!

-- 
sulekha metta
B.E computer science
osmania university

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: A problem in tree

2013-03-12 Thread Krishnan

Example: when we have nodes 1,2,3. The Minimum weight is given by, 2->root
1->left 3->right (Min. Weight - 10) or 3->root 2->left 1->left(left of 2)
(Min. Weight -10).


On Sun, Mar 3, 2013 at 5:46 PM, Krishnan  wrote:

> Given a set of numbers, we have to construct a tree such that their WEIGHT
> is MINIMUM. WEIGHT(node value * height of the node).
>
> (Root is at the height 1).
>
> we need to print the minimum weight.
>
> How to approach this problem ?
>
> Pls somebody help
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] MS Question:WAP to print last n lines of a log file

2013-03-12 Thread Sairam Ravu

lines = 0;
string last_n_lines[n];

//read each line into a circular buffer
while(getline(file,last_n_lines[lines%n]))
{
  lines++;
}

// if number of lines < n
// then print all of them
if(lines<=n)
{
  start = 0;
  count = lines;
}
else
{
   start = lines%n;
   count = lines;
}

//Now print all of them.

for(i=0;ihttps://groups.google.com/groups/opt_out.

Re: [algogeeks] MS Question:WAP to print last n lines of a log file

2013-03-12 Thread sourabh jain

Read line by line . use doublylinkedlist(Queue)/ Circular Buffer of size N.
when EOF is achieved print the lines.


On Mon, Mar 4, 2013 at 9:10 AM, Ashish Goel  wrote:

> Q1. Given a log file, pirnt last n lines. Note that the Log file is being
> written into.
> Q2. Implement Circular Buffer.
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Algo Question

2013-03-12 Thread Nandkishore

I think DP soln would be :

int leastPay(int[] demands, int sum, int index) {
  if(index == demands.length)
return sum;
  else {
  if(sum < demands[index])
return leastPay(demands, sum+demands[index], index+1);
  else
  return Math.min(leastPay(demands, sum, index+1),
leastPay(demands, sum+demands[index], index+1));
}
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: DP equation for interval problem

2013-03-12 Thread Sairam

In the SPOJ , for the given test case, output should be 4 right?

The problem is to find the maximum number of overlapping intervals right? 
If you look at the example it should be 4 rigth?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Query on a tree again!

2013-03-12 Thread BackBencher

Hi Danh , shouldn't  be C will farthest leaf node from given A  and B ?

Thanks
Shashank

On Sunday, January 13, 2013 7:43:23 AM UTC+5:30, Danh Nguyen wrote:
>
> Hi everyone,
>
> I'm trying to solve this problem, but I have no idea to 
> begin. 
> I really need some hints for it:
>
>- 
>
>Given a tree of N nodes, and Q queries. (1 <= N, Q <= 100,000)
>- 
>
>Each query has 2 arbitrary nodes on that tree (let's call them A and 
>B).
>- 
>
>We define that the distance from another node (let's say C) to A and B 
>is the minimum of {the distance from C to A, the distance from C to B}.
>- 
>
>To answer each query, find C so that the distance from C to A and B 
>are as large as possible.
>
> I don't think it's possible to do do each query in O(N). It should be 
> O(lgN).
>
> Please help me! Thanks a lot in advance!
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Algo Question

2013-03-12 Thread BackBencher

@immars , can you explain with some example or algorithm ?

Thanks
Shashank

On Tuesday, February 5, 2013 9:14:03 AM UTC+5:30, immars wrote:
>
> suppose:
>
> v : array of guards' request
>
> P(n): our problem: least coin spent until guard n, according to these rules
>
> M(n, x): least coin possibly combined equal to or larger than x until 
> guard n
>
> then:
>
> P(n) = min(P(n-1)+v[n], M(n-1, v[n]))
> M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n])
>
> On Monday, February 4, 2013 8:24:19 PM UTC+8, marti wrote:
>>
>> You have N guards in a line each with a demand of coins.You can skip 
>> paying a guard only if his demand is lesser than what you have totally paid 
>> before reaching him.Find the least number of coins you spend to cross all 
>> guards.
>> I think its a DP problem but cant come up with a formula.Another approach 
>> would be to binary search on the answer but how do I verify if no. of coins 
>> is a possible answer?
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] help with o/p why 0 comes???

2013-03-12 Thread Pratts

Hi Shubham,
This may be because your final data type you have chosen for your output
is float, n the one which you are trying to print is of int data type (i.e. %d).

Suggestion : Try changing %d to %f and see whether it works for you or not?


Thanks & Regards,

Pratts

On 01-Mar-2013, at 1:11, Shubham Sandeep  wrote:

> code snippet:
> int main()
> {
> printf ("%d\n",(float)((int)(3.5/2)));
> return 0;
> }
> 
> -- 
> Regards,
> SHUBHAM SANDEEP
> IT 3rd yr.
> NIT ALD.
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>  
>  

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] 3d layout problem

2013-03-12 Thread ddyer-google2


My wife plays a 3d "shanghi" variant which has an annoying feature,
that sometimes the game becomes blocked and has to "reshuffle" which
is a totally computerish solution to keep the game going.

It works like this; the game pieces are little cubes which are arranged
in a bigger cube (or other 3d shape) which can be viewed from any angle.
Each cube has the same symbol on each of it's faces, and there are 4 of 
each type of cube.

The game is a speed/dexterity/memory exercise where you identify pairs
of cubes, which disappear and reveal the cubes underneath.  The goal 
on each level is to "eat" the entire formation.  But sometimes there
are no pairs anywhere on the surface of the formation, so the game
is blocked.

So the challenge is to design the cube layout algorithm so that
blockage is impossible, or lacking that less likely.

Here are two trivial but unsatisfactory solutions.
(1) always place all four instances of a symbol together.  This might not
be quite enough to guarantee no blocks, but it would guarantee a completely
boring game.
(2) when removing a pair results in a blocked position, secretly 
reorder the cubes that are about to be revealed so there is no blockage.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Max-Overlapping Intervals

2013-03-12 Thread Sairam


>
> First sort the intervals
>
So, in our example it will be as follows
(2,7),(5,10),(6,15).

make a map which has got interval with corresponding number of overlaps
Now, iterate through each of the interval
 for(i=0;i<(n-1);i++)
  for(j=0;jhttps://groups.google.com/groups/opt_out.

[algogeeks] Help regarding Amazon Online Test ( OffCampus )

2013-03-12 Thread Raghav Garg

Hello All,
I need to know about amazon online test, has anyone given that?
How many and what type of questions they ask? Time period anything?

Thanking you

*Cheers
Raghav Garg
--
+91-9013201944*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Horrible Queries on spoj

2013-03-12 Thread dheeraj hasija

you can have this code for better understanding

#include

long long   v[50];
long long   a[50];


inline long long getvalue( int index, int low, int high)
{
   return a[index] + (high-low+1)*v[index];
}

long long update( long long index, long long down, long long up, long long
low, long long high,long long value)
{
long long mid = (low+high)/2;



if(  down <= low && high <= up)
{v[index] += value;

return 0;
}

if(low> up || high < down)
return 0;

v[2*index] += v[index];
v[2*index+1] += v[index];
v[index]  = 0;

update( 2*index, down,up, low,mid,value);
update(2*index+1 , down,up, mid+1, high,value);



a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
mid+1,high);
return 0;


}



long long query( long long index, long long down, long long up, long long
low, long long high)
{

//printf("%lld %lld  %lld  %lld",low,high,up,down);

long long mid;
mid = (low+high)/2;




if(  down <= low && high<=up)
return a[index]  + v[index]*( high-low+1);

if(  low > up || high < down)
return 0;


v[2*index] += v[index];
v[2*index+1] += v[index];




a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
mid+1,high);



v[index] =0;

return query( 2*index,down,up, low, mid)+query(2*index+1, down,up,
mid+1, high);




}




int main()
{
long long t,n,p,quer,vr,val,i,q;


scanf("%lld",&t);

while(t--)
{
  scanf("%lld%lld",&n,&quer);

  for(i=0;i<=4*n;i++)
a[i] =0,v[i] =0;


  while(quer--)
  {
   // for(i=1;i<8;i++)
//printf("%lld   ",a[i]);
//printf("\n");

scanf("%lld%lld%lld",&vr,&p,&q);
if(!vr)
{scanf("%lld",&val);
update(  1,p,q,1,n,val);
}
else
printf("%lld\n",query( 1, p, q, 1, n));
  }

  //printf("bye");
   }

return 0;
}



On Tue, Feb 26, 2013 at 12:24 PM, emmy  wrote:

> Problem statement 
>
> Here  is my code. I am using segment trees +
> Lazy propagation. Please help me figure out my mistake.
> I am getting a WA
>
> Note:
> invariant : l <= p <=q <= r
>
> l and r are the limits of that node
> p and q is the query range.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
*Dheeraj Hasija*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: A problem in tree

2013-03-12 Thread Krishnan

We need to construct BST not binary tree.



On Sun, Mar 3, 2013 at 6:19 PM, Krishnan  wrote:

> Example: when we have nodes 1,2,3. The Minimum weight is given by, 2->root
> 1->left 3->right (Min. Weight - 10) or 3->root 2->left 1->left(left of 2)
> (Min. Weight -10).
>
>
> On Sun, Mar 3, 2013 at 5:46 PM, Krishnan wrote:
>
>> Given a set of numbers, we have to construct a tree such that their
>> WEIGHT is MINIMUM. WEIGHT(node value * height of the node).
>>
>> (Root is at the height 1).
>>
>> we need to print the minimum weight.
>>
>> How to approach this problem ?
>>
>> Pls somebody help
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] A problem in tree

2013-03-12 Thread Krishnan

Given a set of numbers, we have to construct a tree such that their WEIGHT
is MINIMUM. WEIGHT(node value * height of the node).

(Root is at the height 1).

we need to print the minimum weight.

How to approach this problem ?

Pls somebody help

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Question

2013-03-12 Thread Sairam


No, it is only O(n), but space will be order of O(maximum element in the 
range)

Because only one loop to go through all the intervals and get the maximum.

Then allocate space for that much, after that again go through intervals 
and increment the corresponding value.

Then after that finding maximum can be done in again O(n).

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] java

Re: [algogeeks] Re: Query on a tree again!

Re: [algogeeks] Re: Amazon Interview Questions

Re: [algogeeks] java

Re: [algogeeks] java

Re: [algogeeks] java

[algogeeks] Cyclic sorting problem

[algogeeks] ORDER OF A PERMUTATION

Re: [algogeeks] Re: Amazon Interview Questions

Re: [algogeeks] find out all pairs of numbers a,b such that a^2+b^2 = N

Re: [algogeeks] Re: FInd unique element.

Re: [algogeeks] Re: Print tree node which sum

Re: [algogeeks] Re: Amazon Interview Questions

Re: [algogeeks] help with o/p why 0 comes???

Re: [algogeeks] Print tree node which sum

[algogeeks] java

[algogeeks] Re: A problem in tree

Re: [algogeeks] MS Question:WAP to print last n lines of a log file

Re: [algogeeks] MS Question:WAP to print last n lines of a log file

Re: [algogeeks] Re: Algo Question

[algogeeks] Re: DP equation for interval problem

[algogeeks] Re: Query on a tree again!

[algogeeks] Re: Algo Question

Re: [algogeeks] help with o/p why 0 comes???

[algogeeks] 3d layout problem

[algogeeks] Re: Max-Overlapping Intervals

[algogeeks] Help regarding Amazon Online Test ( OffCampus )

Re: [algogeeks] Horrible Queries on spoj

[algogeeks] Re: A problem in tree

[algogeeks] A problem in tree

Re: [algogeeks] Question

31 matches

Site Navigation

Mail list logo

Footer information