Google Interview Questions
- 10of 12 votes
AnswersGiven a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.
- lilzh4ng June 10, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersGiven a sorted array, find a way to find the # of occurrence of a number
- aj June 09, 2015 in United States
for eg: [1, 1, 2, 3, 3, 3, 4, 5]
find # of occurrence of 3 in time better than O(n)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 4 votes
AnswersGiven a range of floats, find the range of size 1 with max num of elements
- aj June 09, 2015 in United States
for eg: [-13.7, -14.5, -12.3, -12.5, -12.9]
one possible answer: [-12.3, -13.3]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
AnswersDescription
- programming.kingdom June 07, 2015 in United States
A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate.
Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall.
For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.
In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.
Input
There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.
Output
The output contains one line for each data set, formatted as shown in the sample output.
Sample Input
4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1
Sample Output
The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersGiven an array and is rotated n number of times find the number where the peak happens. The array is sorted in increasing order. Follow up question: how will you rearrange them in normal sorted order.
- madhur.eng June 03, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 2 votes
AnswersYou are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit. For example, integer 2048 is represented in the stream as 8, 4, 0, 2.
- autoboli May 30, 2015 in United States
Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.
Example:
s_a: 8 4 0 2
s_b: 4 2 0 1
result: '1024'| Report Duplicate | Flag | PURGE
Google - 0of 4 votes
Answersi18n (where 18 stands for the number of letters between the first i and the last n in the word “internationalization,”) Wiki it.
- Gcrack May 22, 2015 in United States
Generate all such possible i18n strings for any given string. for eg. "careercup"=>"c7p","ca6p","c6up","car5p","ca5up","care4p","car4up","caree3p","care3up"..till the count is 0 which means its the complete string again.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays - 2of 2 votes
AnswersGiven an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO], please reconstruct the itinerary in order,
- blah_blah May 18, 2015 in United States
for example: [ CDG, MUC, LHR, SFO, SJC ].
//tickets can be represented as nodes| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 26of 26 votes
AnswersIf a canoe can hold 2 kids and a max weight of 150 lbs, write a function that returns the minimum number of canoes needed, given a list of kids and their weights.
- Rando May 17, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 4of 4 votes
AnswersGiven a list of queries and their counts, write a function that returns one of the queries at random such that over time it returns an equal distribution based on the counts provided in the input.
- Rando May 17, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 7of 7 votes
AnswersYou are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome.
- um01 May 14, 2015 in United States
Expecting a O(nk) solution where n = number of works and k is length
There can be multiple pairs| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 1of 1 vote
AnswersWrite a function which, given two integers (a numerator and a denominator), print the first N digits of a rational number. For example, for 5 / 3 with N=5, the result should be "1.66666". N=2: 1.66
- Dan Shah May 13, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 4 votes
Answersyou have a stream of bytes (1010101101011110100010......)to send over the net. but if you compress it. you will be charged less for less data usage. please try to compress it in a way that you can decompress at other end ahd you dont loss data
- coinsofakshay May 11, 2015 in United States| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 2of 2 votes
Answers0 1 ?
- .netDecoder May 08, 2015 in United States
? wildcard for 0 or 1
"01?"
010 011
Example:
01?0?
Will produce
01000
01100
01001
01101| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersIn a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:
- Nitin Gupta May 06, 2015 in India
– Top speed: (150 + 10 * i) km per hour
– Acceleration: (2 * i) meter per second square.
– Handling factor (hf) = 0.8
– Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.
Here i is the team number.
The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.
All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.
Taking the number of teams and length of track as the input, Calculate the final speeds and the corresponding completion times.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm Arrays Data Structures Java Object Oriented Design - 3of 5 votes
AnswersLook at the sequence below:
- amirtar May 05, 2015 in United States
1, 11, 21, 1211, 111221, 312211, ...
Write a code that receives n and returns the nth element of the sequence. If it gets 4 as input of the method it should return 1211.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 2 votes
AnswersThe text of question below is exactly given by Google interviewer. So they are owner of the text and I am just quoting them. I am not the author of the text below:
- amirtar May 05, 2015 in United States
"
Imagine a museum floor that looks like this:
.#.G.
..#..
G....
..#..
G == Museum Guard
# == obstruction/impassable obstacle
. == empty space
Write a piece of code that will find the nearest guard for each open floor space. Diagonal moves are not allowed. The output should convey this information:
2#1G1
12#12
G1223
12#34
You may choose how you want to receive the input and output. For example, you may use a 2-d array, as depicted here, or you may use a list of points with features, if you deem that easier to work with, as long as the same information is conveyed.
"| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Ideas Math & Computation - 1of 1 vote
AnswersGiven two binary trees ( not BST) , return true if both of them have same inorder else return false.
Eg.B / \ A C
A \ B \ C
Both of the trees have same inorder ( A-B-C) hence function will return true
- Anonymous April 25, 2015 in United States
P.S.
Please note, we can write inorder method call it once for first tree and then second tree, and finally compare both inorder.
We want to parallely do inorder on both tree, if there is mismatch between inorder nodes of both trees, we can stop the traversal and return false| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a Binary search tree of integer values. return the count of nodes where all the nodes under that sub-tree lies between a given range [x, y]. assume there are more than 100,000 nodes
- solxget April 24, 2015 in United States| Report Duplicate | Flag | PURGE
Google SDET - 0of 0 votes
AnswersBring up as many approaches: Your goal is to make faster web browser for phones. You can change the phones, the data center etc. There's a limited network bandwidth and the browsers from the companies can't be altered.
- ghirlwhocodes April 23, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Brain Storming - 0of 0 votes
AnswersWe've got Quad-trees making up a screen. Every box of the Quad-tree has either color white or black. How would you design the data structure of this Quad-tree?
And how would you count the number of pixels in a screen of a given color, given a Quad-tree?int numberOfPixelsGivenColor(QuadTree* t, bool col)
i used bool to specify white/black.
- ghirlwhocodes April 23, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer 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 - 0of 0 votes
AnswersStarted out with simple question - to get warmed up:
Implement a function:makeNumeronym(string s){...}
Ex: house -> h3e, marcus -> m3s
- ghirlwhocodes April 23, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersYou are given 4 integer numbers. Using each number once and only once with any operators from +, -, *, /, (, ), build an expression that evaluates to 24.
- CodeConquer April 22, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 0of 0 votes
AnswersWrite a method that combines an array of iterators into a new one, such that, e.g. for input [A B C] where:
- CodeConquer April 22, 2015 in United States
A.next() returns a1, a2, respectively;
B.next() returns b1;
C.next() returns c1, c2, c3, respectively;
The new iterator will return elements in this order: a1 b1 c1 a2 c2 c3.| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 0of 0 votes
AnswersSimplify the implementation below as much as you can.
- noam.nta April 12, 2015 in United States
Even better if you can also improve performance as part of the simplification!
FYI: This code is over 35 lines and over 300 tokens, but it can be written in
5 lines and in less than 60 tokens.
קוד: בחר הכל
static int func(String s, char a, char b)
{
if (s.isEmpty()) return -1;
char[] strArray = string.toCharArray();
int i=0;
int aIndex=0;
int bIndex=0;
while (aIndex=0 && bIndex==0 && i<strArray.length)
{
if (strArray[i] == a)
aIndex=i;
if (strArray[i] == b)
bIndex=i;
i++;
}
if (aIndex != 0)
{
if (bIndex == 0)
return aIndex;
else
return Math.min(a, b);
}
else
{
if (bIndex != 0)
return bIndex;
else
return -1;
}
}| Report Duplicate | Flag | PURGE
Google Developer Program Engineer - 0of 0 votes
AnswersGiven 1 byte. Write a function that checks that it have exactly 3 bits which equal to 1.
- noam.nta April 12, 2015 in United States| Report Duplicate | Flag | PURGE
Google Developer Program Engineer - 0of 0 votes
AnswersWrite a function
- psuedo April 10, 2015 in India
bool fancy_shuffle(char* s);
which rearranges characters in the string given as input, in such a way that no same character occurs twice in a row (that is, next to each other).
If such rearrangement is not possible, the function should return false.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an array of numbers, find a pair whose sum is closest to zero.
- psuedo April 10, 2015 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm