Google Interview Questions
- 3of 3 votes
AnswersQuestion 1.
- anonymous October 24, 2017 in India
You are given a string composed of uppercase English letters (‘A’ through ‘Z’).
Set of letters (‘A’, ‘E’, ‘I’, ‘O’, ‘U’) are called vowels. Other letters are called consonants.
We define foo value of a string as number of pairs of exactly same consecutive vowel letters.
For example,
Ex.1: BCDEEIOU - This has a foo value of 1 (because of EE). Note that although I is next to E, and O is next to I, and U is next to O, they aren’t exactly same neighbours, so they don’t contribute to foo value
Ex.2: BCDEEEIOU - This has foo value of 2. Because of first pair of EE and immediately next pair of EE
Ex.3: ABCDEFG - This has foo value of 0. There are no consecutive vowels
Ex.4: ABEUUOUOO - This has foo value of 2, because of UU and OO
You are given 2 inputs, N and K.
How many strings of length N can you form such that they all have foo value of K?
Let’s assume the constraints as:
1<=N<=15
0<=K<N| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGiven 2 words, return true if second word has a substring that is also an anagram of word 1.
- anonymous October 07, 2017 in United States
LGE , GOOGLE- True
GEO, GOOGLE - False| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersCheck if two DOM Trees have the same text.
- wtcupup2017 September 28, 2017 in United States
e.g. <html><p>hello</p></html>, <html><p><b>h</b>ello</p></html> should be the same text
DOMNode class definition (string tag, string text, bool isText, vector<DOMNode*> children)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
Answerscreate a class of integer collection,
- aonecoding September 22, 2017 in United States
3 APIs:
append(int x),
get(int idx),
add_to_all(int x),
in O(1) time。
Follow-up:
implement
multiply_to_all(int x)
e.g.
insert(1)
insert(2)
add_to_all(5)
insert(3)
get(0) -> returns 6
get(2) -> return 3
multiply_to_all(10)
insert(4)
get(1) -> returns 70
get(2) -> returns 30
get(3) -> returns 4| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersLonely Pixel
- aonecoding September 22, 2017 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 Algorithm - 3of 3 votes
AnswersFind max size of contiguous shape below, where X represents a shape and . is empty:
- steez September 21, 2017 in United States
.XXXXXX....
...X..XX..X
...XXXX....
..X.....X..
..XXX..XX..
.....XX....
/*method stub*/
public int GetMaxShape(char[][] array) {
}
i was able to come up with a recursive solution but i'd love tips on a dp solution| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGenerate a random binary tree, with equal probability.
- pb August 30, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -2of 2 votes
AnswersMedian of Stream of Running Integers
- anaghakr89 August 16, 2017 in United States
Note: The integers are in particular range from 1..n
The time complexity of the code should be o(n)| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersRound4
- aonecoding August 09, 2017 in United States
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersRound3
- aonecoding August 09, 2017 in United States
For N light bulbs, implement two methods
I. isOn(int i) - find if the ith bulb is on or off.
II. toggle(int start, int end)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersRound1
- aonecoding August 09, 2017 in United States
Find if two people in a family tree are blood-related.
Round2
Given some nodes in a singly linked list, how many groups of consecutively connected nodes there is.
For linked list
0->1->2->3->4->5->6,
given nodes 1, 3, 5, 6
there are 3 groups [1], [3], and [5, 6].| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersExplain the linear piecewise function.
- anaghakr89 August 09, 2017 in United States for Nest Labs| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersWe have N gas stations, and we are given all the distances between each pair of station. So we have nC2 distances provided to us. For example if I have 3 stations namely A, B, C the distances provided will be AB, AC, BC. We have to find the exact position of each gas station provided with these nC2 distances.
- logan9 August 05, 2017 in United States
eg. we have 5 stations so 5C2 distances are given in random order - 10, 20, 70, 80, 30, 20, 100, 70, 50, 90
Output the exact positions of gas stations A, B, C, D, E
i.e
A - 0
B - 10
C - 30
D - 80
E - 100
refer this image for more clarity
https://drive.google.com/open?id=0BxPkptdH01OBZzEwX29iRGI4cEU| Report Duplicate | Flag | PURGE
Google Software Engineer Problem Solving - 1of 1 vote
AnswersRound 5:
- aonecoding August 03, 2017 in United States
Given a set of synonyms such as (fast, quick), (fast, speedy), (learn, study), decides if two sentences were synonymous.
(The sentences were structurally the same and has the same number of words in them.
The synonymous relation [fast ~ quick] and [fast ~ speedy] does not necessarily mean [quick ~ speedy].)
Follow-up:
If the synonymous relation passes down so that [fast ~ quick] and [fast ~ speedy] implies [quick ~ speedy], decide if two sentences were synonymous.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersRound 4:
- aonecoding August 03, 2017 in United States
Implement a class Employment with these 3 methods: assignManager(p1, p2): assign p1 as p2's manager. beColleague(p1, p2): make p1 and p2 peer colleagues. isManager((p1, p2): decide if p1 is the manager of p2.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersRound 3
- aonecoding August 03, 2017 in United States
Given a matrix of 0s and 1s where 0 is wall and 1 is pathway, print the shortest path from the first row to the last row.
Can walk to the left, top, right, bottom at any given spot.
Follow-up:
If every pathway takes a cost (positive integer) to get through, print the minimum cost path from the first row to the last row.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGoogle on-site June
- aonecoding August 03, 2017 in United States
Round 1
Leetcode 10
Round 2
Select a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).
Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answers1 year exp. Interviewed at Cambridge, MA
- aonecoding July 11, 2017 in United States
Round1
LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.
Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.
Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Follow-up: decode with utf-16. It took quite a while for me to understand the rules.
Round4
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 3 votes
Answers - missing July 07, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 3of 3 votes
AnswersGoogle full-time phD candidate w/ work experience.
- aonecoding June 22, 2017 in United States
Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?
Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)
Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.
Q4.
Design merchandising product data storage service| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersGoogle On-site in May
- aonecoding June 15, 2017 in United States
Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x),//add x to all numbers in collection
These methods should run in O(1) time.
Follow-up
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a large file with sentences and query string, design a system (Class, data structs, functions, etc) and algorithm to return the smallest window (start and end offsets) in the input file where the query words (in any order) are seen in the text file. What is the time complexity?
- Ray May 01, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer System Design - 1of 1 vote
AnswersGenerate a random 4-digit even number : the adjacent 2 digits must be different.
- ajay.raj April 28, 2017 in United States
public int getNumber(){
}| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersFind two strings are meta string or not
- ashishsaraswat.iips April 18, 2017 in India
for eg:-
Converse
Conserve
are meta strings because if we swap s and v in the string both string will become equal. If swapping of more than one pair can be done then it is not a meta string| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersFind the median of a bst in O(n) time and O(1) space
- ashishsaraswat.iips April 18, 2017 in India| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven a count and maxvalue, write a program to return count number of unique random integers between 0 and maxvalue.
- Ray April 17, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersFind the Lexicographic next word of the input word from a list of words
- ajay.raj April 16, 2017 in United States
Example
Words list
[Cat, dog, cow, donkey, zebra, monkey],
input
duck
output
monkey
Input
dog
output
donkey
Can you use trie to solve it?
public String findNextWord(List<String> words, String input){
}| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGiven a equation in the form of "3x+4y+2=-5y+2x+10", simplify the equation to be in form "y=Ax+B", and return A,B. Also allow parenthesis to be in the equation. Ex. "3y-4x+(3-(2x-3y))=10y", result is "y =0.75 - 1.5x"
- anony-mites April 16, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 6of 6 votes
Answers5th Round
- aonecoding April 13, 2017 in United States
Open-ended question What happens when you type a url in the browser and hit enter?
Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
Answerinterviewed by senior engineer
- aonecoding April 13, 2017 in United States
Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
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 Algorithm