4.4

Google’s mission is to organize the world‘s information and make it universally accessible and useful. Since our founding in 1998, Google has grown by leaps and bounds. From offering search in a single l... read more Mountain View, California, United States (USA)

Is this your company?

Claim Account Filter interviews by
Designation

Select Designation

Clear

150 results found

### Interview Rounds

Coding Test

Video Call

I was interviewed in Dec, 2020.

### Interview Questions

• Q1. Min Steps to one using DP

#### You can perform any one of the following 3 steps:

``````1) Subtract 1 from it. (n = n - ­1) ,
2) If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) ,
3) If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ).
``````

#### For example:

``````Given:
‘N’ = 4, it will take 2 steps to reduce it to 1, i.e., first divide it by 2 giving 2 and then subtract 1, giving 1.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The following ‘T’ lines contain a single integer  ‘N’, denoting the number given to us.
``````
##### Output Format :
``````For each test case, You are supposed to return an integer that denotes the minimum steps it takes to reduce the number to 1.
``````
##### Note:
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= ‘T’ <= 5
1 <= ‘N’ <= 10 ^ 5

Time Limit: 1sec.
``````
• Q2. Longest Palindromic Substring

#### Your task is to find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

##### Note:
``````A substring is a contiguous segment of a string.
``````
##### For example :
``````The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome. There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.
``````
##### Input Format:
``````The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.

The first and only one of each test case contains a string (STR).
``````
##### Output Format :
``````For every test case, print a single line containing the longest palindromic substring.

If there are multiple possible answers then you need to print the substring which has the lowest starting index.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````

``````Try to solve it using O(1) space complexity.
``````
##### Constraints :
``````1 <= T <= 10
0 <= N <= 10^3

where 'T' is the number of test cases, 'N' is the length of the given string.

Time Limit: 1 sec
``````
• Q3. Boyer Moore Algorithm for Pattern Searching

#### You are given a string ‘text’ and a string ‘pattern’, your task is to find all occurrences of pattern in the string ‘text’ and return an array of indexes of all those occurrences. You may assume that the length of ‘text’ is always greater than the length of ‘pattern’.

##### For example :
``````Let text = “this is a good place to have a good start”, pattern = “good” so you have to return {10, 31} because at 10 and 31 index pattern is present in the text.
``````
##### Note :
``````If there is no such index in the text then just return an array containing -1.
``````
##### Input format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a string ‘text’ in which the pattern will be searched for.

The second line of each test case contains a string ‘pattern’ of which you have to find all occurrences in ’text’.
``````
##### Output format :
``````For each test case, return an array representing the indices where the pattern is found in the text. The output of each test case is printed in a separate line.
``````
##### Note :
``````You don’t have to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= M < 100
1 <= N < M

Time Limit: 1 sec
``````
• Q4. Median in a stream

#### Median is the middle value in an ordered integer list. If the size of the list is even there is no middle value. So the median is the floor of the average of the two middle values.

##### For example :
``````[2,3,4] - median is 3.
[2,3] - median is floor((2+3)/2) = 2.
``````

##### Input Format:
``````The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow.
The first line of each test case contains the number of elements, N, in the input data stream.

The second line of each test case contains N space separated elements of the input data stream.
``````
##### Output Format:
``````For each test case, print the median of the elements after each incoming element. Each median value is separated by a single space.

The output of each test case is printed in a separate line.
``````
##### Note :
``````You do not need to print anything, just return the vector of medians after each element is read from the stream.
``````
##### Constraints :
``````1 <= T <= 10
1 <= N <= 10^4
0 <= data <= 10^8
Where T is the number of test cases, N is the number of elements in the data stream.

Time Limit : 1 sec
``````
• Q5. Shortest alternate colored path

#### Your task is to compute an array ‘answer’ of size ‘N’, where ‘answer[i]’ stores the length of the shortest path from node ‘0’ to node ‘i’ such that the edges along the path have alternate colors. If there is no such path from node ‘0’ to ‘i’, then ‘answer[i] = -1’.

##### Example:
``````N = 4, redEdges = [[0, 1], [2, 3]], blueEdges = [[1, 2], [1, 3]]
`````` ``````The shortest paths for each node from node ‘0’ are:
1: 0->1         Length: 1
2: 0->1->2      Length: 2
3: 0->1->3      Length: 2
So, the ‘answer’ array will be: [0, 1, 2, 2].
``````
##### Note:
``````1. The given graph could be a disconnected graph.

2. Any two nodes ‘i’ and ‘j’ can have at most one red edge from ‘i’ to ‘j’ and at most one blue edge from ‘i’ to ‘j’.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains three space-separated integers ‘N’, ‘rlen’, and ‘blen’ denoting the number of nodes in the graph, the size of array ‘redEdges’, and the size of array ‘blueEdges’.

The next 'rlen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘red’ edge from node ‘i’ to node ‘j’.

The next 'blen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘blue’ edge from node ‘i’ to node ‘j’.
``````
##### Output format:
``````For every test case, print a single line containing N space-separated integers denoting array ‘answer’, where ‘answer[i]’ contains the valid shortest path length from node ‘0’ to node ‘i’.

The output for each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 200
0 <= rlen + blen <= 1000

Where ‘T’ is the number of test cases, ‘N’ is the number of nodes in the graph, ‘rlen’ is the size of array ‘redEdges’, and ‘blen’ is the size of array ‘blueEdges’.

