This question evaluates competency in designing efficient algorithms for sparse data representations and for identifying connected components in grids, testing skills in handling large inputs, memory-efficient representations, and traversal/graph concepts.
You are asked to solve two coding problems.
Given two vectors A and B of the same length n (potentially large, e.g., up to 100,000), most entries are zero.
Implement a function (or a small class API) to compute the dot product:
Input representation (sparse): Each vector is provided as a list of non-zero entries, e.g. a list of pairs (index, value) sorted by index (or equivalently a map from index to value).
Output: Return the integer dot product.
Constraints/notes:
[0, n-1]
.
Given an m x n 2D grid of characters (or integers) where '1' represents land and '0' represents water, count the number of islands.
An island is a maximal set of land cells connected 4-directionally (up, down, left, right).
Input: grid[m][n] containing '0'/'1'.
Output: The number of islands.
Constraints/notes: