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 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).


