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 Take-home Project rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Implement exponentiation and fill grid distances

Quick Overview

This question evaluates algorithmic problem-solving skills in the Coding & Algorithms domain, specifically numeric algorithms for fast exponentiation and graph traversal techniques for grid-based shortest-path computation (multi-source BFS) with attention to edge-case handling.

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given two separate coding tasks. ## Task 1: Implement fast exponentiation Implement a function `pow(x, n)` that returns \(x^n\). - **Input**: - `x`: a real number (double/float) - `n`: a 32-bit signed integer (can be negative) - **Output**: the value \(x^n\) as a floating-point number - **Requirements / edge cases**: - Handle `n < 0` (e.g., \(x^{-n} = 1/x^n\)). - `n` may be `-2^31`, so be careful when negating. - Aim for \(O(\log |n|)\) time. ## Task 2: Fill shortest distance to a gate in a grid You are given an `m x n` grid of integers representing a map: - `-1` represents a **wall** (blocked cell) - `0` represents a **gate** - A large sentinel value (e.g., `INF = 2^31 - 1`) represents an **empty room** Update the grid **in-place** so that each empty room contains the distance (minimum number of moves) to its nearest gate. - Moves are allowed only in 4 directions: up/down/left/right. - If an empty room cannot reach any gate, it should remain `INF`. ### Example Input: ``` INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF ``` Output: ``` 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 ``` - **Constraints (typical)**: - `1 <= m, n <= 200` (or similar) - Grid updates must be done without changing wall/gate cells.

Quick Answer: This question evaluates algorithmic problem-solving skills in the Coding & Algorithms domain, specifically numeric algorithms for fast exponentiation and graph traversal techniques for grid-based shortest-path computation (multi-source BFS) with attention to edge-case handling.

Fast Exponentiation

Implement solution(x, n) that returns x raised to integer power n using exponentiation by squaring. Return None for 0 raised to a negative power.

Constraints

n is a 32-bit signed integer
Handle negative n without overflowing when negating in fixed-width languages

Examples

Input: (2.0, 10)

Expected Output: 1024.0

Input: (2.0, -2)

Expected Output: 0.25

Input: (2.0, 0)

Expected Output: 1.0

Input: (0.0, -1)

Expected Output: None

Input: (-2.0, 3)

Expected Output: -8.0

Hints

Square the base while halving the exponent.

Fill Distance to Nearest Gate

Given a grid with -1 walls, 0 gates, and INF empty rooms, return a grid where each reachable empty room is replaced by its shortest distance to a gate. Unreachable rooms remain INF.

Constraints

Movement is 4-directional
Do not change walls or gates

Examples

Input: ([[2147483647, -1, 0, 2147483647], [2147483647, 2147483647, 2147483647, -1], [2147483647, -1, 2147483647, -1], [0, -1, 2147483647, 2147483647]],)

Expected Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Input: ([[2147483647, -1], [-1, 0]],)

Expected Output: [[2147483647, -1], [-1, 0]]

Input: ([[2147483647]],)

Expected Output: [[2147483647]]

Hints

Start BFS from all gates at once.

Quick Overview