Sum Every Element of a k-Dimensional Array Readable Only Through get(indices)

You are given a k-dimensional array and a list `dimensions`, where `dimensions[d]` is the size of dimension `d`. The only way to read an element is to call `array.get(indices)`, where `indices` is a list of k integers with `0 <= indices[d] < dimensions[d]` for every `d`. Return the sum of all elements of the array. The number of dimensions k is not fixed in advance, so the solution cannot be written as a fixed number of nested loops. ```python def sum_k_dimensional(array, dimensions: list[int]): ... ``` Example: ```text dimensions = [2, 3] array.get([0, 0]) = 1 array.get([0, 1]) = 2 array.get([0, 2]) = 3 array.get([1, 0]) = 4 array.get([1, 1]) = 5 array.get([1, 2]) = 6 result = 21 ``` ```hint Picture the loops you cannot write Think about what k nested loops would do to an index list, and how a single function could play the role of any number of them. ``` ```hint When the index is complete Decide at which point the index list is fully filled in and ready to pass to `get`, and whether you need a new list for every element. ``` ### Constraints and Clarifications - `get` is the only access path: `array` offers no flattening, iteration or shape information beyond `dimensions`. - `dimensions` has exactly k entries, and the elements are numbers. ### Clarifying Questions - Can k be 0, and can a dimension have size 0? What should the sum be in those cases? - Are the elements integers or floating-point, and can the sum overflow a fixed-width integer? - How expensive is `get`: an in-memory lookup, or a disk or network read for which access order matters? - May `get` keep a reference to the list it receives, or is it safe to reuse and mutate one index list between calls? ### What a Strong Answer Covers - Visits every index tuple exactly once for any k, without hardcoding the loop depth - Calls `get` exactly once per element, with the total running time and extra space stated in terms of the dimension sizes and k - Handles k = 0, a zero-size dimension, and overflow or precision of the sum - Compares the recursive formulation with an iterative one, including recursion depth limits - Clean code checked with a short hand trace ### Follow-up Questions - Rewrite the solution without recursion. - `get` is now a remote call with high latency, and the data is stored in row-major blocks. How would you change the traversal? - The array has billions of elements. How would you split the sum across workers? - Return the sum along one chosen dimension instead, producing a (k − 1)-dimensional result. How does your code change?