Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

---

Examples

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

---

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

---

Follow up

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

---

Examples

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no common subsequence, so the result is 0.

---

Constraints

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

The deletion can be divided into two stages:

1. Search for the node to remove.
2. If the node is found, delete it.

---

Examples

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. Node 3 has two children, so we replace it with its in-order successor (4).

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value 0, so the tree is unchanged.

Example 3:

Input: root = [], key = 0
Output: []

---

Constraints

• The number of nodes in the tree is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• Each node has a unique value.

Follow up: Can you solve it with time complexity O(height of tree)?

Flatten a Nested Array

Problem Description

Implement a flatten function that takes a nested array and returns a new array with the nesting removed. An optional depth parameter controls how many levels of nesting to flatten. If no depth is given, flatten completely.

This is a common interview question that tests recursion and array manipulation skills.

Function Signature

function flatten(arr: any[], depth?: number): any[]

Parameters

• arr — A potentially nested array.
• depth (optional) — The number of nesting levels to flatten. Defaults to Infinity (flatten completely).

Returns

A new flattened array.

Examples

Example 1

flatten([1, [2, 3], [4, [5]]]);
// [1, 2, 3, 4, 5]  (fully flattened)

Example 2

flatten([1, [2, [3, [4]]]], 1);
// [1, 2, [3, [4]]]  (one level)

Example 3

flatten([1, [2, [3, [4]]]], 2);
// [1, 2, 3, [4]]  (two levels)

Example 4

flatten([1, 2, 3]);
// [1, 2, 3]  (already flat)

Constraints

• The array can contain any values including nested arrays.
• 0 <= depth <= Infinity
• Do not mutate the original array.

Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 Output: 700 Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through city 1 and 2 is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200

Constraints:

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 10^4
• There will not be any multiple flights between two cities.
• 0 <= src, dst, k < n
• src != dst

Movie Rating

Table Schema

CREATE TABLE Movies (
    movie_id INT PRIMARY KEY,
    title VARCHAR(255)
);

CREATE TABLE Users (
    user_id INT PRIMARY KEY,
    name VARCHAR(255)
);

CREATE TABLE MovieRating (
    movie_id INT REFERENCES Movies(movie_id),
    user_id INT REFERENCES Users(user_id),
    rating INT,
    created_at DATE,
    PRIMARY KEY (movie_id, user_id)
);

Problem Statement

Write a SQL query to:

1. Find the name of the user who has rated the greatest number of movies. In case of a tie, return the lexicographically smaller user name.
2. Find the movie name with the highest average rating in February 2020. In case of a tie, return the lexicographically smaller movie name.

The result should have a single column results with two rows — the user name first, then the movie name.

Example 1

Input:

Movies table: | movie_id | title | |----------|----------| | 1 | Avengers | | 2 | Frozen 2 | | 3 | Joker |

Users table: | user_id | name | |---------|--------| | 1 | Daniel | | 2 | Monica | | 3 | Maria | | 4 | James |

MovieRating table: | movie_id | user_id | rating | created_at | |----------|---------|--------|------------| | 1 | 1 | 3 | 2020-01-12 | | 1 | 2 | 4 | 2020-02-11 | | 1 | 3 | 2 | 2020-02-12 | | 1 | 4 | 1 | 2020-01-01 | | 2 | 1 | 5 | 2020-02-17 | | 2 | 2 | 2 | 2020-02-01 | | 2 | 3 | 2 | 2020-03-01 | | 3 | 1 | 3 | 2020-02-22 | | 3 | 2 | 4 | 2020-02-25 |

Output:

| results | |----------| | Daniel | | Frozen 2 |

Explanation: Daniel rated 3 movies, Monica rated 3 movies — Daniel is alphabetically first. In Feb 2020, Frozen 2 average = (5+2)/2 = 3.5, Avengers = (4+2)/2 = 3, Joker = (3+4)/2 = 3.5. Frozen 2 wins alphabetically.

Constraints

• Each user can rate each movie only once.
• Rating is between 1 and 5.

Design Search Autocomplete System

Design a real-time search autocomplete system similar to Google Search or Amazon's search bar. When a user types a prefix, the system should suggest the top $K$ (e.g., 5-10) most relevant and popular completed queries.

Requirements

Functional Requirements

1. Top K Suggestions: Return the most popular/relevant completions starting with the given prefix.
2. Frequency Tracking: When a user completes a search, its popularity score should be updated.
3. Real-time Performance: Suggestions must appear as the user types, requiring extremely low latency.

Non-Functional Requirements

1. Low Latency: The response time for each character typed should be under 100ms.
2. High Scalability: Handle billions of searches per day and a massive dictionary of potential queries.
3. High Availability: The system must remain operational even if some backend components fail.
4. Accuracy: Suggestions should be relevant and spelled correctly.

Architectural Components

1. Data Structure: Trie

A Trie (Prefix Tree) is the classic choice for storing strings for prefix-based recovery.

• Each node represents a character.
• To speed up queries, each node can store the top $K$ results for its prefix directly, avoiding a full tree traversal during a live search.

2. Scaling: Sharding

How do you shard a Trie across multiple servers?

• By First Character: Server A handles prefixes starting with 'a', Server B for 'b', and so on.
• Pros: Easy to implement.
• Cons: Uneven distribution (e.g., 's' and 't' are more common than 'x' and 'z').
• Solution: Use consistent hashing or a range-based partition mapping (e.g., 'a-m' on one node, 'n-z' on another).

3. Updating Popularity: The Aggregation Service

Query frequencies shouldn't be updated in the Trie in real-time for every single keystroke.

Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

---

Examples

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

---

Constraints

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

• For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"], but it is lexically larger.

Constraints:

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• from_i.length == 3, to_i.length == 3
• $from_i$ and $to_i$ consist of uppercase English letters.

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

---

Examples

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

---

Constraints

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

---

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

Maximum Width of Binary Tree

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

---

Examples

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).

---

Constraints

• The number of nodes in the tree is in the range [1, 3000].
• -100 <= Node.val <= 100

Implement Debounce

Problem Description

Implement a debounce function that delays invoking the provided function until after delay milliseconds have elapsed since the last time the debounced function was invoked.

Debouncing is a common technique used in web development to limit the rate at which a function fires. It is particularly useful for handling events that fire rapidly, such as keyup, scroll, or resize.

Function Signature

function debounce(fn: (...args: any[]) => void, delay: number): (...args: any[]) => void

Parameters

• fn — The function to debounce.
• delay — The number of milliseconds to delay.

Returns

A new debounced function. Each time the debounced function is called, it resets the timer. The original function fn is only called once the debounced function stops being called for delay milliseconds.

Examples

Example 1

let count = 0;
const increment = debounce(() => { count++; }, 100);

increment(); // Timer starts
increment(); // Timer resets
increment(); // Timer resets
// After 100ms of no calls, count becomes 1

Example 2

const log = debounce((msg: string) => console.log(msg), 200);

log("a"); // Timer starts
log("b"); // Timer resets — "a" is never logged
// After 200ms: logs "b"

Example 3

const search = debounce((query: string) => fetchResults(query), 300);

// User types "react" quickly:
search("r");
search("re");
search("rea");
search("reac");
search("react");
// Only fetchResults("react") is called after 300ms pause

Constraints

• 0 <= delay <= 10000
• fn is a valid callable function
• The debounced function must forward all arguments to fn
• The debounced function must maintain the correct context