Queue

Problem Given a stack of N elements, interleave the first half of the stack with the second half reversed using only one other queue. This should be done in-place. Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue. Hint: Try working backwards from the end state. Examples Example 1: Input: stack = [1, 2, 3, 4, 5] Output: [1,5,2,4,3] Explanation: We interleave first and last element first - 1, 5, then we interleave 2nd and 2nd last element, 2, 4 and then finally middle element 3. ...

Problem Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit. Examples Example 1: Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff |7-7| = 0 <= 4. Therefore, the size of the longest subarray is 2. ...

Problem Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects. ...

Problem You are given an array representing the heights of neighboring buildings on a city street, from east to west. The city assessor would like you to write an algorithm that returns how many of these buildings have a view of the setting sun, in order to properly value the street. Assumption: Good to clarify with the interviewer, if the heights are equal? For this problem, equal height building don’t obstruct the view, and should be included in answer. ...

Problem Given a string and a set of delimiters, reverse the words in the string while maintaining the relative order of the delimiters. For example, given “hello/world:here”, return “here/world:hello” Follow-up Does your solution work for the following cases: "hello/world:here/", "hello//world:here" Examples Example 1: Input: s = hello/world:here Output: here/world:hello Solution Method 1 - Using stack to store words and queue for delimiters Code Java class Solution { public String reverseWords(String s) { Stack<String> stack = new Stack<>(); Queue<String> queue = new LinkedList<>(); StringBuilder word = new StringBuilder(); int i = 0; while (i < s.length()) { char c = s.charAt(i); if (Character.isLetterOrDigit(c)) { word.append(c); i++; } else { if (word.length() > 0) { stack.push(word.toString()); } word = new StringBuilder(); // clear word for next word StringBuilder delim = new StringBuilder(); delim.append(c); i++; // tracking continuous delimiter to add to queue while (i < s.length() && !Character.isLetterOrDigit(s.charAt(i))) { delim.append(c); i++; } queue.add(delim.toString()); } } // if string ends with words if (word.length() != 0) { stack.push(word.toString()); } boolean isWordFirst = Character.isLetterOrDigit(s.charAt(0)); StringBuilder sb = new StringBuilder(); // if word is not first, add 1 entry from queue if (!isWordFirst) { if (!queue.isEmpty()) { sb.append(queue.remove()); } } // now put 1 element from either till not empty while (!stack.isEmpty() || !queue.isEmpty()) { if (!stack.isEmpty()) { sb.append(stack.pop()); } if (!queue.isEmpty()) { sb.append(queue.remove()); } } return sb.toString(); } } ...

Problem There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker. We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules: Every worker in the paid group must be paid at least their minimum wage expectation. In the group, each worker’s pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker. Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within $10^{-5}$ of the actual answer will be accepted. ...

Problem You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k. For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j]. Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j]. ...

Problem You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Sometimes k is also denoted as w. Example Example ...

Problem Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement the MyQueue class: void push(int x) Pushes element x to the back of the queue. int pop() Removes the element from the front of the queue and returns it. int peek() Returns the element at the front of the queue. boolean empty() Returns true if the queue is empty, false otherwise. Notes: ...

Problem Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the MyStack class: void push(int x) Pushes element x to the top of the stack. int pop() Removes the element on the top of the stack and returns it. int top() Returns the element on the top of the stack. boolean empty() Returns true if the stack is empty, false otherwise. Notes: ...