## Google Interview Questions

- 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 - 0of 0 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 1 vote

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 - 0of 0 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 - 2of 2 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 - 3of 3 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 - 2of 2 votes

Answers[Google On-site 2018 Winter]

- aonecoding4 November 28, 2018 in United States

Set Matrix Zeroes II

There are orbs on an NxM board ('O' denotes orb. 'X' denotes empty slot).

Whenever two orbs are in the same column or the same row, you get to erase one of them.

Try to erase as many orbs as possible.

Find the minimum number of orbs remained on board eventually.

e.g.

OXOXXO

XXXXXO

XXXXOX

erase (0,0) and get

XXOXXO

XXXXXO

XXXXOX

erase (2,0) and get

XXXXXO

XXXXXO

XXXXOX

erase (5,0) and get

XXXXXX

XXXXXO

XXXXOX

no more moves available. Return 2 e.g.

OXOXXO

XXXXXO

XXOXOX

erase(4,2), (2,2), (0,0), (2,0), (5,0)

Return 1

e.g.

OXOXXX

XOXXXO

XXXOOX

erase(0,0), (1,1), (3,2)

Return 3

Follow-up Build a solver for this board game that erases the as many orbs as possible.| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

AnswerRoulette -Gamblers Fallacy. start with $50, bet opposite color every time same color 4 in a row. loop 100 time or until $0. Suggest create roulette wheel object with history, a gambler object with maybe gamblingplan object. (you can find more detailed suggestions elsewhere)

- whoknows November 18, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 2of 2 votes

AnswersGiven a tree with n nodes. Each node has k coins, where 0 <= k <= n . There are total n coins on the tree.

- aonecoding4 November 18, 2018 in United States

The goal is to move the coins such that each node has exactly one coin. What's the minimum moves required?

Each move can only move one coin to an adjacent node.| Report Duplicate | Flag | PURGE

Google Software Engineer - 3of 3 votes

AnswersYou have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in 5 boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum.

- parni November 01, 2018 in United States

You can only choose consecutive toffee packets to put in a box.| Report Duplicate | Flag | PURGE

Google - 0of 0 votes

AnswersThe difference between move and forward in C++

- parni November 01, 2018 in United States| Report Duplicate | Flag | PURGE

Google C++ - -3of 3 votes

Answerbinary search

- James666 October 22, 2018 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

AnswersHow would you tell whether a graph has a node with n degree??

- shivamdurani220 October 11, 2018 in United States

tell your approach| Report Duplicate | Flag | PURGE

Google SDE-2 - 0of 0 votes

AnswersThere is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

- shivamdurani220 October 09, 2018 in United States

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.| Report Duplicate | Flag | PURGE

Google SDE-2 - 1of 1 vote

AnswersGiven an array of integers, find out how many unique BST can be generated from the array.

- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Trees and Graphs - 1of 1 vote

AnswersGiven an array of Integers, find out how many combinations in the array, satisfy the equation x+y+z=w, where x,y,z and w belong to the array and idx(x)<idx(y)<idx(z)<idx(w). Elements are unique.

- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Arrays - 0of 0 votes

AnswersGiven a bench with n seats and few people sitting, tell the seat number each time when a new person goes to sit on the bench such that his distance from others is maximum?

- shivamdurani220 September 22, 2018 in United States| Report Duplicate | Flag | PURGE

Google Software Developer

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window