Before the interview they gave me two time windows to choose from, morning or afternoon. After I picked one, it was four rounds back to back, about an hour each.
Part 1: The process and the questions
Round 1 | BQ + quick-fire technical concepts + algorithm
The interviewer was a guy based in Pittsburgh.
BQ:
Have you ever been blocked for a long time? How did you solve the problem and keep moving forward?
Technical concepts:
- What is your understanding of thread-safe?
- What is a deadlock?
- What ways can you think of to resolve a deadlock?
- How do you understand arrays and linked lists?
Algorithm: clone a doubly linked list with a special pointer.
You are given a doubly linked list. Besides value, left and right, each node also has a special pointer that can point to any node in the list. You need to fully clone this linked list.
The interviewer did not want me to just use Java's built-in LinkedList. He wanted me to create the Node class myself and also implement a LinkedList myself.
Round 2 | Self-introduction + algorithm
The interviewer was a guy.
Algorithm: the minimum ship capacity needed to ship packages within D days.
There is a batch of packages, each with a different weight. There is one ship that can only make one trip per day, and the ship has a maximum load. Given an array of all the package weights and the number of days D in which shipping must be finished, find the smallest maximum load that guarantees everything gets shipped within D days.
Round 3 | Principal SWE: self-introduction + BQ/career direction + System Design
The interviewer was a Principal SWE, a woman.
First we chatted about work and career direction:
- What is your current job mainly about? What do you focus on?
- Why do you want a new job now?
- What technical direction do you plan to focus on in the future?
System Design: a massive Log Storage System.
Design a system that writes a massive number of log records into storage and supports reading them back. She kept adding questions throughout:
- How do you handle the massive write traffic?
- How should the data be partitioned?
- Once data is spread across different data nodes, how do you know where to look when reading a file?
- Under a huge number of writes, how do you improve write efficiency?
- If a file is still being written to, how does a user who is reading it see the newly added data in time?
- If you set up a long-lived connection for every reader, would that put too much load on the server?
- How do you scale further?
Questions for the interviewer:
I asked her: at the Principal SWE level, what does your day-to-day work life look like?
She said it is basically meetings, reviewing design docs, deciding on important technical directions, and talking to different people and pushing projects forward.
So I followed up: if you have this many meetings and review this many design docs every day, how do you quickly understand a design, grab the key points, and ask the critical questions?
She said that once you reach this level you have accumulated enough experience, and you gradually build up your own mental models. After that, when you see a design, you quickly know roughly what the options are, what the trade-offs of each are, and where things are most likely to go wrong.
She also recommended a set of books she had read, The Great Mental Models. Each book in the series introduces reusable mental models from a different discipline or field.
She also told me that I probably do not have as much experience as she does right now, but once I accumulate enough, I will naturally form these things too.
I had only asked a question I was curious about, off the cuff, and I did not expect her to answer so seriously. After the interview I even looked the books up on Goodreads, and the ratings are pretty high, so they may go on my reading list.
The only thing was that
She! Did! Not! Turn! On! Her! Camera!
Round 4 | BQ + System Design
The interviewer was an older guy.
BQ:
Have you ever had a project that could not be finished before the deadline? Or a situation where users had a lot of complaints about your project? How did you handle it?
Sorry, I cannot remember the other BQs. By this point my brain was completely overloaded.
System Design: design an online Tic-Tac-Toe game system.
Requirements:
- Must use REST APIs
- Support two players playing online
- Support online matchmaking
- Consider scalability
- Consider multi-region expansion
Part 2: My solutions and a review of my answers
Below are my own answers and how I worked through the problems. It is long. If you only want the interview questions, you can stop at the part above.
Round 1: Clone Linked List
I had never seen this one, so I started by creating the two classes to buy time. Ugh, now I have to deal with the special pointers, what do I do. So let's split it into two steps. In the first iteration I create a new node for every node of the input linked list and put it in the new linked list, with the special pointer set to null for now, so at least we have cloned a plain linked list. Then I got stuck. I thought, if it were an index instead of a pointer, it would be great, because the new linked list would have the same indices. The hard part is that the original node's special pointer points to a node in its own linked list, which is useless to us. Then I thought, can I add an index field to Node? The interviewer said, can't you record extra information inside your algorithm function? We would rather not change the original data structure. I totally agreed.
My approach was two maps + an index + two passes.
In the first pass over the original list, I number every node with index++, and maintain two maps at the same time:
- Map<Integer, Node>: number -> the Node created in the new LinkedList
- Map<Node, Integer>: Node in the original LinkedList -> number
The first pass creates all the new nodes and copies the value and the left/right pointers. The second pass uses the two maps to find the new node that each special pointer corresponds to, and fills in all the special pointers. I was so focused on the special pointer that I just copied the left and right pointers over directly. Then the interviewer pointed out: if you copy left/right directly like this, don't they still point to nodes in the input linked list?
...Yes. He was completely right. I was so focused on the special pointer that I forgot about left and right. I admit that was a real problem. I was ready to keep fixing it, but he said he was already fairly satisfied with the answer, and time was up, he had another interview after mine, so he did not let me keep writing.
I was ten minutes late to the first round. I had the time wrong. The recruiter called me and I was still in bed...
I thought the first round was at 8:45, but at 8:08am the recruiter suddenly called to ask whether I was still interested in the position and whether I was still going to attend the interview today. I jumped straight out of bed. In that moment I really wanted to give up, because I figured: being late to the very first round because I got the time wrong, the first impression is already bad, so what is the point of continuing? But then I thought, I already took the day off. So I forced myself up, changed out of my pajamas at top speed, opened my laptop, logged on, apologized, and started the interview. Unexpectedly, the whole interview went really smoothly. By the end the interviewer even started complaining to me about C#, a language Microsoft uses a lot. I played along and complained that my team started out with PHP.
Round 2: Shipping Capacity
I had not seen this one before either. When I first read it I thought, I have no idea at all... But after a few minutes I suddenly realized: isn't this just binary search? The key is not to compute the answer directly, but: given a maximum capacity, can I ship everything within D days? That condition can be checked quickly. So the answer itself is monotonic:
- capacity too small -> cannot finish
- capacity big enough -> can finish
What we want is the smallest capacity that satisfies the requirement.
So we can binary search on the answer. The search range I gave at first was [0, avg]. The interviewer hinted that this range was not right. I thought about it, and it was indeed wrong, so I changed it to [avg, sum]. He said the lower bound was still not right, it should be [max, sum], that is:
- lower bound = the weight of the heaviest single package
- upper bound = the sum of all package weights
I felt that using avg as the lower bound was not necessarily wrong, but there was no point arguing over a small detail like that in an interview, so I just followed his hint. After that I made a point of confirming the range of sum. Since I use Java, I was worried that adding up all the weights would overflow int. He said not to worry about it and to assume the sum does not exceed int. Then I wrote two functions: one for the binary search, and one to check whether a given capacity can finish shipping within the given days.
The binary search logic is: if mid can finish within D days, this capacity is big enough but may be able to shrink further, so right = mid; if it cannot finish, the capacity is too small, so left = mid + 1. In the end the position where left == right is the minimum feasible capacity. The condition function itself has no real algorithm in it, it just translates the shipping process directly into code. What surprised me was that it passed all the test cases on the first try. The details of binary search, the boundaries, mid, and the left/right updates, can really be torture sometimes. I told the interviewer: the details of binary search are really easy to get wrong. He laughed and said he totally agreed.
Round 3: Massive Log Storage
My first reaction was: massive data + massive write traffic -> partitioning. The data cannot all hit one storage node, so first we need to spread out the write traffic.
As for how to partition, I asked her whether reads would need things like range search. She said no, it is basically just reading a file directly. Since there is no need for range queries, I thought hash partitioning was enough. We can distribute data across different data nodes based on the hash, which scales out the write traffic.
She then asked: now that the data is spread across many data nodes, when reading, how do you know where a file's data actually is? My answer was to add a plain metadata table. For example, recording file name, file path, size, user, created time, physical locations, etc. What the user sees is a logical file, and how many physical files are behind that logical file and which data nodes they are on can all be found through the metadata. She continued: with very heavy write traffic, how do you further improve write efficiency? I answered: buffer + batch. Buffer the small writes first, then write them to storage in batches, so that lots of small random writes are turned into more efficient sequential writes. Then she continued: if the file is still being written to, how does a user who is reading it know there is new data? I answered that we can set up a long-lived connection, for example SSE, and have the server keep pushing the newly added data to the client.
She kept digging: how do you know which "new" data to send each time? My answer was to maintain something like an offset. For example, every message records the start/end position of that batch of data. The next time, we continue from the position we last sent up to, so we know which new data the client has not received yet. Then she asked: if every reader has a long-lived connection, wouldn't that put a lot of pressure on the server? I said that if the business allows some latency, we can add a Kafka layer in the middle. Different files map to corresponding topics/partitions, and readers subscribe to the corresponding data stream, so Kafka does the fan-out for us instead of the original write server maintaining the data distribution for all readers. I think there were a few more detail questions after that, but I cannot remember them.
Round 4: Online Tic-Tac-Toe
By the fourth round my brain was already overloaded.
The question was to design an online Tic-Tac-Toe, and it explicitly required: must use REST APIs. My biggest question at the time was: why does an online game system that needs real-time state sync have to be restricted to REST APIs??? This is not a design I would normally choose at all. But since the interviewer explicitly required it, I had to work within that constraint.
I drew three layers directly on the web page: Data Layer -> Game Logic Layer -> REST APIs, with a Load Balancer in the middle. After one player makes a move, the other player needs to see the updated board. But the problem is that a REST API is a client request -> server response model, and the server has no way to proactively push updates to the other client the way WebSocket/SSE can. Since the question forced REST, all I could do was have the client keep polling. Periodically asking the server: has the board updated? Has the board updated? Has the board updated? It is ugly, but it works under this constraint.
Then he asked about scalability. The Game Logic Layer itself can be stateless, so it can scale horizontally to multiple instances, with traffic distributed by the Load Balancer. That is the design within a single region. If we expand to global users later, we can replicate the whole architecture to multiple regions. As for the data layer, I think game sessions and the matchmaking waitlist have no need for global synchronization at all. We should not be matching two players who are far apart in different regions anyway, because that would only add game latency for no reason. So: game session / matchmaking -> region-local.
User data has two options. The simplest is to also separate users completely by region, with the regions independent of each other. If the business really requires global user data, we could consider an architecture like AWS Aurora Global Database: one primary write region, with read replicas in the other regions. Since basic user info does not change often, I thought the little extra latency from cross-region writes would be acceptable.
But honestly, by the fourth round there was only one thought left in my head: when will this be over?
Discussion
Loading comments…