Practice DSA interview questions

You have a `RecentCounter` class which counts the number of recent requests within a certain time frame. Implement the `RecentCounter` class: `RecentCounter()` initializes the counter with zero recent requests. `int ping(int t)` adds a new request at time `t`, where `t` represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (inclusive). Specifically, return the number of requests that have happened in the time range `[t - 3000, t]`. A queue is the perfect data structure for this.

Design a data structure that implements 'k' queues using a single array of size 'n'. The challenge is to manage the array space efficiently. This tests your ability to manage pointers and array indices creatively. A common approach uses a 'free' list to manage available space and additional arrays to track the front, rear, and next element for each queue.

Design an algorithm to find the first non-repeating character in a continuous stream. Implement a class that supports `add(char)` and `getFirstUnique()`. If no unique character exists, return '#'. This problem requires maintaining the state of character counts and their order of appearance. A queue is ideal for tracking the order, and a hash map is perfect for tracking counts.

Given a positive integer `n`, write a function to generate and return all binary numbers from 1 to `n` in string format. For example, if `n = 3`, the output should be `['1', '10', '11']`. This problem can be solved elegantly using a queue (specifically, BFS). The core idea is that any binary number can be used to generate the next 'level' of binary numbers by appending a '0' and a '1' to it. A queue helps us process these numbers in the correct order.

Given a queue, write a function to reverse its elements. The only operations allowed on the queue are the standard `enqueue()`, `dequeue()`, `front()`, `isEmpty()`, and `size()`. You cannot use any other data structure explicitly, but you can use the call stack (i.e., recursion). This problem is a classic example of using recursion to simulate the behavior of a stack. The call stack holds the elements as they are dequeued, and on the way back up, they are enqueued in reverse order.

Implement a LIFO (Last-In-First-Out) stack using only one queue and its standard operations (enqueue, dequeue, front, size, isEmpty). The implemented stack should support all functions of a normal stack: `push`, `pop`, `top`, and `empty`. This is a clever puzzle that requires you to manipulate the queue's FIFO property to simulate LIFO. The key is to rotate the queue after each `push` operation so that the newly added element moves to the front, effectively becoming the 'top' of the stack.

There are `n` friends playing a game, sitting in a circle and numbered from 1 to `n`. The game proceeds in rounds. In each round, you start from the `k`-th friend and count `k` friends clockwise, and the last one you count is removed. This repeats until only one friend remains. The goal is to find the number of the friend who remains last. This classic problem, known as the Josephus Problem, can be simulated directly using a queue.

You are given an integer array `deck` representing a deck of cards. You pick up the deck and reveal the cards one by one: 1. Take the top card, reveal it, and remove it. 2. If there are still cards, move the new top card to the bottom. 3. Repeat. Return an ordering of the deck that would reveal the cards in increasing order. This problem is a 'reverse simulation' that can be solved with a queue.

In the world of Dota2, there are two parties, Radiant and Dire. Given a string `senate` ('R' or 'D'), we need to predict which party will win. Each senator can either ban one senator from the other party or announce victory. If a senator bans another, the banned senator is removed. This can be solved greedily using queues.

There are `n` rooms, and you are given an array `rooms` where `rooms[i]` is a list of keys in that room. Each key `v` opens room `v`. Initially, all rooms are locked except for room 0. Return `true` if you can visit all rooms, and `false` otherwise. This is a graph traversal problem. You can use either Depth-First Search (DFS) with a stack or Breadth-First Search (BFS) with a queue to see if all nodes (rooms) are reachable from the starting node (room 0).

Given an `n x n` binary matrix `grid`, return the length of the shortest clear path in the matrix. If there is no clear path, return -1. A clear path is a path from `(0, 0)` to `(n-1, n-1)` such that all visited cells are `0` and all adjacent cells in the path are 8-directionally connected. This is a classic shortest path problem on an unweighted graph, which is a perfect application for Breadth-First Search (BFS) using a queue.

Given an array `arr`, find the sum of `min(b)` for every possible contiguous subarray `b`. Since the answer may be large, return the answer modulo 10^9 + 7. This problem can be solved in O(n) time using a monotonic stack. The key is to find, for each element `arr[i]`, its 'previous less element' (PLE) and 'next less element' (NLE). `arr[i]` will be the minimum for all subarrays between its PLE and NLE.

Given a circular integer array `nums`, return the *next greater element* for every element. The next greater element of `x` is the first greater number to its traversing-order next in the array, which means you could search circularly. If one does not exist, return -1. This is a variation of the 'Next Greater Element' problem. To handle the circularity, we can iterate through the array twice.

A parentheses string is valid if: it is empty, it can be written as `AB` (`A` concatenated with `B`), or it can be written as `(A)`, where `A` is valid. Given a parentheses string `s`, return the minimum number of parentheses ( `(` or `)` ) we must add to make the string valid. This problem can be solved by tracking the balance of open and closed parentheses.

Given two strings `s` and `t`, return `true` if they are equal when both are typed into empty text editors. A `#` character means a backspace character, which deletes the last typed character. This problem can be perfectly simulated using stacks. We 'build' the final string for both `s` and `t` by processing the backspaces with a stack, and then compare the results.