Time limit: 1 second
``````
• Q6. Spell Checker

#### Note:

``````1) The suggested correct strings for the string  ‘QUERY’ will be all those strings present in the ‘DICTIONARY[]’ that have the prefix same as the longest prefix of string ‘QUERY’.

2) The ‘DICTIONARY[]’ contains only distinct strings.
``````

#### For example:

``````Given 'DICTIONARY[]' = {“ninja”, “ninjas”, “nineteen”, “ninny”} and query = “ninjk”. Since “ninjk” is not present in the ‘DICTIONARY[]’, it is an incorrect string. The suggested current spellings for “ninjk” are “ninja” and “ninjas”. It is because “ninj” is the longest prefix of “ninjk” which is present as the prefix in ‘DICTIONARY’.
``````
##### Input Format
``````The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of strings in the list, ‘DICTIONARY[].’

The second line of each test case contains ‘N’ space separated strings present in the list, ‘DICTIONARY[]’.

The last line of each test case contains the ‘QUERY’ string.
``````
##### Output Format:
``````For each test case, return a list of strings containing all suggested correct spellings from the list, ‘DICTIONARY[]’, if the spelling of the ‘query’ string is incorrect. Otherwise, return an empty list that will be internally interpreted as the correct string and will print “CORRECT”.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 5
1 <= N <= 100
1 <= |DICTIONARY[i]| <= 100
1 <= |QUERY| <= 100
‘DICTIONARY[i]’ and ‘QUERY’ contains only lowercase english letters.

Where ‘|DICTIONARY[i]|’ is the length of the string in the list ‘DICTIONARY' and ‘|QUERY|’ is the length of the ‘QUERY’ string.

Time limit: 1 sec
``````
• Q7. The Skyline Problem

#### The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1, y1], [x2, y2], ...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

##### Note:
``````There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3], [4 5], [7 5], [11 5], [12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output.

As such: [..., [2 3], [4 5], [12 7],...].

Also, the buildings are sorted by a non-decreasing order.

For more clarification see sample case 1.
``````
##### Input Format:
``````The first line of input contains a single integer ‘N’ denoting the number of buildings that would be given.

And the rest of the ‘N’ lines contain three space-separated integers: Left and right Indices of the vertical edges of the building while the last integer represents the height of the building ‘H’.
``````
##### Output Format :
``````Return the list of skylines formed by these buildings collectively.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1, y1], [x2, y2],...]. Each key point is on the left.

The endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark.

The skyline's termination is where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= | BUILDINGS | <= 10^4
0 <= LEFT_i < RIGHT_i <= 2^31 - 1
1 <= HEIGHT_i <= 2^31 - 1

Time Limit: 1 sec
``````

### Interview details

Professional and academic backgroundI completed Computer Science Engineering from Delhi Technological University. I applied for the job as SDE - 1 in BangaloreProposed: Eligibility criteriaNo Criteria
Google interview Rounds:Round 1
Round type - Online Coding Test
Round duration - 60 minutes
Round difficulty - Medium
Round description -

This round was held on Hackerearth from 2:00 PM to 3:00 PM
This round had 2 questions of easy/medium difficulty. Both were based on concepts of DP.
The use of offline IDE was prohibited so we were supposed to code it on Hackerearth IDE itself.

Round 2
Round type - Video Call
Round duration - 45 minutes
Round difficulty - Medium
Round description -

The round was held on Google Meet and I was given 2 coding problems for which first I had to explain my approach and then I had to write code in Shared Google Docs and dry run on sample test cases and discuss Time and Space Complexity.
There were 2 interviewers and both were very friendly and helpful and tried to bring us to our comfort level first.

Round 3
Round type - Online Coding Test
Round duration - 90 minutes
Round difficulty - Hard
Round description -

This round was also virtual. It has some difficult questions when compared to the previous rounds.
This was also held on Google Meet with shared docs for writing code.
There were 2 interviewers and both were helpful.

Google interview preparation:Topics to prepare for the interview - Data Structures - Trie, HashMap, Sets, Priority Queue, Stack, Advanced Topics like Fenwick Tree, Segment Trees, Game Theory, Dynamic Programming, Union Find, Graph Algorithms, BitmasksTime required to prepare for the interview - 5 monthsInterview preparation tips for other job seekers

Tip 1 : Reading other’s interview experiences is one of the best ways to get yourselves ready for the next job interview. Practice daily atleast 5 questions.
Tip 2 : Most commonly asked topics in Google Interviews ( as per the mail I received from my recruiter ) :
BFS/DFS/Flood fill, Binary Search, Tree traversals, Hash tables, Linked list, stacks, queues, two pointers/sliding window
Binary heaps, Ad hoc/string manipulations.
Tip 3 : Highly recommended sites for practicing questions ( usually practice medium and hard level questions) -

Leetcode (highly encouraged)
Geeksforgeeks (highly encouraged)
CodeZen( highly encouraged)
Codeforces

Application resume tips for other job seekers

Tip 1 : Mention past working experience in detail as how you were important to your previous company.
Tip 2 : Try to keep your resume to 1 page if work experience < 5 years
Tip 3 : Update your resume according to role you are applying for and never put false things on resume.

Final outcome of the interviewSelected
View More 3 ### Interview Rounds

