Compute sparse dot product and count islands

Q: 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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Compute sparse dot product and count islands

Quick Overview

Problem 1: Sparse vector dot product

Problem 2: Count connected islands in a grid

Comments (0)