Google Interview Questions
- 77of 79 votes
AnswersYou have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
- ericaturner0 April 01, 2013 in United States
For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 44of 48 votes
AnswersPots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.
- 352905 February 12, 2013 in United States
The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?
At the end I was asked to code this strategy!| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 33of 39 votes
AnswersGiven an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
- LAP June 10, 2013 in United States
* The sub-arrays should not overlap.
eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16
I gave him o(n^2) algorithm but he was not satisfied.| Report Duplicate | Flag | PURGE
Google 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 - 25of 27 votes
AnswersGiven a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls.
- chandeepsingh85 September 26, 2013 in United States
(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps), and get the top ten in the combined map)
The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 25of 25 votes
AnswersThere is an island which is represented by square matrix NxN.
- amnesiac March 01, 2013 in India
A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.
Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is alive after he walks n steps on the island?
Write a psuedocode & then full code for function
" float probabilityofalive(int x,int y, int n) ".| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 22of 38 votes
AnswersGive you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
- lxfuhuo August 23, 2013 in CHINA
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is perfect.| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 21of 27 votes
AnswersYou are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex
- grave August 04, 2013 in India
A: 3 2 1
B: 0 1 1
It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them
Ouput should be.
3 1 2
Here - 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 21of 23 votes
AnswersGiven a undirected graph with corresponding edges. Find the number of possible triangles?
- redsanket March 25, 2014 in United States
Example:
0 1
2 1
0 2
4 1
Answer:
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 19of 19 votes
AnswersGiven two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:
- Masterchief117 March 23, 2014 in United States
if a = xyz and b = afdgzyxksldfm then the program should return true.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer String Manipulation - 18of 22 votes
AnswersGiven a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree
- pavel.em January 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 16of 20 votes
AnswersGiven two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.
- dee707 July 28, 2016 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 16of 18 votes
AnswersOutput top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:
- John July 15, 2014 in United States
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 15of 15 votes
AnswersThere is a graph which has 1 source and 1 sink(destination node)
- student1234 August 28, 2015 in United States
In between those 2 nodes there are n levels of nodes. At each level there are exactly m nodes.
Every node of level i is connected to every node of level i+1 (All edges go in forward direction)
Find total no. of paths between source and sink.
This was basic question. Then he tweaked it by adding few more edges.
Now there were some additional edges. Now sdges can go from any lower level to any higher level. That is not just from i to i+1..
can be from i to i+2 or i +3 so on...
(such bouncing edges were added only in the n levels not from or to (to src or sink)
Now find number of paths?| Report Duplicate | Flag | PURGE
Google Algorithm - 14of 14 votes
AnswersGiven a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard):
- Obiwana March 10, 2014 in United States
0 0 0
B G G
B 0 0
calculate the steps from a room to nearest Guard and set the matrix, like this
2 1 1
B G G
B 1 1
Write the algorithm, with optimal solution.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 13of 13 votes
AnswersA book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurences 'k' of certain digit 'd' in this string.
- autoboli January 16, 2015 in United States
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occure five times in that string.
Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages| Report Duplicate | Flag | PURGE
Google - 12of 14 votes
Answerswe will name a number "aggregated number" if this number has the following attribute:
- holmespanda November 16, 2012 in United States
just like the Fibonacci numbers
1,1,2,3,5,8,13.....
the digits in the number can divided into several parts, and the later part is the sum of the former parts.
like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8
122436, because 12+24=36
1299111210, because 12+99=111, 99+111=210
112112224, because 112+112=224
so can you provide a function to check whether this number is aggregated number or not?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 12of 12 votes
AnswersGiven a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.
- lxfuhuo September 09, 2015 in -
i.e:
bcabc
You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.
ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:
cbacdcbc. answer is acdb not adcb
I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 11of 15 votes
AnswersGiven an int array which might contain duplicates, find the largest subset of it which form a sequence.
- learner October 06, 2011 in -
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Software Engineer / Developer Arrays Algorithm - 11of 11 votes
AnswersThere are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?
- CodeKaur August 04, 2014 in United States
Ex:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say 'true'.
Ex2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false.
Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 11of 11 votes
AnswersGiven an unsorted array of integers, you need to return maximum possible n such that the array consists at least n values greater than or equals to n. Array can contain duplicate values.
- abc June 20, 2014 in India
Sample input : [1, 2, 3, 4] -- output : 2
Sample input : [900, 2, 901, 3, 1000] -- output: 3| Report Duplicate | Flag | PURGE
Google Applications Developer - 11of 11 votes
AnswersGive a N*N matrix, print it out diagonally.
- Mem February 28, 2014 in United States
Follow up, if it is a M*N matrix, how to print it out.
Example:
1 2 3
4 5 6
7 8 9
print:
1
2 4
3 5 7
6 8
9
This is the question in the phone interview.
Please share more questions.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 10of 12 votes
AnswersGiven an equation in the form 2^i * 3^j * 5^k * 7^l where i,j,k,l >=0 are integers.write a program to generate numbers from that equation in sorted order efficiently.
- Rohit July 29, 2013 in United States
for example numbers from that equation will be in the order 2,3,5,6,7,8,9.....and so on..| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 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 - 10of 10 votes
AnswersYou are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows:
- autoboli June 30, 2015 in United States
If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'.
You are not allowed to use any conditional operator (including ternary operator).
Follow up: Solve the problem without utilizing arithmetic operators '+ - * /'.| Report Duplicate | Flag | PURGE
Google - 10of 10 votes
AnswersConsider a hash table with M slots. Suppose hash value is uniformly distributed between 1 to M, and it uses linked list to handle conflicts (if two keys hashed to the same slot). Suppose we put N keys into this M-slotted hash table, what is the probability that there will be a slot with i elements? i could vary from 0 to N.
- seanren7 August 13, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Hash Table - 10of 10 votes
AnswersGiven a Binary Search tree of integers, you need to return the number of nodes having values between two given integers. You can assume that you already have some extra information at each node (number of children in left and right subtrees !!).
- abc June 19, 2014 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 10of 10 votes
Answershow to merge two binary search tree into balanced binary search tree.. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time with in constant space.
- vivek August 11, 2013 in United States
Examples:
A Balanced BST 1
90
/ \
70 110
A Balanced BST 2
60
/ \
5 800
output :-->
70
/ \
60 90
/ \
5 800| Report Duplicate | Flag | PURGE
Google Computer Scientist Algorithm - 9of 9 votes
AnswersGiven an array of integers, sort the array into a wave like array, namely
- Zen April 22, 2014 in United States
a1 >= a2 <= a3 >= a4 <= a5.....| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a string (1-d array) , find if there is any sub-sequence that repeats itself.
- for.anonymous.usa October 22, 2014 in United States
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.
Eg:
1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice
The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.
In the sense, it should be checked for every pair of characters in the string.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm Brain Teasers C C++ Coding Data Structures Dynamic Programming Problem Solving String Manipulation