Coding Test

Video Call

I was interviewed in Nov, 2020.

### Interview Questions

• Q1. Min Steps to one using DP

#### You can perform any one of the following 3 steps:

``````1) Subtract 1 from it. (n = n - ­1) ,
2) If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) ,
3) If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ).
``````

#### For example:

``````Given:
‘N’ = 4, it will take 2 steps to reduce it to 1, i.e., first divide it by 2 giving 2 and then subtract 1, giving 1.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The following ‘T’ lines contain a single integer  ‘N’, denoting the number given to us.
``````
##### Output Format :
``````For each test case, You are supposed to return an integer that denotes the minimum steps it takes to reduce the number to 1.
``````
##### Note:
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= ‘T’ <= 5
1 <= ‘N’ <= 10 ^ 5

Time Limit: 1sec.
``````
• Q2. Longest Palindromic Substring

#### Note that in case of more than one longest palindromic substrings with the same length you need to return the rightmost substring in the given string. For example in string “bbbab”, there are two possible longest palindromic substrings i.e. “bbb” and “bab”, and since you are supposed to return the rightmost substring, so you need to return “bab” as the answer.

##### Note:
``````A substring is a contiguous sequence of elements within a string (for example, “bcd” is a substring of “abcde” while “bce” is not).

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The only line of each test case contains a single string ‘S’ consisting of only lowercase English letters.
``````
##### Output Format:
``````For each test case, print a single string in a single line denoting the longest palindromic substring of string ‘S’.

The output for each test case is in a separate line.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
1 <= N <= 100

Where ‘N’ is the length of the string.

Time limit: 1 sec
``````
• Q3. Pattern Matching

#### You are given a pattern in the form of a string and a collection of words. Your task is to determine if the pattern string and the collection of words have the same order.

##### Note :
``````The strings are non-empty.

The strings only contain lowercase English letters.
``````
##### Input Format :
``````The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow.

The first line of each test case contains the string pattern and an integer N, denoting the number of words in the collection.

The second line of each test case contains N-words.
``````
##### Output Format :
``````For each test case print in a new line, “True” if the strings in the words array follow the same order as the order of the characters in the pattern string. Otherwise, print “False”.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.

Output for each test case will be printed in a separate line.
``````
##### Constraints :
``````1 <= T <= 100
1 <= |pattern| <= 5000,
1 <= N <= 5000
1 <= X <= 6

Time Limit: 1sec
``````
• Q4. Running Median

#### You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

##### Input Format :
``````The first line of input contains an integer 'N', denoting the number of integers in the stream.

The second line of input contains 'N' integers separated by a single space.
``````
##### Output Format :
``````Print the running median for every integer added to the running list in one line (space-separated).
``````
##### Input Constraints
``````0 <= N <= 10 ^ 5
1 <= ARR[i] <= 10 ^ 5

Time Limit: 1 sec
``````
• Q5. Shortest alternate colored path

#### Your task is to compute an array ‘answer’ of size ‘N’, where ‘answer[i]’ stores the length of the shortest path from node ‘0’ to node ‘i’ such that the edges along the path have alternate colors. If there is no such path from node ‘0’ to ‘i’, then ‘answer[i] = -1’.

##### Example:
``````N = 4, redEdges = [[0, 1], [2, 3]], blueEdges = [[1, 2], [1, 3]]
`````` ``````The shortest paths for each node from node ‘0’ are:
1: 0->1         Length: 1
2: 0->1->2      Length: 2
3: 0->1->3      Length: 2
So, the ‘answer’ array will be: [0, 1, 2, 2].
``````
##### Note:
``````1. The given graph could be a disconnected graph.

2. Any two nodes ‘i’ and ‘j’ can have at most one red edge from ‘i’ to ‘j’ and at most one blue edge from ‘i’ to ‘j’.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains three space-separated integers ‘N’, ‘rlen’, and ‘blen’ denoting the number of nodes in the graph, the size of array ‘redEdges’, and the size of array ‘blueEdges’.

The next 'rlen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘red’ edge from node ‘i’ to node ‘j’.

The next 'blen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘blue’ edge from node ‘i’ to node ‘j’.
``````
##### Output format:
``````For every test case, print a single line containing N space-separated integers denoting array ‘answer’, where ‘answer[i]’ contains the valid shortest path length from node ‘0’ to node ‘i’.

The output for each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 200
0 <= rlen + blen <= 1000

Where ‘T’ is the number of test cases, ‘N’ is the number of nodes in the graph, ‘rlen’ is the size of array ‘redEdges’, and ‘blen’ is the size of array ‘blueEdges’.

Time limit: 1 second
``````
• Q6. Spell Checker

#### Note:

``````1) The suggested correct strings for the string  ‘QUERY’ will be all those strings present in the ‘DICTIONARY[]’ that have the prefix same as the longest prefix of string ‘QUERY’.

2) The ‘DICTIONARY[]’ contains only distinct strings.
``````

#### For example:

``````Given 'DICTIONARY[]' = {“ninja”, “ninjas”, “nineteen”, “ninny”} and query = “ninjk”. Since “ninjk” is not present in the ‘DICTIONARY[]’, it is an incorrect string. The suggested current spellings for “ninjk” are “ninja” and “ninjas”. It is because “ninj” is the longest prefix of “ninjk” which is present as the prefix in ‘DICTIONARY’.
``````
##### Input Format
``````The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of strings in the list, ‘DICTIONARY[].’

