E
EduScale
319 challenges in the catalogue. Browse freely; sign in to open the editor and submit.
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than $O(n^2)$.
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13.
Input: matrix = [[-5]], k = 1
Output: -5
n == matrix.length == matrix[i].length1 <= n <= 300-10^9 <= matrix[i][j] <= 10^91 <= k <= n^2Follow up:
CREATE TABLE Activity (
player_id INT,
device_id INT,
event_date DATE,
games_played INT,
PRIMARY KEY (player_id, event_date)
);
Each row is a record of a player who logged in and played some number of games (possibly 0) using some device on a given date.
Write a SQL query to report the first login date for each player.
Return the result table with columns player_id and first_login in any order.
Input:
Activity table: | player_id | device_id | event_date | games_played | |-----------|-----------|------------|--------------| | 1 | 2 | 2016-03-01 | 5 | | 1 | 2 | 2016-05-02 | 6 | | 2 | 3 | 2017-06-25 | 1 | | 3 | 1 | 2016-03-02 | 0 | | 3 | 4 | 2018-07-03 | 5 |
Output:
| player_id | first_login | |-----------|-------------| | 1 | 2016-03-01 | | 2 | 2017-06-25 | | 3 | 2016-03-02 |
Explanation: Player 1 first logged in on 2016-03-01. Player 2 first on 2017-06-25. Player 3 first on 2016-03-02.
event_date is a valid date.The Tribonacci sequence T(n) is defined as follows:
T(0) = 0, T(1) = 1, T(2) = 1
T(n) = T(n-1) + T(n-2) + T(n-3), for n >= 3
Given n, return the value of T(n).
Example 1:
Input: n = 4
Output: 4
Explanation:
T(3) = 0 + 1 + 1 = 2
T(4) = 1 + 1 + 2 = 4
Example 2:
Input: n = 25
Output: 1389537
0 <= n <= 37Design a complete AWS infrastructure using Terraform that follows production best practices. The configuration should create a VPC with public/private subnets, compute resources, and a managed database.
Given infrastructure requirements, generate Terraform HCL configuration that provisions:
variable blocks for all configurable valueslocals for computed valuesoutput blocks for VPC ID, subnet IDs, RDS endpointdata sources for AZ lookupExample 1:
Input: {
region: "us-east-1",
vpcCidr: "10.0.0.0/16",
azCount: 3,
instanceType: "t3.medium",
dbEngine: "postgres"
}
Output: Terraform config with:
- VPC (10.0.0.0/16)
- 3 public subnets (10.0.1.0/24, 10.0.2.0/24, 10.0.3.0/24)
- 3 private subnets (10.0.11.0/24, 10.0.12.0/24, 10.0.13.0/24)
- NAT Gateway in first public subnet
- ASG with t3.medium instances in private subnets
- PostgreSQL RDS in private subnets
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: The longest increasing subsequence is [0,1,2,3].
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Explanation: All elements are equal, so the LIS has length 1.
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4Can you come up with an algorithm that runs in O(n log n) time complexity?
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
The algorithm for myAtoi(string s) is as follows:
'-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present."123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).[-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.Note:
' ' is considered a whitespace character.Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-2^31, 2^31 - 1], the final result is 42.
Example 2:
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Example 1:
Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167
Example 2:
Input: nums = [1,5]
Output: 10
n == nums.length1 <= n <= 3000 <= nums[i] <= 100A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -infinity. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return index 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index 1 (value 2) or index 5 (value 6). Index 5 is returned.
Example 3:
Input: nums = [1]
Output: 0
Explanation: Single element is always a peak.
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1nums[i] != nums[i + 1] for all valid i.Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor, return null.
The in-order successor of a node p is the node with the smallest key greater than p.val.
Example 1:
Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor is 2.
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: 6 is the largest node, so there is no in-order successor.
[1, 10^4].-10^5 <= Node.val <= 10^5There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums are unique.nums is an ascending array that is possibly rotated.-10^4 <= target <= 10^4You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.
Define a pair (u, v) which consists of one element from nums1 and one element from nums2.
Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
1 <= nums1.length, nums2.length <= 10^5-10^9 <= nums1[i], nums2[i] <= 10^9nums1 and nums2 are sorted in non-decreasing order.1 <= k <= 10^4k <= nums1.length * nums2.lengthGiven an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Explanation: Subarrays [1,2] and [3] both sum to 3.
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7for_each or count for subnet creation (DRY)Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-2^31, 2^31 - 1], the final result is -42.
Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-2^31, 2^31 - 1], the final result is 4193.
0 <= s.length <= 200s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.