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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Instacart.

What role is this question designed for?

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

Solve Two Sorted-Array Tasks | Instacart Coding Question

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.

Part 1: Sorted Values, Return Sorted Squares

You are given an integer array `nums` sorted in non-decreasing order. The array may contain negative numbers. Return a new array containing the square of each value, sorted in non-decreasing order.

Constraints

0 <= len(nums) <= 100000
-10000 <= nums[i] <= 10000
`nums` is sorted in non-decreasing order

Examples

Input: ([-7, -3, 0, 2, 5],)

Expected Output: [0, 4, 9, 25, 49]

Explanation: Squaring gives [49, 9, 0, 4, 25], which sorted becomes [0, 4, 9, 25, 49].

Input: ([],)

Expected Output: []

Explanation: Edge case: an empty input array has no squares.

Input: ([-5],)

Expected Output: [25]

Explanation: Edge case: a single negative value squares to a positive value.

Input: ([-4, -1, 0, 3, 10],)

Expected Output: [0, 1, 9, 16, 100]

Explanation: The largest square comes from 10, then -4, while 0 remains smallest.

Input: ([-9, -7, -3, -1],)

Expected Output: [1, 9, 49, 81]

Explanation: All numbers are negative, so their squares are in reverse order of the original array.

Hints

The largest square may come from either the most negative number or the most positive number.
Try using two pointers from both ends of the array and fill the result from right to left.

Part 2: Find the First and Last Position of a Target

You are given an integer array `nums` sorted in non-decreasing order and an integer `target`. Return a list `[left, right]`, where `left` is the index of the first occurrence of `target` and `right` is the index of the last occurrence of `target`. If `target` does not appear in the array, return `[-1, -1]`.

Constraints

0 <= len(nums) <= 100000
-1000000000 <= nums[i] <= 1000000000
-1000000000 <= target <= 1000000000
`nums` is sorted in non-decreasing order

Examples

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

Expected Output: [1, 3]

Explanation: The target 2 starts at index 1 and ends at index 3.

Input: ([], 4)

Expected Output: [-1, -1]

Explanation: Edge case: an empty array cannot contain the target.

Input: ([5], 5)

Expected Output: [0, 0]

Explanation: Edge case: the only element is the target, so first and last positions are both 0.

Input: ([1, 3, 5, 7], 4)

Expected Output: [-1, -1]

Explanation: The target 4 does not exist in the array.

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

Expected Output: [0, 3]

Explanation: All elements are the target, so the range spans the entire array.

Hints

Because the array is sorted, you can use binary search instead of scanning linearly.
Find the first index where a value is at least `target`, and the first index where a value is greater than `target`.

Quick Overview

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.