Coding questions · Meta

Compute sparse dot product and count islands

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.

Problem 1: Sparse vector dot product

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:

$A \cdot B = \sum_{i=0}^{n-1} A_i \times B_i$

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:

Indices are in [0, n-1].
Values can be negative.
Aim for time proportional to the number of non-zero entries.

Problem 2: Count connected islands in a grid

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:

You may modify the grid in-place or use auxiliary memory.
Consider edge cases like empty grid, all water, all land, and thin grids (1 row/1 column).

Sparse Vector Dot Product

Given two equal-length integer arrays that may contain many zeros, return their dot product using their non-zero entries.

Examples

Example 1

Input: ([1, 0, 0, 2, 3], [0, 3, 0, 4, 0])
Output: 8

Explanation: Only index 3 contributes.

Example 2

Input: ([0, 0, 0], [4, 5, 6])
Output: 0

Explanation: All-zero sparse vector.

Hints

Start with a direct data structure representation.
Handle edge cases before the main loop.

Count Islands in a Binary Grid

Given a binary grid, count connected components of land cells. Land is 1 or "1", connected vertically or horizontally.

Examples

Example 1

Input: ([['1', '1', '0'], ['0', '1', '0'], ['1', '0', '1']],)
Output: 3

Explanation: String grid with three islands.

Example 2

Input: ([[1, 1, 0], [0, 1, 0], [1, 0, 1]],)
Output: 3

Explanation: Integer grid uses the same rule.

Hints

Start with a direct data structure representation.
Handle edge cases before the main loop.