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 Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Reconstruct original array from doubled shuffle

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an integer array `changed` that was produced from some unknown integer array `original` using the following process: 1. Start with `original`. 2. Create a second array by doubling every element in `original` (i.e., `2 * original[i]`). 3. Concatenate the doubled elements to the end of `original`. 4. Shuffle the resulting array arbitrarily to get `changed`. Example: - `original = [1, 4]` - After doubling and concatenation: `[1, 4, 2, 8]` - After shuffling: `[2, 1, 4, 8]` (this is `changed`) ## Task Given `changed`, return the lexicographically smallest possible `original` that could have generated it. If no valid `original` exists, return an empty array. ## Input / Output - **Input:** Integer array `changed` (length `n`) - **Output:** Integer array `original` (length `n/2`) or `[]` if impossible ## Constraints (assume typical interview constraints) - `n = changed.length` can be up to `10^5` - Elements can be negative, zero, or positive integers - If `n` is odd, it is impossible ## Notes - If multiple valid `original` arrays exist, return the lexicographically smallest one. - You may return `original` in any order only if explicitly stated; otherwise, return it sorted ascending to make the output deterministic.

Quick Answer: This question evaluates array manipulation, multiset/frequency reasoning, pairing logic, and careful handling of edge cases such as zeros and negative numbers.

You are given an integer array `changed` formed by taking every element of an unknown array `original`, appending its doubled value, and then shuffling the combined array. Reconstruct `original`. Return the answer sorted in ascending order so it is the lexicographically smallest valid result. If no valid `original` exists, return `[]`.

Constraints

0 <= len(changed) <= 100000
If len(changed) is odd, the answer is impossible
Each value in changed can be negative, zero, or positive

Examples

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

Expected Output: [1, 4]

Explanation: `[1, 4]` produces doubled values `[2, 8]`, and after shuffling we can get `[2, 1, 4, 8]`.

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

Expected Output: [-2, -1, 1]

Explanation: `original = [-2, -1, 1]` has doubled values `[-4, -2, 2]`, which together match the multiset in `changed`.

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

Expected Output: [0, 0]

Explanation: Zero doubles to zero, so four zeroes in `changed` correspond to two zeroes in `original`.

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

Expected Output: []

Explanation: The length is odd, so `changed` cannot be split into an original half and a doubled half.

Input: ([-6, -3, -3, -12],)

Expected Output: []

Explanation: There are two copies of `-3`, so we would need two copies of `-6` to match them, but only one exists.

Input: ([],)

Expected Output: []

Explanation: An empty `changed` array comes from an empty `original` array.

Hints

Because the array was shuffled, positions do not matter. Count how many times each value appears.
Process values in order of increasing absolute value. For each `x`, every remaining copy of `x` must be matched with a copy of `2 * x`. Handle `0` carefully.

Quick Overview

This question evaluates array manipulation, multiset/frequency reasoning, pairing logic, and careful handling of edge cases such as zeros and negative numbers.