Hiring process8 levels
  1. 1 IQ Test
  2. 2 Additional Online Test (If Required)
  3. 3 Office Interview with Hiring Manager
  4. 4 Unpaid Test Task (Motivation Check)
  5. 5 Paid Test Task and Follow-Up Interview
  6. 6 Iterative Paid Test Tasks
  7. 7 Office Verification
  8. 8 Final Interview with the Founder

Problems > Range Sums in a Window > Editorial

Range Sums in a Window — Solution & Editorial

Back to the Problem

A subarray (q, p] qualifies iff prefix[p] − prefix[q] ∈ [LO, HI], i.e. prefix[q] ∈ [prefix[p]−HI, prefix[p]−LO]. Sweep prefixes counting predecessors in that window with a BIT over compressed prefix values (or merge-sort recursion). A balanced-list insertion also passes at these limits.

Complexity: O(N log N)