Google Interview Questions
- 1of 1 vote
AnswersGiven a sorted array and n, find the count of sum of 2 numbers greater than or equal to n
- Killbill June 17, 2015 in United States| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersGiven a sorted array which contains scores range from 0 to 100. Write a program to find occurrence of given score.
- MaYanK July 29, 2010
eg. 1,1,1,40,40,40,100,100
input: 40
o/p : 3 (as 40 appear 3 times in array)| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 1of 1 vote
AnswersWrite 2 functions to serialize and deserialize an array of strings. strings can contain any unicode character. Do not worry about string overflow.
- TheShocker1999 December 08, 2015 in United States| Report Duplicate | Flag | PURGE
Google Developer Program Engineer String Manipulation - 1of 1 vote
AnswersGiven a set of values 0-9, return all permutations of that set of length n. Example: n=2, set ={2,3,4} Return: {2,2}, {3,3}, {4,4}, {2,3}, {3,2}, {3,4}, {4,3}, {2,4}, {4,2}
- PradeepN October 27, 2015 in United States| Report Duplicate | Flag | PURGE
Google 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 - 1of 1 vote
Answersgiven an array of integers generate out put using product of N-1.
- Tester August 09, 2012 in United States
eg: if input is 1,2,3,4
output will be each product of other int in the array : eg: 2*3*4 , 1*3*4 ,1*2*4 , 1*2*3
solve in N not in N2 algo.| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Coding - 1of 1 vote
AnswersGiven an 32-bit integer X, swap the i-th and j-th bit.
- onetreehill April 23, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Bit Manipulation - 1of 1 vote
Answers/*
- thomascom136 August 03, 2013 in United States
Random set of WORD.
Criterion : Given a word find out if the word can be broken into smaller word, by removing one alphabet at a time.
a) all such word should be valid dictionary word.( Assume a function is there to test whether the word exist in dictionary)
b) Remove one alphabet at a time but the new word need to be in dictionary.
For eg :
restated -> restate -> estate -> state -> stat -> sat -> at -> a
fullfill the criterion. ( single alphabet assume belong to dict)
My solution below. I assume it can be done using dynamic programming or trie data structure
*/| Report Duplicate | Flag | PURGE
Google Java Developer Algorithm - 1of 1 vote
AnswersGiven N students, find the number of ways the students could be ranked. Also one or more students can have ties and can have the same ranks. I was stumped at this question. Seem like a dp question?? Any suggestions?
- amm February 25, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a preorder traversal of a binary search tree w/o recursion / stack / extra memory storage. Hint - you can augment the node data structure. However, you can't add a visited field to the node.
- goog August 04, 2010
I will let you guys ponder out a solution before answering with mine :o)
PS: Given the constraints, I believe its impossible to find a fix w/o augmenting the data structure. (If anyone else differs, please enlighten me).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersAssume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor.
- evi March 22, 2015 in United States
As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21...
so the pair sequence is:
[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ...
Write a function to output the first n pairs of this sequence.
void Outputpairs(int n)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWe have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?" and "*"
We want to check if the first string match the pattern, where the ? means that every char (alphanumeric) is permitted in that position, while * allows to have a sequence of alphanumeric chars.
as test we want to check that the function returns true to the following calls.
isMatching("abab","abab")
isMatching("abab","a**b")
isMatching("ababab","ab*b")
isMatching("","*")
isMatching("aaaaaab","*?*b")
i found this question hard, since the language we want to parse is not L1 (there's an ambiguity in the parsing tree) it means that a backtrack modality must be implemented.
Took me a while to find a reasonable solution (that, to be honest i was not happy with)
- Mark Ransew July 31, 2013 in United Statesfunction isLegal(string:String,pattern:String):Boolean{ if(pattern.length == 0 && string.length == 0) return true; if(pattern.length == 0 && string.length > 0) return false; // NOT PROUD OF THE FOLLOWING CONDITION if(pattern.length == 1 && string.length == 0){ if(pattern.charAt(0) == "*") return true; } if(isLetter(pattern.charAt(0))){ if(string.charAt(0) == pattern.charAt(0)){ // CHAR BY CHAR CONTROL return isLegal(string.substr(1),pattern.substr(1)); } return false; } else if(pattern.charAt(0) == "?"){ if(isLetter(string.charAt(0))){ // RECURSIVE CALL return isLegal(string.substr(1),pattern.substr(1)); } return false; } else if(pattern.charAt(0) == "*"){ var possibleSolution:Boolean = false; for(var i:int = 1; i< string.length && !possibleSolution;i++){ possibleSolution = isLegal(string.substr(i),pattern.substr(1)); } return possibleSolution; } else { // ILLEGAL PATTERN return false; } } function isLetter(s:String):Boolean{ return s.charCodeAt(0) > 96 && s.charCodeAt(0)<122; }
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answersgiven sorted int[] A, int[] B. How would you find the maiden that would have been if both were combined to one big sorted array? Use divide and conqure recurssion.
- adam2008 February 28, 2013 in United States
please write method "GetMutualMaiden" and explaint it's time and space complexity| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersBuild a key-value data structure which can perform following 2 functions
- darklight December 28, 2012 in India
- lookup
- rangeLookup(key1, key2)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersHow to check num is power of 2?
- superffeng September 27, 2012 in United States for Site reliabilty| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 1of 1 vote
AnswersGiven tree integers a, b,c. Write a function: int median (int a,int b,int c) to get the median number among a,b,c. Can not use sort, the times of integer operations (e.g. compare, + - * /, bit computing) the less the better. Analyze the best and the worst situation.
- gusuyucc September 24, 2012 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersAn interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.
- wtcupup2017 December 28, 2016 in United States
Follow up: Minimize steps needed.
ex:
{1 2 3 -1 4 5}
move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}
push 1 to the output list because you move car 1 to the empty spot
suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersA circus is designing a tower routine consisting of people standing atop one another’s
- Priti May 27, 2011
shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people
in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given an array of size n (may be a stream also). You have a sliding window of size k. The window first boxes the first k elements of the array and slides slowly over the array by shifting its position 1 element each time. At each position of the array, you need to find the minimum element in the sliding window. i.e. you need to give the minimum of 0 to k-1 elements, then 1 to k elements, 2 to k+1 elements etc. So if your array's size is n, you have to give me n-k+1 minimum values.
- AL May 06, 2011
E.g. Assume that the array is 5,1,3,2,6,8,4,6, and the window size is 3
You should give me 1,1,2,2,4,4. How will you give it?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersGiven a seria of points (Xi, Yi), find the line containing the highest number of points from the list.
- Grr1967 November 29, 2012
Per my question he mentioned that I can assume that there is a given function that receives two points and returns the a and b of the line euqation (aX+b)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures - 1of 1 vote
AnswersYou are given 'n' appointments. Each appointment contains startime and
- topcoder99 November 12, 2011 in India
endtime. You have to retun all conflicting appointments efficiently
starttime and endtime can range from a few min to few years.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answersgiven a string find the number of distinct substrings of the string.
- Anonymous July 09, 2010
ex:
input-> aaaa
output-> 4(a, aa, aaa, aaaa)
input->abcd
output->10(a, b, c, d, ab, bc, cd, abc, bcd, abcd)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersEfficiently implement 3 stacks in a single array.
- me December 27, 2008| Report Duplicate | Flag | PURGE
Google Software Engineer in Test - 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 - 1of 1 vote
AnswersWrite a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).
- Anonymous January 27, 2015 in Israel
The stream ends with the special pair {0,0}.
The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights sum when stream has ended).
Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption.
Example: If this was the stream: {1,2},{2,2},{3,4},{4,10}, then id 2 would be returned with probability 1/9.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersFind the majority number in a given sequence of numbers (a number that occurs more than N/2 times where N is the count of numbers in the sequence). Don't maintain a map of all occurring numbers along with a count. No number may be a majority.
- hsantosh71 June 15, 2013 in United States
Example: 1 1 2 3 4 1 6 1 7 1 1
Majority number is 1 since it occurs 6 times (> 11/2)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGenerate a random 4-digit even number : the adjacent 2 digits must be different.
- ajay.raj April 28, 2017 in United States
public int getNumber(){
}| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersWrite a program to return list of words (from the given list of words) that can be formed from the list of given characters. This is like Scribble game. Say for example the given characters are ('a' , 'c' , 't' } and list the words are {'cat', 'act', 'ac', 'stop' , 'cac'}. The program should return only the words that can be formed from given letters. Here the output should be {'cat', 'act', 'ac'}.
- vimal.varadachari December 19, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersHow many unique words(does not required to have meaning) can you generate from a "EFFICIENT" word
- raghav.nagabandi June 21, 2013 in India| Report Duplicate | Flag | PURGE
Google Quality Assurance Engineer Math & Computation - 1of 1 vote
Answersimplement adding two unsigned numbers without using "+" or "++"
- Steve October 17, 2012 in United States| Report Duplicate | Flag | PURGE
Google Algorithm