E
EduScale
319 challenges in the catalogue. Browse freely; sign in to open the editor and submit.
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.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9, so we return [0, 1].
Example 2:
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: nums[1] + nums[2] = 2 + 4 = 6.
Example 3:
Input: nums = [3, 3], target = 6
Output: [0, 1]
Explanation: Both elements are 3 and their sum is 6.
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9Can you come up with an algorithm that is less than O(n²) time complexity?
Implement a caching layer service that sits between your API and database, using Redis-like semantics. The cache should support TTL-based expiration, multiple caching strategies (cache-aside, write-through), and handle common cache problems like stampede and invalidation.
interface CacheService {
get<T>(key: string): Promise<T | null>;
set(key: string, value: any, ttlSeconds?: number): Promise<void>;
delete(key: string): Promise<boolean>;
getOrSet<T>(key: string, fetcher: () => Promise<T>, ttlSeconds?: number): Promise<T>;
mget<T>(keys: string[]): Promise<(T | null)[]>;
mset(entries: { key: string; value: any; ttl?: number }[]): Promise<void>;
invalidatePattern(pattern: string): Promise<number>;
getStats(): CacheStats;
}
// First call - cache MISS, fetches from database
const user = await cache.getOrSet('user:123', async () => {
return await db.users.findById(123);
}, 300);
// Returns: { data: {...}, source: 'database' }
// Second call - cache HIT
const user2 = await cache.getOrSet('user:123', fetchFn, 300);
// Returns: { data: {...}, source: 'cache' }
await cache.set('session:abc', { userId: 1 }, 60);
// After 60 seconds...
const session = await cache.get('session:abc');
// Returns: null (expired)
await cache.set('user:1:profile', {...});
await cache.set('user:1:posts', [...]);
await cache.set('user:2:profile', {...});
const count = await cache.invalidatePattern('user:1:*');
// Returns: 2 (deleted user:1:profile and user:1:posts)
Build a collaborative filtering recommendation engine using user-based cosine similarity. Given a user-item rating matrix, predict ratings for items a user hasn't rated and recommend the top items.
function recommend(
ratings: number[][],
userId: number,
numRecs: number
): { recommendations: number[] }
ratings: 2D array (users x items), 0 means unrated, 1-5 are ratingsuserId: Target user indexnumRecs: Number of recommendations to returnInput:
ratings = [
[5, 3, 0, 1],
[4, 0, 0, 1],
[1, 1, 0, 5],
[1, 0, 0, 4],
[0, 1, 5, 4]
]
userId = 0, numRecs = 2
Output:
recommendations = [2, 3]
Explanation:
User 0 has not rated items 2 and 3. Using cosine similarity
with other users to predict those ratings, item 2 gets a higher
predicted score than item 3 (or vice versa based on similarity).
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.[0,1,2,4,5,6,7] if it was rotated 7 times.Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums are unique.nums is sorted and rotated between 1 and n times.You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if both squares have an elevation at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
You start at the top left square (0, 0). What is the least time t until you can reach the bottom right square (n - 1, n - 1)?
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid[0][0] = 0.
You cannot go anywhere until time 2, when you can swim to grid[0][1] and grid[1][0].
At time 3, the entire grid is connected, and you can reach (1,1).
Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
n == grid.lengthn == grid[i].length1 <= n <= 500 <= grid[i][j] < n^2grid[i][j] is unique.Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation: At speed 4, Koko needs ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 hours.
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation: With 5 piles and 5 hours, she needs to eat each pile in 1 hour, so k = max(piles) = 30.
Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Explanation: At speed 23, she needs 2+1+1+1+1 = 6 hours.
1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9Create production-ready Kubernetes manifests for deploying a containerized application. Your configuration must include a Deployment, Service, HorizontalPodAutoscaler, and Ingress.
Given an application configuration, generate complete Kubernetes YAML manifests that follow best practices for production workloads.
maxUnavailable: 0 and maxSurge: 1replicas (min) and replicas * 3 (max)Example 1:
Input: {
name: "api",
image: "myregistry/api:v1.0.0",
replicas: 3,
port: 3000,
resources: { cpu: "500m", memory: "512Mi" }
}
Output: (4 YAML documents separated by ---)
apiVersion: apps/v1
kind: Deployment
metadata:
name: api
spec:
replicas: 3
strategy:
type: RollingUpdate
rollingUpdate:
maxUnavailable: 0
maxSurge: 1
selector:
matchLabels:
app: api
template:
spec:
containers:
- name: api
image: myregistry/api:v1.0.0
ports:
- containerPort: 3000
resources:
requests:
cpu: "250m"
memory: "256Mi"
limits:
cpu: "500m"
memory: "512Mi"
livenessProbe:
httpGet:
path: /health
port: 3000
readinessProbe:
httpGet:
path: /ready
port: 3000
...
Each node in a tree can be one of three types:
Write a solution to report the type of each node in the Tree table.
| Column Name | Type | | :--- | :--- | | id | int | | p_id | int |
id is the primary key for this table.
Each row of this table contains information about the id of a node and the id of its parent node.
Input: Tree table: | id | p_id | | :--- | :--- | | 1 | null | | 2 | 1 | | 3 | 1 | | 4 | 2 | | 5 | 2 |
Output: | id | type | | :--- | :--- | | 1 | Root | | 2 | Inner | | 3 | Leaf | | 4 | Leaf | | 5 | Leaf |
Explanation:
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
| Symbol | Value | |--------|-------| | I | 1 | | V | 5 | | X | 10 | | L | 50 | | C | 100 | | D | 500 | | M | 1000 |
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.X can be placed before L (50) and C (100) to make 40 and 90.C can be placed before D (500) and M (1000) to make 400 and 900.Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
1 <= s.length <= 15Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder and inorder consist of unique values.inorder also appears in preorder.preorder is guaranteed to be the preorder traversal of the tree.inorder is guaranteed to be the inorder traversal of the tree.A Segment Tree is a powerful data structure that allows for efficient range queries and range updates.
In this challenge, you will implement a Segment Tree that supports two operations on an array nums:
[l, r] by val.[l, r].To achieve $O(\log N)$ for both operations, you must use Lazy Propagation.
Input: nums = [1, 2, 3, 4, 5]
query(0, 2) -> Returns 6 (1 + 2 + 3)update(1, 3, 2) -> nums becomes [1, 4, 5, 6, 5]query(0, 2) -> Returns 10 (1 + 4 + 5)1 <= nums.length <= 10^50 <= l <= r < nums.length10^5 calls to update and query.s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').s is a valid roman numeral in the range [1, 3999].