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 Onsite 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 bounds, minimum, pathfinding, and moving average

Quick Overview

This question evaluates proficiency with core data structures and algorithms—specifically array operations (merge and bounds), minimum-finding strategies, 2D graph pathfinding (BFS vs. DFS and path reconstruction), and streaming sliding-window statistics (moving average).

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Solve the following data-structures problems: ( 1) Given two sorted integer lists A and B, merge them into a single non-decreasing array. Then, for a target x, return the indices of the first element ≥ x (lower bound) and the first element > x (upper bound) in the merged array. Specify time and space complexity, and handle duplicates and empty inputs. ( 2) Implement a function that returns the minimum value in an array; discuss approaches and edge cases for both sorted and unsorted arrays. ( 3) Given a 2D grid of 0s (open) and 1s (walls) and a start cell, find a path to any exit on the grid boundary (an open boundary cell) and return the path as a list of coordinates. Discuss BFS vs. DFS, how to reconstruct the path, and complexity. ( 4) Design a class MovingAverage(k) that ingests a stream of numbers and returns the average of the last k values after each insertion. Support amortized O( 1) updates/queries and define behavior when the stream has fewer than k elements.

Quick Answer: This question evaluates proficiency with core data structures and algorithms—specifically array operations (merge and bounds), minimum-finding strategies, 2D graph pathfinding (BFS vs. DFS and path reconstruction), and streaming sliding-window statistics (moving average).

Merge Sorted Lists and Return Bounds

Merge two sorted lists, then return lower_bound and upper_bound indices for x.

Constraints

A and B are sorted

Examples

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

Expected Output: {'merged': [1, 2, 3, 3, 3, 4], 'lower': 2, 'upper': 5}

Explanation: Duplicates around x.

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

Expected Output: {'merged': [1, 2], 'lower': 0, 'upper': 0}

Explanation: Empty A.

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

Expected Output: {'merged': [1, 2], 'lower': 2, 'upper': 2}

Explanation: Upper past end.

Hints

After merging, use binary search for first >= x and first > x.

Minimum Value in an Array

Return the minimum value in an array, or None for empty input.

Examples

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

Expected Output: 1

Explanation: Unsorted array.

Input: ([],)

Expected Output: None

Explanation: Empty input.

Input: ((-1, -5, 0),)

Expected Output: -5

Explanation: Tuple input with negatives.

Hints

Scan every value unless sortedness can be guaranteed.

Path from Start to Any Grid Exit

Return one shortest path from a start cell to an open boundary cell in a 0/1 grid, or [] if none exists.

Constraints

0=open, 1=wall

Examples

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

Expected Output: [(1, 1), (1, 2)]

Explanation: Path to right boundary.

Input: ([[0]], (0, 0))

Expected Output: [(0, 0)]

Explanation: Start already at exit.

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

Expected Output: [(1, 1)]

Explanation: Boundary start at bottom-right.

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

Expected Output: []

Explanation: No exit.

Hints

BFS gives a shortest path and parent pointers reconstruct it.

Moving Average of Last k Values

Return the moving average after each inserted stream value, averaging over fewer than k values at the beginning.

Constraints

k > 0

Examples

Input: (3, [1, 10, 3, 5])

Expected Output: [1.0, 5.5, 4.666667, 6.0]

Explanation: Window grows then slides.

Input: (1, [4, 5])

Expected Output: [4.0, 5.0]

Explanation: Window size one.

Input: (5, [])

Expected Output: []

Explanation: Empty stream.

Hints

Keep a queue of the last k values and a running sum.

Quick Overview