Online Stock Span Medium

faq

1.  Name some applications of stack. 

Ans:

Evaluation of arithmetic expression
Code generation for stack machine. 
Backtracking. 
Decimal to binary conversion

2. How do you generate code for stack machines? 

Ans:Stack machine is a machine which use a stack instead of registers to store intermediate results temporaries. Using a stack, we can easily generate an assembly code from a postfix notation. 

3) Dicuss reversing a list of items in stack. 

Ans:Reversing data requires that a given set of data will reordered. So that the first and last elements are exchanged, with are of the positions between the first and last being relatively exchanged also. 

4) What are indirect applications of stacks? 

Ans:

Auxiliary data structure for other algorithms such as tree traversal algorithms. 
Components of other data structures such as simulating queues. 

5) Can we evaluate the infix expression with stacks in one pass? 

Ans:Using two stacks we can evaluate an infix expression in one pass without converting to postfix. 

hints

1. we will use stack with pair, we will store array element and its index, each time we iterate through array element. 
2. We check the previous next greater element, if the previous greater element is found at some location i, then we will take the difference between the current index element and the previous greater element.
3. We will use a vector for each index to push the number of elements that are smaller than or equal to the current element.
4. We will use a boolean variable flag, if the element is pushed according to condition then make variable flag true otherwise push 1 as only that element is valid and all element before is greater than it.

mcq

Q1) What is the average time complexity of this problem?
a) O(n*n)
b) O(n)
c) O(1)
d) None of the above
Ans: b

Q2) What is the average space complexity of this problem?
a) O(n*n)
b) O(1)
c) O(n)
d) None of the above
Ans: c

Q3) The greatest number of consecutive days just before the given day for which the stock's price on the present day is _________ to its price on the given day is described as the span Si of the stock's price on that day.
a)equal
b)less than or equal
c)greater than or equal
d)none of the above
Ans: b

Q4) The condition top<1 when top=1; is for

a) Pop operation

b) Push operation

c) Status

d) none of these

Ans:a(Pop operation) 

Q5)  set of statements which are executed repeatedly until some specified condition is satisfied called

a) Iteration

b) Recursion

b) Monolithic program

d) none of these

Ans:a(iteration)