Google Interview Questions
- 2of 2 votes
AnswersGiven a set top box:
- chandeepsingh85 September 26, 2013 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 Site Reliability Engineer String Manipulation Algorithm - 2of 2 votes
AnswersGiven an array and an integer k , find the maximum for each and every contiguous sub array of size k.
- abc February 15, 2011
Sample Input :
1 2 3 1 4 5 2 3 6
3 [ value of k ]
Sample Output :
3
3
4
5
5
5
6| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 2 votes
AnswersWe define C(n) as the number of ways to take n identical objects out of a bucket, where objects may be taken 1, 2, or 3 at a time.
- skeptical.scientist January 05, 2013 in United States
Example: C(4)=7, because you can take 4 objects in the following 7 ways:
1,1,1,1
2,1,1
1,2,1
1,1,2
2,2
3,1
1,3
Write a function for C(n) in the language of your choice.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 2of 2 votes
AnswersYou are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
- Biswajit Sinha October 26, 2012 in India
Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,....n]. Write the below function in language of your choice.
vector* FindPermute(const string& signature);| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a String of number characters (S), like the following for example:
- SK January 15, 2015 in United States
"132493820173849029382910382"
Now, let's assume we tie letters to numbers in order such that:
A = "0"
B = "1"
C = "2"
...
M = "12"
N = "13"
...
Y = "24"
Z = "25"
Write an algorithm to determine how many strings of letters we can make with S, by converting from numbers to letters.| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersNumber list compressing.
- byPaco September 15, 2015 in United States
Given an sorted array. Input: sorted number list
1, 2, 3,10, 25, 26, 30, 31, 32, 33
Output: find consecutive segments
print: 1-3, 10, 25-26, 30-33| Report Duplicate | Flag | PURGE
Google iOS Developer - 2of 2 votes
AnswersWrite the code to find lexicographic minimum in a circular array, e.g. for the array
- ALgeek September 25, 2012 in India
BCABDADAB, the lexicographic mininum is ABBCABDAD| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersConsider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.
- eng.ahmed.moustafa February 23, 2015 in United States
What is the minimum number of bits required to send the sequence?
Hint: It is not 6 x 52| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 2of 2 votes
AnswersYou have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit.
- jerry January 12, 2012 in United States| Report Duplicate | Flag | PURGE
Google Brain Teasers - 2of 2 votes
AnswersFind the longest sequence of prefix shared by all the words in a string.
- employee11 July 15, 2014 in Israel
"abcdef abcdxxx abcdabcdef abcyy" => "abc"| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.
- NaiveCoder March 21, 2012 in India
eg :
Matrix
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}
And pattern is microsoft.
It's funny when google looks for pattern of microsoft ;)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 2 votes
AnswersGiven a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)?
- Anonymous November 11, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGenerate MAX_INT (Max signed int value) using bitwise operators. Should work in 32 and 64 bit processors
- bartcois January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Bit Manipulation - 2of 2 votes
AnswersGiven a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)
- Prateek Agrawal December 02, 2018 in United States
For example
s = 'ababac'
Then substrings are as follow:
1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c
Now, The lengths of LCP of all substrings are as follow
1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0
String contains only lowercase alphabates.| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures - 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 - 2of 2 votes
Answersfind consecutive integers in a list that give you the biggest sum
- J@sper February 09, 2016 in United States
Like for -2 5 -1 7 -3 it would be 5 -1 7| Report Duplicate | Flag | PURGE
Google Java - 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 - 2of 2 votes
AnswersU have a number, don't know how long it is, do not know how many digits, don't know when number ends, do not know which is the last number. There is a function to increment the number by 1, but function can take only stream of digits and not the complete number e.g if you have 878999 as a number, you could input this number into the function only as single digit e.g 8,7,8,9,9,9. The output should be the whole number incremented by 1 i.e 879000, remember only single digits you can send to function as input. You can use any data structure, but need to tell why you are using that particular data structure. No need to worry about Time complexity.
- algoram November 29, 2012 in United States for Site Reliability Engineering Team
Kindly, suggest how to approach this problem ?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersImplement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
- abhishek January 01, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.
- Anonymous November 21, 2011 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFind how many numbers of length n are there such that each number is at least 4 smaller/greater than the number before and after it.
- coolProgrammer August 02, 2015 in United States
Eg: if n = 5, such numbers are 39518, 15951, etc.| Report Duplicate | Flag | PURGE
Google Software Developer Dynamic Programming - 2of 2 votes
Answersgiven a vector of integers, v[i] represent the stock price on day i. Now you may do at most K transactions. you must sell your stock before you buy it again and that means you can NOT have two stocks at the same time. write a program to find max profit you can get.
- rjrush December 17, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
Answershow to implement a queue using one integer. this should store value 0 to 9. example suppose queue has first value 2 then insert 4 then 6 so it should look like 246. first value should be popped as 2. then it should be 46. program should support 0 in all the levels also. example queue should handle like 01235 also, 0 as first value in queue. remember 0 just to use integer, nothing else as data storage.
- Justin January 13, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven N stacks, each stack contains Si elements, find the maximum sum of the M numbers in the N stacks. To get the number of the stack, only supporting get the top number. For example, S=[1,200,1,2,3], if you want to get the number 200, you need choose 3,2,1 first.
- jeffrey November 28, 2016 in United States
EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]
the maximum sum of the 3 numbers in the above stacks is 3+100+3=107.
Any better solution for this problem?| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 2of 2 votes
AnswersDefine a function that can detect whether the characters of a string can be shuffled without repeating same characters as one other's neighbors. E.g. :
- fahmida.hamid February 11, 2016 in United States
apple >> alpep, so valid
a >> a, valid
aa >> aa, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.
You do not have to find one representation, just have to detect if it is possible or not!| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersYou are given a range [first, last], initially white. You need to paint it black.
For this purpose you have a set of triples
[(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).
Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible
Example:[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]
Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.
Another example:[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]
answer is -1, because it's impossible to color whole range.
- emb June 05, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersYou are given an array, divide it into 2 equal halves such that the sum of those 2 halves are equal. (Imagine that such division is possible for the input array and array size is even)
- gulusworld1989 January 13, 2014 in United States for Android| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a doubly linked list and an array of references to nodes on the linked list. How many "blocks" are there present in the linked list?
- Aasen May 27, 2013 in United States
A "block" is defined as a group of nodes on the list with references directed at them and adjacent to eachother.
For example
[node #0] -><-[node#1] -><-[node#2] -><-[node#3]
node[] nodes = {ref_to_node#0, ref_to_node#2, ref_to_node#3};
Is two blocks because the first block is at node #0.
Node #1 has no incomming reference. Node #2 and Node #3 have references are are adjacent so it's just one block.
Implement using JAVA: Hint: You can try using a HashMap.
Thanks.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 2of 2 votes
Answersthere are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)
- srcnaks February 02, 2015 in -
Write two methods called "getNumber" and "requestNumber" as follows
Number getNumber();
boolean requestNumber(Number number);
getNumber method should find out a number that did not assigened than marks it as assiged and return that number.
requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.
design a data sturucture to keep those numbers and implement those methods| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Hash Table