You are given a list of strings `operations`. You start with an empty record. The operations are: `x` (an integer) - record a new score of `x`. `+` - record a new score that is the sum of the previous two scores. `D` - record a new score that is double the previous score. `C` - invalidate the previous score, removing it from the record. Return the sum of all scores on the record. A stack is the perfect data structure to manage this record.

A valid parentheses string `s` is 'primitive' if it cannot be split into `s = A + B` with `A` and `B` being non-empty valid parentheses strings. Given `s`, consider its primitive decomposition: `s = P_1 + ... + P_k`. Return `s` after removing the outermost parentheses of every primitive string in the decomposition. This can be solved by tracking the 'balance' of the parentheses and only appending when parentheses are not 'outer'.

Design a stack that supports `push`, `pop`, `top`, and an `increment(k, val)` operation. `increment(k, val)` adds `val` to the bottom `k` elements of the stack. If there are fewer than `k` elements, it increments all. This problem requires a modification to the standard stack. One efficient way is to store the increments lazily, applying them only when elements are popped.

Design a stack-like data structure that supports `push` and `pop`. `push(val)` pushes `val` onto the stack. `pop()` removes and returns the element with the **highest frequency**. If there is a tie in frequency, the element closest to the top (most recently pushed) is popped. This requires tracking element frequencies and the order of elements within each frequency group. A 'stack of stacks' approach is effective.

You are given a string `s` that consists of lower case English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one. The result should not contain any brackets. For example, `(u(love)i)` becomes `(uevoli)` and then `iloveu`. This problem has a nested structure. A clever O(n) approach involves pre-calculating 'portals' between matching parentheses.

Given a string containing just the characters `(` and `)`, find the length of the longest valid (well-formed) parentheses substring. For example, in `(()`, the longest valid substring is `()` with length 2. In `()()`, it's `()()` with length 4. This is a classic problem that can be solved efficiently in O(n) time using a stack. The stack helps track the indices of 'unmatched' parentheses.

Given `n` non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. This is a classic interview problem that can be solved in multiple ways, including a dynamic programming approach or a two-pointer approach. However, it can also be solved elegantly using a monotonic (decreasing) stack. The stack stores the indices of the bars, and when we find a bar taller than the stack's top, we can calculate the water trapped on the popped bar.

Given an integer array `nums`, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order. Return the length of the shortest such subarray. This problem can be solved in O(n) time and O(n) space using a stack. The idea is to find the incorrect positions of the minimum and maximum elements in the unsorted part. A monotonic stack helps find the boundaries where the sorting is violated.

You are given an integer array `nums`. The range of a subarray is the difference between the largest and smallest element in the subarray. Return the sum of all subarray ranges. A naive O(n^2) solution finds the min and max for each subarray. However, a much more efficient O(n) solution exists using monotonic stacks. The logic is similar to 'Sum of Subarray Minimums'. We can find the sum of all subarray maximums and subtract the sum of all subarray minimums.

There are `n` people in a queue, and you are given their heights in an array `heights`. A person `i` can see person `j` if `i < j` and everyone in between is shorter than both of them. More formally, `min(heights[i], heights[j]) > max(heights[i+1], ..., heights[j-1])`. Return an array `answer` where `answer[i]` is the number of people person `i` can see. This problem can be solved efficiently using a monotonic stack. We iterate from right to left.

Given an integer array `nums` and an integer `k`, return the length of the shortest non-empty subarray of `nums` with a sum of at least `k`. If there is no such subarray, return -1. This problem is tricky because the array can contain negative numbers, which means the prefix sum array is not monotonically increasing, and a standard sliding window won't work. The optimal solution uses a monotonic deque (double-ended queue) to store indices of the prefix sum array.

A ramp in an integer array `nums` is a pair of indices `(i, j)` with `i < j` and `nums[i] <= nums[j]`. The width of such a ramp is `j - i`. Return the maximum width of a ramp in `nums`. If there is no ramp, return 0. A naive O(n^2) solution will time out. An efficient O(n) solution can be achieved using a stack. The key is to create a monotonic (decreasing) stack of indices that are candidates for the `i` (left side) of the ramp.

Implement a basic stack data structure that supports `push`, `pop`, `top` (or `peek`), and `isEmpty` operations. However, instead of using a dynamic array (like a Python list), the underlying data structure must be a singly linked list. This is a foundational data structures problem. The 'top' of the stack will be the 'head' of the linked list. This ensures that `push` and `pop` operations are O(1).

Implement a basic queue data structure that supports `enqueue` (add to back), `dequeue` (remove from front), `front` (peek at front), and `isEmpty` operations. The underlying data structure must be a singly linked list. To achieve O(1) `enqueue` and `dequeue` operations, you must maintain pointers to both the `head` (front) and the `tail` (back) of the linked list. This is a foundational problem.

Given an array `arr` of positive integers, consider all binary trees where `arr` values are the leaves, in-order. Each non-leaf node's value is the product of the largest leaf value in its left and right subtree. Find the minimum sum of all non-leaf node values. This problem can be modeled as finding the optimal 'pairing' of leaf nodes. A greedy approach using a monotonic stack provides an efficient O(n) solution.