Round 0 - Coding Round

There were 4 problems to be solved in 1.5 hours.
Problem1. Some manager-employee relationship was given in the form of an array and we have to find out the minimum number of groups that must-be formed such that no employee is grouped with its manager, direct or indirect. The problem boiled down to find the maximum height of any tree formed by these relationships.

Problem2. This question was based on the union-find algorithm (easy version). Please also read about compressed dsu as it was needed to pass all test cases without giving TLE.

Problem3. This was a dp medium/hard question but the brute force was also getting accepted. Given an array, you can change signs of every element between two indices i and j. You can do this by swapping any number of times and then we had to maximise the sum of all elements of the array.

Problem 4. (Ad-hoc) This was a simple mix match string problem. This was more of an implementation problem. Read KMP.

I did 3 questions completely and got shortlisted along with 16 students. 3 technical rounds + 1 HR round in the end. Each round was eliminatory.

Techincal Round 1
The interviewer was SDE-3 and just joined mind tickle. He was very friendly and introduced himself. He asked me about this simple DFS problem.

Problem - Given a 2D matrix filled with characters. It contains my name in it. Count the number of times your name is written in the matrix. You can start from any position in the matrix and move in 4 directions. I explained to him my approach and asked him if I can move ahead. He gave me the green signal and started coding on the shared code pad. He helped me in writing base conditions and also guided me in writing code. I coded it easily and he was really impressed. Also, take care of the space and time complexity. Then he asked me a second question.

Problem - Given an infinite stream of characters, find the first occurrence of 'b'. I asked some clarifying questions. The stream consists of only 'a's and 'b's and all a's will be in the starting of b. I told him to modify the binary search as it was similar to the LC problem 'First Bad Version'. The only difference is stream is of infinite length.

I completed these 2 questions in 20 minutes only and later I asked him questions in the end. I got shortlisted for a further round.

Techincal Round 2
The interviewer was not so friendly. He asked me some questions, in the beginning, to make me feel comfortable. I introduced myself, told them about my college life and he asked about corona cases in my area. He started asking questions randomly like he had made his mind to just pass the time. He asked about UNIX commands like a top, processes and threads, the difference between them, the number of cores in my machine, how can I verify it from my terminal. Later, he told me to search it on google. I did the same and explained to him the output on my terminal. He spent 30 minutes in this shit. Then he asked me a data structure question (LLD).

Design Red Bus
We want to get the list of buses that are scheduled between source and destination on a given date. This should be implemented efficiently.

User(source, destination , date) {
    // complete the logic
}

Admin can add/register a new bus schedule. Implement this function.

RegisterBus( busID, list<<pair>> routeInfo) {
    // (1234 ,  Delhi 26th July, Agra 26th july , jabalpur 27th july , mumbai 27th july)
    // register the bus, complete the logic
}

You are free to make any assumptions you like.

How would you design the data structure such that the user search function should be optimal?
He also told me it was a kind of an open-ended question. I used a simple hash map and gave me O(1) search time solution but it was memory heavy. This round did not go well.

After 3 hours, around 5 pm, I received the link for the 3rd round.

Techincal Round - 3
This round was taken by a 12 years experienced manager of the QA team. He started with some questions on my resume, experience in my internship. He also explained to me his role in managing the team. Then he asked me for a puzzle. Egg drop puzzle. There are 2 eggs and 100 floors in buildings, minimise the number of trials to find out the floor from where the egg will start to break after dropping. I instantly gave him a DP solution and also wrote the pseudo-code in 15 minutes. But later realised that the eggs are only 2. Then I explained to him the binary search solution.

HR round
It was a small round and he asked about my experience of the above rounds. He also offered me the SDET role.

Suggestion
Read theory but also understand OS in-depth, networks, and read interview experience and try to find their answers. Also, practice LLD design (hard). Always think of Hashing, linked list, etc in low-level design.