Managed to go till the 3rd (and final) round, was rejected afterwards. Following were the questions of each round:

1. Interviewer wrote a class template and I was supposed to complete the function definitions. Basically it was a server which would initailize job IDs starting from a certain integer N. The server would be sent acknowledgements as to which jobs have been complete via a function call and it was supposed to return the least id of the unfinished job ID via another function call. There were 3 functions:

   • void Initialize : It would take as input N, the starting ID of the job
   • void ack(int job_completed) : This func call is used to tell that this certain job has been finished. This function can be called multiple times with the same argument.
   • int get_first_unfinished_job() : This is supposed to return the first unfinished job ID.
   • Initially all the jobs are in pending state
     I used an unordred_map to create an entry everytime an ack was received for a job. To get the first unfinished job, I would traverse the unordred map and return the first entry not present in the map.
     For further optimizations on space and time, while traversing the map in get_job function, I would keep on deleting the finished job entries from the map. Also , in the function call my loop for finding out the job ID will always start from the last returned job ID and not N

   Interviewer said that it can still explode on memory since the upper limit on job IDs could be quite high. And so if a certain job remains unfinished then map willhave to still store the status of all the job IDs after that one.

2. In this round, I was given two strings A and B and had to transform one to another using the following rule:
   * all characters which are same in A have to changed simultaneoulsy to the same character, example : if A is qwewqq and I choose to transform first q to x, then I would have to make it to this -> xwewxx
   * Make no assumptions about the length of A and B
   * The example transformation in the first point counts as 1 transformation/move.
   * Return the minimum number of transformations or -1 if it's not possible.

   So first of all if lengths of A and B are different then transofrmation isn't possible since we can't add/remove any charactrers. And here the order in which we choose the characters in A for transformation is very important. Probably the interviewer was looking for a graph based approach (she hinted for it), where I had to form a directed graph where nodes represented characters (of both A and B) and edges denoted direction from initial to final character.

   So we'll have to follow the reverse topological order for picking up the order of characters in string A for transformation in every component of the graph. Not sure what will happen if there are cycles though. I came up with this approach quite late and time was up by now.

3. In this I was give a text file which basically contained on every new line chat messages of certain users in a group. I had to find top k users on the basis of their valid word count in all of their messages. Here valid word is the one which contains atleast one alphanumeric character. n is the total number of users and k << n.
   So I suggested that we can find the word count of each user and later find a max heap to find the top k ones. He asked to optimize it on space, since in this case heap would take O(n) memory. So the trick here is to use a min heap to filter out bottom (n-k) users and that would require a heap of size (k+1) since if that element is minimum of any (k+1) elements, then it's certainly not in the top k elements. Take some exemplar values of n and k and then think if you haven't understood.

   Apart from this there were questions like would you help a fellow googler if he approaches you for help and how would you priroritize multiple assignemnts if they have the same deadline ?