The second line of each test case contains ‘N’ space separated strings present in the list, ‘DICTIONARY[]’.

The last line of each test case contains the ‘QUERY’ string.
``````
##### Output Format:
``````For each test case, return a list of strings containing all suggested correct spellings from the list, ‘DICTIONARY[]’, if the spelling of the ‘query’ string is incorrect. Otherwise, return an empty list that will be internally interpreted as the correct string and will print “CORRECT”.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 5
1 <= N <= 100
1 <= |DICTIONARY[i]| <= 100
1 <= |QUERY| <= 100
‘DICTIONARY[i]’ and ‘QUERY’ contains only lowercase english letters.

Where ‘|DICTIONARY[i]|’ is the length of the string in the list ‘DICTIONARY' and ‘|QUERY|’ is the length of the ‘QUERY’ string.

Time limit: 1 sec
``````
• Q7. The Skyline Problem

#### The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1, y1], [x2, y2], ...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

##### Note:
``````There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3], [4 5], [7 5], [11 5], [12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output.

As such: [..., [2 3], [4 5], [12 7],...].

Also, the buildings are sorted by a non-decreasing order.

For more clarification see sample case 1.
``````
##### Input Format:
``````The first line of input contains a single integer ‘N’ denoting the number of buildings that would be given.

And the rest of the ‘N’ lines contain three space-separated integers: Left and right Indices of the vertical edges of the building while the last integer represents the height of the building ‘H’.
``````
##### Output Format :
``````Return the list of skylines formed by these buildings collectively.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1, y1], [x2, y2],...]. Each key point is on the left.

The endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark.

The skyline's termination is where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= | BUILDINGS | <= 10^4
0 <= LEFT_i < RIGHT_i <= 2^31 - 1
1 <= HEIGHT_i <= 2^31 - 1

Time Limit: 1 sec
``````

### Interview details

Professional and academic backgroundI applied for the job as SDE - 1 in BangaloreProposed: Eligibility criteriaNeed 2 years work experience
Google interview Rounds:Round 1
Round type - Online Coding Test
Round duration - 60 minutes
Round difficulty - Medium
Round description -

This round was held on Hackerearth from 2:00 PM to 3:00 PM
This round had 2 questions of easy/medium difficulty. Both were based on concepts of DP.
The use of offline IDE was prohibited so we were supposed to code it on Hackerearth IDE itself.

Round 2
Round type - Video Call
Round duration - 45 minutes
Round difficulty - Medium
Round description -

The round was held on Google Meet and I was given 2 coding problems for which first I had to explain my approach and then I had to write code in Shared Google Docs and dry run on sample test cases and discuss Time and Space Complexity.
There were 2 interviewers and both were very friendly and helpful and tried to bring us to our comfort level first.

Round 3
Round type - Online Coding Test
Round duration - 90 minutes
Round difficulty - Medium
Round description -

This round was also virtual. It has some difficult questions when compared to the previous rounds.
This was also held on Google Meet with shared docs for writing code.
There were 2 interviewers and both were helpful.

Google interview preparation:Topics to prepare for the interview - Data Structures - Trie, HashMap, Sets, Priority Queue, Stack, Advanced Topics like Fenwick Tree, Segment Trees, Game Theory, Dynamic Programming, Union Find, Graph Algorithms, BitmaskingTime required to prepare for the interview - 3 monthsInterview preparation tips for other job seekers

Tip 1 : Bookmark the GFG Google Archives. It helped me a lot during my preparations. Reading other’s interview experiences is one of the best ways to get yourselves ready for the next job interview. Practice daily atleast 5 questions.
Tip 2 : Most commonly asked topics in Google Interviews ( as per the mail I received from my recruiter ) :
BFS/DFS/Flood fill, Binary Search, Tree traversals, Hash tables, Linked list, stacks, queues, two pointers/sliding window
Binary heaps, Ad hoc/string manipulations.
Tip 3 : Highly recommended sites for practicing questions ( usually practice medium and hard level questions) :
Leetcode (highly encouraged)
Geeksforgeeks (highly encouraged)
CodeZen( highly encouraged)
Codeforces
Tip 4 : This is a great bigocheatsheet that could be of great help https://www.bigocheatsheet.com/

Application resume tips for other job seekers

Tip 1 : Mention past working experience in detail as how you were important to your previous company.
Tip 2 : Try to keep your resume to 1 page if work experience < 5 years
Tip 3 : Update your resume according to role you are applying for and never put false things on resume.

Final outcome of the interviewSelected
View More 1 ### Interview Rounds

Video Call

HR

I was interviewed before Sep, 2020.

### Interview Questions

• Q1. Special Numbers

#### You are given an integer, ‘MAXVAL’. Your task is to determine the total number of special numbers present in the range, 1 to ‘MAXVAL’.

##### Note:
``````A special number is a number, which when rotated 180 degrees, resembles some other number in the same range. Every digit of a special number must be a valid digit.

The digits, 0,1,6,8,9, when rotated 180 degrees, become 0,1,9,8,6 respectively. While the digits, 2,3,4,5,7, when rotated do not become any valid digit.
``````
##### For example:
``````‘8196’, when rotated 180 degrees, will become ‘9618’. We can observe that all the digits of this number are valid. So, this is a special number.
``````
##### Input Format:
``````The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.

