Google Interview Questions
- 5of 5 votes
AnswersThere are n bombs in a big circle,and each bomb has a value and a 'effect range'.If you detonated a bomb,you will get this bomb's value,but a bomb can have effect on the neighbors which the distance(difference between index) between them is smaller than the 'effect range'.It's say that the neighbor bomb will be destoryed and you could not get their values.
- lxfuhuo September 13, 2013 in CHINA
You will given each bomb's value and the 'effect range',and you need calculate the max value you can get.
eg. n=3 index 0's bomb' v is 2,range is 0(will not effect others).and v[1]=1,r[1]=1,v[2]=3,r[2]=1;
this case's max value is 5.(detonate the 0's and than the 2's).
HELP ME.
ps: It's a interval DP.| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 5of 5 votes
Answers
- Alex March 04, 2015 in United StatesQuestion: Given two strings, find number of discontinuous matches. Example: “cat”, “catapult” Output: 3 => “CATapult”, “CatApulT”, “CAtapulT”
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersI came across this problem online.
- xiaoc10 August 07, 2015 in United States
> Given an integer:N and an array int arr[], you have to add some
> elements to the array so that you can generate from 1 to N by using
> (add) the elements in the array.
Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers.
For example:
N=6, arr = [1, 3]
1 is already in arr.
add 2 to the arr.
3 is already in arr
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3
So we return 1 since we only need to add one element which is 2.
Can anyone give some hints?| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 5of 5 votes
AnswersWrite a function which, given two integers (a numerator and a denominator), prints the decimal representation of the rational number "numerator/denominator".
- loganwol August 18, 2014 in United States
Since all rational numbers end with a repeating section, print the repeating section of digits inside parentheses; the decimal printout will be/must be
Example:
1 , 3 = 0.(3)
2 , 4 = 0.5(0)
22, 7 = 3.(142857)
etc..| Report Duplicate | Flag | PURGE
Google SDET Coding - 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 - 5of 5 votes
Answersfind the no of possible patterns in android lock screen. write a program to count them.
- h3dnvb January 04, 2016 in United States| Report Duplicate | Flag | PURGE
Google - 5of 5 votes
AnswersGiven an integer, find the next highest and next lowest integers, with equal number of 1s in their binary representation as the original number.
- gulusworld1989 January 13, 2014 in United States for Android| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 5of 5 votes
AnswersGiven a string, find the longest substring with k distinct characters.
- getPDat February 03, 2017 in United States
e.g - “aaaabbbb”, k = 2, “aaaabbbb”
“asdfrttt” k = 3, “asd”, “frttt”
[Telephonic Question]| Report Duplicate | Flag | PURGE
Google Software Developer Java - 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
AnswersWe have words and there positions in a paragraph in sorted order. Write an algorithm to find the least distance for a given 3 words.
- pqrabcd November 14, 2014 in United States
eg. for 3 words
job: 5, 9 , 17
in: 4, 13, 18
google: 8, 19, 21
...
...
Answer: 17, 18, 19
Can you extend it to "n" words?
Context: In Google search results, the search terms are highlighted in the short paragraph that shows up. We need to find the shortest sentence that has all the words if we have word positions as mentioned above.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
Answersdesign a system to return an unique ID for each request. For most of requests, the ID value should increase as time goes, the system should handle 1000 requests per second at least.
- codingfunnyguy December 04, 2013 in United States
timestamps alone is not valid since there might be multiple requests with same timestamps.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 5of 5 votes
AnswersYou are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
- john August 29, 2018 in United States. - Free path/road # - Building B - Google bike Employee location - (x, y) - (1, 2) . . . . . # . . E . . # # # # # . # . B . . . . . . . . . B
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersWrite the code for a change vending machine.
- Java Coder October 12, 2008| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
Answers[Google] Design Text Editor (Doubly Linked List)
- aonecoding4 December 04, 2018 in United States
Build a text editor class with the following functions,
moveCursorLeft(),
moveCursorRight(),
insertCharacter(char) //insert the char right before cursor
backspace() //delete the char right before cursor
Follow-up
Implement undo() //undo the last edit. Can be called multiple times until all edits are cancelled.
All functions above should take O(1) time.
Example
( '|' denotes where the cursor locates. 'text' shows what's been written to the text editor. )
Start with empty text
text = "|"
insertCharacter('a')
text = "a|"
insertCharacter('b')
text = "ab|"
insertCharacter('c')
text = "abc|"
moveCursorLeft()
text = "ab|c"
moveCursorLeft()
text = "a|bc"
backspace()
text = "|bc"
moveCursorLeft()
text = "|bc" (nothing happens since cursor was on the leftmost position)
undo()
text = "a|bc"
undo()
text = "ab|c"
undo()
text = "abc|"
undo()
text = "ab|"
undo()
text = "a|"| Report Duplicate | Flag | PURGE
Google Software Engineer - 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 - 5of 5 votes
AnswersTree Game
- aonecode May 17, 2019 in United States
class TreeNode {
TreeNode parent; //parent node
TreeNode left; //left child
TreeNode right; //right child
}
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.
Follow up: if player B takes the first hand instead, which node should he pick?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 14 votes
AnswersGiven two aligned sequences `a` and `b`. Write a function "findCommon", that finds the longest substring of the longer sequence that align to the smaller sequence in such a way that the alignment length (matching length) can be maximized. Sequences initially were of different lengths but the smaller one is padded with hyphen ('-') after alignment to make it equal to the longer sequence. The length of longer sequence is known in advance (m, which is same for the smaller padded sequence). The output is always the subsequence of the longer string.
- mary.kindall November 19, 2013 in United States
The total number of such operations to be done is in billions.
findCommon(a, b, m)
Example 1:
a = ------bixg--
b = xxxxxxbi-gzz
m = 12
output: big
Example 2:
a = xxxxxxbxigxx
b = ------b-ig--
m = 12
output = bxig
Example 3:
a = bigxxxxxxxxx
b = bi-x--------
m = 12
output = bigx| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 8 votes
AnswersDesign an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )
- Aashish June 27, 2012 in India
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 8 votes
AnswersGiven a set top box:
- Guy January 18, 2014 in United States
a, b, c, d, e,
f, g, h, i, j,
k, l, m, n, o
p, q, r, s, t
u, v, w, x, y
z
Write code to give the character sequence given a word, For example, if the word is "CON", the function will print this:
Right//now we're at B
Right//now we're at C
OK//to select C
Down
DOwn
Right
Right
OK//to select O
Left//now at N
OK//to select N
note: Be careful when you're at Z. if you go to the right, you will get stuck.
Afterwards, the interviewer adds a space to the right of 'Z' to test the code.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 6 votes
AnswersGiven a server that has requests coming in. Design a data structure such that you can fetch the count of the number requests in the last second, minute and hour.
- AVK June 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 4of 6 votes
AnswersYou have two integer arrays. Treat these arrays as if they were big numbers, with one digit in each slot. Perform addition on these two arrays and store the results in a new array.
- Aasen October 24, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 4of 6 votes
AnswersWrite a program to implement Double Linked List from Stack with min. complexity.
- Purushotham Kumar October 20, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Data Structures Java Linked Lists Stacks - 4of 4 votes
AnswersGiven a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles
- nikki December 31, 2018 in United States
Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 4of 4 votes
AnswersGiven a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
- xyz_coder November 20, 2014 in United States
Find the length of the shortest palindrome that you can create from S by applying the above transformation.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.
- adam2008 February 22, 2013 in United States
Write a function:
int number_of_disc_intersections(int A[], int N);
that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:
A[0] = 1 A[1] = 5 A[2] = 2
A[3] = 1 A[4] = 4 A[5] = 0
intersecting discs appear in eleven pairs of elements:
0 and 1,
0 and 2,
0 and 4,
1 and 2,
1 and 3,
1 and 4,
1 and 5,
2 and 3,
2 and 4,
3 and 4,
4 and 5.
so the function should return 11.
The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Assume that:
N is an integer within the range [0..10,000,000];
each element of array A is an integer within the range [0..2147483647].
Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 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 - 4of 4 votes
AnswersPrint combinations of strings from List of List of String
- mohrmanla October 23, 2014 in United States
Example input: [[quick, slow], [brown, red], [fox, dog]]
Output:
quick brown fox
quick brown dog
quick red fox
quick red dog
slow brown fox
slow brown dog
slow red fox
slow red dog| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven a polygon with N vertexes and N edges. There is an int number(could be negative) on every vertex and an operation in set(*,+) on every edge. Every time, we remove an edge E from the polygon, merge the two vertexes linked by the edge(V1,V2) to a new vertex with value: V1 op(E) V2. The last case would be two vertexes with two edges, the result is the bigger one.
- zilchistDeepblue January 15, 2013 in United States
Return the max result value can be gotten from a given polygon.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersI Got this Crazy Question on PHONE INTERVIEW AT GOOGLE:
- hhh April 11, 2013 in United States
Design and implement a class to generate random numbers in an arbitrary probability distribution given by an array of integer weights, i.e. for int[] w return a number, n, from 0 to w.length - 1 with probability w[n] / sum(w). Using an existing random number generator with a uniform distribution is permitted.
Example distribution:
w = 1, 2, 3, 2, 1
Example probabilities:
w / sum = 1/9, 2/9, 1/3, 2/9, 1/9
Example results:
n = 0, 1, 2, 3, 4
Documentation:
Class java.util.Random
public int nextInt(int n)
Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.
Parameters:
n - the bound on the random number to be returned. Must be positive.
Returns:
the next pseudorandom, uniformly distributed int value between 0 (inclusive) and n (exclusive) from this random number generator's sequence
Throws:
IllegalArgumentException - if n is not positive| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding