Google Interview Questions
- 3of 3 votes
AnswersHow many occurrences of a given search word can you find in a two-dimensional array of characters given that the word can go up, down, left, right, and around 90 degree bends?
- lueikhong June 07, 2014 in Australia
Ex:
Count of occurrences of SNAKES
S N B S N
B A K E A
B K B B K
S E B S E
The answer is 3.
Write a program for that question.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersConsider the following array {1,2,3,4,5,2,5,4,4};
In the above array, index 4 could be considered as breaking point where summation of 0 to 4 in the array is equal to summation of 5 to end of array. We need to find the breaking point for the given array. I solved this. But follow up was for this array{1,0,-1,-1,1};
. Mathematically the later array's breaking point is 2.
- Madan January 23, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 3of 3 votes
AnswersWrite a function that takes a list L and returns a random sublist of size N of that list. Assume that the indexes must be in increasing order. That is, you cannot go backwards.
- neer.1304 July 03, 2019 in United States
Example:
L = [1, 2, 3, 4, 5]
N = 3
The function should return one of these lists:
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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 - 3of 3 votes
Answerswe have a random list of people. each person knows his own height and the number of tall people in front of him. write a code to make the equivalent queue.
- pari February 18, 2014 in United States
for example :
input: <"Height","NumberOfTall","Name">,
<6,2,"A">,<1,4,"B">,<11,0,"C">,<5,1,"D">,<10,0,"E">,<4,0,"F">
output: "F","E","D","C","B","A" --> end of queue| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven an array of length N and an integer K, sort the array as much as possible such that no element travels more than k positions to its left - an element however can travel as much as it likes to its right.
- testing@123 June 01, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 3of 3 votes
AnswersGiven two sorted arrays A and B. Find the first K pairs (a, b) from A and B which have the smallest sum of a & b. Supposed K is small compared to |A| x |B|
- anonymous August 05, 2017 in United States
For example:
A = [1, 2, 3, 6, 10]
B = [1, 4, 5, 7]
K = 5
Result [(1,1), (1,4), (1,5), (2,1), (3,1)]| Report Duplicate | Flag | PURGE
Google Intern - 3of 3 votes
AnswersYou are given an array of distinct numbers. You need to return an index to a "local minimum" element, which is defined as an element that is smaller than both its adjacent elements. In the case of the array edges, the condition is reduced to one adjacent element.
- Anonymous January 27, 2015 in Israel
Reach a solution with better time complexity than the trivial solution of O(n).
If there are multiple "local minimums", returning any one of them is fine.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 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 - 3of 3 votes
Answerswrite a function:
int median(int a, int b, int c)
and then write another function:
- ghirlwhocodes April 23, 2015 in Switzerlandint median(int a, int b, int c, int min, int max)
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersFind the longest words in a given list of words that can be constructed from a given list of letters.
- Rohitraman2006 August 01, 2014 in United States
Your solution should take as its first argument the name of a plain text file that contains one word per line.
The remaining arguments define the list of legal letters. A letter may not appear in any single word more times than it appears in the list of letters (e.g., the input letters ‘a a b c k’ can make ‘back’ and ‘cab’ but not ‘abba’).
Here's an example of how it should work:
prompt> word-maker WORD.LST w g d a s x z c y t e i o b
['azotised', 'bawdiest', 'dystocia', 'geotaxis', 'iceboats', 'oxidates', 'oxyacids', 'sweatbox', 'tideways']
Tip: Just return the longest words which match, not all.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 3of 3 votes
AnswersGiven two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents?
- Madan December 04, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 - 3of 3 votes
AnswersGiven a sorted array, find all the numbers that occur more than n/4 times.
- alisonlee659 March 24, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven an array of object A, and an array of object B. All A's have
- hao.liu0708 October 30, 2014 in United States
different sizes, and all B's have different sizes. Any object A is of the
same size as exactly one object B. We have a function f(A, B) to compare the
size of one A and one B. But we cannot compare between two A's or two B's.
Give an algorithm to match each A with each B.| Report Duplicate | Flag | PURGE
Google Software Development Manager Algorithm - 3of 3 votes
AnswersGiven 'n' circles (each defined by center and radius)
- sheva November 12, 2016 in United States
Write an algorithm to detect if circles intersect with any other circle in the same plane
Better than O(n^2) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersWrite an algorithm that returns any duplicate in an array of integers. The algorithm must run in O(n) time and O(1) space. (hint: the integers in the array are not greater than the size of the array).
- davidgbadebo6 November 08, 2016 in United States| Report Duplicate | Flag | PURGE
Google Intern - 3of 3 votes
AnswersDesign an application which sends the user the 10 closest hotels based on his geo location.
- assaf.keret1 June 21, 2015
When i asked roughly how many hotels in total are we talking about, i was asked to estimate how many hotels are there in the world...| Report Duplicate | Flag | PURGE
Google Software Engineer in Test - 3of 3 votes
AnswersWrite an algorithm to find the ‘next’ node (e.g., post-order successor) of a given node in a binary tree and binary search tree
- Jeff May 18, 2014 in United States
a.) where each node has a link to its parent.
b.) without parent pointer
implement 2 versions of the algorithm: 1.) binary tree 2.) BST| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersReturn a shortest prefix of <code>word</code> that is <em>not</em> a prefix of any word in the <code>list</code>
- pk March 07, 2013 in United States
e.g.
word: cat, it has 4 prefixes: “”, “c”, “ca”, “cat”
list: alpha, beta, cotton, delta, camera
Result is “cat”| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersI was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:
- Jaysun October 26, 2019 in United States
There's a list of (x,y) points and a method getCircle with the following signature:
/**
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
*/
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.
The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?| Report Duplicate | Flag | PURGE
Google SDE-2 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 - 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 - 3of 3 votes
AnswersGiven a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.
Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>
- wtcupup2017 December 08, 2016 in United States-AAA -BBB -CCC -DDD -EEE
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answerspublic class LogEntry {
- Invhelper May 05, 2014 in United States
public final long startTime; // start time of a job in millisec granularity
public final long endTime; // end time of a job in millisec granularity.
public final long ram; // the amount of ram the job occupies.
public final long jobId;
... constructor ...
}
running total of RAM
|
| 3GB
| -----
| 2GB
| ------
| 1GB -----------
|----- -----------
|
|____________________________________________________time
Find the peakRAM when the input is a collection of LogEntry objects| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 3of 3 votes
AnswersGiven a string and a dictionary. Break the string into meaningful words.
- RXH February 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
Answersvery large bytestream (PB)
- Yashwanth January 08, 2013 in United States for Youtube
synchronization algorithm
given:
unsigned char read_byte(); ← side effect that it advances a byte pointer in the stream
write:
unsigned char read_sync_byte(); ← may result in >1 calls to read_byte()
remove byte '03' from the stream if the stream is in pattern 00 00 03
Example:
read_byte():
00 0f 42 17 00 00 03 74 00 00 00 00 14 ...
read_sync_byte():
00 0f 42 17 00 00 74 00 00 00 00 14 ...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersSuppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.
- lucifer1986 August 28, 2015 in United States
The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.| Report Duplicate | Flag | PURGE
Google Data Structures - 3of 3 votes
AnswersGiven a board made of 2 x n squares, and boards made of 2 x 1 squares, write a function that will calculate the number of possible ways to arrange the 2 x 1 boards on the 2 x n board, in a way that will fill it completely.
- GeorgyBoy December 30, 2013 in Israel
(Asked to refine the solution to be more efficient)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Coding Problem Solving - 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 - 3of 3 votes
AnswersGiven a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.
- md.lisul.islam November 22, 2017 in United States
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm