Google Interview Questions
- 2of 2 votes
AnswersGiven an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.
- me December 27, 2008
This is same as You have an array containing only '0's, '1's and '2's. Club same items together in single scan.| Report Duplicate | Flag | PURGE
Google Software Engineer in Test - 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 - 2of 2 votes
AnswersGiven a list of words with lower and upper cases. Implement a function to find all Words that have the same unique character set .
- marium27 March 14, 2017 in United States
For example:
May student students dog studentssess
god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice
output:
may amy
student students studentssess
dog god
cat act
tab bat
flow wolf
lambs balms
looped, poodle| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersYou have rating (0-10) of the hotels per user in this format:
- theconqueror July 07, 2016 in United States
scores = [
{'hotel_id': 1001, 'user_id': 501, 'score': 7},
{'hotel_id': 1001, 'user_id': 502, 'score': 7},
{'hotel_id': 1001, 'user_id': 503, 'score': 7},
{'hotel_id': 2001, 'user_id': 504, 'score': 10},
{'hotel_id': 3001, 'user_id': 505, 'score': 5},
{'hotel_id': 2001, 'user_id': 506, 'score': 5}
]
Any given hotel might have more than one score.
Implement a function, get_hotels(scores, min_avg_score) that returns a list of hotel ids that have average score equal to or higher than min_avg_score.
get_hotels(scores, 5) -> [1001, 2001, 3001]
get_hotels(scores, 7) -> [1001, 2001]
*/
How to solve this in C++ and Python?| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersYou are given information about hotels in a country/city. X and Y coordinates of each hotel are known. You need to suggest the list of nearest hotels to a user who is querying from a particular point (X and Y coordinates of the user are given). Distance is calculated as the straight line distance between the user and the hotel coordinates.
- abc June 19, 2014 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 2of 2 votes
AnswersI have a list of several million words unsorted.
- Anon August 08, 2013 in United States
How can you find the largest and the smallest words that can be typed by a single hand on a qwerty-style keyboard? Following the rules of finger placement, a word can either be typed fully on the left-hand side of the keyboard, the right-hand side, or both. Find the largest and smallest left-hand word(s), and the largest and smallest right-hand word(s).
given: millions of words, unsorted
given: set of left-hand chars - a,s,d,f,...
given: set of right-hand chars - j,k,l...| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Data Structures - 2of 2 votes
AnswersGiven a family tree for a few generations for the entire population and two people write a routine that will find out if they are blood related. Siblings are blood related since they have the same parents. Cousins are blood related since one of their parents have the same parents etc. Design the data structure first and then write the routine.
- hsantosh71 June 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 2of 2 votes
AnswersGiven a set of intervals, find the interval which has the maximum number of intersections.
- hello world February 27, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm Data Structures - 2of 2 votes
AnswersGiven a binary tree, implement an iterator that will iterate through its elements.
- carlosgsouza July 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a string A consisting of n characters and a string B consisting of m characters, write a function that will return the number of times A must be stated such that B is a substring of the repeated A. If B can never be a substring, return -1.
- neer.1304 July 03, 2019 in United States
Example:
A = ‘abcd’
B = ‘cdabcdab’
The function should return 3 because after stating A 3 times, getting ‘abcdabcdabcd’, B is now a substring of A.
You can assume that n and m are integers in the range [1, 1000].| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven an int array without repeated elements and a target, count the total number of subset that can be generated from the array such that min (subset) + max (subset) < target
- ajay.raj March 13, 2017 in United States
public int countSubSet(int[] nums, int target){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
Answersstd C library has pow(x, n) function - implement that function
- kumarr.arvind June 20, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer 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 - 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
AnswersYou are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.
- camiloni42 November 19, 2016 in United States
When facing each enemy you can either:
1) Fight him (if your strength is enough). You keep your money.
2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.
Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).
This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersCount triangles in an undirected graph where a triangle is a unique set of three vertices connected to one another.
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersYou are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
- game January 21, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
Answersfind nearest word from the given non-english dictionary which is one off character. (could be non ascii characters)
- prathji October 01, 2019 in United States
for eg. dictionary contains { apple, pineapple, banana, orange }
if given word "applx" then return true, as applx matches with apple and only one character is off.
aplpe returns false| Report Duplicate | Flag | PURGE
Google Software Developer - 2of 2 votes
AnswersWe have an iterator class as below:
class CIterator { int Next(); //Returns the value of the next element in the iteration by advancing the iterator bool HasNext() const; //check whether any next element for the current iterator };
We need a CPeekIterator class which is having below functionalities
Class CPeekIterator { int Next (); //Same as CIterator does bool HasNext() const; //same as CIterator does int Peek(); // Returns the next element in the iteration without advancing the iterator };
Write the CPeekIterator class
- johnsvakel November 24, 2015 in United States for GFS| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersGiven 2 sorted array print their intersection.
- morpheus September 26, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Arrays - 2of 2 votes
AnswersWhen a person who knows it meets any other person, they immediately share the story with them.
- veeru June 25, 2021 in India
Initially, only person 1 knows the story. Given a list of meetings between people in a form of
(person_1_id, person_2_id, timestamp) construct a list of the persons who will know the story
at the very end.
Example: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 // The events could be out of order.
Person 2 will learn the story at the moment 100, person 3 — at the moment 300,
person 5 — in the moment 400. Person 4 will never learn the story. So the answer is [1, 2, 3, 5].
Eg2: [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2
where the first parameter is array of the Persons meet at particular timestamp, second parameter is the PersonId who knows the story first.
Output: [1, 2, 3]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 2 votes
AnswersFind three non-overlap windows of size k in an int array, that together has a maximum sum
- ajay.raj March 14, 2017 in United States
of the 3k entries.
example
int[] nums = [1,2,1,2,6,7,5,1]
k = 2
output
[1,2],[2,6],[7,5]| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersData structure which supports both map operations and array operations without time complexity penalty.
- Ray November 14, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Data Structures - 2of 2 votes
AnswersSort a list of numbers in which each number is at a distance k from its actual position
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
AnswersYou have N points on a 2D surface. List K points at a shortest distance to the point (0, 0).
- tested.candidate March 22, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a list of 2d points, if any two points have distance(straight line) <= k , group them together. For example. [P1,P2,P3], P1 to P2 <=k, P2 to p3<=k, p1 to p3>k. they are still in the same group. (distance relationship is chainable ) ask how many groups can you find ? I can think of N^2 time complexity with union and find. but how to do better than that? maybe NlogN or O(N)?
- laoen November 30, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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 - 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 - 2of 2 votes
AnswersYou are trying to to daemonize an unknown, black-box binary executable. The binary executable returns no output to STDOUT or STDERR. Assume that the mystery binary return code is non-zero. What troubleshooting steps might you take to learn more about what the binary is supposed to do, and why it is failing?
- longbelly March 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Unix - 2of 2 votes
AnswersGiven two numbers m and n, write a method to return the first number r that is
- GillY January 21, 2012 in India
divisible by both (e.g., the least common multiple)| Report Duplicate | Flag | PURGE
Google