Apple Two-Round Pure Coding Interview Experience Round

Given an integer array nums and an integer k, find all continuous subarrays whose sum is exactly equal to k.

Solution Approach
Use 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)

Complexity
Time: O(n)
Space: O(n) (for the hash map)

Follow-up Questions
Will 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 Approach
During 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

Complexity
Each 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 Questions
If 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).