Google

4.4
i
Google overall rating is based on 361 company reviews, including all divisions and wholly owned subsidiaries.

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

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 are given a positive integer 'N’. Your task is to find and return the minimum number of steps that 'N' has to take to get reduced to 1.

    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

    You are given a string (STR) of length N.

    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.
    

    Follow up:

    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

    Given that integers are read from a data stream. Your task is to find the median of the elements read so far.

    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

    Consider a directed graph of ‘N’ nodes where each node is labeled from ‘0’ to ‘N - 1’. Each edge of the graph is either ‘red’ or ‘blue’ colored. The graph may contain self-edges or parallel edges. You are given two arrays, ‘redEdges’ and ‘blueEdges’, whose each element is of the form [i, j], denoting an edge from node ‘i’ to node ‘j’ of the respective color.

    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]]
    

    example

    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

    You are given a list of strings, ‘DICTIONARY[]’ that represents the correct spelling of words and a query string ‘QUERY’ that may have incorrect spelling. You have to check whether the spelling of the string ‘QUERY’ is correct or not. If not, then return the list of suggestions from the list ‘DICTIONARY’. Otherwise, return an empty list which will be internally interpreted as the correct string.

    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

    You are given 'N' rectangular buildings in a 2-dimensional city. Your task is to compute the skyline of these buildings, eliminating hidden lines return the skyline formed by these buildings collectively. A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. The geometric information of each building is given in the array of buildings where BUILDINGS[i] = [LEFT_i, RIGHT_i, HEIGHT_i]:

    -> LEFT_i is the x coordinate of the left edge of the ith building.

    -> RIGHT_i is the x coordinate of the right edge of the ith building.

    -> HEIGHT_i is the height of the ith building.

    You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

    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
track
3
Software Engineer interview
track

Interview Rounds

Coding Test

Video Call

I was interviewed in Nov, 2020.

Interview Questions

  • Q1. Min Steps to one using DP

    You are given a positive integer 'N’. Your task is to find and return the minimum number of steps that 'N' has to take to get reduced to 1.

    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

    Given a string ’S’ consisting of lower case English letters, you are supposed to return the longest palindromic substring of ‘S’.

    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

    Consider a directed graph of ‘N’ nodes where each node is labeled from ‘0’ to ‘N - 1’. Each edge of the graph is either ‘red’ or ‘blue’ colored. The graph may contain self-edges or parallel edges. You are given two arrays, ‘redEdges’ and ‘blueEdges’, whose each element is of the form [i, j], denoting an edge from node ‘i’ to node ‘j’ of the respective color.

    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]]
    

    example

    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

    You are given a list of strings, ‘DICTIONARY[]’ that represents the correct spelling of words and a query string ‘QUERY’ that may have incorrect spelling. You have to check whether the spelling of the string ‘QUERY’ is correct or not. If not, then return the list of suggestions from the list ‘DICTIONARY’. Otherwise, return an empty list which will be internally interpreted as the correct string.

    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

    You are given 'N' rectangular buildings in a 2-dimensional city. Your task is to compute the skyline of these buildings, eliminating hidden lines return the skyline formed by these buildings collectively. A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. The geometric information of each building is given in the array of buildings where BUILDINGS[i] = [LEFT_i, RIGHT_i, HEIGHT_i]:

    -> LEFT_i is the x coordinate of the left edge of the ith building.

    -> RIGHT_i is the x coordinate of the right edge of the ith building.

    -> HEIGHT_i is the height of the ith building.

    You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

    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
