The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
464 views

How it is 24? I'm not getting it.

asked in DS by Loyal (4.7k points)
edited by | 464 views
I too think 12 is correct
Still ambigious answer, no valid reason for weather it's 12 or 24??
I think with each element they are also storing the value of max element till that point for e.g if we push elements in this order 5,5,4,3,6,2

then  where each tuple means (max value of element till this point, current element)  

6,   2     top

6,   6

5,   3,

5,   4

5,   5

5,   5   Bottom

@  akb1115 ,I think,you approach for finding max,but how MAX is working internally,should not be considered as a part of answermlike we didnt bother how push and pop are implemented.

Defiantly this question is ambiguous because they haven't told how they are actually implementing the max so answer varies how you interpret the question by applying different approaches and interpretation we will get different answer like 12,16,24 etc,

5 Answers

+4 votes

I think the answer is 24. 

If we see, there will be only three elements after all the operations which may prompt us to think the size of the stack is =12 bytes (3*4 bytes) .

But STACK is a static data structure  and hence needs to allocate space for all the numbers even if they are not present in the stack simultaneouly. 

Here , numbers are  - 5 5 6 6 7 8  (Consider them as block of memory rather than nummbers )

So, size of the  datastructure will be = 6* 4 Bytes= 24 Bytes 

PUSH and POP operations doesn't allocate or free memory . They are simply the  Increment/decrement of Stack Pointer.

answered by (405 points)
if this is the case then we have atmost 4 elements.

push(5) push(6) push(7) pop push(6) push(8) pop pop push(5)

then 4*4=16

isn't it?

 

and other thing if we use linked list instead of array then what will be size??

There will be six elements after the above set of operations. So size of stack is 24. Max reports the maximum element in stack and will not remove it. And Stack need not be a static data structure. If Stack is implemented using a linked list then it can grow dynamically. PUSH operation will create a node, allocate memory to it and then add it to the stack. If so each node will also contain a pointer which will consume some memory. But no such condition is mentioned in the question and hence can be ignored.

I will upvote only if you remove that "I think" written in your answer. 

I have a better implementation for this. Consider storing the elements as the normal stack, but with it we have another stack to store the max element. Whenever we perform push operation on the original stack, we check if it is larger(or equal) than top of currMax stack, if it is we push it into both the stacks, otherwise push it only on the original stack. Now when we perform POP, we check if the top element of original stack is equal to the top element of currMax stack, if it is, then we pop from both the stacks, otherwise pop only from original stack.

Consider the example:

O denotes original stack, M denotes currMax stack. The rightmost element is the top element of the stack

push(5):

O: 5

M: 5

push(6):

O: 5 6

M: 5 6   (since, 6 >= 5)

push(7):

O: 5 6 7

M: 5 6 7 (since 7 >= 6)

pop:

O: 5 6

M: 5 6 (since top of M == element to be popped, i.e. 7 == 7)

max:

returns 6 (top of M)

push(6):

O: 5 6 6

M: 5 6 6  (since 6 >= 6)

push(8)

O: 5 6 6 8

M: 5 6 6 8  (since 8 >= 6)

pop:

O:5 6 6

M: 5 6 6  (since top of M == popped element, i.e 8 == 8)

pop:

O: 5 6

M: 5 6    (again, since top of M == popped element, i.e 6 == 6)

push(5):

O: 5 6 5

M: 5 6   (This time we will not push 5 into M, since 5 >= 6 is false).

So, this requires lesser space and same time complexity. So, the answer according to this is 20 (= 5 * 4)

Am I wrong somewhere?
When we implement a Stack using an array then it is static in nature and after push and pop operation no memory is allocated or freed but when we implement a Stack using linked list then for push operation we have to allocate memory and after pop operation memory is freed then I think the answer will be 12 bytes.
they are asking size of stack after performing those operations so in that way 24B seems a wrong answer.
The question is referring to the additional memory required to support the max operation assuming it to be done in O(1) time -- though this is not mentioned in the question.
Hello Sir , sorry but i didn't get your point.

How can we tell MAX of an array in O(1)?
Suppose this question of Stack with Max operation is given as a programming assignment -- how will you do it?
Hello sir , sorry for late response. Happy Diwali :)

as i'm able to see , if there is condition like 'No additional space avail' then i don't think that this work can be done in constant time...if there is again condition like only PUSH is allowed , no POP then , using some temp variable we can certainly tell MAX in const time but when 'in b/w' POP is going on , we can't tell MAX in O(1) unless we use some additional stack like Rishabh answered...

I'm not that good with programming , please tell me if i went wrong somewhere.
+2 votes

Ans b) 24

There will be six elements after the above set of operations. So size of stack is 24. Max reports the maximum element in stack and will not remove it. And Stack need not be a static data structure. If Stack is implemented using a linked list then it can grow dynamically. PUSH operation will create a node, allocate memory to it and then add it to the stack. If so each node will also contain a pointer which will consume some memory. But no such condition is mentioned in the question and hence can be ignored.

answered by Loyal (4.6k points)
+1 vote

Answer Varies.

Stack is linear data structure.

If its static implementation of stack, iel using linear array then answer is 24 bytes. when total used space is asked.

If its dynamic implementation of stack, ie. using linked list then answer is 12 bytes.

Also if current allocated space asked in static implementation then its 12 bytes.

answered by Junior (733 points)
0 votes
Its a made easy test series question.

After performing all the operations stack will have 3 values and max will have 1 value so size of data structure after all these operations = size of stack+max= (3+1)*4 =16.

 

In made easy solution,they have given 24 as answer and they have assumed that eachs tack entry is 8B(but question says4).

But we need to include memory occupied by max also as it is part of the data structure.

So 16 should be correct answer
answered by Veteran (17.3k points)
0 votes

Ans: 20 bytes

 

Applying efficient algorithm, 

Main_Stack Max_Stack
5  
8 8
6  
7 7
6 6
5 5

Here, when 7 is pushed, new entry is created in MAX_STACK because it is the new MAX. 

Next element to be pushed is 6. Applying efficient algorithm there is no need to push it in MAX_STACK. 

Similarly, when 8 is pushed, new entry is created in MAX_STACK of new MAX.

 

Now, coming to POP peration, 8,6,7 are popped from MAIN_STACK and along with it 8 and 7 are also popped from MAX_STACK.

At the end, 5 is pushed on MAIN_STACK and no need to insert it on MAX_STACK.

So, final table is - 

MAIN_STACK MAX_STACK
5  
6 6
5 5

 

So, total number of elements = 5

Total size = 5*4 bytes = 20 Bytes

 

PS : Above concept is discussed in Data Structures and Algorithms - Narasimha Karumanchi 

answered ago by (137 points)
edited ago by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,834 questions
36,688 answers
90,628 comments
34,641 users