The first line of each test case contains a single integer, ‘MAXVAL’.
``````
##### Output Format:
``````For each test case, print a single integer, denoting the total number of special numbers in the range, 1 to ‘MAXVAL’.

Output for each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= MAXVAL < 10^4

Time Limit: 1sec
``````
• Q2. Basic HR Questions

1. Tell me about yourself
3. Which product of Google you like most? Why? Any competing products in the market?
4. If I asked your current organization for feedback then what will they say? Focusing on negative points.
5. If you have to improve one technical and one behavioral point then which one will you improve?
6. In your last organization or before that any leadership work have you done? Mentorship/organizer type.
7. What will you do when your work’s credit will be given to another person?
8. Any situation when your manager didn’t agree with your idea and how did you convince him?
9. Why you are leaving before 1 year?
10. What is your plan for 2 years in technical and non-technical aspects?
11. Do you have any questions for me?

• Q3. Covid Vaccination

#### 4. Vaccines administered on ‘dayNumber’ th day should be maximized.

##### Input Format:
``````The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow.

The first line contains three space-separated integers ‘n’, ‘dayNumber,’ and ‘maxVaccines,’ denoting the number of days for which this vaccination drive will go on, the total number of vaccines available for the campaign, and the day for which the number of vaccines administered needs to be maximized respectively.
``````
##### Output Format:
``````For each test case, print an integer denoting the maximum number of vaccines administered on the day ‘dayNumber’.

Print the output of each test case in a separate line.
``````
##### Note:
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1<= T <= 50
1 <= n <=  maxVaccines <= 10^9
0 <= dayNumber < n

Time Limit: 1 sec
``````
• Q4. Painter's Partition Problem

#### You are supposed to return the area of the minimum time to get this job done of painting all the ‘N’ boards under a constraint that any painter will only paint the continuous sections of boards.

##### For example :
``````In the below figure where array/list elements are {2, 1, 5, 6, 2, 3}.
`````` ``````A painter can paint blocks {5,6} or {1,5,6,2} together but not {2,5,6} or {5,6,3}.
``````
##### Input format :
``````The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘K’ denoting the number of elements in the array/list and number of painters available.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
``````
##### Output format :
``````For each test case, print the minimum time required to get the job done.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10^4
1 <= K <= N
1 <= ARR[i] <= 10^5

Where ‘T’ is the number of test cases.
'N' is the length of the given array/list (boards).
‘K’ is the number of painters available.
And, ARR[i] denotes the i-th element in the array/list.

Time Limit: 1 sec.
``````
• Q5. Chocolate Problem

#### Example :

``````Given 'N' : 5 (number of packets) and 'M' : 3 (number of students)
`````` ``````And chocolates in each packet is : {8, 11, 7, 15, 2}

All possible way to distribute 5 packets of chocolates among 3 students are -

( 8,15, 7 ) difference of maximum-minimum is ‘15 - 7’ = ‘8’
( 8, 15, 2 ) difference of maximum-minimum is ‘15 - 2’ = ‘13’
( 8, 15, 11 ) difference of maximum-minimum is ‘15 - 8’ = ‘7’
( 8, 7, 2 ) difference of maximum-minimum is ‘8 - 2’ = ‘6’
( 8, 7, 11 ) difference of maximum-minimum is ‘11 - 7’ = ‘4’
( 8, 2, 11 ) difference of maximum-minimum is ‘11 - 2’ = ‘9’
( 15, 7, 2 ) difference of maximum-minimum is ‘15 - 2’ = 13’
( 15, 7, 11 ) difference of maximum-minimum is ‘15 - 7’ = ‘8’
( 15, 2, 11 ) difference of maximum-minimum is ‘15 - 2’ = ‘13’
( 7, 2, 11 ) difference of maximum-minimum is ‘11 - 2’ = ‘9’

Hence there are 10 possible ways to distribute ‘5’ packets of chocolate among the ‘3’ students and difference of combination (8, 7, 11) is ‘maximum - minimum’ = ‘11 - 7’ = ‘4’ is minimum in all of the above.
``````
##### Input format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains two space-separated integers ‘N’ denoting the number of packets of chocolate and ‘M’ denotes the number of students.

The second line of each test case contains ‘N’ space-separated integers denoting the number of chocolate in each of ‘N’ packets.
``````
##### Output Format :
``````For each test case, print the minimum difference of the chocolates contained in the packets distributed to the students.
``````
##### Note :
``````You don't need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
2 <= M <= N <= 10^4
1 <= CHOCOLATES[i] <= 10^9

Time Limit : 1 sec
``````
• Q6. Minimize the Maximum

#### You are given an array of N integers and an integer K. For each array element, you are allowed to increase or decrease it by a value k. The task is to minimize the difference between the maximum element and the minimum element after modifications.

##### Input Format :
``````The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the test cases follow.

The first line of each test case contains a positive integer N which represents the number of elements of an array.

The Second line of each test case contains N integers denoting the elements of the array.

The third line of each test case contains a positive integer K.
``````
##### Output Format :
``````For each test case, return the minimum difference between the maximum element and minimum element of the array by either increasing or decreasing elements of the array by K.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10^5
0 <= arr[i] <= 10^5
0 <= K <= 10^5

Time limit = 1 sec
``````
• Q7. Farthest Distance From Lands

#### Note :

``````The distance between any two cells (x0, y0) and (x1, y1) is given by the Manhattan distance: |x0 - x1| + |y0 - y1|.
If no land or water exists in the grid, then return -1.
``````
##### Input Format :
``````The first line of input contains an integer ‘T' representing the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the size of the matrix.

The next ‘N’ lines contain ‘N’ integers separated by spaces describing rows of matrix ‘ARR’ (each element of ‘ARR’ is either 0 or 1).
``````
##### Output Format :
``````For each test case, on a separate line, output one integer - the largest distance from a water cell to the nearest land cell.
``````
##### Note :
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10^3
ARR[i][j] = 0 or 1

Time limit: 1 sec
``````

### Interview details

Professional and academic backgroundI applied for the job as SDE - 1 in BangaloreProposed: Eligibility criteriaNo Criteria
Google interview Rounds:Round 1
Round type - Video Call
Round duration - 60 Minutes
Round difficulty - Easy
Round description -

It was a hangout video call. The interviewer asked me these questions. Tell me about yourself and 1 coding question.

Round 2
Round type - Video Call
Round duration - 60 Minutes
Round difficulty - Easy
Round description -

This was an On-site (Behavioural Round) interview. He asked me these questions.

Round 3
Round type - Video Call
Round duration - 60 Minutes
Round difficulty - Easy
Round description -

This was another On-site ( DS & Algo) algorithm.

Round 4
Round type - Video Call
Round duration - 60 Minutes
Round difficulty - Easy
Round description -

Another On-site ( DS & Algo) interview.

Round 5
Round type - Video Call
Round duration - 60 Minutes
Round difficulty - Easy
Round description -

Another On-site ( DS & Algo) interview.

Round 6
Round type - HR Round
Round duration - 60 minutes
Round difficulty - Easy
Round description -

On-site ( DS & Algo) interview.
Google mainly focuses on logic and how you are coming with a solution. It notes down each and every small mistake. Interviewers are really very helpful. They expect clear code with an optimal approach.

Google interview preparation:Topics to prepare for the interview - Java, Data Structure, Algorithms, Dynamic Programming, STLTime required to prepare for the interview - 12 MonthsInterview preparation tips for other job seekers

Tip 1 : Participate in coding contests.
Tip 2 : Practice as many questions as you can.
Tip 3 : Do some good projects.

Application resume tips for other job seekers

Tip 1 : Have some projects on your resume.
Tip 2 : Do not put false things on your resume.

Final outcome of the interviewSelected
View More 1

## Jobs at Google ### Interview Rounds

Coding Test

Video Call

I was interviewed in Feb, 2021.

### Interview Questions

• Q1. Minimum Time To Solve The Problems

#### There are 'N' number of subjects and the ith subject contains subject[i] number of problems. Each problem takes 1 unit of time to be solved. Also, you have 'K' friends, and you want to assign the subjects to each friend such that each subject is assigned to exactly one friend. Also, the assignment of subjects should be contiguous. Your task is to calculate the maximum number of problems allocated to a friend is minimum. See example for more understanding.

##### For Example:
``````If N = 4, K = 2 and subjects = {50,100,300,400}
Assignment of problems can be done in the following ways among the two friends.
{} and {50,100,300,400}. Time required = max(0, 50+100+300+400) = max(0, 850) = 850
{50} and {100,300,400}. Time required = max(50, 100+300+400) = max(50, 800) = 800
{50, 100} and {300,400}. Time required = max(50+100, 300+400) = max(150, 700) = 700
{50,100,300} and {400}. Time required = max(50+100+300, 400) = max(450, 400) = 400
{50,100,300, 400} and {}. Time required = max(50+100+300+400, 0) = max(850, 0) = 850

So, out of all the above following ways, 400 is the lowest possible time.
``````
##### Input format:
``````The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.

Then the 'T' test cases follow.

The first line of each test case contains a single space-separated two integers 'N' and 'K' representing the total subjects and friends.

The second line of each test case contains 'N' space-separated integers representing the problems of the array “subjects”.
``````
##### Output format:
``````For each test case, print the minimum possible time to solve all the problems.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N, K <= 10^4
1 <= subjects[i] <= 10^9

Time limit: 1 sec
``````
• Q2. Sum of Bit Difference Among all Pairs

#### Bit difference of a pair ('ARRi', 'ARRj') is the number of different bits in the numbers’ binary representation. For example, the bit difference of (3,5) is 2. The binary representation of 3 is 011, and of 5 is 101.

##### Note:
``````1. If ('ARRi', 'ARRj') is a pair, then ('ARRj', 'ARRi') will also be considered as a pair.
2. Both positive and negative numbers may be present.
3. Don't ignore the negative sign of the number.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2* T lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘N’ denoting the given integer array size.
The second line of each test case contains the ‘N’ space-separated integers denoting the array elements.
``````
##### Output Format
``````For each test case, return the sum of bit differences among all the pairs.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
1 <= N <= 300
-10^9 <= ARR[i] <= 10^9

Where ARR[i] is the 'i-th' element of the given array.

Time Limit: 1 sec
``````
• Q3. Sum of LCM

#### You are given an integer ‘N’ , calculate and print the sum of :

``````LCM(1,N) + LCM(2,N) + .. + LCM(N,N)
``````

