Just finished Google The first round of technical aspects of Virtual Onsite (R1), the overall experience is very typical of Google style: the questions are not biased and not strange, but you will be deepened in your understanding of data structure, complexity and engineering scenarios through follow-up, rather than just whether you can write code. The interviewer's pace is not fast. There are two questions in total, each with a clear follow-up.
Question 1: Binary tree traversal and concurrency design
The question itself is a classic but easily underestimated design question:
Design an iterator to perform non-recursive in-order traversal of a binary tree. Each call to next() returns the next node value, requiring an average time complexity of O(1).
I first confirmed the interface semantics with the interviewer, such as whether hasNext() is required and whether preprocessing of the entire tree is allowed. After it is clear that one-time expansion is not allowed, go directly to the standard solution. The core idea is to use the stack to simulate the recursive calling process. During initialization, starting from the root node, the current node and all left child nodes are pushed onto the stack to ensure that the top of the stack is always the frontmost node in the current in-order traversal.
Each time next() is called:
Pop the top node of the stack, which is the current return value;
If the node has a right subtree, start from the right subtree and push it and all its left subtrees onto the stack in sequence.
The advantage of this is that it is completely "traversal on demand" without generating the complete in-order sequence in advance. Although a single next() may push multiple nodes in the worst case, In summary, each node will only be pushed into and popped out of the stack once, so the average time complexity is O(1), and the space complexity is O(h), where h is the height of the tree.
The interviewer was quite satisfied with this part, and then moved on to the real bonus point.
Follow-up: Thread-safe design in multi-threaded environment
The interviewer came up with a very Google follow-up:
If in a multi-threaded environment, multiple iterators may traverse the same tree at the same time, how to ensure thread safety?
The key here is not to "lock it and it's done", but to distinguish between shared state and private state.
My answer is:
If each iterator maintains its own independent stack structure, and the tree itself is read-only during the traversal process, then multiple iterators traversing the same tree concurrently is thread-safe and does not require locking the tree.
What really needs to be considered for synchronization is whether a single iterator will be called next() by multiple threads at the same time.
If this situation exists, you can add a mutex lock to the next() method inside the iterator, or use a thread-safe data structure to protect stack reading and writing.
If you further pursue performance, you can also avoid lock competition through the design of "one iterator per thread", thus eliminating concurrent writing problems from the design level.
The interviewer is obviously testing your judgment on concurrency boundaries, rather than rigidly answering synchronized.
Question 2: Counting problem of subarray sum equal to k
The second question is a very classic, but basic question that Google still tests:
Given an array of integers, count how many subarrays whose sum equals a target value k.
I started directly from the brute force solution, explaining that O(n²) is not feasible, and then introduced the optimization solution of prefix sum + hash table. The specific steps are:
Iterate over the array while maintaining the current prefix and sum.
Use a hash table to record "the number of times a certain prefix sum appears". When traversing to the current position, if sum – k appears in the hash table, it means that there are several subarrays ending at the current position and with a sum of k, and the number is exactly equal to the number of occurrences of (sum – k). When initializing, {0: 1} should be placed in the hash table, which means "the prefix sum is 0 and appears once", which is used to process subarrays starting from index 0. The overall time complexity is O(n) and the space complexity is O(n).
Follow-up: How to optimize when array contains negative numbers?
The interviewer emphasized one point in the follow-up: the array may contain negative numbers. Will this affect the algorithm?
This is actually a "trap confirmation". My answer is:
The existence of negative numbers does make the prefix sum no longer monotonic, so double pointers or sliding windows cannot be used, but the method of recording the prefix sum in the hash table itself does not rely on monotonicity, and the time complexity is still O(n). If you consider it from an engineering perspective, you can optimize the capacity allocation of the hash table and reduce rehash costs by estimating the value range of the prefix sum (maximum value, minimum value), but the algorithm level does not need to be changed.
Practical assistance at key points in interviews
If you encounter a bottleneck in the OA or VO stage, there is no need to panic. Although the question types of Dachang seem to be diverse, they can often be broken down into parts: algorithm core, complexity analysis, boundary conditions, and expression of ideas. We accompanied some students through the OA + VO of many major manufacturers. Real-time assistance , the rhythm of the interview process is smoother, the answers are more organized, and the probability of passing is naturally higher.
