Stacks

Stack Builder

1. Design and implement a Stack data structure.

Your stack should support the following operations:

push(value): Add an element to the top of the stack.
pop(): Remove and return the top element of the stack. If the stack is empty, return an appropriate value or error.
peek(): Return the top element without removing it.
isEmpty(): Return true if the stack is empty; otherwise, return false.
size(): Return the number of elements in the stack.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	push(1) → pop()	1000 consecutive push and pop calls	pop() on an empty stack
Output	Returns 1	Each pop returns most recently pushed	Returns null or throws “Stack Underflow” error
Explanation	Only one element handled, all operations are direct	Still constant time per operation, just more calls	Handles robustness when stack has no elements

Nested Brackets

2. Given a string containing only the characters '(', ')', '{', '}', '[' and ']'. Design an algorithm that returns true if the string is valid, otherwise false.

A string id valid if:

Brackets are closed by the same type (e.g., ( with )).
Brackets close in the correct order (e.g., "([])" is valid but ([)] is not).
All brackets must be matched with no leftover open or close brackets.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	"()"	"(((([[[{{{}}}]]])))"	"", "[", "](", "([)]"
Output	true	true or false (depends on proper match)	false, false, false
Explanation	Already a simple valid pair	Nested, deeply matched — requires full scan	Empty or improperly matched input

Reverse String

3. Given a string of ASCII characters. Design an algorithm that reverses the string and return the reversed string.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	"a"	Very long string (e.g., 10⁶ chars)	"" (empty string)
Output	"a"	Reversed string of same length	""
Explanation	Single character remains same when reversed. Minimal computation.	Full traversal and allocation of reversed string; most resource-intensive.	No computation needed; return as-is.

Two Stacks One Array

4. Design a data structure that implements two stacks using a single array of fixed size n.

Data structure must support the following operations efficiently:

You must use only one array.
push1(x): Push element x into Stack 1. Stack 1 grows from the start of the array (index 0 → right).
push2(x): Push element x into Stack 2. Stack 2 grows from the end of the array (index n-1 → left).
pop1(): Pop element from Stack 1.
pop2(): Pop element from Stack 2.

All operations (push1, pop1, push2, pop2) must be done in O(1) time.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	push1(1), pop1()	Alternating push1, push2 until array full	Array of size n = 1, or stack overflows
Output	Value pushed/popped correctly	Last push1 or push2 fails when no space between pointers	-1 or "Stack Overflow"/"Stack Underflow" error
Explanation	Stack 1 has space and pushes/pops easily	Both stacks approach each other, leaving no space to insert more	Tests boundary condition handling and resizing

Next Greater Element

5. Given an array of integers. Design an algorithm that returns an array where each element is replaced by the next greater element to its right.

If no such element exists, replace it with -1.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	[1, 3, 5, 7, 9]	[9, 8, 7, 6, 5]	[7] or []
Output	[3, 5, 7, 9, -1]	[-1, -1, -1, -1, -1]	[-1] for [7], [] for []
Explanation	Every element has a greater one to the right.	No element has a greater one to the right.	No next element exists or only one element.

Postfix Calculator

1. Design an algorithm that evaluates expressions written in Reverse Polish Notation also known as Postfix Notation.

You are given a list of strings that represent integers and the four basic operations (+ , - , * , /).

Division should truncate toward zero (e.g., 5 / 2 = 2, -5 / 2 = -2).

The algo is to evaluate the expression and return the final result as an integer.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input Parameters	["2", "3", "+"]	["10", "6", "9", "3", "/", "-", "*"]	["42"]
Output	5	30	42
Explanation	Only one operation, minimal stack usage	Multiple nested operations and stack depth	Only one operand; no operations applied

Min Stack

2. Design an algorithm that implement a data structure that mimics a stack but also efficiently keeps track of the minimum value at any point in time.

The stack should support the following operations in O(1) time:

push(val) - Push an integer onto the stack.
pop() - Remove the element from the top.
top() - Get the top element.
getMin() - Retrieve the minimum element in the stack.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input Parameters	Push increasing elements: [1, 2, 3, 4]	Push decreasing elements: [4, 3, 2, 1]	Push duplicate mins: [2, 2, 2] and pop all
Output	Min = 1 after all ops	Min = updates at every push, so getMin() changes frequently	All values same, min should remain 2 after each op until empty
Explanation	Min doesn't change after first push	Min updates with each push/pop → high internal state tracking	Edge test of handling same min value multiple times

Warmer Days

3. Given a array of temperatures, representing the daily temperatures for a sequence of days. Design an algorithm that returns a new array result[] where each element at index i is the number of days you would have to wait after day i to get the next warmer temperature.

If there is no future warmer temperature, return 0.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input Parameters	[70, 71, 72, 73]	[80, 79, 78, 77]	[], [73
Output	[1, 1, 1, 0]	[0, 0, 0, 0]	[], [0]
Explanation	Each day is warmer than the previous → O(n) forward	No warmer days ahead → no stack popping → O(n²) naive, but optimized stack is O(n)	No work to do for empty/single element list

Starry Nested Brackets

4. Given a string s containing only the characters '(', ')', and '*'.

Design an algorithm that returns true is the string is valid, otherwise it return false.

A string is considered valid if,

Every open bracket '(' has a matching closing bracket ')'.
'*' can be treated as open bracket '(', closing bracket ')', or an empty string (i.e., it can be ignored).
The parentheses must be closed in the correct order.

Your algorithm must validate whether there exists a valid way to interpret all '*' such that the string becomes a valid sequence of parentheses.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input Parameters	"()"	"(((**))(()))"	[], [73
Output	true	true (after evaluating multiple wildcard combinations)	[], [0]
Explanation	Already valid, no wildcard	Needs wildcard handling to balance nested brackets	Single * can be empty

Largest Histogram Area

5. You are given an array heights[] where each element represents the height of a bar in a histogram. All bars have a width of 1 unit.

Design an algorithm to return the area of the largest rectangle that can be formed in the histogram. The rectangle must be entirely contained within the histogram.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input Parameters	[2, 2, 2, 2]	[6, 2, 5, 4, 5, 1, 6]	[1], [], [3, 1, 3]
Output	8 (2×4)	12 (4×3 from bars [5,4,5])	1, 0, 3
Explanation	All bars are the same height, so the area is height × number of bars	Multiple height drops force stack pops and recalculations for many sub-rectangles	Single bar or empty input handled gracefully without error

Simulate FIFO with LIFO

6. Design an algorithm that implements a queue using stack data structure.

The queue should support the following operations:

enqueue(x): Push element x to the back of the queue.
dequeue(): Removes the element from the front of the queue and returns it.
peek(): Return the front element.
empty(): Return whether the queue is empty.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input Parameters	enqueue(1), dequeue()	enqueue(1..n), dequeue()	No operations or only empty()
Output	1	Sequential values from 1 to n	true or appropriate error handling
Explanation	Minimal transfer from one stack to another since only one item	Requires full transfer from stackIn to stackOut for the first dequeue, which is O(n), but amortized	Tests queue behavior on no or limited data; validates correctness on boundary conditions

- Fundamentals -