#### where LCM(i,n) denotes the Least Common Multiple of the integers ‘i’ and ‘N’.

##### Input Format:
``````The first line of input contains a single integer T representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the number of times we have to take LCM sum.
``````
##### Output Format :
``````For each test case, return the required sum in a new line
``````
##### Note :
``````You don’t need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 50
1 <= N <= 10^4
Where ‘T’ is the number of test cases, and ‘N’ is the given integer

Time Limit:1sec
``````
• Q4. Sudoku

#### For example: Consider following sudoku: #### It will be solved as: #### Input Format:

``````First nine lines of input contain N(=9) space-separated integers, representing elements of 2D array ARR.
``````

#### Output Format

``````For each test case, return the solution of sudoku.
``````

#### Note:

``````You do not need to print anything; it has already been taken care of. Just implement the given function.

The system will print ‘CORRECT SOLUTION’ if your solution to sudoku is correct, ‘INCORRECT SOLUTION’ otherwise.
``````

#### Constraints:

``````N = 9
0<= ARR[i][j] <=9

Time Limit: 1 second
``````
• Q5. Delete Node In A Linked List

#### Note:

``````• The reference to the head of the linked list is not given.
• The node to be deleted is not a tail node.
• The value of each node in the Linked List is unique.
• It is guaranteed that the node to be deleted is present in the linked list.
``````

#### A sample Linked List- ##### Input format:
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.

The second line of each test case contains a single integer K which denotes the node to be deleted from the Linked List.

For more clarity please refer to the sample inputs.
``````
##### Output format:
``````For each test case, delete the given node and then print a single line containing the elements of the Linked List separated by a single space, '-1' at the end denotes the end of the linked list.

The output for each test case will be printed in a new line.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
2 <= N <= 5000
-10 ^ 9 <= NODE.DATA <= 10 ^ 9 and node.data != -1

Where 'N' denotes the total number of nodes in the Linked List and 'NODE.DATA' is the value of the node present.

Time limit: 1 sec.
``````
• Q6. Aptitude Question

Alok has three daughters. His friend Shyam wants to know the ages of his daughters. Alok gives him first hint.

1) The product of their ages is 72.

Shyam says this is not enough information Alok gives him a second hint.

2) The sum of their ages is equal to my house number.

Shyam goes out and look at the house number and tells “I still do not have enough information to determine the ages”.

Alok admits that Shyam can not guess and gives him the third hint

3) The oldest of the girls likes strawberry ice-cream.

Shyam is able to guess after the third hint. Can you guess what are the ages of three daughters?

• Q7. Maximum Subarray Sum

#### For e.g.- All the non-empty subarrays of array [1,2,3] are , , , [1,2], [2,3], [1,2,3].

##### Input Format
``````The first line of input contains a single integer ‘N’ denoting the number of elements in the array/list.

The second line of input contains ‘N’ single space-separated integers, denoting the elements of the array.
``````
##### Output Format :
``````Print the maximum possible sum of any subarray of the array/list.

Note: You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= N <= 5*10^5
-10^9 <= ARR[i] <=10^9

Time Limit: 1sec
``````
• Q8. Technical Questions

1) What are the different types of scaling?

2) Few SQL Queries

• 1) Getting top salary for a department
• 2) Queries based on Joins

3) Virtual Memory

### Interview details

Professional and academic backgroundI applied for the job as SDE - Intern in DelhiProposed: Eligibility criteriano
Google interview Rounds:Round 1
Round type - Online Coding Test
Round duration - 60 minutes
Round difficulty - Easy

Round 2
Round type - Online Coding Test
Round duration - 60 minutes
Round difficulty - Medium

Round 3
Round type - Video Call
Round duration - 60 minutes
Round difficulty - Hard

Round 4
Round type - Video Call
Round duration - 60 Minutes
Round difficulty - Easy
Round description -

Timing was around 3 pm.

Google interview preparation:Topics to prepare for the interview - Confidence in Problem-Solving, Data Structures & Algorithms (PS/DS), Practice a few machine coding problems, Refine CS foundations notes, Fix common interview mistakes, Start coding a few problems on whiteboard or paper to get used to it.Time required to prepare for the interview - 8 MonthsInterview preparation tips for other job seekers

Tip 1 : Practice on white board
Tip 2 : Spend daily some time
Tip 3 : Practice previous questions

Application resume tips for other job seekers

Tip 1 : Resume should be short and neat
Tip 2 : Keep only thing in which you are sure you will answer all questions

Final outcome of the interviewRejected
View More 1 1

### Interview Rounds

Coding Test

Video Call

I was interviewed in Sep, 2020.

### Interview Questions

• Q1. Distance between two nodes of a Tree

#### Distance between two nodes is defined as the minimum number of edges in the path from one node to another.

##### Input Format:
``````The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains elements in the level order form, and all the node values in the given tree are unique. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

The second line of each test case contains two single-spaced integers, Node 1 and Node 2, representing the values of the two nodes.

For example, the input for the tree depicted in the below image would be:
`````` ``````1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
7 5
``````

#### Explanation:

``````First 5 lines represent the tree, and the last line contains the value of the nodes between which we have to find the distance.

Level 1:
The root node of the tree is 1

Level 2:
Left child of 1 = 2
Right child of 1 = 3

