Solve grid min path and sqrt by binary search

Q: Solve grid min path and sqrt by binary search

This is a Coding & Algorithms interview question from TikTok for Software Engineer roles. View the full question and solution on PracHub.

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

Given an m x n matrix of non-negative integers, find a path from the top-left to the bottom-right that minimizes the sum of cell values. You may only move right or down. Return both the minimum sum and one optimal path. Describe the algorithm, justify correctness, and analyze time/space complexity. Consider how to handle very large matrices that do not fit entirely in memory.
Implement sqrt(x) using binary search.

Version A: return floor(sqrt(x)) for a non-negative 32-bit or 64-bit integer x without using built-in square root functions; avoid overflow and analyze complexity.
Version B: return a double approximation within 1e-6 for a non-negative real x; discuss stopping conditions, numerical stability, and edge cases (x=0, 0<x<1, very large x).

Solve grid min path and sqrt by binary search

Comments (0)