Google Interview Questions
- 0of 0 votes
AnswersYou have a binary tree where each node knows the number of nodes in its sub-tree (including itself).
- mikewhity November 06, 2014 in United States
Given a node n and an int k,
write a function to return the kth
node in an in order traversal.
Can you do this non recursively| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven the relative positions (S, W, N, E, SW, NW, SE, NE) of some pairs of points on a 2D plane, determine whether it is possible. No two points have the same coordinates.
- united November 02, 2014 in United States
e.g., if the input is "p1 SE p2, p2 SE p3, p3 SE p1", output "impossible".| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of integer, find the number of un-ordered pairs in that array, say given {1, 3, 2}, the answer is 1 because {3, 2} is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3, 2}, {3, 1}, {2, 1}.
- lsdtc1225 November 02, 2014 in United States
Obviously, this can be solved by brute force with O(n^2) running time, or permute all possible pairs then eliminate those invalid pairs.
My question is does any body have any better solution and how would you do it because it seems like a dynamic programming problem. A snippet of code would be helpful| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersThe third question is a brain teaser: if 1000 couples are to give birth to male and female babies(50% change each), and they would keep giving birth until they have a girl, what's the boy to girl ratio in 20 years
- fenghanlu October 30, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersGiven an array of object A, and an array of object B. All A's have
- hao.liu0708 October 30, 2014 in United States
different sizes, and all B's have different sizes. Any object A is of the
same size as exactly one object B. We have a function f(A, B) to compare the
size of one A and one B. But we cannot compare between two A's or two B's.
Give an algorithm to match each A with each B.| Report Duplicate | Flag | PURGE
Google Software Development Manager Algorithm - -6of 8 votes
Answers2.
- mapan0817 October 30, 2014 in United States
String encode(List<String> input);
List<String> decode(String input);| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - -5of 7 votes
AnswersThis is two questions I got from a google interview. Not very sure how to solve it. Any comments would be appreciated.
- mapan0817 October 30, 2014 in United States
1.
interface RateLimit {
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
boolean allowThisRequest();
}
brief example:
server instantiates your object, calls setQPS(1)
at at time t, user1 makes a request, allowThisRequest() returns true
at time t+0.01 sec, user2 makes a request, allowThisRequest() returns false
at at time t+1, user4 makes a request, allowThisRequest() returns true
at time t+5 sec, user3 makes a request, allowThisRequest() returns true| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 4of 4 votes
AnswersQuestion: Two players A and B are playing a game. Pots of gold, each with
- kiran.sanni October 28, 2014 in United States
varying number of coins are placed in a single line. The rules of the game are:
1) Players play turn by turn.
2) On each turn a player can pick a pot of gold from either end of the line. He
gets all the gold in that pot. The next pot of gold on that end is now available
for picking.
What is the maximum number of gold can the first player get ?| Report Duplicate | Flag | PURGE
Google Intern Algorithm - -3of 3 votes
Answersa left grow binary tree. Describe as below. (Transform from A to B)
- kiran.sanni October 28, 2014 in United States
A: B:
1 1
/ \ /
2 3 2 - 3
/ \ /
4 5 4 - 5
/ \ /
6 7 6 - 7
a left grow binary tree. Describe as below. (Transform from A to B)
A: B:
1 1
/ \ /
2 3 2 - 3
/ \ /
4 5 4 - 5
/ \ /
6 7 6 - 7| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 1of 1 vote
AnswersUse the shorest unique prefix to represent each word in the array
- sunshihaosd October 25, 2014 in United States
input: ["zebra", "dog", "duck",”dot”]
output: {zebra: z, dog: do, duck: du}
[zebra, dog, duck, dove]
{zebra:z, dog: dog, duck: du, dove: dov}
[bearcat, bear]
{bearcat: bearc, bear: ""}| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer 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 - 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 - 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 - 2of 2 votes
AnswersFind the 90th percentile of a stream of numbers between 1 and 10^6.
- addy October 16, 2014 in United States
Followup: What if there is not enough memory to store all numbers and no upper bound.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 3of 3 votes
AnswersYou are given a string S. Each character of S is either ‘a’, or ‘b’. You wish to reverse exactly one sub-string of S such that the new string is lexicographically smaller than all the other strings that you can get by reversing exactly one sub-string.
- Rahul Sharma October 09, 2014 in India
For example, given ‘abab’, you may choose to reverse the substring ‘ab’ that starts from index 2 (0-based). This gives you the string ‘abba’. But, if you choose the reverse the substring ‘ba’ starting from index 1, you will get ‘aabb’. There is no way of getting a smaller string, hence reversing the substring in the range [1, 2] is optimal.
Input:
First line contains a number T, the number of test cases.
Each test case contains a single string S. The characters of the string will be from the set { a, b }.
Output:
For each test case, print two numbers separated by comma; for example “x,y” (without the quotes and without any additional whitespace). “x,y” describe the starting index (0-based) and ending index respectively of the substring that must be reversed in order to acheive the smallest lexicographical string. If there are multiple possible answers, print the one with the smallest ‘x’. If there are still multiple answers possible, print the one with the smallest ‘y’.
Constraints:
1 ? T ? 100
1 ? length of S ? 1000
Sample Input:
5
abab
abba
bbaa
aaaa
babaabba
Sample Output:
1,2
1,3
0,3
0,0
0,4| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 7of 7 votes
AnswersGiven a number M (N-digit integer) and K-swap operations(a swap
- Rahul Sharma October 03, 2014 in India
operation can swap 2 digits), devise an algorithm to get the maximum possible integer?
Examples:
M = 132 K = 1 output = 312
M = 132 K = 2 output = 321
M = 7899 k = 2 output = 9987
M = 8799 and K = 2 output = 9987| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 0of 4 votes
AnswersProblem Link:https://code.google.com/codejam/contest/4214486/dashboard#s=p1
- codingfunnyguy September 18, 2014 in United States
At new years party there is a pyramidal arrangement of glasses for wine. For example, at the top level, there would just be one glass, at the second level there would be three, then 6 and then 10 and so on and so forth like the following image
.
The glasses are numbered using 2 numbers, L and N. L represents the level of the glass and N represents the number in that level. Numbers in a given level are as follows:
Level 1:
1
Level 2:
1
2 3
Level 3:
1
2 3
4 5 6
Level 4:
1
2 3
4 5 6
7 8 9 10
Each glass can hold 250ml of wine. The bartender comes and starts pouring wine in the top glass(The glass numbered L = 1 and N = 1) from bottles each of capacity 750ml.
As wine is poured in the glasses, once a glass gets full, it overflows equally into the 3 glasses on the next level below it and touching it, without any wine being spilled outside. It doesn't overflow to the glasses on the same level beside it. It also doesn't overflow to the any level below next level (directly).
For example: When the glass of L = 2 and N = 2 overflows, the water will overflow to glasses of L = 3 and N = 2, 4, 5.
Once that the bartender is done pouring B bottles, figure out how much quantity in ml of wine is present in the glass on level L with glass number N.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three integers, B, L, N, B is the number of bottles the bartender pours and L is the glass level in the pyramid and N is the number of the glass in that level.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the quantity of wine in ml in that glass.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 4 votes
AnswersThere is an array of 3-tuple, in the form of (a, 1, 5). The first element in the tuple is the id, the second and third elements are both integers, and the third is always larger than or equal to the second. Assume that the array is sorted based on the second element of the tuple. Write a function that breaks each of the 3-tuple into two 2-tuples like (a, 1) and (a, 5), and sort them according to the integer.
- Nobody September 11, 2014 in United States
E.g. given (a, 1, 5), (b, 2, 4), (c, 7, 8), output (a, 1), (b, 2), (b, 4), (a, 5), (c, 7), (c, 8).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 6 votes
AnswersThere are a large number of leaves eaten by caterpillars. There are 'K"' caterpillars which jump onto the leaves in a pre-determined sequence. All caterpillars start at position 0 and jump onto the leaves at positions 1,2,3...,N. Note that there is no leaf at position 0.
Each caterpillar has an associated 'jump-number'. Let the jump-number of the i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats the leaves at the positions which are multiples of /'.
Given a set 'A' of 'IC elements. 'e<=15.,. 'N'<=109, we need to determine the number of uneaten leaves.
Input Format:
N -number of leaves
A - Given array of integers
Output Format:
An integer denoting the number of uneaten leaves.
Sample Input:
N = 10
A = [2,4,5]
Sample Output:
4
Explanation
1,3,7,9 are the leaves which are never eaten. All leaves which are multiples of 2, 4, and 5 have been eaten.
Java Code:
- balakrishna.pininti September 09, 2014 in United Statespublic class Solution { //need to complete the function below static int countUneatenLeave(int N, int[] A { } public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); final String fileName = System.getenv("OUTPUT_PATH"); BufferedWriter bw = new BufferedWriter(new FileWriter(fileName)); int res; int _N; _N = Integer.parseInt(in.nextLine()); int _A_size = Integer.parseInt(in.nextLine()); int[] _A = new int(_A_size]; int _A_item; for(int _A_i = 0; _A_i < _A_size; _A_i++) { _A_item = Integer.parseInt(in.nextLine()); _A[_A_i] = _A_item; } res = countUneatenLeaves(_N,_A); bw.write(String.valueOf(res)); bw.newLine(); bw.close(); } }
| Report Duplicate | Flag | PURGE
Google SDE1 Developer Program Engineer Algorithm - 1of 1 vote
AnswersGiven a start position and an target position on the grid. You can move up,down,left,right from one node to another adjacent one on the grid. However there are some walls on the grid that you cannot pass. Now find the shortest path from the start to the target.
- fmars September 07, 2014 in United States
(This is easy done by BFS)
Extend. If you can remove three walls, then what is the shortest path from start to the target. (I have no ideal except for enumerate all the possibility of three walls. It must be the silly solution.) Does anyone have any idea?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - -4of 8 votes
AnswersGiven an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance.
Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.*
Example:Input: arr[] = {1, 2, 3, -4, -1, 4} Output: arr[] = {-4, 1, -1, 2, 3, 4} Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8} output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}
Limitations:
- gdg August 27, 2014 in United States
a) Use O(1) extra space
b) Time Complexity should be O(N)
c) Maintain the order of appearance of elements as in original array.| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersYou are given a list of items / combo_items with their price list.
- Greg August 22, 2014 in United States for Bing
And you are given list of items to buy.
Now you are asked to find which combination to buy so that it costs you minimum.
It doesnt matter if you are getting some extra items if it costs less.
Sr.No Price | Items/Combo_Items
1. 5 | Burger
2. 4 | French_Frice
3. 8 | Coldrink
4. 12 | Burger, French_Frice, Coldrink
5. 14 | Burger, Coldrink
Input Items to Buy:
Coldrink
Output(Sr.No)
3
Input Items to Buy:
Burger Coldrink
Output(Sr.No)
4
Input Items to Buy:
Burger French_Frice
Output(Sr.No)
1,2| Report Duplicate | Flag | PURGE
Google Software Engineer / 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 - 2of 2 votes
AnswersYou are given a text file that has list of dependencies between (any) two projects in the soure code repository. Write an algorithm to determine the build order ie. which project needs to be build first, followed by which project..based on the dependencies.
- enok August 18, 2014 in United States
Bonus point: If you can detect any circular dependencies and throw an exception if found.
EX: ProjectDependencies.txt
a -> b (means 'a' depends on 'b'..so 'b' needs to be built first and then 'a')
b -> c
b -> d
c -> d
Then the build order can be
d , c, b, a in that order| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer 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 - 3of 3 votes
AnswersFind the longest words in a given list of words that can be constructed from a given list of letters.
- Rohitraman2006 August 01, 2014 in United States
Your solution should take as its first argument the name of a plain text file that contains one word per line.
The remaining arguments define the list of legal letters. A letter may not appear in any single word more times than it appears in the list of letters (e.g., the input letters ‘a a b c k’ can make ‘back’ and ‘cab’ but not ‘abba’).
Here's an example of how it should work:
prompt> word-maker WORD.LST w g d a s x z c y t e i o b
['azotised', 'bawdiest', 'dystocia', 'geotaxis', 'iceboats', 'oxidates', 'oxyacids', 'sweatbox', 'tideways']
Tip: Just return the longest words which match, not all.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 1of 1 vote
AnswersGiven 2 set of arrays of size N(sorted +ve integers ) find the median of the resultant array of size 2N.
- gdg July 25, 2014 in United States
(dont even think of sorting the two arrays in a third array , though u can sort them. Try something better than order NLogN| Report Duplicate | Flag | PURGE
Google - -7of 7 votes
AnswersWrite a method to return first five 10 digit prime numbers
- saudip100 July 22, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm