← Quora Interview Insights

Quora·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Interviewed for a software engineering role at Quora and got a heap-based algorithmic problem that looked deceptively clean on the surface. The reverse simulation angle took me a while to see.

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. Can you determine whether the target array is reachable?

Algorithms & Data Structures
Author's notes

My first instinct was to try building forward from the ones array and I wasted probably five minutes on that before realizing it was going to explode in complexity.

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 reverse the operation. Repeat this reduction, using a max-heap and modulo optimization to handle large values efficiently, until all elements become 1 or you detect an invalid state.

Pro tip: Emphasize that reversing the process is key, and mention that using modulo instead of repeated subtraction prevents timeouts on large inputs—this shows you think about efficiency beyond the naive approach.

1. Understand the forward operation

Clarify that each step replaces one element with the sum of all elements before the replacement. This means the new value is always greater than the previous value at that index.

2. Reverse the process

Start from the target array. The largest element must have been the last one set, so its previous value was (largest - sum of others). Replace it with that value.

3. Optimize with modulo

Instead of subtracting the sum repeatedly, compute how many times you can subtract the sum from the largest element without making it non-positive. Use modulo to jump directly to the remainder.

4. Use a max-heap for efficiency

Maintain the current array in a max-heap to quickly access and update the largest element. This keeps the time complexity at O(n log n) per reduction step.

5. Check termination and validity

Stop when all elements are 1 (reachable) or when an element becomes less than 1 or the reduction doesn't change the array (unreachable). Also handle edge cases like n=1.

Key Points to Mention

  • Reverse simulation: the largest element must have been the last one set.
  • The previous value of the largest element is (largest - sum of others).
  • Use modulo to avoid O(k) subtraction when the largest is much bigger than the sum.
  • Maintain a max-heap to efficiently find and update the largest element.
  • Handle edge cases: n=1 (target must be [1]), and elements must remain positive.
  • Time complexity: O(n log n * log(max_value)) with modulo optimization.

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