Visa Coding Interview: Memory Allocator Allocate/Erase

You are given a 0/1 array representing memory cells (1 = occupied, 0 = free). You must process queries that persistently modify memory and return one integer per query. There are two operations:

• Allocate [0, k]: find the leftmost contiguous run of zeros of length >= k. If found, set the first k cells of that run to 1 and return the starting index; otherwise return -1.
• Erase [1, idx]: if idx is the starting index of a previously allocated (and not yet erased) block, free that whole block (set its cells to 0) and return the number of cells freed; otherwise return 0.

Core flow — what the interviewer expects you to walk through:

• Validate input and initial memory state, explain invariants you will maintain.
• Describe a data structure to find the leftmost zero-run of length >= k fast (naive scan vs. efficient approaches).
• Show how you will track allocated blocks so erase([1, idx]) can verify starts and free the correct length.
• Discuss complexity and edge cases (k > n, repeated erases, adjacent allocations causing fragmentation).

Skill signals you should demonstrate:

• Interval/segment management (segment tree, interval set, or ordered map of free segments).
• Range-query / range-update thinking and lazy propagation if using segment trees.
• Correctness on boundary cases and amortized/ worst-case complexity (aim for O(log n) per query).

Hints to mention in discussion: maintain a map from start-index to length for allocations, and a structure that supports find-first-range-with-length >= k (max-free-length per segment).