Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

---

Examples

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

---

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

---

Examples

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

---

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

---

Examples

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

---

Constraints

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

---

Follow up:

Could you do it in O(n) time and O(1) space?

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

---

Examples

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are 2 courses. To take course 1 you need to take course 0. This is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are 2 courses. To take course 1 you need to take course 0, and to take course 0 you also need to take course 1. This creates a cycle, so it is impossible to finish all courses.

---

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Longest Word in Dictionary

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Note that the word should be built from left to right with each additional character being added to the end of the previous word.

---

Examples

Example 1:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

---

Constraints

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 30
• words[i] consists of lowercase English letters.

Minimum Spanning Tree

Given an undirected connected graph with n vertices (numbered 0 to n-1) and a list of edges, where edges[i] = [u, v, weight], find the total weight of the Minimum Spanning Tree (MST).

A Minimum Spanning Tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Example 1:

Input: n = 4, edges = [[0,1,1],[1,2,2],[2,3,3],[0,3,4],[0,2,5]] Output: 6 Explanation: The MST includes edges (0,1), (1,2), and (2,3) with weights 1+2+3 = 6.

Example 2:

Input: n = 3, edges = [[0,1,5],[1,2,1],[0,2,1]] Output: 2 Explanation: The MST includes edges (1,2) and (0,2) with weights 1+1 = 2.

Constraints:

• 1 <= n <= 10^4
• n-1 <= edges.length <= 10^5
• 0 <= edges[i][2] <= 10^6 (weight)
• The graph is guaranteed to be connected.

Design a URL Shortener

Problem Description

Design and implement a URL shortening service similar to bit.ly or TinyURL. The system should generate short, unique aliases for long URLs, resolve short URLs back to originals, handle high read traffic with caching, and provide click analytics.

Requirements

Functional Requirements

1. Shorten URL: Given a long URL, generate a unique short URL
2. Redirect: Given a short URL, redirect to the original long URL
3. Custom Aliases: Allow users to specify custom short codes
4. Expiration: Support optional TTL on shortened URLs
5. Analytics: Track click count, referrers, geolocation

Non-Functional Requirements

• Handle 100M total URLs in the database
• Support 10K URL redirections per second (read-heavy)
• Short URLs should be 6-8 characters long
• System should be highly available (99.9% uptime)
• Redirect latency < 100ms

Scale Estimates

• Write: ~100 URL shortenings per second
• Read: ~10,000 URL redirections per second (100:1 read/write ratio)
• Storage: 100M URLs * 500 bytes = ~50GB
• Cache: Top 20% of URLs handle 80% of traffic

API Design

POST /api/shorten
  Body: { url: string, customAlias?: string, expiresAt?: string }
  Response: { shortUrl: string, shortCode: string, createdAt: string }

GET /:shortCode
  Response: 301 Redirect to original URL

GET /api/analytics/:shortCode
  Response: { totalClicks: number, clicksByDay: [...], topReferrers: [...] }

Examples

Example 1: Shorten a URL

POST /api/shorten
{ "url": "https://example.com/very/long/article/about/system-design" }

Response (201):
{
  "shortUrl": "https://short.ly/a1B2c3",
  "shortCode": "a1B2c3",
  "originalUrl": "https://example.com/very/long/article/about/system-design",
  "createdAt": "2024-01-15T10:00:00Z"
}

Example 2: Custom Alias

POST /api/shorten
{ "url": "https://example.com/promo", "customAlias": "sale2024" }

Response (201):
{ "shortUrl": "https://short.ly/sale2024", "shortCode": "sale2024" }

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

---

Examples

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount = 2 + 9 + 1 = 12.

Example 3:

Input: nums = [2,1,1,2]
Output: 4
Explanation: Rob house 1 (money = 2) and house 4 (money = 2).
Total amount = 2 + 2 = 4.

---

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

All Nodes Distance K in Binary Tree

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

Example 2:

Input: root = [1], target = 1, k = 3 Output: []

Constraints:

• The number of nodes in the tree is in the range [1, 500].
• 0 <= Node.val <= 500
• All Node.val are unique.
• target is the value of one of the nodes in the tree.
• 0 <= k <= 1000

Asteroid Collision

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5] Output: [5,10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8] Output: [] Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. Then 10 and -5 collide resulting in 10.

Constraints:

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Unique Paths II

You are given an m x n integer array obstacleGrid. There is a robot initially located at the top-left corner (i.e., obstacleGrid[0][0]). The robot tries to move to the bottom-right corner (i.e., obstacleGrid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 and 0 respectively in the grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

---

Examples

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

---

Constraints

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous non-empty sequence of elements within an array.

---

Examples

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

---

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

---

Follow-up

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.