Implement bounds, minimum, pathfinding, and moving average

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.

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

Example 1

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

Explanation: Duplicates around x.

Example 2

Input: ([], [1, 2], 0)
Output: {'merged': [1, 2], 'lower': 0, 'upper': 0}

Explanation: Empty A.

Hints

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

Example 1

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

Explanation: Unsorted array.

Example 2

Input: ([],)
Output: None

Explanation: Empty input.

Hints

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

Example 1

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

Explanation: Path to right boundary.

Example 2

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

Explanation: Start already at exit.

Hints

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

Example 1

Input: (3, [1, 10, 3, 5])
Output: [1.0, 5.5, 4.666667, 6.0]

Explanation: Window grows then slides.

Example 2

Input: (1, [4, 5])
Output: [4.0, 5.0]

Explanation: Window size one.

Hints

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