How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Solve grid min path and sqrt by binary search

Quick Overview

This question evaluates proficiency in dynamic programming and algorithm design for grid-based path optimization as well as numerical methods and binary search for square-root approximation, encompassing time/space complexity analysis, external-memory handling for very large matrices, overflow avoidance, and numerical stability.

Quick Overview

Solve grid min path and sqrt by binary search

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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

Quick Answer: This question evaluates proficiency in dynamic programming and algorithm design for grid-based path optimization as well as numerical methods and binary search for square-root approximation, encompassing time/space complexity analysis, external-memory handling for very large matrices, overflow avoidance, and numerical stability.

Minimum-Sum Grid Path

Move only right or down from top-left to bottom-right. Return [minimum_sum, path_coordinates]. Ties choose right before down.

Constraints

Cell values are non-negative

Examples

Input: ([[1, 3, 1], [1, 5, 1], [4, 2, 1]],)

Expected Output: [7, [[0, 0], [0, 1], [0, 2], [1, 2], [2, 2]]]

Input: ([[5]],)

Expected Output: [5, [[0, 0]]]

Input: ([[1, 1], [1, 1]],)

Expected Output: [3, [[0, 0], [0, 1], [1, 1]]]

Hints

Fill DP from bottom-right and reconstruct greedily.

Integer Floor Square Root

Return floor(sqrt(x)) for non-negative integer x without using a square-root function.

Constraints

x is non-negative

Examples

Input: (0,)

Expected Output: 0

Input: (1,)

Expected Output: 1

Input: (8,)

Expected Output: 2

Input: (16,)

Expected Output: 4

Input: (1000000000000,)

Expected Output: 1000000

Hints

Binary search on the answer and compare with division to avoid overflow.

Real Square Root Approximation

Return sqrt(x) rounded to 6 decimal places using binary search.

Constraints

x is non-negative

Examples

Input: (0.0,)

Expected Output: 0.0

Input: (2.0,)

Expected Output: 1.414214

Input: (0.25,)

Expected Output: 0.5

Input: (100.0,)

Expected Output: 10.0

Hints

For 0 < x < 1, search in [0,1].

Last updated: Jun 27, 2026

Loading coding console...