Google Interview Questions
- 0of 0 votes
AnswersGiven
colors = ["red", "blue", "green", "yellow"];
and a string
str = "Lorem ipsum dolor sit amet";
write a function that prints each letter of the string in different colors. ex. L is red, o is blue, r is green, e is yellow, m is red, after the space, i should be blue.
- rninja2019 May 08, 2019 in United States| Report Duplicate | Flag | PURGE
Google Front-end Software Engineer - 2of 2 votes
AnswersImplement an iterator<WordAndCount> which takes iterator<String> and its next() method returns the count for same word in a row. I was also asked to implement hasNext method.
- Desi May 03, 2019 in United States
WordAndCount class had two properties:
1. Word
2. Count
I was asked to implement hasNext() and next() method which basically returns a WordAndCount object.
To make it clear, following is the example:
lets say Iterator<String> has following values:
{foo,foo,foo,bar,foo,bar,bar}
iterator<WordAndCount> next() method should return this:
{{foo,3},{bar,1},{foo,1},{bar,2}}
It seemed like an easy problem and because we ran out of time during coding i think interviewer didn't ask me the follow up question. Interviewer was nice and he told me he doesn't expect me to code in time limit but he only wants to see how i approach the problem.| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersWrite a program to find the given new program can be scheduled or not?
- veeru April 23, 2019 in United States
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.
As the P4 overlaps with P1, So P4 cannot be scheduled.| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 1of 1 vote
AnswersLonely Pixel
- acoding167 April 22, 2019 in United States
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGiven unsorted array, find how many elements can be found using binary search
- neer.1304 April 21, 2019 in United States
- ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersImplement an api that let's users create multiple timers. You can only use one system timer in your implementation though. For example a user can write:
- neer.1304 April 21, 2019 in United States
timer.startTimer(3, callback)
timer.startTimer(7, callback)
timer.startTimer(1, callback)
and the user will get three callbacks 1, 3, and 7 seconds later. In startTimer you only have one timer that you call like this:
System.startTimer(seconds, callback)
but it can only be called once it has finished with the previous timer.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersBrace Expansion
- neer.1304 April 21, 2019 in United States
Given a string, perfrom the brace expansion
For example,
Input: s = "a{d,c,b}e"
output: {ade , ace , abe}| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a rectangle with width 'W' and height 'H', you have to fit a string 'S' in it with maximum possible font size
- neer.1304 April 21, 2019 in United States
The font size ranges from 1 to 30
You are given two APIs getCharacterWidth(char c , int font_size) and getCharacterHeight(int font_size)
getCharacterWidth(char c , int font_size): returns the width of a character for a particular font size
getCharacterHeight(int font_size): returns the height of characters for a particular font size| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswerHow will you implement organizational chart? Implement two methods - isPeer - Should return true if two employees have same managers. isManager - should return true if manager is management chain of given employee.
- neer.1304 April 21, 2019 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersRelation between 2 animals is given. A is child of B C is child of B A is child of D
- neer.1304 April 21, 2019 in United States
An animal can be child of 0 to 2 parents. With this given data, find out if two animals are related to each other. Follow up question was - Maternal side animals, should not be related to patrernal side family.| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersYou have a 3x3 grid. In each cell you can have two colors, white or black. At the beginning, the matrix has some cells painted white and others black.
- neer.1304 April 21, 2019 in United States
If you change a color cell, that is, grid [i] [j] the cells grid [i-1] [j], grid [i + 1] [j], grid [i] [j-1] and grid [ i] [j + 1] also change (if these positions do not leave the 3x3 grid), that is, if they were white, they change to black.
Return, the minimum number of cells you have to flip for the 3x3 grid to be totally white. If you cannot do this, return -1!
Sample input/output - ibb.co/3Y0WVNR| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersCount number of possible rhythm in a poem.
- nitinguptaiit April 18, 2019 in India
Explanation:
Twinkle, twinkle, little star, [ A ]
How I wonder what you are! [A]
Up above the world so high, [B]
Like a diamond in the sky. [B]
In the above poem, we see the first two line ( ending with "star" and "are" ) is in the rhythm that's why they are given as character "A" and similarly last two lines (ending with "high" and "sky" ] s in the rhythm that's why they are given as character "B".
Questions: Given "n" number of lines in a poem, Count number of possible rhythm in a poem.
P.S. output should be in lexicographical order only
Example:
n=1
only one possible "A"
Answer: A, count =1
n=2 [ possible chars are A,B]
AA
AB
BA <- This is not possible as it collide with AB. How? Look at the pattern
AB says first line has different rhythm and second line has different rhythm then first line.
Similarly BA is also shows the same ; first line has different rhythm and second line has different rhythm then first line.
Hence discard
n=2
AA
AB , count=2
n=3 [ possible chars are A,B, C]
AAA
AAB
ABA
ABB
ABC, count=5
Look we can't have AAC as it collide with AAB (first two are same and last is different in both)
Similarly other BCA/ BAC etc we'll discard them because of collide and lexicographical ordering.
n=4, there will be 15 [ we need to print all of them too ]
My Finding;
1. I found out that, this is just a bell number ( see the pattern 1,2,5,15.... )
2. I found, this is Dynamic programming question, we can generate the next n+1 from n; How
n=2 has
AA
AB
n=3
Take AA; there are three possiblilties to append a character is A,B,C
But since the last character is A; so lexicographically A and B can be appended at the most, since appending C could conflict with B.
AA(A)
AA(B)
Take AB; there are three possibilities to append a character is A,B,C
But since the last character is B; which is lexicographically smaller than A, so lexicographically A, B,C can be appended easily,
AB(A)
AB(B)
AB(C) <- this is possible since its not colliding with any thing
So ans; 5
AA(A)
AA(B)
AB(A)
AB(B)
AB(C)
Now lets try n=4 [ now its become complicated ;A,B,C,D]
Take AAA; possibilty A,B, not possible C/D conflict with B
AAA(A)
AAA(B)
Take AAB, Possibility is A, B C but what about D; is it possible ? Yes/No
AAB(A)
AAB(B)
AAB(C)
AAB(D) <- it collide with last C so discard ;
Hence with AAB
AAB(A)
AAB(B)
AAB(C)
Take ;
ABA(A)
ABA(B)
ABA(C)
ABA(D) Not possible ; collide with C
If you observe there is a pattern with last character to first character from right to left;
Solution: Brute force is obvious solution; and generating number is also fine since you can use Bell number [ i was not able to come up with this solution though, found later]
Any one can help me over here?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersGiven matrix in which each cell is either filled with 'C' (Computer) or empty.
- igeek April 13, 2019
Computers can communicate if they are in the same row or in the same column.
Computers can also communicate through middleware computers.
Given index of a computer, find all computers it can communicate with.
How many communication paths are there?
Find the order of turning computers off, in which every computer will manage to communicate with another computer in order to pass the data it stores before it is turned off, keeping minimum computers on in the end.| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersWrite a program to sort a string without using java API?
- vijaydhanakodi April 10, 2019 in India
I/P : "a390testai"
O/P: 039aaiest| Report Duplicate | Flag | PURGE
Google Backend Developer Algorithm - 1of 3 votes
AnswersA graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted vertices given in K. If it creates a path, we have to discard the edge.
- setu April 01, 2019 in India
Example: N = 4; K = {(1,4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answers":=" denotes the substitution, and "=" is the equal comparator. ======== Initial state of an array "a": [[4, 2, 4, 2], [4, NULL, 4, 2], [2, NULL, 8, 2], [16, NULL, 4, NULL]] ======== Main function: FUNCTION foo() FOR y := 0 to 3 FOR x := 0 to 3 IF a[x+1][y] != NULL IF a[x+1][y] = a[x][y] a[x][y] := a[x][y]*2 a[x+1][y] := NULL END IF IF a[x][y] = NULL a[x][y] := a[x+1][y] a[x+1][y] := NULL END IF END IF END FOR END FOR END FUNCTION
What is the issue with the above code, and how would you fix it?
- aviralchhabra March 26, 2019 in Australia| Report Duplicate | Flag | PURGE
Google Technical Support Engineer Pseudocode - 0of 0 votes
AnswersGiven two binary trees, explain how you would create a diff such that if you have that diff and either of the trees you should be able to generate the other binary tree. Implement a function which takes Node tree1, Node tree2 and returns that diff.
- dovahkiin March 19, 2019 in India| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersCreate an iterator class that stores a list of the built-in Iterators.
- acoding167 March 15, 2019 in United States
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators| Report Duplicate | Flag | PURGE
Google - 5of 5 votes
AnswersFind whether string S is periodic.
- aonecoding4 March 01, 2019 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersGiven a dictionary of words & a miss-spelled input, write a function which will find 3 words from the dictionary which are closest (by difference of 1-character) to the given input.
- vinzee93 February 28, 2019 in United States
eg - dict = {vil, sit, flick, pat, pluck, sat, vat}, input = vit, ans = {sit, vil, vat}| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
Answers// For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
- samayragoyal990 February 24, 2019 in United States
// For example, for K = 8 and vector [2, 4, 5, 7], the solution is 5 ([2], [4], [2, 4], [2, 4, 5], [2, 5])
The time complexity should be O(n2). Approach and code was asked| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersWrite a retry function, continue to fetch data until u have exhausted max entries. If it fails, continue to retry until retry's have been exhausted.
- pri9 February 16, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Coding - 2of 2 votes
AnswersThere are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.
- crowdx February 12, 2019 in India
Given N and number of players from each country and size K. Find the maximum number of teams you can form.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 1of 1 vote
AnswersGiven two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
- aonecoding4 January 30, 2019 in United States
Follow-up: If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGiven a directed graph and a node , find the shortest cycle in a graph with given node .
- saurabh January 23, 2019 in India| Report Duplicate | Flag | PURGE
Google Software Developer Coding - 4of 4 votes
AnswersGiven a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles
- nikki December 31, 2018 in United States
Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 5of 5 votes
Answers[Google] Design Text Editor (Doubly Linked List)
- aonecoding4 December 04, 2018 in United States
Build a text editor class with the following functions,
moveCursorLeft(),
moveCursorRight(),
insertCharacter(char) //insert the char right before cursor
backspace() //delete the char right before cursor
Follow-up
Implement undo() //undo the last edit. Can be called multiple times until all edits are cancelled.
All functions above should take O(1) time.
Example
( '|' denotes where the cursor locates. 'text' shows what's been written to the text editor. )
Start with empty text
text = "|"
insertCharacter('a')
text = "a|"
insertCharacter('b')
text = "ab|"
insertCharacter('c')
text = "abc|"
moveCursorLeft()
text = "ab|c"
moveCursorLeft()
text = "a|bc"
backspace()
text = "|bc"
moveCursorLeft()
text = "|bc" (nothing happens since cursor was on the leftmost position)
undo()
text = "a|bc"
undo()
text = "ab|c"
undo()
text = "abc|"
undo()
text = "ab|"
undo()
text = "a|"| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGiven a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)
- Prateek Agrawal December 02, 2018 in United States
For example
s = 'ababac'
Then substrings are as follow:
1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c
Now, The lengths of LCP of all substrings are as follow
1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0
String contains only lowercase alphabates.| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures