Solve Two Sorted-Array Tasks
Company: Instacart
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Implement solutions for the following two array problems:
1. **Sorted values, return sorted squares**
You are given an integer array sorted in non-decreasing order. The array may contain negative numbers. Return a new array containing the square of each value, also sorted in non-decreasing order.
Example:
Input: `[-7, -3, 0, 2, 5]`
Output: `[0, 4, 9, 25, 49]`
2. **Find the first and last position of a target**
You are given an integer array sorted in non-decreasing order and a target value. If the target appears multiple times, return the index of its leftmost occurrence and the index of its rightmost occurrence. If the target does not exist, return `[-1, -1]`.
Example:
Input: `nums = [1, 2, 2, 2, 3, 5]`, `target = 2`
Output: `[1, 3]`
Discuss the expected time and space complexity for each problem.
Quick Answer: This question evaluates competency in array manipulation, handling of sorted data, search techniques and algorithmic complexity analysis, focusing on skills such as leveraging sorted order and reasoning about time and space trade-offs.