So from what it was described to me
1. Screen Call
2. Tech screen with Karat
3. Systems Design
4. Virtual onsite
I only made it to the Karat screen. If your scheduled for the Karat screen keep reading your in for a treat.
So tech screen wasnt anything exciting, your normal screening questions But the Karat screen was a bit of a joke. Some guy in what I assume was India 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 guy was like "you only have 3 minutes left and I have to submit it as is" so I reckon i got graded on that and then rejected. Apparently there is meant to be a second problem but i guess the guy didnt want to give it to me due to time. I was told by the recruiter if there isnt enough time for the second one to just explain how to do it, but he didnt 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
