Solve three classic coding problems
Quick Overview
These tasks evaluate algorithmic problem-solving, data structure mastery, and implementation skills within the Coding & Algorithms domain, touching on dynamic programming (longest increasing subsequence), order-statistics in sorted arrays, tree pointer manipulation for perfect binary trees, and graph traversal for connected components.
You are given three independent coding tasks. Implement a function for each.
1) Longest Increasing Subsequence (LIS)
Given an integer array nums, return the length of the longest strictly increasing subsequence.
-
Input:
nums(array of integers) - Output: integer length of the LIS
-
Constraints (typical):
1 <= n <= 2e5(or smaller), values fit in 32-bit signed int
2) k-th Largest Element in Two Sorted Arrays
Given two arrays A and B, each sorted in non-decreasing order, and an integer k (1-indexed), return the k-th largest element in the multiset union of A and B.
-
Input:
A,B(sorted arrays),k - Output: the k-th largest element
- Notes: Arrays may have different lengths; duplicates are allowed.
-
Constraints (typical):
0 <= len(A), len(B) <= 2e5,1 <= k <= len(A)+len(B)
3) Connect Nodes at the Same Tree Level
Given a perfect binary tree (all internal nodes have exactly two children and all leaves are at the same depth), populate each node’s next pointer so it points to its immediate neighbor to the right on the same level. If there is no neighbor, set next = null.
-
Input:
root of a perfect binary tree with fields
left,right,next - Output: the root (after pointers are populated)
-
Requirement (typical):
use
O(1)extra space (excluding recursion stack)
4) Number of Islands
Given an m x n grid of characters containing '1' (land) and '0' (water), return the number of connected components of land. Cells are connected 4-directionally (up/down/left/right).
-
Input:
grid(2D array of'0'/'1') - Output: integer number of islands
-
Constraints (typical):
1 <= m,n <= 200(or similar)