@Prateek Jain : Middle element is nothing but a median ( i.e. middle
element in sorted state)
Soluton
1. Maintain a sorted stack using an extra stack , pop half of the elements
or get the middle and if it's implemented using arrays fetch middle index
value (top/2)
T(N)= O(n^2) to maintain a
Code is here http://codebin.org/view/30e9f2c0. Logic is made clear by the
variable names. Idea is similar to the one which is used to build a queue
using 2 stacks.
On Wed, May 22, 2013 at 8:45 AM, MAC macatad...@gmail.com wrote:
I think this is only possible if you make sure that at push you
I think there is no need for such a complex code. use length() method to
get the size of the stack and return the middle element i.e.
m=S.length()
if(m is even)
return arr[m/2]
else
return arr[m+1/2]
it can be done in O(const) time
On Thu, May 23, 2013 at 12:54 PM, Avi Dullu
Using two stacks to simulate the getmiddle behavior.
Amortized analysis can show each geimiddle is O(1) time complexity.
Best,
2013/5/23 Prateek Jain prateek10011...@gmail.com
I think there is no need for such a complex code. use length() method to
get the size of the stack and return the
Saw this on a seperate group .. Since answer not known to me sharing it
here
you have a stack . Exposed functionality is push and pop only .
What minimal modifications would you do such that
you should find middle element in o(1) time .
I think this is only possible if you make sure that at
hw will u design a stack which will have push pop and min fxn...all should
operate in o(1) tymreplyn asap
--
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
already discussed.search in archives
On Fri, Sep 30, 2011 at 6:29 PM, rahul sharma rahul23111...@gmail.comwrote:
hw will u design a stack which will have push pop and min fxn...all should
operate in o(1) tymreplyn asap
--
You received this message because you are subscribed to the
plz post link as m not able to find it
On Fri, Sep 30, 2011 at 7:17 PM, sukran dhawan sukrandha...@gmail.comwrote:
already discussed.search in archives
On Fri, Sep 30, 2011 at 6:29 PM, rahul sharma rahul23111...@gmail.comwrote:
hw will u design a stack which will have push pop and min
http://groups.google.com/group/algogeeks/browse_thread/thread/1dd628ee5e7939da/decedd114a26e564?hl=enlnk=gstq=stack+problem#
On Fri, Sep 30, 2011 at 7:41 PM, rahul sharma rahul23111...@gmail.comwrote:
plz post link as m not able to find it
On Fri, Sep 30, 2011 at 7:17 PM, sukran dhawan
In the classic problem of the Towers of Hanoi, you have 3 rods and N disks
of different sizes which can slide onto any tower. The puzzle starts with
disks sorted in ascending order of size from top to bottom (e.g., each disk
sits on top of an even larger one). You have the following constraints:
stfu !
On Tue, Sep 20, 2011 at 10:27 AM, prasanth n nprasnt...@gmail.com wrote:
In the classic problem of the Towers of Hanoi, you have 3 rods and N disks
of different sizes which can slide onto any tower. The puzzle starts with
disks sorted in ascending order of size from top to bottom
@surender: say the hash table of freq,linked_lis is as follows...
1,2-3-4
2,5-6
3,7-8
pop(7) would decrease the frequency of element 7 means that element has to
be added to 2nd key i.e 2,5-6-7 here
how do u get the element 7 from hash table as freq is the key element in u'r
table?
And after
@bharat
take two hashmaps of
hash1data, freq and
hash2freq,linked_list
take frequency of a data from hash1, and find its list in hash2.
if ur poping, reduce frequency in hash1 and in corresponding hash2 remove
its entry in that list and put it in freq-1 entry
and keep track of max and second max
maintain a hash of freq,linked_list
linked_list consists of values of that frequency.
values with same frequency comes under same list
if pop of a particular value is done, then frequency is changed of that
number, a new record would be created if required.
maintain two values tracking max and
The frequency is also stored in the heap right? So to do heapify based on
frequency, first you have to spot the element on the heap. That itself will
take O(n). [ Heapfying after that takes only O(log n) ] If you use a hashmap
and store frequencies, and each time mostFrequent is called, do a
HI,
Need logic to implement a stack which should support push , pop , top as
well as mostFrequent. mostFrequent should return the most frequently pushed
element.
I have provided the following logic
have one general stack implementation and one Heap .. (Heapify based on
frequeny not based on
How would you design a stack which,in addition to push and pop,also
has a function min which returns the minimum element?push,pop and min
should all operate in O(1) time
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
we can take another variable min..
first time push operation is done , store the element into min..
next time push is performed , compare the number u r pushing with the
already stored no in min variable.. and store minimum of two no's in min
variable.. and thn perform the push operation..
so
no this wont work coz wat will hapen if that min is popped out ?
On Sun, Sep 4, 2011 at 11:11 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote:
we can take another variable min..
first time push operation is done , store the element into min..
next time push is performed , compare the
+1 sandeep
On Sun, Sep 4, 2011 at 11:11 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote:
we can take another variable min..
first time push operation is done , store the element into min..
next time push is performed , compare the number u r pushing with the
already stored no in min
not possible to track min. because even if u keep track min position if u
pop tat element again we need to search for next min which isnot possible in
o(1)
correct me if im wrong
On Sun, Sep 4, 2011 at 10:38 PM, Sangeeta sangeeta15...@gmail.com wrote:
How would you design a stack which,in
maintain a separate stack containing min and max element at each step.
so if u pop an element for the original stack, pop from the second stack
also...
On Sun, Sep 4, 2011 at 11:13 PM, Deepak Garg deepakgarg...@gmail.comwrote:
+1 sandeep
On Sun, Sep 4, 2011 at 11:11 PM, SANDEEP CHUGH
+1 Deepak..
On Sun, Sep 4, 2011 at 11:15 PM, Deepak Garg deepakgarg...@gmail.comwrote:
maintain a separate stack containing min and max element at each step.
so if u pop an element for the original stack, pop from the second stack
also...
On Sun, Sep 4, 2011 at 11:13 PM, Deepak Garg
suppose in that max stack max elements are maitained.suppose one element
with value less arrives.u need to insert it in proper pos.how is that
possible in 0(1) ?
On Sun, Sep 4, 2011 at 11:15 PM, Deepak Garg deepakgarg...@gmail.comwrote:
maintain a separate stack containing min and max element
Suppose that a client performs an intermixed sequence of (stack) push
and pop operations. The push operations put the integers 0 through 9
in order on to the stack; the pop operations print out the return
value. Which of the following sequences could not occur?
(a) 4 3 2 1 0 9 8 7 6 5
(b) 4 6 8 7
b f g
On Wed, Aug 31, 2011 at 11:49 AM, shiva shiva8ve...@gmail.com wrote:
Suppose that a client performs an intermixed sequence of (stack) push
and pop operations. The push operations put the integers 0 through 9
in order on to the stack; the pop operations print out the return
value. Which
couldn't get it... what are the sequences given in options??? are they the
pushed values or popped values or what???
--
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
The sequence like 3 1 2 is invalid.
So, ans is *b*,* f* and *g*
On Wed, Aug 31, 2011 at 1:35 AM, Siddhartha Banerjee
thefourrup...@gmail.com wrote:
couldn't get it... what are the sequences given in options??? are they the
pushed values or popped values or what???
--
You received this
I DNT GET IT.. EXPLAIN PROPERLY ANYONE
On Wed, Aug 31, 2011 at 12:57 PM, Yuchen Liao lycdra...@gmail.com wrote:
The sequence like 3 1 2 is invalid.
So, ans is *b*,* f* and *g*
On Wed, Aug 31, 2011 at 1:35 AM, Siddhartha Banerjee
thefourrup...@gmail.com wrote:
couldn't get it... what
explanation for *b)*
push(0)
push(1)
push(2)
push(3)
push(4)
pop()---4
push(5)
push(6)
pop()-6
push(7)
push(8)
pop()-8
pop()7
pop()5
pop()-3
pop()2
push(9)
pop()--9
here, noway we can get 0 before 1 .. so this sequence is not
@all i think c is also invalid since after 7 how 4 can popped
with out poping 6 and 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,
Please mention the source of the question when you ask such question to
confirm that a solution exists for this prob.
--
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
exactly try posting links to the problem...
On Sat, Aug 27, 2011 at 10:33 AM, raj kumar megamonste...@gmail.com wrote:
Please mention the source of the question when you ask such question to
confirm that a solution exists for this prob.
--
You received this message because you are
how to implement a stack(push and pop) using binary search tree??
--
*prasanth*
--
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
Stack A has the entries a,b,c ( with a on the TOp) Stack B is empty.
an entry pooped out of the stack A can be printed immediatly or pushed to
stack B. An Entry popped out of the stack B can only be printed. In this
Arrangement ,if Stack A has 4 entries, then number of possible permutation
will be
Stack A has the entries a,b,c ( with a on the TOp) Stack B is empty.
an entry pooped out of the stack A can be printed immediatly or pushed
to stack B. An Entry popped out of the stack B can only be printed. In
this Arrangement ,if Stack A has 4 entries, then number of possible
permutation will be
Manually calculated it to be 14.. [?]
Can't think of any general formula but i think a formula or at least
recursive function must be there to solve this.
On Sat, Jun 4, 2011 at 1:01 PM, siva viknesh sivavikne...@gmail.com wrote:
Stack A has the entries a,b,c ( with a on the TOp) Stack B is
@anurag
I meant the sorting without using any auxiliary data structure .Also we
have to put the element in the tree and carry out a traversal for every
element we insert in the tree .This takes O(n*logn) time ,
If one can sort the elements using a stack in O(n) time , we better sort
with this
Another way in which this can be thought is in terms of Tower of Hanoi
problem.Just introduce two more stacks of same size as input stack and get
the sorted output as result.
On Mon, Jun 14, 2010 at 9:18 AM, Anurag Sharma anuragvic...@gmail.comwrote:
Why not just pop all elements from stack (
Thats what he is referring to :)
Anurag Sharma
On Tue, Jun 15, 2010 at 4:49 PM, Amit Jaspal iit2007...@iiita.ac.in wrote:
But what about the Stack Space Used while doing Merge and Quick Sort?
On Mon, Jun 14, 2010 at 9:30 AM, Anurag Sharma anuragvic...@gmail.comwrote:
Seems correct to me
quicsort takes a bit of memory during recursion calls. it depends how many
variable you pass in each function and number of variables defined inside
the function.so most of the time we don't consider quicksort inplace
In worst case quicksort take O(n) extra space
correct me if i am wrong
--
Why not just pop all elements from stack ( O(n) ) and insert it in a self
balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and
inorder traversal ( O(n) )and push elements in stack again.
Time = O(nlog(n) + n)
Space=O(n) (for storing the tree)
Anurag Sharma
On Sun, Jun 13,
Seems correct to me :)
Anurag Sharma
On Sun, Jun 13, 2010 at 11:23 PM, amit amitjaspal...@gmail.com wrote:
Can anyone tell what is Stack Space required for Quick Sort and Merge
Sort.And how in each case it can be modified.
Correct me if I am wrong on this.
Space Complexity of Merge Sort (
But what about the Stack Space Used while doing Merge and Quick Sort?
On Mon, Jun 14, 2010 at 9:30 AM, Anurag Sharma anuragvic...@gmail.comwrote:
Seems correct to me :)
Anurag Sharma
On Sun, Jun 13, 2010 at 11:23 PM, amit amitjaspal...@gmail.com wrote:
Can anyone tell what is Stack
how to sort elements of stack using constant space
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
what do you mean by sorting elements in stack ? A stack is a data structure
in which the relative position of elements depend on their order of
insertion.
If we sort elements in stack, how does it retain the property of a stack ?
If we really want that property, we will have O(n) rather than
it's not always possible to sort a stack in all the cases , consider the
stack 2143 and one tries to sort it feeding the elements in order , we have
now whatever popping technique we use , we cannot have a 1234 kind of
stack in order .The maximum number of permutations we can have with a stack
Stack can be sorted in O(n^2).
@sankalp:
Stack can always be sorted. Why do you think it cant be in some cases ?
One can think like insertion sort
algo :
1. for i in (1,n)
2. Pop up the top n-1 element and keep nth element in global variable say
hold
3. while pushing get the position for
Can anyone tell what is Stack Space required for Quick Sort and Merge
Sort.And how in each case it can be modified.
Correct me if I am wrong on this.
Space Complexity of Merge Sort ( Not Inplace) - O(n)
Space Complexity of Quick Sort - O(1)
--
You received this message because you are
@jalaj: These were few solutions discussed b4
1. For 3 stacks a efficient algo is not easy to think in a single array ,
yet we can optimise according the usage. For example lets say out of 3 stack
we know the growth of 2nd stack more closely and we know its variations
boundary of 2nd stack more
Give an algorithm to implement n stacks in an array... take care of the
empty space too i.e no overflow shld occur if there is eny empty space left
.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Is it without having the need to shift elements at all?
Anurag Sharma
On Fri, Jun 11, 2010 at 3:41 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
Give an algorithm to implement n stacks in an array... take care of the
empty space too i.e no overflow shld occur if there is eny empty space
@jalaj: This question has already been discussed for n=2,3
On Fri, Jun 11, 2010 at 4:11 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
Give an algorithm to implement n stacks in an array... take care of the
empty space too i.e no overflow shld occur if there is eny empty space left
.
@raj n
for 2 stacks its fine can you please tell for 3 stacks ...i'll generalize it
On Fri, Jun 11, 2010 at 9:32 PM, Anurag Sharma anuragvic...@gmail.comwrote:
Is it without having the need to shift elements at all?
Anurag Sharma
On Fri, Jun 11, 2010 at 3:41 PM, jalaj jaiswal
54 matches
Mail list logo
