Example coding interview: Designing Google Docs
A lot of you asked for an example interview after my Google interview video. You can watch the previous introductory video here:
In this video, I’m interviewing my friend Petros Angelatos of resin.io. We talk about designing a system like Google Docs. The questions pertain to designing the database, managing users and documents, designing the communication protocol, supporting multiple users editing simultaneously and resolving diffs.
A picture of the whiteboard after the end of the interview is here:
https://imgur.com/a/Jr0NH
Petros is an experienced software engineer and did extremely well in this interview, even though he did not know the particular problem beforehand. My assessment notes follow.
In terms of the database, I noticed that he was confident in designing relational database schemas, including many-to-many relationships using intermediate tables (the users – documents relationship in this case). He was also able to identify queries that would run often and point out candidate keys for optimizing the database, including non-trivial composite keys (in our case, the (document_id, revision) composite key). Perhaps the only shortcoming of the interview was that he included an unnecessary ‘revision’ field in the ‘document’ table; this was an un-normalized database schema, but he quickly figured it out when I pointed it out to him.
In terms of protocols, he was able to successfully leverage the standard Internet protocols, including HTTP for developing a regular API and websockets for implementing a real-time API. He quickly dodged the somewhat misleading question of “what cryptographic scheme would you use to protect the data on the wire” and opted with the ready solution of employing HTTPS. In addition, he mentioned HSTS and certificate pinning, which can offer better security. I was happy to see that he did not propose inventing his own methods, but readily reused an existing obvious solution.
In terms of system design, he was familiar with locks and semaphores and used successful analogies to design the first version of the software – where each user must obtain a lock before editing.
The next version was developed with a successful analogy with git, for which he showed extreme familiarity. He decided to reuse the git library to implement diffs, which points out that he’s not reinventing the wheel, a desirable virtue. He pointed out analogies with git’s “rebase”, illustrating quite experienced use of version control. He was able to successfully design the system to the end, describe managing conflicts and resolving complicated diffs.
Finally, he described an offline mechanism which can allow editing without an Internet connection. His architecture is a classical design pattern which is often used in mobile applications. He leveraged HTML5’s localStorage to persist his documents and proposed the use of an offline cache mechanism, which is the right solution here.
In the end, he made some insightful comments and suggestions with technologies I did not expect him to be familiar with: Compiling C libraries for the browser, and eventually consistent data structures. Last but not least, he was able to argue against the use of git itself as a backend for this service, and provided convincing technical arguments confidently supporting his views.
Such questions are typical in large company software interviews, especially for full-time or more senior engineers. They will often contain many of the elements described here: Protocol design, security, database design, analogies to existing software, and library reuse.
Thanks for watching! If you liked this video, don’t forget to 👍 and +subscribe 🙂 Leave a comment if you have questions or suggestions.
I’ve just created a Patreon where you can buy me a cup of coffee. Thanks so much for supporting me! https://www.patreon.com/dionyziz
source
