Google Sse Interview

Summary

I interviewed for a Staff Software Engineer role at Google, facing three technical rounds covering system design, concurrency, and tree traversal with string search. Unfortunately, I was rejected, particularly struggling with the first round's concurrency implementation.

Full Experience

Round 1 you are given a few api

API that is responsible to calculate a callback function after relative_time_stamp_in_mills from the time of the call setCallBackHandler. void setCallBackHandler(int relative_time_stamp_in_mills);

API that gives current system time in mills. int getSysTime();

You have to write a method called ScheduleCallback(call_back_func_pointer, time_in_mills) that does the job of scheduling a call to call_back_func_pointer after time_in_mills from the call.

The calls might come in parallel.
setCallBackHandler can only save ONE TRIGGER AT A TIME. So if the new request is supposed to get executed first, you need to handle that gracefully.
setCallBackHandler takes in relative time.

Round 2 You are given a Class with two methods

Class CWFuture{
	CWFuture(Const int machine_id, const int doc_id);
	int join() // Returns the number of words in the document file. This is a blocking call, it won't return if the process is still calculating the words in the document
	int isDone() // Returns true if the calculation is done else false
}

Given max_doc_ids, you need to write a method, use CWFuture class and calculate the total number of words in doc ids ranging from [0, max_doc_ids) and return that number.

Scenario 1: You have unlimited number of machines available. Follow up scenario 2: What if you have at max N number of machines with you. Scen 3: Discussion: How would you improve the accuracy of your result if the API is not accurate every time. Let's say 90% of the time it returns correct response.

Write C++ code for both scenarios separately and implement a method called CountWords.

Round 3: You are given a data structure of HTML Content and tags. Looks like this. A node can be an html tag OR a string text.

class Node{
	bool isText();
	string getText();
	vector<Node*> getChildren();
}

You need to implement a method that takes in Head of the node and a string to search. And you should return the nodes that cover the search string within the structure.

This is a funny Text. 

         <span> 1
         /  |   \
        /   |    \
       /    |     \
     2<b> 4" is a"  <i>5
     /\t\t\t\t \
    /\t\t\t\t  \
   /\t\t\t\t   \
3"This"\t\t\t\t" funny Text."6

Case 1: Search = "is a" Returns Node 4

Case 2: Search "a fun" Returns Node 4 and Node 6.

vector<Node*> GetNodes(Node* head, string& search);

Implement GetNodes.

Overall it was a reject. You'll find the answers on Chat GPT. Apparently interviewer for the first round was expecting me to use threads and mutexes and actually implement it. That's where I lost.

Interview Questions (3)

Callback Scheduler with Concurrent Calls

System Design

API that is responsible to calculate a callback function after relative_time_stamp_in_mills from the time of the call setCallBackHandler. void setCallBackHandler(int relative_time_stamp_in_mills);

API that gives current system time in mills. int getSysTime();

You have to write a method called ScheduleCallback(call_back_func_pointer, time_in_mills) that does the job of scheduling a call to call_back_func_pointer after time_in_mills from the call.

The calls might come in parallel.
setCallBackHandler can only save ONE TRIGGER AT A TIME. So if the new request is supposed to get executed first, you need to handle that gracefully.
setCallBackHandler takes in relative time.

Count Words using CWFuture Class with Concurrency

Data Structures & Algorithms

You are given a Class with two methods

Class CWFuture{
	CWFuture(Const int machine_id, const int doc_id);
	int join() // Returns the number of words in the document file. This is a blocking call, it won't return if the process is still calculating the words in the document
	int isDone() // Returns true if the calculation is done else false
}