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.

What difficulty level is this interview 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.

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 Overview

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.

Implement exponentiation and fill grid distances

Quick Overview

Task 1: Implement fast exponentiation

Task 2: Fill shortest distance to a gate in a grid

Example

Submit Your Answer to Earn 20XP

Implement exponentiation and fill grid distances

Quick Overview

Task 1: Implement fast exponentiation

Task 2: Fill shortest distance to a gate in a grid

Example

Submit Your Answer to Earn 20XP