Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Run through this example case:
HAPPY CASE
Input:
["MyQueue","push","push","peek","pop","empty"]
Output:
[[],[1],[2],[],[],[]]
Input:
["MyQueue","push","push","peek","pop","empty","empty"]
Output:
[[],[1],[2],[],[],[],[]]
EDGE CASE
["MyQueue","push","push","peek","empty","empty"]
[[],[1],[2],[],[],[]]
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: For pushing a new value to the queue, push it in the incoming stack. When popping from the queue, check if the outgoing stack is empty. If it is empty then pop all elements from the incoming stack and push them into the outgoing stack once to reverse the ordering. When the outgoing stack is not empty then we can just pop the top element in constant time, making this an amortized O(1) operation. Peeking is the same as popping except we will only return and not pop the top element at the end.
push(value): Push value to the intake stack
int pop(): 1. If the output stack has any elements, pop and return the top value.
2. If the output stack is empty and the intake stack has elements, then pop each element from intake stack and push it onto output stack. Finally pop and return the top value of output stack.
int peek(): Same steps for pop() but only returning the top value
boolean empty(): Returns true if the intake and output stacks are both empty, false otherwise
โ ๏ธ Common Mistakes
Implement the code to solve the algorithm.
class MyQueue:
def __init__(self):
# we either add to the add or remove from queue.
self.addStack, self.popStack = [], []
def push(self, x):
# When we add to the queue, we want to add to the addStack
# if we previously popped, we want to move all items from the popStack to the addStack
while self.popStack:
self.addStack.append(self.popStack.pop())
self.addStack.append(x)
def pop(self):
# when we pop from the queue, we need to migrate items from addstack to popstack
# doing this allows us to properly utilize a stack by using the FILO (first in last out) ideology
while self.addStack:
self.popStack.append(self.addStack.pop())
return self.popStack.pop()
def peek(self):
# if we previously added, look at the last item in the AddStack
# if we previously popped, look at the first item in the PopStack
return self.popStack[-1] if self.popStack else self.addStack[0]
def empty(self):
# check to see if either stack has items
return True if not self.addStack and not self.popStack else False
class MyQueue {
// initialize your data structure here
Stack<Integer> input;
Stack<Integer> output;
public MyQueue() {
input = new Stack<>();
output = new Stack<>();
}
// push element x to the back of queue
public void push(int x) {
input.push(x);
}
// removes the element from in front of queue and returns that element
public int pop() {
// we need to reverse the input sequence for getting result acc to queue
if(output.size() > 0){
return output.pop();
}else{
while(input.size() > 0){
output.push(input.pop());
}
return output.pop();
}
}
// get the front element
public int peek() {
// we need to reverse the input sequence to get result acc to queue
if(output.size() > 0){
return output.peek();
}else{
while(input.size() > 0){
output.push(input.pop());
}
return output.peek();
}
}
// returns whether the queue is empty
public boolean empty() {
return (input.size() == 0 && output.size() == 0) ;
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.