Interview Experience

Google India Interview Experience|SWE (Intern)- SET 1

Company Name: Google India

Job Role: Summer’22 Software Engineer Internship (10 weeks)

Years of Experience Required: 0

Drive: Off-Campus

Preparation

Topics: DSA, OS, OOPS, DBMS

Duration: I already had some experience in CP and had done Leetcode before. So it took 1 month of pure company-wise preparation filtering Medium-Hard Google questions on Geeks for Geeks.

Source of Preparation:

Google SWE Interview Rounds

Round 1: Technical Round (Video Call – 45 minutes)

The interview started with normal greetings. Then straight away, he jumped into the DSA question. No introductions were asked.

Problem Statement: Cord is a tree-like data structure where each node (apart from the leaf node) represents the number of characters present in the leaf nodes below it. The leaf node only represents the string and its length. (I don’t remember the exact statement, but this is the gist of it)

Here is an example of Cord for better understanding.

Question 1: Define a Data Structure to store the information provided.

Question 2: You are given an integer. Find the character corresponding to that integer. The sequencing is done in such a way that first all the left nodes are traversed and then the right nodes.

Example 1: In the given example, if the user inputs 3, the function should return “C”

Example 2: In the given example, if the user inputs 9, the function should return “Q”

I started off with a brute force approach of traversing all the nodes in a recursive manner and then returning the character. I explained the approach in less than 5 minutes along with the time and space complexity and the interviewer agreed with me. Next, I proceeded with a more optimized approach of choosing a single direction to move (left or right) based on the value stored in the current node instead of traversing all the nodes.

After writing only the optimized code, it was a dry run with a sample input. Then different edge cases inputs were provided and the code was tested.

Question 3: Now you are provided with two integers, the start, and the end integer. Return the complete string between them.

Example 1: In the given example, if the user inputs 3 and 5, the function should return “CDE”

Example 2: In the given example, if the user inputs 3 and 9, the function should return “CDEFGPQ”

Similar to the first question, I explained the brute-force approach first along with the time and space complexity. Then I started coding the optimized approach. As the time ran out, the code could not be tested but the interviewer agreed with my approach and seemed happy.

After the round was over, I asked a few questions and we ended the meet.

Round 2: Technical Round (Video Call – 45 minutes)

The interview started on a positive note with the introductions. I stated about my academic status and a brief on previous work experience through internships. Next, the question was presented on a shared Google Doc file.

Problem Statement: Various cities and the path distance of roads present are given. But, some cities are locked, i.e. they cannot be entered or left. The roads were bi-directional.

In this example, “D” is the locked city.

Question 1: Define a Data Structure to store the information provided.

Question 2: You are provided a source and destination city. Write a code to find the shortest path distance between the cities, if it exists. 

Example 1: In the given example, if the start city is “A” and destination is “C”. The result will be 8 units. The route taken will be “ABEFC”

Initially, the distance between each city was 1. I explained the BFS approach and he changed the question that the distances can be different. Then I explained the Priority Queue approach. He agreed to it and allowed me to code.

The code was a dry run and checked for edge cases as well. Also, the time and space complexities were discussed.

Question 3: Now you are provided with a special pass that can give you the power to cross “k” locked cities. Write a code to check if the destination can be reached provided the start city.

Example 1: In the given example, if the start city is “A” and destination is “C”. The value of “k” is 1.  The result will be true. The route taken will be “ABDC”

I explained the Dijkstra approach and he agreed to it. I coded the approach and he tested it for some edge cases as well.

Next, we also had a quick discussion to find the shortest path length in Part 3 of the question. Came to the solution and pseudo code. But I couldn’t finish the complete code as the time ran out but he seemed satisfied.

Next, he asked if I had some questions. I asked about his experience and growth curve at Google.

Verdict: Selected

Message to Aspiring Students: DSA and Problem Solving is the key for any interview. And give ample Coding Contests to get used to the time-boundness and pressure in an interview, not just for ratings. Practice speaking while solving questions.