### 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.`

View Answer (2)Collapse - 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`

View Answer (3)Collapse - 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`

View Answer (2)Collapse - 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`

View Answer (3)Collapse - 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]]`

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

View Answer (2)Collapse - 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`

View Answer (1)Collapse - 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`

View Answer (2)Collapse

### Interview details

**Professional and academic background**I completed Computer Science Engineering from Delhi Technological University. I applied for the job as SDE - 1 in Bangalore

**Proposed: Eligibility criteria**No 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, Bitmasks

**Time required to prepare for the interview**- 5 months

**Interview 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 interview**Selected