E
EduScale
319 challenges in the catalogue. Browse freely; sign in to open the editor and submit.
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge: The inputs to the judge are given as follows (your program is not given these inputs):
intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.listA - The first linked list.listB - The second linked list.skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
listA is in the m.listB is in the n.1 <= m, n <= 3 * 10^41 <= Node.val <= 10^5\n- 0 <= skipA <= m0 <= skipB <= nCould you write a solution that runs in O(m + n) time and use only O(1) memory?
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Input: nums = [0]
Output: [0]
1 <= nums.length <= 10^4-2^31 <= nums[i] <= 2^31 - 1Follow up: Could you minimize the total number of operations done?
The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
For example, "ACGTACGTACGT" is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
1 <= s.length <= 10^5s[i] is either 'A', 'C', 'G', or 'T'.There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5Implement the K-Means Clustering algorithm from scratch. K-Means partitions data into K clusters by iteratively assigning points to the nearest centroid and updating centroids.
function kMeans(
data: number[][],
k: number,
maxIterations?: number
): { assignments: number[]; centroids: number[][] }
data: 2D array of data points (n_samples x n_features)k: Number of clustersmaxIterations: Maximum iterations (default: 100)Input:
data = [[1,1],[1,2],[2,1],[8,8],[8,9],[9,8]]
k = 2
Output:
assignments = [0,0,0,1,1,1]
centroids = [[1.333,1.333],[8.333,8.333]]
Implement a memoize function that caches the result of a function call based on its arguments. If the function is called again with the same arguments, the cached result should be returned without re-executing the function.
function memoize<T extends (...args: any[]) => any>(fn: T): T
fn — The function to memoize.A memoized version of the function. Repeated calls with the same arguments return the cached result.
let callCount = 0;
const add = (a: number, b: number) => { callCount++; return a + b; };
const memoizedAdd = memoize(add);
memoizedAdd(1, 2); // 3, callCount = 1
memoizedAdd(1, 2); // 3, callCount = 1 (cached)
memoizedAdd(2, 3); // 5, callCount = 2 (new args)
const factorial = memoize((n: number): number => {
if (n <= 1) return 1;
return n * factorial(n - 1);
});
factorial(5); // 120 — each sub-call is cached
factorial(3); // 6 (already cached from factorial(5))
const fetchUser = memoize(async (id: string) => {
const res = await fetch(`/api/users/${id}`);
return res.json();
});
await fetchUser("123"); // Network call
await fetchUser("123"); // Cached — no network call
JSON.stringify for cache key generationImplement the Saga pattern for managing distributed transactions across microservices. When a multi-step business process (like placing an order) spans multiple services, you need to ensure that either all steps complete successfully, or all completed steps are compensated (rolled back) in reverse order.
interface SagaStep {
name: string;
execute: (context: SagaContext) => Promise<any>;
compensate: (context: SagaContext) => Promise<void>;
}
interface SagaContext {
sagaId: string;
data: Record<string, any>;
stepResults: Record<string, any>;
}
Step 1 Execute -> Step 2 Execute -> Step 3 Execute -> COMPLETED
|
(failure)
|
Step 2 Compensate <- Step 1 Compensate -> COMPENSATED
const saga = new SagaOrchestrator();
saga.addStep({
name: 'reserve-inventory',
execute: async (ctx) => {
const reserved = await inventoryService.reserve(ctx.data.items);
return { reservationId: reserved.id };
},
compensate: async (ctx) => {
await inventoryService.release(ctx.stepResults['reserve-inventory'].reservationId);
},
});
saga.addStep({
name: 'charge-payment',
execute: async (ctx) => {
const charge = await paymentService.charge(ctx.data.amount);
return { chargeId: charge.id };
},
compensate: async (ctx) => {
await paymentService.refund(ctx.stepResults['charge-payment'].chargeId);
},
});
saga.addStep({
name: 'create-shipment',
execute: async (ctx) => {
return await shippingService.create(ctx.data.address);
},
compensate: async (ctx) => {
await shippingService.cancel(ctx.stepResults['create-shipment'].shipmentId);
},
});
const result = await saga.execute({ items: [...], amount: 99.99, address: {...} });
// All steps succeed: { status: 'completed', steps: [...] }
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
pow(x, 0.5) in C++ or x ** 0.5 in Python.Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
0 <= x <= 2^31 - 1Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:
Input: head = []
Output: []
[0, 5 * 10^4].-10^5 <= Node.val <= 10^5Follow up: Can you sort the linked list in O(N log N) time and O(1) memory (i.e. constant space)?
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
[0, 100].-100 <= Node.val <= 100Implement a class ZeroEvenOdd with three methods that run concurrently. The output should follow the pattern: 0, 1, 0, 2, 0, 3, 0, 4, ... up to n.
zero() prints "0"odd() prints odd numbers (1, 3, 5, ...)even() prints even numbers (2, 4, 6, ...)The three functions run concurrently and must coordinate to produce the correct interleaved output.
class ZeroEvenOdd {
constructor(n: number);
zero(printZero: () => void): Promise<void>;
even(printEven: (n: number) => void): Promise<void>;
odd(printOdd: (n: number) => void): Promise<void>;
}
Input: n = 5
Output: "0102030405"
Input: n = 2
Output: "0102"
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.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: [0,1,2,3] is also valid.
Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 2All the pairs [ai, bi] are distinct.// Same saga as above, but payment fails
// Step 1 (reserve-inventory): SUCCESS
// Step 2 (charge-payment): FAILS
// Compensation: release-inventory runs (reverse order)
// Result: { status: 'compensated', failedStep: 'charge-payment', error: 'Card declined' }
// Step 1: SUCCESS, Step 2: SUCCESS, Step 3: FAILS
// Compensate Step 2: SUCCESS
// Compensate Step 1: FAILS (service down)
// Result: { status: 'compensation_failed', compensationErrors: [...] }
// Requires manual intervention