Q
Q
Q
Q
Q
Q

A stack of Q’s 😉

Stack: first in, last out (FILO)

METHOD DESCRIPTION
empty() Returns true if the stack is empty. Else, returns false.
peek() Returns the element on the top of the stack, but does not remove it.
pop() Removes and returns the top element of the stack. Depending on the language and implementation, an error may be thrown if pop() is called when the stack is empty.
push(element) Pushes element to the top of the stack.

Example

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Create a Stack
        Stack<Integer> stack = new Stack<>();

        // Push elements onto the stack
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        
        // stack = [1, 2, 3, 4]

        boolean empty = stack.empty();
        // empty = false

        // Peek at the top element without removing it
        Integer topOfStack = stack.peek();
        // topOfStack = 4
        // stack = [1, 2, 3, 4]
        
        // Pop element from the stack
        Integer popped = stack.pop();
        // popped = 4
        // stack = [1, 2, 3]

        popped = stack.pop();
        // popped = 3
        // stack = [1, 2]
    }
}

Queue: first in, first out (FIFO)

METHOD DESCRIPTION
peek() Returns the element at the front of the queue, but does not remove it.
poll() Removes and returns the front element of the queue or null.
offer(element) Pushes element to the front of the queue.

Example

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // Create a Queue using LinkedList
        Queue<Integer> queue = new LinkedList<>();

        // Enqueue elements
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);

        // queue = [1, 2, 3, 4]

        // Peek at the front element without removing it
        Integer frontOfQueue = queue.peek();
        // frontOfQueue = 1
        // queue = [1, 2, 3, 4]
        
        // Dequeue elements
        Integer dequeuedElement = queue.poll();
        // dequeuedElement = 1
        // queue = [2, 3, 4]

        dequeuedElement = queue.poll();
        // dequeuedElement = 2
        // queue = [3, 4]
    }
}

1) Is Palindrome

Given a string, return true if the string is a palindrome, false if not. A palindrome is a word that is the same forward and backward (ex: kayak, racecar)

Input: racecar
Output: true

Input: palindrome
Output: false

2) Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

3) Time Needed to Buy Tickets

There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person initially at position k (0-indexed) to finish buying tickets.

Input: tickets = [2,3,2], k = 2
Output: 6

Input: tickets = [5,1,1,1], k = 0
Output: 8

4) Valid Parentheses

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

Valid Characters: (){}[]

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.
Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s - "{[()]}"
Output: true

Input: s = "([{"
Output: false

Input: s = "()[{]}"
Output: false

5) Use a stack to make a queue / Use a queue to make a stack

  • Create a stack out of queues, or a queue out of stacks.
  • If you are making a stack, you can use multiple queues, and vice versa.
  • Assume that only positive integers will be added.

STARTER CODE

class Solution {
     // HINT: You may want to initialize some variables here!

     public void push(int num) { }

     public int pop() { }

     public int peek() { }

     public boolean isEmpty() { }
}

TEST CASES

MyStack myStack = new MyStack();     // uses queues
myStack.push(1);       // [1]    → returns nothing
myStack.push(2);       // [2, 1] → returns nothing
myStack.peek();        // [2, 1] → returns 2
myStack.pop();         // [2]    → returns 2
myStack.isEmpty();     // returns False

MyQueue myQueue = new MyQueue();     // uses stacks
myQueue.push(1);       // [1]    → returns nothing
myQueue.push(2);       // [1, 2] → returns nothing
myQueue.peek();        // [1, 2] → returns 1
myQueue.pop();         // [2]    → returns 1
myQueue.isEmpty();     // returns False

Solution mySolution = new Solution();
mySolution.peek();     // [] → returns -1
mySolution.pop();      // [] → returns -1

Trial Problems

public class LinkedList{
    private class LinkedNode{
        private String msg;
        private int forwardSteps;
        private LinkedNode next;
        private LinkedNode prev;

        /*
        Class constructors for LinkedNode
        */
     }

    private int size = 0;
    private LinkedNode head;
    private LinkedNode tail;

    /*
    LinkedList constructor

    LinkedList functions
    */
}

1) Create Message

See the above LinkedList definition for this question. Given a circular doubly-linked list. Using the class variable msg containing a portion of the message, forwardSteps which contains the amount of nodes to move forward, and an integer n representing the number of nodes making up the message. Return the full message.

Input:
head = [AA, 1] ⇄ [B B, 2] ⇄ [C, 1] ⇄ [d, 0]
        ↑                             ↓
        └─────────────────────────────┘
n = 4

Output: AAB Bdd

Input:
head = [H, 5] ⇄ [E, 1] ⇄ [L, 1] ⇄ [L, 1] ⇄ [O, 1]
        ↑                                      ↓
        └──────────────────────────────────────┘
n = 4

Output: "HHHH"

2) Message Path

Return the LinkedNodes that created the message in the order you came across them.

public class LinkedList{
    private class LinkedNode{
        private String msg;
        private int forwardSteps;
        private int backwardSteps;
        private LinkedNode next;
        private LinkedNode prev;

        /*
        Class constructors for LinkedNode
        */
     }

    private int size = 0;
    private LinkedNode head;
    private LinkedNode tail;

    /*
    LinkedList constructor

    LinkedList functions
    */
}

Input:
head = [A, 1] ⇄ [B, 2] ⇄ [C, 1] ⇄ [D, 0]
        ↑                             ↓
        └─────────────────────────────┘
n = 4

Output: [A, 1] → [B, 2] → [D, 0] → [D, 0]

or

[[A, 1], [B, 2], [D, 0], [D, 0]]  // Array of LinkedNodes that still have their next and prev references

3) All Possible Messages

See the above modified LinkedList definition for this question. Given a circular doubly-linked list. Using the class variable msg containing a portion of the message, forwardSteps which contains the amount of nodes to move forward, backwardSteps which contains the amount of nodes to move backwards, and integer n representing the number of nodes making up the message. Return each possible message that can be generated by going either forwards or backwards.

Input:
head = [A, 1, 1] ⇄ [B, 1, 1] ⇄ [C, 1, 1] ⇄ [D, 1, 1]
        ↑                                        ↓
        └────────────────────────────────────────┘
n = 3

Output:
ABC
ABA
ADC
ADA

Explaination:
ABC: forward, forward
ABA: forward, backward
ADC: backward, backward
ADA: backward, forward