Re: [algogeeks] Divide the array into groups
@snehal jain
As many group as possible?
All the inputed n numbers can be divided into n groups...
On Sun, Jan 30, 2011 at 2:13 PM, snehal jain learner@gmail.com wrote:
@nishanth
divide into groups ( not necessarily 2) in as many group as possible.. such
that elements in each group is consecutive
another example to clearify
A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15)
ans
9,7,13,11,6,12,8,10
3,4,2
16,14,17,13,15
On Sun, Jan 30, 2011 at 11:32 AM, nishaanth nishaant...@gmail.com wrote:
@snehal..i guess you are missing something in the question...divide it
into 2 groups such that (there should be some other condition or
criterion).
On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.comwrote:
my approach
sort in nlogn and then while traversing the array put the elements in a
group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in
different group.. now we need to rearrange elements in the group so that
they are according to the given array.. but that will make it O(n^2) ..
anyone with better ideas?
On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote:
Divide a list of numbers into groups of consecutive numbers but their
original order should be preserved.
Example:
8,2,4,7,1,0,3,6
Two groups:
2,4,1,0,3 8,7,6
Better than O(n^2) is expected.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Southeast University
Nicholas.Zhaoyu
--
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.
Re: [algogeeks] Divide the array into groups
@ ^ Why do you try hard not to understand the question or what one meant by the question and instead try hard to find out flaws. I mean ain't that obvious that you need to divide into minimum number of groups? -- Rohit Saraf Third Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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.
[algogeeks] design a data structure
Design a data structure that supports the following two operations on a set S of integers: a. Insert(x; S), which inserts element x into set S, and b. DeleteLargerHalf(S), which deletes the largest ceil(|S|/2) elements from S. Show how to implement this data structure so both operations take O(1) amortized time. -- 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.
Re: [algogeeks] Re: Amazon Again
@Wei.Qi the algorithm is right, but the running time is ...? define Pi the amount of petrol each pumps has. Di is the distance between Ith and i+1th pumps. then we can double the circle, we can get to sequence p1, p2, p3, p4...pn, p1, p2, p3..pn d1, d2, d3, d4...dn, d1, d2, d3..dn the problem will become to find a subsequence in above sequences with length N where sum(P(start, start+i)) = sum(D(start, start+i)) for any 0=iN. change those two sequences to below one. p1-d1, p1+p2-d1-d2, p1+p2+p3-d1-d2-d3 . p1+p2+..+p2-d1-d2...-dn make the sequence as s1, s2, s3, s4...sn, s1, s2..sn finally the problem becomes to find a subsquence in Sn start at element j where S(j+i) = Sj and Sj = 0. So it can be solved in NlogN On Sun, Jan 30, 2011 at 1:47 PM, nishaanth nishaant...@gmail.com wrote: @Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Southeast University Nicholas.Zhaoyu -- 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.
Re: [algogeeks] Re: Amazon Again
It's not right. On Sun, Jan 30, 2011 at 4:19 PM, Nich01as nicholas.zha...@gmail.com wrote: @Wei.Qi the algorithm is right, but the running time is ...? define Pi the amount of petrol each pumps has. Di is the distance between Ith and i+1th pumps. then we can double the circle, we can get to sequence p1, p2, p3, p4...pn, p1, p2, p3..pn d1, d2, d3, d4...dn, d1, d2, d3..dn the problem will become to find a subsequence in above sequences with length N where sum(P(start, start+i)) = sum(D(start, start+i)) for any 0=iN. change those two sequences to below one. p1-d1, p1+p2-d1-d2, p1+p2+p3-d1-d2-d3 . p1+p2+..+p2-d1-d2...-dn make the sequence as s1, s2, s3, s4...sn, s1, s2..sn finally the problem becomes to find a subsquence in Sn start at element j where S(j+i) = Sj and Sj = 0. So it can be solved in NlogN On Sun, Jan 30, 2011 at 1:47 PM, nishaanth nishaant...@gmail.com wrote: @Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Southeast University Nicholas.Zhaoyu -- Southeast University Nicholas.Zhaoyu -- 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.
[algogeeks] Re: design a data structure
1. Add element to the end of the array. 2. Find median of the array, and partion the array into two sets, the second one (where element = median) is removed. At each operation 2, array's size decreasing by factor 0.5. -- 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.
Re: [algogeeks] Re: design a data structure
@juvir++ how is the deletion O(1) ? On Sun, Jan 30, 2011 at 4:14 PM, juver++ avpostni...@gmail.com wrote: 1. Add element to the end of the array. 2. Find median of the array, and partion the array into two sets, the second one (where element = median) is removed. At each operation 2, array's size decreasing by factor 0.5. -- 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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Amazon Written Tes Q1
Sort the Doubly Linked List..In Minim time complexity...is it possible to sort doubly linked list in O(n)..can some one provide..tutorial ,code or algo fro thiswhen u will fright with with amazon..you will see this question..as it is..so try it now.. Thanks Shashank -- 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.
[algogeeks] Amazon Written Test Q1
Sort the Doubly Linked List..In Minim time complexity...is it possible to sort doubly linked list in O(n)..can some one provide..tutorial ,code or algo fro thiswhen u will fright with with amazon..you will see this question..as it is..so try it now.. Thanks Shashank -- 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.
Re: [algogeeks] Re: design a data structure
It is amortized time. Search the web. This execise is from CLRS. -- 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.
[algogeeks] Re: Amazon Written Tes Q1
It is not possible using comparison sort. -- 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.
Re: [algogeeks] Re: Amazon Written Tes Q1
cannot figure out.. On Sun, Jan 30, 2011 at 8:48 PM, juver++ avpostni...@gmail.com wrote: It is not possible using comparison sort. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Southeast University Nicholas.Zhaoyu -- 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.
[algogeeks] Re: Amazon Written Tes Q1
@above... we have to sort the DLL ..so navies solution prduce the O(n^2) solution using merger sort we can do it in (nlogn)...but using merger we can also sortv the doubly linked list in (nlogn) then what is benefit of having perv pointer in DLL ..so according to me we can do it in O(n) because DLL has two pointers that gives use benefit..i have n^2 solution..but need something less then it..so now try to solve the problem.hope u got..it.. Thanks Shashank The best way to escape from a problem is to solve it. -- 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.
[algogeeks] Re: design a data structure
Another approach will be to insert the elements in order and remove the first(or the second) half in operation 2 Another approach would be to use a bitset , just mark all the elements in the specific range as 0 . We are not supposed to retrieve the elements so , keep a bit corresponding to every element (has the number , find it's position and put it there , a simple one one mapping will do) Now , just mark all top elements as false on the second go . PS:Would come up with the proof for amortized complexity soon , but can be done something like this First operation O(1) , second operation O(n) .However , we can only insert or delete , from this sequence of n items , in O(n) time in the worst case . These operations can be completed in a sequence in O(n) time . So the amortized complexity should be O(n)/n or O(1) . On Jan 30, 3:44 pm, juver++ avpostni...@gmail.com wrote: 1. Add element to the end of the array. 2. Find median of the array, and partion the array into two sets, the second one (where element = median) is removed. At each operation 2, array's size decreasing by factor 0.5. -- 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.
[algogeeks] Re: Frequently one of the Top Question Asked in Amazon
Spiral order .. means zigzag order for example
1
2 3
4 5 6 7
Then , you need to print it in the order
1-2-3-7-6-5-4
Two of my friends were asked this questions in the interview , so I
will list both of the approaches .
1)Use 1 stack and 1 queue .
push the elements of one level in stack 1
and the other in queue2
print both the stack and queue recursively.
algo :-
printZigZag(node * node , int level)
{
if(node==NULL)
return ;
if(level==0)
{
level=1;
stack1.push(node-data);
printZigZag(node-left , level);
printZigZag(node-right , level);
}
else
{
level=0;
stack2.push(node-data);
printZigZag(node-left , level)
printZigZag(node-right , level)
}
}
After this recursion ends , the two stacks will have the contents as
(1) (2)
4 2
5 3
6
7
1
Another approach would be to use two stacks . google it up .
and like this , now just print it recursively
On Jan 29, 10:17 pm, saurabh gupta sgup...@gmail.com wrote:
what do you mean by spiral order ?
On Sat, Jan 29, 2011 at 8:25 PM, bittu shashank7andr...@gmail.com wrote:
Convert BT in to DLL such that DLL represents the Sprial order
traversal of BT.
Inplace
its Written Test Question They wants Exact Working Code...Not
Approach..Be Clear..Try to provide best solutions
Thanks Regards
Shashank The best way to escape from a problem is to solve it.
--
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.comalgogeeks%2Bunsubscribe@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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.
[algogeeks] Re: design a data structure
Also , there is a pretty nice theorem on the fact that , if an array's size is increased/decreased by a constant size (like in STL vector class), the sequence of these doubling operations always take place O(1) time . On Jan 30, 3:44 pm, juver++ avpostni...@gmail.com wrote: 1. Add element to the end of the array. 2. Find median of the array, and partion the array into two sets, the second one (where element = median) is removed. At each operation 2, array's size decreasing by factor 0.5. -- 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.
[algogeeks] Re: Divide the array into groups
why have you divided it into three . I mean it can be divided into
many groups of consecutive .
Please write the statement properly !
On Jan 30, 11:13 am, snehal jain learner@gmail.com wrote:
@nishanth
divide into groups ( not necessarily 2) in as many group as possible.. such
that elements in each group is consecutive
another example to clearify
A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15)
ans
9,7,13,11,6,12,8,10
3,4,2
16,14,17,13,15
On Sun, Jan 30, 2011 at 11:32 AM, nishaanth nishaant...@gmail.com wrote:
@snehal..i guess you are missing something in the question...divide it into
2 groups such that (there should be some other condition or criterion).
On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.comwrote:
my approach
sort in nlogn and then while traversing the array put the elements in a
group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in
different group.. now we need to rearrange elements in the group so that
they are according to the given array.. but that will make it O(n^2) ..
anyone with better ideas?
On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote:
Divide a list of numbers into groups of consecutive numbers but their
original order should be preserved.
Example:
8,2,4,7,1,0,3,6
Two groups:
2,4,1,0,3 8,7,6
Better than O(n^2) is expected.
--
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.comalgogeeks%2Bunsubscribe@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.comalgogeeks%2Bunsubscribe@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.comalgogeeks%2Bunsubscribe@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.
[algogeeks] Re: Google Question
Suppose I press As only throughout . We will have the number of As as A*(number of keystrokes) .This is the least we can get provided we play stupidly enough . On Jan 29, 9:16 pm, Saikat Debnath saikat@gmail.com wrote: @ Sankalp : plz explain this line of yours : No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As On Jan 29, 5:32 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- 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.
[algogeeks] Re: Amazon Again
[quote]We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle.[/quote] So , we just need to find a petrol pump which takes you just a full circle , not anything ahead , not anything behind . 1)Sort the petrol he can get from maximum stations .If the total distance is not given , calculate this while sorting . Binary search over this array for the required distance . complexity :-O(nlogn+k) 2)Hash it !! keep a hash for all the distance in some boolean array .now find out the one which can get you the full circle , O(n) complexity . Not space efficient . 3)Using dynamic programming . dp[i][j] :-The distance we still need to cover (j) .while , we are on the started at the ith station . dp[i][0]:- answer , we need to look at the all the dp pairs for the answer . dp[i][j]= min(dp[i+next[i][j-d[i][next[i]]]) Basically a BFS . O(n^2) . worst case . -- 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.
Re: [algogeeks] Re: Microsoft Written Test Questions
Does anyone have details of whether the test was conducted on the 30th? If yes, which city? --AB On Thu, Jan 27, 2011 at 5:33 PM, Rahul Menon menonrahul1...@gmail.com wrote: This time MS rather than conducting the written tests by itself has outsourced the procedure to MERITTRAC Services to be conducted to jan 30th, So unlike the regular 6 questions type written test , it will be replaced by MCQs which is the regular pattern of merittrac tests [think so] . From a bit googling I came to know that these people put lot of repeated questions and each time and if we can get questions from previously conducted tests of MS , it can be very helpful. So the ones with experience with merritrac tests here ,can do a lot help, I would also like to know about the pattern or topics they usually test. And also sample questions Regards, Rahul -- 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.
[algogeeks] Re: Frequently one of the Top Question Asked in Amazon
Hi Guys...I think I am right I have written the code for this..please
go through it... let me know if any issuecheck the ouyouti
have write the solution for the BT of height 2 ..
1
/ \
2 3
/ \ / \
4 5 6 7
its printing 1237654. now it become DLL so head is pointed by Doubly
Linked start Pointer ..
Prev Next Pointers of DLL..which was left right pointers for the
Tree.
#includestdio.h
#includestdlib.h
struct node
{
struct node *left;
struct node *right;
int data;
};
struct node *rslt;//Global structure pointer
int height(struct node* head)
{
if(head==NULL)
return 0;
if(head-left==NULL head-right==NULL)
return 0;
int lh=height(head-left);
int rh=height(head-right);
return lhrh?(lh+1):(rh+1);
}
struct node* appnd(struct node *a,struct node *b)
{
if(a==NULL)return b;
if(b==NULL)return a;
struct node* result=a;
while(result-right!=NULL)
result=result-right;
result-right=b;
b-left=a;
result=a;
return result;
}
void printGivenLevel(struct node* head,int level,int ltr)
{
struct node *current;
struct node *temp;
if(head==NULL)
return;
if(level==0)
{
printf( %d --- ,head-data);
temp=current;
current=head;
rslt=appnd(temp,current);
}
if(level0)
{
if(ltr)
{
printGivenLevel(head-left,level-1,ltr);
printGivenLevel(head-right,level-1,ltr);
scanf(%d);
}
else
{
printGivenLevel(head-right,level-1,ltr);
printGivenLevel(head-left,level-1,ltr);
}
}
}
void printGivenOrder(struct node* head)
{
int i=0;
int ltr=0;
for(i=0;i=height(head);i++)
{
printGivenLevel(head,i,ltr);
ltr=~ltr;
}
}
struct node* NewNode(int data)
{
struct node* tmp=(struct node *)malloc(sizeof(struct node));
tmp-data=data;
tmp-left=NULL;
tmp-right=NULL;
return tmp;
}
void printList(struct node* node)
{
struct node* current=node;
while(current!=NULL)
{
printf(%d \n,current-data);
current=current-right;
}
}
int main()
{
struct node* start=NULL;
start=NewNode(1);
start-left=NewNode(2);
start-right=NewNode(3);
start-left-left=NewNode(4);
start-left-right=NewNode(5);
start-right-left=NewNode(6);
start-right-right=NewNode(7);
printGivenOrder(start);
printList(rslt);
return 0;
}
in output extra 4 is printing in the last.after printing 1237654
(4).if sum1 able to figure out it..please let know
Thanks Regards
Shashank The best way to escape from a problem is to solve it.
--
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.
Re: [algogeeks] Re: Frequently one of the Top Question Asked in Amazon
Isn't it just a coding question? @ ^ : your code is not clean enough for anyone to read. As far as data-structures are concerned... a stack and a queue suffice. There is no algorithmic issue I can see. So, I guess you should solve these problems yourself or some programming forum. For those who don't know spiral order traversal : There is always something called *google. *Please google it out before asking. -- 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.
Re: [algogeeks] Re: Divide the array into groups
@above
ignore my second example.. its incorrect.. go by 1st one
On Sun, Jan 30, 2011 at 6:11 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
why have you divided it into three . I mean it can be divided into
many groups of consecutive .
Please write the statement properly !
On Jan 30, 11:13 am, snehal jain learner@gmail.com wrote:
@nishanth
divide into groups ( not necessarily 2) in as many group as possible..
such
that elements in each group is consecutive
another example to clearify
A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15)
ans
9,7,13,11,6,12,8,10
3,4,2
16,14,17,13,15
On Sun, Jan 30, 2011 at 11:32 AM, nishaanth nishaant...@gmail.com
wrote:
@snehal..i guess you are missing something in the question...divide it
into
2 groups such that (there should be some other condition or
criterion).
On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.com
wrote:
my approach
sort in nlogn and then while traversing the array put the elements in
a
group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1]
in
different group.. now we need to rearrange elements in the group so
that
they are according to the given array.. but that will make it O(n^2)
..
anyone with better ideas?
On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.com
wrote:
Divide a list of numbers into groups of consecutive numbers but their
original order should be preserved.
Example:
8,2,4,7,1,0,3,6
Two groups:
2,4,1,0,3 8,7,6
Better than O(n^2) is expected.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups .com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: Amazon Written Tes Q1
There is a well-known bound for the comparison sort, O(nlogn). If there is a way to sort doubly-linked list in a linear time, so we are able to sort all sequencies in this time. But it is impossible! -- 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.
Re: [algogeeks] Re: Amazon Written Tes Q1
O(n) is impossible even for an array where we can do random access. On Sun, Jan 30, 2011 at 11:39 AM, juver++ avpostni...@gmail.com wrote: There is a well-known bound for the comparison sort, O(nlogn). If there is a way to sort doubly-linked list in a linear time, so we are able to sort all sequencies in this time. But it is impossible! -- 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Amazon Again
For any gas pump, when your car arrives, it contains 0 or more gas. So, for each gas pump, the worst case is starting from that pump. Then, if we starting from pump A1, passed A2 - Ak and failed at Ak+1. for A1 to Ak, we can not pass Ak+1 starting from any of them. So we try start from Ak+1. This could be solved in liner time. finding a possible start pump use O(n) and prove it use another O(n). -weiq On Sat, Jan 29, 2011 at 9:47 PM, nishaanth nishaant...@gmail.com wrote: @Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: Amazon Question
Here is working Code
//code is very simple from understanding points of view
//we can solved the problem dynamically or more efficiently but i
posted the solution by taking every things statically ..but its
working what question asked.for
#includestdio.h
#includeconio.h
int main()
{
int a[5]={1,2,3,4,5};
int b[10]={6,7,8,9,10};
int i=0,j=0,x=5,y=5;;
int t=5; //temp which pints to location in array b after 5 elements
while((ix) (jy))
{
if(a[i]=b[j])
{
b[t]=b[j];
b[j]=a[i];
i++;
j++;
}
else
{
b[t]=a[i];
printf(%d ,b[t]);
b[i]=b[j];
j++;
i++;
}
t++;
}
for(i=0;i10;i++)
{
printf(%d\t,b[i]);
}
getch();
return 0;
}
Thanks Regards
Shashank The best way to escape from a problem is to solve it.
--
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.
Re: [algogeeks] Re: Amazon Written Tes Q1
if we can do it for DLL using Comparison sort, then why not for array make an DLL of elements of array, sort in DLL and put back in array. not possible using Comparison sort. i think interviewer asked this question to see your reasoning, how you handle these type of question ? -- 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.
Re: [algogeeks] Re: Frequently one of the Top Question Asked in Amazon
@bittu: please write the subject which could summarize the problem statement or give a context instead of writing top question, amazon everywhere. you have multiple posts with the same problem. In the content you can write this co., that co., frequency of questions etc etc whatever you like after your problem statement. @Rohit: I agree with you partly here. As long as the question contains terms which are generally known it should be fine but if somebody mentions a term which is rare it is always better to give a few examples to clarify, in my opinion. If majority of readers are forced to google then examples are necessary. This again is subjective so it's always the problem writer's call. This post qualifies for examples in the problem statement. On Sun, Jan 30, 2011 at 8:38 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Isn't it just a coding question? @ ^ : your code is not clean enough for anyone to read. As far as data-structures are concerned... a stack and a queue suffice. There is no algorithmic issue I can see. So, I guess you should solve these problems yourself or some programming forum. For those who don't know spiral order traversal : There is always something called *google. *Please google it out before asking. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.
Re: [algogeeks] Re: Frequently one of the Top Question Asked in Amazon
@bittu: you may also want to answer juver++'s off topic question in your future posts. On Mon, Jan 31, 2011 at 1:15 AM, saurabh gupta sgup...@gmail.com wrote: @bittu: please write the subject which could summarize the problem statement or give a context instead of writing top question, amazon everywhere. you have multiple posts with the same problem. In the content you can write this co., that co., frequency of questions etc etc whatever you like after your problem statement. @Rohit: I agree with you partly here. As long as the question contains terms which are generally known it should be fine but if somebody mentions a term which is rare it is always better to give a few examples to clarify, in my opinion. If majority of readers are forced to google then examples are necessary. This again is subjective so it's always the problem writer's call. This post qualifies for examples in the problem statement. On Sun, Jan 30, 2011 at 8:38 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Isn't it just a coding question? @ ^ : your code is not clean enough for anyone to read. As far as data-structures are concerned... a stack and a queue suffice. There is no algorithmic issue I can see. So, I guess you should solve these problems yourself or some programming forum. For those who don't know spiral order traversal : There is always something called *google. *Please google it out before asking. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.
[algogeeks] Re: Amazon Written Tes Q1
can u provide solution..nlogn or n^2 ..write algo..or exact working code for this... thanks shashank -- 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.
Re: [algogeeks] Re: Amazon Intrerview
I am completely confused here As i understand, a binary tree has a root, and unrooted binary tree, i could not understand what it is and what is the relevance(are we alking about forest here?) Also, i finding LCA for a BST is extremly easy, but for Binary tree, need to understand how is it done with an example, request someone to throw some light Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jan 12, 2011 at 2:18 AM, saurabh gupta sgup...@gmail.com wrote: Based on various comments I think folks do not consider B in the path from A to C which leads to the LCA solution. @SVIX, one can implement the tree with a parent pointer in each node but that doesn't matter in the general case. What you are essentially saying is: consider the tree to be a directed graph with parent - child link to be one way, if that were the case we cannot even reach from A to C so that is out of question that's why we consider it to be a both way link. Now given this one can always argue that B lies in the path from A to C! i.e. A-D-M-B-M-C so here we can, perhaps, define a shortest path from A to C and it has to go through LCA. @all guys, one request please use @XYZ in case you are referring to a particular post by the person XYZ unless it is a general comment. just to avoid confusion. On Tue, Jan 11, 2011 at 8:06 PM, juver++ avpostni...@gmail.com wrote: The tree can be unrooted. Although, in any tree there is unique path from one node to another. Not only from the parent to childs. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Amazon Intrerview
I am not clear if the code tells the algo.
The moment we are calling t.getRoot() implies that we are using parent
pointer. Maybe, i am not a JAVA guy so donot understand how parent is
obtained in this..may be insert times... can someone elaborate..
public StackNode trace(Tree t, Node node){
mainStack = new StackNode();
trace(t.getRoot(),node);
return mainStack;
}
private boolean trace(Node parent, Node node){
mainStack.push(parent);
if(node.equals(parent)){
return true;
}
if(parent.left != null){
if (trace(parent.left, node))
return true;
}
if(parent.right!=null){
if (trace(parent.right, node))
return true;
}
mainStack.pop();
return false;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jan 31, 2011 at 9:00 AM, Ashish Goel ashg...@gmail.com wrote:
I am completely confused here
As i understand, a binary tree has a root, and unrooted binary tree, i
could not understand what it is and what is the relevance(are we alking
about forest here?)
Also, i finding LCA for a BST is extremly easy, but for Binary tree, need
to understand how is it done with an example, request someone to throw some
light
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 2:18 AM, saurabh gupta sgup...@gmail.com wrote:
Based on various comments I think folks do not consider B in the path from
A to C which leads to the LCA solution.
@SVIX, one can implement the tree with a parent pointer in each node but
that doesn't matter in the general case.
What you are essentially saying is: consider the tree to be a directed
graph with parent - child link to be one way, if that were the case we
cannot even
reach from A to C so that is out of question that's why we consider it to
be a both way link.
Now given this one can always argue that B lies in the path from A to C!
i.e. A-D-M-B-M-C
so here we can, perhaps, define a shortest path from A to C and it has to
go through LCA.
@all
guys, one request please use @XYZ in case you are referring to a
particular post by the person XYZ unless it is a general comment.
just to avoid confusion.
On Tue, Jan 11, 2011 at 8:06 PM, juver++ avpostni...@gmail.com wrote:
The tree can be unrooted. Although, in any tree there is unique path from
one node to another. Not only from the parent to childs.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up.
Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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.comalgogeeks%2bunsubscr...@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.
[algogeeks] first larger element in unsorted array...
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
--
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.
Re: [algogeeks] first larger element in unsorted array...
simple dp
void solve(int *arr,int sz)
{
int ans[sz];
ans[sz-1]=-1;
for(int i=sz-2;i=0;i--)
{
if(arr[i]arr[i+1]) ans[i]=arr[i+1];
else ans[i]=ans[i+1];
}
for(int i=0;isz;i++)
printf(%d ,ans[i]);
}
On Sun, Jan 30, 2011 at 10:00 PM, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
--
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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] first larger element in unsorted array...
@above I think you should process not only the right part but the left one too. -- 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.
[algogeeks] Re: first larger element in unsorted array...
for {9,7,8} it gives me {8,8,-1}...not correct
On Jan 31, 11:16 am, abhijith reddy abhijith200...@gmail.com wrote:
simple dp
void solve(int *arr,int sz)
{
int ans[sz];
ans[sz-1]=-1;
for(int i=sz-2;i=0;i--)
{
if(arr[i]arr[i+1]) ans[i]=arr[i+1];
else ans[i]=ans[i+1];
}
for(int i=0;isz;i++)
printf(%d ,ans[i]);
}
On Sun, Jan 30, 2011 at 10:00 PM, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
--
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.comalgogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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.