Level 3:
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4:
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5:
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1). The last line contains the value of the two nodes (7 and 5) between which we have to find the distance.
``````
##### Note:
``````The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
7 5
``````
##### Output Format:
``````For each test case, a single integer denoting the distance between the two nodes is printed. In case, if any of the nodes is not found in the tree, return -1.

The output for each test case is in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the give function.
``````
##### Constraints:
``````1 <= T <= 10 ^ 2
1 <= N <= 3 * 10 ^ 3
0 <= DATA <= 10 ^ 6 and DATA != -1

Where ‘T’ is the number of test cases, ‘N’ is the total number of nodes in the binary tree, and ‘DATA’ is the value of the binary tree node.

Time Limit: 1 sec.
``````
• Q2. Delete Leaf Nodes with Value X

#### Your task is to delete all the leaf nodes with value X. In the process, if the newly formed leaves also have value X, you have to delete them too.

##### For example:

``````For the given binary tree, and X = 3:
`````` ##### Input Format:
``````The first line contains an integer T, the number of test cases. Then T cases follow.

For each test case, the first line contains input in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

The second input line contains integer X, the value to be deleted.

For example, the input for the tree depicted in the below image would be :
`````` ``````1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
``````

#### Explanation :

``````Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
``````
##### Note :
``````The above format was just to provide clarity on how the input is formed for a given tree.

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
``````
##### Output Format:
``````For each test case, in a new output line, print the inorder traversal of the tree.
``````
##### Note:
``````You don't need to print anything. Just make the changes in the given tree itself and return the root of the updated tree.
``````
##### Constraints:
``````1 <= T <= 100
0 <= N <= 3*10^3
1 <= A <= 10^5
1 <= X <= 10^5

Time limit: 1sec
``````
• Q3. Maximum sum path from the leaf to root

#### For Example: ``````All the possible root to leaf paths are:
3, 4, -2, 4 with sum 9
5, 3, 4 with sum 12
6, 3, 4 with sum 13
Here, the maximum sum is 13. Thus, the output path will be 6, 3, 4.
``````

### Note:

``````There will be only 1 path with max sum.
``````
##### Input format:
``````The very first line of input contains an integer 'T' denoting the number of queries or test cases.

The first and only line of every test case contains elements of the binary tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take 0 in its place.

For example, the level order input for the tree depicted in the above image would be :

4
-2 3
4 0 5 6
0 3 0 0 0 0
0 0
``````

#### Explanation :

``````Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = -2
Right child of 4 = 3

Level 3 :
Left child of -2 = 4
Right child of -2 = null (0)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (0)
Right child of 4 = 3
Left child of 5 = null (0)
Right child of 5 = null (0)
Left child of 6 = null (0)
Right child of 6 = null (0)

Level 5 :
Left child of 3 = null (0)
Right child of 3 = null (0)
``````
##### Note :
``````The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

4 -2 3 4 0 5 6 0 7 0 0 0 0 0 0
``````
##### Output format:
``````For each test case, print integers representing the path from the leaf node to the root node which has the maximum sum separated by spaces in a single line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 3000
-10 ^ 5 <= DATA <= 10 ^ 5, DATA != 0

where 'T' is the number of test cases, 'N' is the number of nodes in the tree and 'DATA' is the value of each node.

Time limit: 1 sec
``````
• Q4. Ninja and the bulbs

#### The number of bulbs that are on after the end of 'N' rounds are of good quality. Your task is to help Ninja in finding the number of good bulbs.

##### Example
``````Let 'N' = 4

Then in the first round, all bulbs are on.

In the second round bulbs, 2 and 4 are turned off.

In the third round bulb, 3 is turned off.

In the fourth round bulb, 4 is turned on.

So at the end of 'N' (4) round, only the bulb 1 and 4 is on, so there are 2 good bulbs.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

Each test case contains an integer 'N' representing the number of bulbs.
``````
##### Output Format :
``````For every test case, return an integer denoting the number of good bulbs.
``````
##### Note:
``````You don’t need to take input or print anything. This already has been taken care of. Just implement the function.
``````
##### Constraints
``````1 <= T <= 10
1 <= N <= 10^9

Time limit: 1 sec
``````

### Interview details

Professional and academic backgroundI completed Computer Science Engineering from Chitkara University. I applied for the job as SDE - Intern in HyderabadProposed: Eligibility criteriaMust be enrolled in a Bachelor's degree
Google interview Rounds:Round 1
Round type - Online Coding Interview
Round duration - 45 minutes
Round difficulty - Easy
Round description -

Timing : Evening

Round 2
Round type - Video Call
Round duration - 45 minutes
Round difficulty - Easy
Round description -

Timing : 10:00 pm

Round 3
Round type - Video Call
Round duration - 45 minutes
Round difficulty - Easy
Round description -

Timimg : 11:00 pm

Google interview preparation:Topics to prepare for the interview - Data Structures, Algorithms, Dynamic Programming, Trees, Operating SystemTime required to prepare for the interview - 7-8 monthsInterview preparation tips for other job seekers

Tip 1 : Practice as much you can
Tip 2 : Study Data Structures
Tip 3 : Be confident

Application resume tips for other job seekers

Tip 1 : Mention only what you are confident about
Tip 2 : Mention tools & technologies used in the project as well

Final outcome of the interviewRejected
View More  Contribute to the growing community

Don’t worry. You can choose to be anonymous.