Compute sparse dot product and count islands
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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).
Quick Answer: 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.
Sparse Vector Dot Product
Given two equal-length integer arrays that may contain many zeros, return their dot product using their non-zero entries.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ([1, 0, 0, 2, 3], [0, 3, 0, 4, 0])
Expected Output: 8
Explanation: Only index 3 contributes.
Input: ([0, 0, 0], [4, 5, 6])
Expected 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.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ([['1', '1', '0'], ['0', '1', '0'], ['1', '0', '1']],)
Expected Output: 3
Explanation: String grid with three islands.
Input: ([[1, 1, 0], [0, 1, 0], [1, 0, 1]],)
Expected Output: 3
Explanation: Integer grid uses the same rule.
Hints
- Start with a direct data structure representation.
- Handle edge cases before the main loop.