← Quora Interview Insights

Quora·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Quora software engineer interview with a tricky array reconstruction problem. The algorithmic angle wasn't obvious at first and the reverse simulation approach took a while to click.

Questions Asked (1)

Q1

Given an array of n integers as the target, and starting from an array of n ones, you can repeatedly pick any index and set it to the current total sum of the array. Is it possible to reach the target array using this operation?

Algorithms & Data Structures
Author's notes

My first instinct was to go forward and try building up toward the target, which went nowhere fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Work backwards from the target array: the largest element must have been the last one set, so subtract the sum of the other elements from it to undo the operation. Repeat until all elements become 1 (possible) or an element becomes ≤ 0 (impossible).

Pro tip: Use a max-heap to efficiently extract the largest element and handle large values with modulo arithmetic to avoid O(n) subtractions per step, ensuring O(n log n) time.

1. Understand the forward operation

Clarify that each operation replaces one element with the sum of all current elements, so the total sum increases by the previous value of that element.

2. Reverse the process

Start from the target array and undo the last operation: the largest element must have been the one set last, so subtract the sum of the other elements from it.

3. Iterate with a max-heap

Use a max-heap to repeatedly extract the largest element, compute the new value by subtracting the sum of the rest, and push it back if it remains > 1.

4. Handle large values efficiently

If the largest element is much larger than the sum of the others, use modulo to reduce it in one step: new_val = largest % (sum - largest), but ensure it stays ≥ 1.

5. Check termination conditions

If all elements become 1, return true; if any element becomes ≤ 0 or the heap cannot be reduced further, return false.

Key Points to Mention

  • Working backwards from the target array is the key insight.
  • The largest element must be the last one modified in the forward process.
  • Use a max-heap to efficiently find and update the largest element.
  • Modulo arithmetic optimizes repeated subtractions when the largest element is much larger than the sum of the others.
  • Time complexity: O(n log n) with heap and modulo, or O(n * max_value) without optimization.
  • Edge cases: target contains 1s, target has elements ≤ 0, or target sum is less than n.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.