Google Interview Questions
- 3of 3 votes
AnswersFind if a given binary tree has duplicate sub trees or not.
- neer.1304 December 25, 2015 in United States
(Two leaf nodes of a parent do not count as subtree)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an array of words (i.e. ["ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF"]), find the max value of length(s) * length(t), where s and t are words from the array. The catch here is that the two words cannot share any characters.
- supatroopa December 13, 2015 in United States
Assume that there are many words in the array (N words) and average length of word is M.
Answer for the example above is "ABCW" and "XTFN" as the result is 4 * 4 = 12.
"ABCW" and "ABCDEF" do not work since they share similar characters.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersImagine you have a row of numbers like below(a traiangle) .By starting at the top of the triangle find the maximum number in each line and sum them up example below
- Avinash Paritala November 25, 2015 in India
5
9 6
4 6 8
8 7 15
Answer I.e. 5+9+8+7 = 29
writw a code to find the maximum total from top to bottom. Assume triangle can have at most 100000 rows.
Input Output specifications
Input Specification
A string of n numbers (where 0<=n<=10^10)
eg.5#9#6#4#6#8#0#7#1#5
Output Specification
A sum of the max numbers in each line (as string ) or Output invalid in case of invalid input/triangle
Examples
eg1.
Input :5#9#6#4#6#8#0#7#1#5
Output:29
eg 2 .
Input :5#9#6#4#6#8#0#7#1
Output:invalid
eg 2 .
Input :5#9##4#6#8#0#7#1
Output:invalid| Report Duplicate | Flag | PURGE
Google Software Engineer - 5of 5 votes
AnswersGiven N balloons, if you burst ith balloon you get Ai−1∗Ai∗Ai+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.
- dp November 25, 2015 in United States
Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions)
Hence if we have left or right boundary positions we multiply 1.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersWrite a bitmap class where we don’t have fixed size for the bitmap. Calculate the changed bits from previous instance to new instance in least iteration.
- johnsvakel November 24, 2015 in India for GFS
Real-time usage : In file systems we will scan only those parts changed from last save to new edit. At that time this bitmap should be used to scan the changed/added/removed parts.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersBest Time To Sell Stock but with 1 restriction: after you sell your stock, you cannot buy stock on next day.
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersDesign a locking mechanism for a distributed system .
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Software Design - -1of 1 vote
AnswersTwo political parties are contesting in the elections in the N number of states in the country. Each party wins some seats every year in each state. After the current elections are over we have the result of both the parties with their number of seats won in each state.
- Avinash Paritala November 21, 2015 in India
The two parties are considered equal if they win the same number of seats in the N states in any order. Otherwise, they are considered unequal. Input/Output Specifications
INPUT: 1) It is an array of N integers depicting number of seats won by party one in each state. 2) It is an array of N integers depicting number of seats won by party two in each state. 3) An integer containing number of states (N).
OUTPUT: Equal/Unequal/Invalid
Equal: if political parties are equal Unequal: if political parties are unequal Invalid: if any party has invalid number of seats in any state
Examples
Example 1:
Two parties contested in seven states Seats won by party one in all the seven states: {12,11,5,2,7,5,-11} Seats won by party two in all the seven states: {5,12,5,7,11,2,11} The party two has an invalid number of winning seats(-11). So the output will be "Invalid".
Input :
1) {12,11,5,2,7,5,-11}
2) {5,12,5,7,11,2,11}
3) 7
Output: Invalid
Example 2:
Two parties contested in seven states Seats won by party one in all the seven states: {12,11,5,2,7,5,11} Seats won by party two in all the seven states: {5,12,5,7,11,2,11} Both the parties are equal because they have got 11(2 times each), 5(2 times each),7( 1 time each), 2(1 time each), 12( 1 time each other outputs (0 times each).
Input :
1) {12,11,5,2,7,5,11}
2) {5,12,5,7,11,2,11}
3) 7
Output: Equal
Example 3:
Input :
{12,11,5,2,7,5,11}
{5,0,5,7,11,2,11}
7
Output: Unequal| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 4 votes
AnswersGiven that you have a graph with an even number of points, how do you find two points that equally subdivide the graph?
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersRahul is playing a very interesting game. He has some N different type of match boxes. All match boxes may have different number of matchsticks (S1, S2, S3... Sn).
- Avinash Paritala November 19, 2015 in India
Rahul chooses two random numbers F and K. K should be less than N. The game is that Rahul wants to select any K match boxes out of N match boxes such that total number of matchsticks in these K selected match boxes should be multiple of F.
At the sametime Rahul wants that sum matchsticks of all the selected match boxes should be minimum possible.
Input Specifications:
1) Array S = {S1,S2,S3,...Sn} of size N corresponding to the number of match sticks in N matchboxes(0<=N<=1000}
2) F-Value (as explained above)
3) K-Value ( as explained above)
Output:
1 2 3 4 5 Here 3 is the number of matchsticks in matchbox I II III IV V minimum possible total number of matchsticks such that the conditioned explained in the problem statement is satisfied. Output -1 if it is not possible or invalid input.
For example, there are 5 match boxes i.e., N = 5
Let's say K is 3 (Rahul has to choose any 3 matchboxes)
Let's say F is 5(sum of matchsticks in 3 selected matchboxes should be multiple of 5).
Rahul can choose II, III and V matchboxes which would give the total sum of 10 which is multiple of F i.e., 5. And 10 is the minimum possible matchsticks possible in the above case.
So you have to answer the minimum possible matchstick(sum of the matchsticks in the selcted matchboxes) but the conditions given above should be satisfied.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven an active stream of sorted arrays, how would you merge them efficiently?
- Ray November 14, 2015 in Canada| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersGiven a string of characters, find the longest legal word. A generic method to check word legality is given.
- tgerg2009@my.fit.edu November 06, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 5of 5 votes
AnswersGiven an infinite stream of characters and a list L of strings, create a function that calls an external API when a word in L is recognized during the processing of the stream.
- ragmo2223 November 05, 2015 in United States
Example:
L = ["ok","test","one","try","trying"]
stream = a,b,c,o,k,d,e,f,t,r,y,i,n,g.............
the call to external API (let's call it some function callAPI()) would be called when the 'k' is encountered, again when the 'y' is encountered, and again at 'g'.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersGiven a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number.
- pandacoder October 30, 2015 in United States
E.g., prime set = {2, 3}
expressible number = {1,2,3,4,6,8, 9, 12...}
non-expressible number = {5, 10... }
The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersYou have some money in your bank account, the only function to withdraw money is uint16 Withdraw(uint16 value), if the value is greater than the money you have it returns 0, otherwise it withdraws the requested amount and returns the "value"
- mike.radula October 13, 2015 in United States
Write a function that withdraws all your money.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersRearrange characters in a string so that no character repeats twice.
- pcinterview October 10, 2015 in United States
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 5 votes
AnswersThere are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers.
- xblwyc October 07, 2015 in United States
1. the swap can happen between any two position.
2. E.g. AABCCDB -> AADCCBB, ans is 1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 8of 8 votes
AnswersGiven an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]
That is, implement the following naive algorithm faster than O(n^2)def naive_algorithm(lst, a, b): result = 0 for i in xrange(len(lst)): for j in xrange(i, len(lst)): if a <= sum(lst[i:j + 1]) <= b: result += 1 return result
Examples:
count([1,2,3], 0, 3) = 3 # [1], [2], [3], [1, 2], [3] count([-2,5,-1], -2, 2) = 3 # [-2], [-1], [-2, 5, -1]
You may assume that there are no overflows, that is sum(|x_i|) <= MAX_INT - 1
- emb September 26, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 5 votes
AnswersYou are given an array of n unique integer numbers 0 <= x_i < 2 * n
- emb September 23, 2015 in United States
Print all integers 0 <= x < 2 * n that are not present in this array.
Example:
find_missing([0]) = [1]
find_missing([0, 2, 4]) = [1, 3, 5] # because all numbers are [0, 1, 2, 3, 4, 5]
find_missing([]) = []
find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # because all numbers are [0, 1, 2, 3, 4, 5, 6, 7]
Quirks are about requirements:
Time complexity O(n) - BUT there should be some fixed constant C independent of size of input such that every element of array is written/read < C times, so radix sorting the array is a no go.
Space complexity O(1) - you may modify the initial array, BUT sorted(initial_array) must equal sorted(array_after_executing_program) AND you can't store integers outside range [0, 2n) in this array (imagine that it's an array of uint32_t).| Report Duplicate | Flag | PURGE
Google Software Engineer Brain Teasers - 1of 1 vote
AnswersYou are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour.
- aijackmoore September 21, 2015 in United States
e.g. 100207 100208 2
100305 100307 5
100207 100209 4
111515 121212 1
Answer: 100207
(Need to consider different scenarios like the time slots could be very sparse)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 6of 6 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
Without modifying original structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 0of 0 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
To simplify you can modify the structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 2of 4 votes
AnswersYou are given a matrix n rows, m columns where each row is sorted in increasing order. Find median of the overall elements. What is the time complexity?
- emb September 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersYou are given a flat room 1x1 metres, a position of victim in it (v_x, v_y) and a position of a killer (k_x, k_y) both inside this room (in range [0, 1]).
- emb September 06, 2015 in United States
Then the killer shoots once at some direction. The bullet reflects of the walls as if it was a light ray - if it falls under angle X degrees, it will reflect at angle X degrees, if it gets into the corner it just reflects back. If the bullet hits guardian (see below) it stops and killer fails.
Write a function that will be given coordinates of victim and a killer and will return a list of coordinates of guardians such that it's impossible for a killer to kill victim.
That is, whichever direction the killer will shoot, the bullet will never reach victim, or will be stopped by a guardian.
Here is an example for the case when we assume the walls don't reflect bullet (for simplicity):
killer: (0, 0), victim: (1, 1). The solution to this simplified problem is to place 1 guardian between killer and victim e.g. on (0.1, 0.1).
Your task is to do this with accounting bullet reflection. E.g. in the previous case the killer can shoot at (1/3, 1), the bullet will reflect to (2/3, 0) and finally get to the victim at (1, 1).| Report Duplicate | Flag | PURGE
Google Software Engineer Brain Teasers - 0of 0 votes
AnswersImplement a method for the following signature:
void * alignedAllocate(size_t sizeInBytes, size_t alignment) { }
The method should allocate memory for the given size and the pointer should be aligned.
For example ifp = alignedAllocate(1000,64);
p%8 should be 0.
- thewhatwhat September 05, 2015 in United States
Implement a second method that deleted the pointer give p.
Extend the delete method to handle multiple p's.| Report Duplicate | Flag | PURGE
Google Software Engineer C C++ - 1of 1 vote
AnswersWrite function to determine if given unsigned 32-bit number is a power of 3
int is_power_of_3(uint32_t n)
return 1 if yes, 0 otherwise.
e.g.is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0
Expected the answer not to be straightforward loop, but something faster.
- emb August 28, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Math & Computation - 1of 1 vote
AnswersGiven an array consisting of N Numbers.
- smarthbehl August 25, 2015 in United States
Divide it into two Equal(it is important) partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum.
If number of elements are odd difference in partition size can be at most 1.| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersWrite all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5] in at least O(n^2) complexity
- dev123 August 24, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersDesign a data structure which should have following operation. Insert, Delete, Random access
- hm August 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 1of 1 vote
AnswersGiven 2 large number A and B, create a new number C using the digits from A which needs to be grater than B.
- hm August 21, 2015 in United States
e.g. A = 5281, B = 7443
C = 8125.| Report Duplicate | Flag | PURGE
Google Software Engineer Math & Computation