Apple Two-Round Pure Coding Interview Experience: Prefix Sum and Tree Iterator

Given an integer array nums and an integer k, find all continuous subarrays whose sum is exactly equal to k.Solution ApproachUse prefix sum + hash map. Maintain the current prefix sum sum. If sum - k

Given an integer array nums and an integer k, find all continuous subarrays whose sum is exactly equal to k.Solution ApproachUse prefix sum + hash map. Maintain the current prefix sum sum. If sum - k has appeared in the hash map before, it means there exists a subarray with sum k. Initialize the hash map with {0: 1} (indicating that the prefix sum of 0 has appeared once — before the array starts). Traverse the array: Update the prefix sum sum += nums[i] Check how many times sum - k has appeared in the map and add that count to the result Then add the current sum to the hash map (increase its frequency) ComplexityTime: O(n) Space: O(n) (for the hash map)

Follow-up QuestionsWill negative numbers or zeros affect the solution? How to optimize further? Answer: Negative numbers or zeros make the sliding window approach invalid, so prefix sum + hash map is more robust and stable. For further optimization (in very special cases), you could consider using a balanced BST (ordered map) or combining two pointers with a sorted structure, but usually not necessary. Round 2 Design an iterator for inorder traversal of a binary tree, returning nodes in the order left → root → right, and you cannot store all nodes at once (must support lazy traversal).Solution ApproachDuring initialization: push the root and all its left children onto the stack in sequence. For next() operation: Pop the top node from the stack (node) If this node has a right child, push the right child and all its left descendants onto the stack Return the value of node For hasNext(): check whether the stack is empty ComplexityEach node is pushed and popped from the stack exactly once Amortized time per next() call: O(1) Space: O(h), where h is the height of the tree Follow-up QuestionsIf multiple iterators are concurrently accessing the same tree, how do you ensure thread safety? Answer: Each iterator maintains its own independent stack state, and the tree itself is read-only → safe for concurrent access. If there are write operations (modifications to the tree), then you would need locking mechanisms or versioned snapshot techniques (like copy-on-write or using a version number).