track
1
Software Engineer interview
track

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
    2. Why Google?
    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?

    Add Answer Collapse
  • Q3. Covid Vaccination

    We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase vaccination following safety measures. Time is running out. Can you help the nation?

    You are given two positive integers: ‘n,’ ‘maxVaccines’ denoting the number of days for which this vaccination drive will go on and the total number of vaccines available for the drive, respectively. You have to find the number of vaccines administered each day. You are also given a number ‘dayNumber,’ and we are interested to know the maximum number of vaccines that can be administered on ‘dayNumber’ th day.

    The rules of the vaccination drive :

    1. There should be a positive number of vaccines administered each day during the vaccination drive.

    2. The absolute difference between the number of vaccines in two consecutive days should not exceed 1.

    3. The sum of all the elements of the vaccines array does not exceed maxVaccines, that is, you cannot administer more vaccines than what is provided to you.

    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

    Given an array/list of length ‘N’, where the array/list represents the boards and each element of the given array/list represents the length of each board. Some ‘K’ numbers of painters are available to paint these boards. Consider that each unit of a board takes 1 unit of time to paint.

    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}.
    

    alt text

    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

    Given an array/list of integer numbers 'CHOCOLATES' of size 'N', where each value of the array/list represents the number of chocolates in the packet. There are ‘M’ number of students and the task is to distribute the chocolate to their students. Distribute chocolate in such a way that:

    1. Each student gets at least one packet of chocolate.

    2. The difference between the maximum number of chocolate in a packet and the minimum number of chocolate in a packet given to the students is minimum.

    Example :

    Given 'N' : 5 (number of packets) and 'M' : 3 (number of students)
    

    subsequence

    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

    You are given a binary square matrix ‘ARR’ with N rows and N columns, in which 0 represents the water and 1 represents the land.

    You have to find a water cell such that its distance to the nearest land cell is maximized and print the maximum distance.

    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
track
1

Jobs at Google

Software Engineer interview
track

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

    Given an array of size ‘N’ containing integer elements and let the elements of the given array be 'ARR1', 'ARR2',…..,' ARRN'. You need to find the sum of bit differences among all the pairs that can be formed using the given array elements.

    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

    You are given a 9x9 sudoku. Your task is to solve sudoku and return the solution.

    A sudoku is a puzzle in which players insert the numbers one to nine into a grid consisting of nine squares subdivided into a further nine smaller squares in such a way that every number appears once in each horizontal line, vertical line, and square.

    For example: Consider following sudoku:

    example1

    To solve it you have to fill blank spaces by numbers from 1 to 9 subject to constraints:

    Any number should not occur more than once per row.

    Any number should not occur more than once per column.

    Any number should not occur more than once per block of 3x3(here, each block is distinguished by bold borders).

    It will be solved as:

    example1

    Input Format:

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

    Note: Empty slots in the input are represented by number 0.

    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

    You are given a Singly Linked List of integers and a reference to the node to be deleted. Every node of the Linked List has a unique value written on it. Your task is to delete that node from the linked list.

    A singly linked list is a linear data structure in which we can traverse only in one direction i.e. from Head to Tail. It consists of several nodes where each node contains some data and a reference to the next node.

    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-

    singly_linkedlist

    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?

    Add Answer Collapse
  • Q7. Maximum Subarray Sum

    You are given an array/list ARR consisting of N integers. Your task is to find the maximum possible sum of a non-empty subarray(contagious) of this array.

    Note: An array C is a subarray of array D if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end of array D.

    For e.g.- All the non-empty subarrays of array [1,2,3] are [1], [2], [3], [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 

    Add Answer Collapse

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
track
1
Software Engineer interview
track
1

Interview Rounds

Coding Test

Video Call

I was interviewed in Sep, 2020.

Interview Questions

  • Q1. Distance between two nodes of a Tree

    Given a binary tree and the value of two nodes, find the distance between the given two nodes of the Binary 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:
    

    example

    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

    You are given a binary tree, in which the data present in the nodes are integers. You are also given an integer 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:
    

    tree

    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 :
    

    alt text

    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

    You are given a binary tree of 'N' nodes.

    Your task is to find the path from the leaf node to the root node which has the maximum path sum among all the root to leaf paths.

    For Example:

    sample tree

    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

    Ninja owns an electronic shop. In the shop, Ninja has 'N' bulbs. To sell these bulbs, Ninja has to check if they are of good quality. To check bulbs, Ninja uses a unique technique.

    In this technique, in the first round he, turn on all the bulbs, then in the second round, he turns off every second bulb then in the third round, he chooses every third bulb and turns off it is on, or turn on if it is off and so no. He repeats this process 'N' times.

    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
track
Software Engineer interview
track

Contribute to the growing community

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

Report Interview Advice

What’s wrong with this interview advice?