Katkat
Back

Compute sparse dot product and count islands

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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).