Panda Web

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

HARD

6) Simplify Path

Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.

The canonical path should have the following format:

The path starts with a single slash '/'.
Any two directories are separated by a single slash '/'.
The path does not end with a trailing '/'.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Input: path = "/home/"
Output: "/home"
Explanation: The trailing slash should be removed.

Input: path = "/home/user/Documents/../Pictures"
Output: "/home/user/Pictures"
Explanation: A double period ".." refers to the directory up a level (the parent directory).

Input: path = "/E/a/../b/c/../d/./"
Output: "/E/b/d"
Explanation: A single period '.' represents the current directory.