The interview process, as described to me, included the following stages:

1. Screen Call
2. Tech screen with Karat
3. Systems Design
4. Virtual onsite

I only made it to the Karat screen. If you're scheduled for the Karat screen, keep reading – you're in for a treat.

The initial tech screen wasn't anything exciting; it was your normal screening questions. However, the Karat screen was a bit of a joke. Some guy, in what I assume was India, was reading off a script. You only get 30 minutes for the actual coding. I managed to get the code working with a few minutes to spare. To be honest, my code was a bit messy. I wanted to clean it up, but the interviewer said, "You only have 3 minutes left, and I have to submit it as is." So, I reckon I was graded on that and then rejected. Apparently, there's meant to be a second problem, but I guess the interviewer didn't want to give it to me due to time constraints. I was told by the recruiter that if there isn't enough time for the second one, I should just explain how to do it, but he didn't even give me the opportunity.

Anyways, now for the treat. I saved the questions before he could clear them. I have the exact Karat questions, word for word. Here they are:

1. We are working on a clone of Google Docs. The software has the following features and limitations:

   • Multiple users may work on a single document at the same time.
   • A document must be handled by a single server, no matter how many users are using it.
   • There is no way of spreading a document's server load among multiple servers.
   • Each server can handle multiple documents at once.
   • We have a fixed number of servers, which will be sufficient to handle our expected load if used properly.

   Our load balancer uses a round-robin system to permanently assign documents to each server, so each server will have an equal number of documents.

   Do you have any concerns about this load balancing system?

2. Which consistency model is more appropriate for each of these applications: strong consistency, or eventual consistency? Why?

   • An API call that needs to respond within 20 milliseconds, used by a web service to retrieve metadata about a piece of streaming media.
   • A web analytics platform recording every single click on a popular web page.
   • A banking system that makes deposits and payments to checking accounts.

3. We maintain a distributed system that allows users to "e-sign" legal documents. After a document is fully signed, the owner gets an email notification. A document may need hundreds of signatures in order to be fully signed.

   We recently had a bug that caused the notifications to fail (about 50% of the time) over the course of a week. We have two pieces of information:

   • A database table that records whether the document is fully signed or not, and the date and time at which it was signed.
   • Flat-file logs from our 500 production servers. We log the ID of a document when we send out a notification, so the failed notifications are missing from these logs.

   How can you use the logs and database to find all the missed notifications? The service handles hundreds of millions of documents per day, so we need a scalable solution.

4. The coding question: You're developing a system for scheduling advising meetings with students in a Computer Science program. Each meeting should be scheduled when a student has completed 50% of their academic program.

   Each course at our university has at most one prerequisite that must be taken first. No two courses share a prerequisite. There is only one path through the program.

   Write a function that takes a list of (prerequisite, course) pairs and returns the name of the course that the student will be taking when they are halfway through their program. (If a track has an even number of courses, and therefore has two "middle" courses, you should return the first one.)

   Sample input 1: (arbitrarily ordered) prereqs_courses1 = [ ["Foundations of Computer Science", "Operating Systems"], ["Data Structures", "Algorithms"], ["Computer Networks", "Computer Architecture"], ["Algorithms", "Foundations of Computer Science"], ["Computer Architecture", "Data Structures"], ["Software Design", "Computer Networks"] ]

   In this case, the order of the courses in the program is: Software Design Computer Networks Computer Architecture Data Structures Algorithms Foundations of Computer Science Operating Systems

   Sample output 1: "Data Structures"

   Sample input 2: prereqs_courses2 = [ ["Algorithms", "Foundations of Computer Science"], ["Data Structures", "Algorithms"], ["Foundations of Computer Science", "Logic"], ["Logic", "Compilers"], ["Compilers", "Distributed Systems"] ]

   Sample output 2: "Foundations of Computer Science"

   Sample input 3: prereqs_courses3 = [ ["Data Structures", "Algorithms"], ]

   Sample output 3: "Data Structures"

   Complexity analysis variables:

   n: number of pairs in the input