Practice DSA interview questions

Given a string `s`, find the length of the longest substring that contains at most two distinct characters. This is a classic sliding window problem. The window should contain at most two distinct characters at any time.

A gene string can be represented by an 8-character string with characters 'A', 'C', 'G', 'T'. Given a `start` gene string, an `end` gene string, and a `bank` of valid gene strings, find the minimum number of mutations needed to get from `start` to `end`. This is a shortest path problem, perfect for BFS.

Design a file system class with `create`, `read`, `write`, `ls`, and `mkdir` operations. This is a design problem that can be solved by modeling the file system structure with a tree data structure and using a hash map to map paths to nodes.

Design a data structure that supports adding a new number and finding the median of the numbers. A median is the middle value in an ordered integer list. If the size of the list is even, there is no single middle value, so the median is the average of the two middle values. This problem is about designing a data structure for efficient median calculation.

Serialize and deserialize a Binary Search Tree (BST). This is a specialized version of the general Binary Tree serialization problem. The key is to leverage the BST property to simplify the reconstruction process, as the in-order traversal of a BST is always sorted.

Given a sorted array `arr`, two integers `k` and `x`, return the `k` closest integers to `x` in the array. The result should also be sorted in ascending order. If there's a tie, the smaller element should be preferred. This problem can be solved with binary search to find a good starting point and then using two pointers to expand outwards.

Given a characters array `tasks`, representing the tasks a CPU needs to do, where each letter represents a different task. You are also given a non-negative integer `n` that represents the cooldown period between two same tasks. Return the least number of intervals the CPU requires to finish all the given tasks. This problem is a scheduling problem that can be solved with a greedy approach.

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither. The rules for a valid IPv4 and IPv6 address are strict and involve checking for valid numbers, lengths, and character sets. This is a string parsing problem that requires careful handling of multiple conditions.

Given an `m x n` grid of characters and a string `word`, return true if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. This is a backtracking problem.

Given a string containing digits from `2-9` inclusive, return all possible letter combinations that the number could represent. This is a classic backtracking or recursive problem.

A peak element is an element that is strictly greater than its neighbors. Given an integer array `nums`, find a peak element and return its index. If the array contains multiple peaks, return the index to any of them. You can assume `nums[-1] = nums[n] = -inf`. This problem is a classic application of binary search, which can find a peak in O(log n) time.

Write an efficient algorithm that searches for a `target` value in an `m x n` integer `matrix`. The matrix has the following properties: integers in each row are sorted from left to right, and the first integer of each row is greater than the last integer of the previous row. This structure allows us to use a form of binary search.

You have `n` binary tree nodes labeled from `0` to `n-1`. You are given two integer arrays `leftChild` and `rightChild` of length `n`, where `leftChild[i]` and `rightChild[i]` are the labels of the left and right children of the `i`-th node. Return true if and only if all the given nodes form a valid binary tree. This problem tests your understanding of tree properties and can be solved by checking for a single root, connectivity, and acyclicity.

Design a time-based key-value data structure. It should support two operations: `set(key, value, timestamp)` and `get(key, timestamp)`. `set` stores the value for the given key at the given timestamp. `get` retrieves the value of the given key at the closest timestamp less than or equal to the given timestamp. If no such timestamp exists, return an empty string. This is a design problem that requires using a suitable data structure to handle the timestamp queries efficiently.

Given an array of strings `words` and a string `chars`, return the sum of lengths of all good strings in `words`. A string is good if it can be formed by characters from `chars` (each character can only be used once). This is a character counting and frequency comparison problem.

Given an `m x n` matrix, return all elements of the matrix in spiral order. This is a simulation problem where you need to carefully handle the boundaries as you traverse the matrix in a spiral pattern. The key is to manage four boundary pointers.

Given an `m x n` matrix of integers, find the length of the longest increasing path. An increasing path is a sequence of adjacent cells where each cell's value is strictly greater than the previous one. This can be solved with dynamic programming and memoization to avoid redundant computations.

You are given an `m x n` 2D grid initialized with three possible values: `-1` (a wall or an obstacle), `0` (a gate), and `inf` (an empty room). Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave `inf`. This is a multi-source shortest path problem, which is a perfect use case for Breadth-First Search (BFS).

You want to build a house on an empty land that is `0` and travel a minimum total distance to all buildings `1`. You are given a 2D grid of values. This is a multi-source shortest path problem, similar to Walls and Gates, but more complex because we must consider distances to all buildings.

Given an array `nums` and a target value `k`, find the maximum length of a subarray that sums to `k`. If no such subarray exists, return 0. This is a classic problem that can be solved efficiently with a hash map to store prefix sums.

TinyURL is a URL shortening service where you enter a URL and get a short URL back. Design the TinyURL's encode and decode methods. There is no restriction on how your encoder/decoder should work. This is a design problem that can be solved with a hash map to store the mapping between long and short URLs.

Given a file and a function `read4` that reads 4 bytes at a time, implement a function `read` that reads `n` bytes. The function `read4` returns the number of actual bytes read. This problem is about managing a buffer to correctly read the required number of characters, especially when the file size is not a multiple of 4.

Extend the `read` function from the previous problem to be callable multiple times. This means we must persist the internal buffer and its state across multiple calls. The core logic remains the same, but the state management is crucial.

Design a leaderboard that supports three operations: `addScore(playerId, score)`, `top(K)`, and `reset(playerId)`. `addScore` updates a player's score. `top` returns the sum of the scores of the top `K` players. `reset` removes a player's score. This is a design problem that requires a combination of data structures for efficiency.

Given an array of strings `words` and a width `maxWidth`, format the text into lines that are justified. Each line should contain as many words as possible. The lines are then justified by distributing extra spaces. This problem is a text formatting problem with specific rules for justification.

Given a string `s`, you can convert it to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation. This problem can be solved by finding the longest palindromic prefix of the string and then using it to build the shortest palindrome.

Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)). This is a classic and challenging binary search problem.

Given an unsorted integer array `nums`, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space. This is a trickier problem that requires using the array itself to store information.

Given an array of integers `heights` representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. This problem can be solved with a stack to efficiently find the left and right boundaries for each bar.

Given an encoded string, return its decoded string. The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is repeated exactly `k` times. This problem can be solved using two stacks, one for numbers and one for strings.