Google Interview Questions
- 0of 4 votes
AnswersGiven that you have a graph with an even number of points, how do you find two points that equally subdivide the graph?
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 4 votes
AnswersGiven a kernal code in "0"th machine. How soon you can replicate the kernal across N machines. Now if the machines has upload and download bandwidth constraints, how can you impove the copy time.
- Guy January 24, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Operating System - 0of 2 votes
AnswersGiven a List of Strings, return the number of sets of anagrams.
- SK June 30, 2015 in United States
For instance, given:
<abc,cab,dac,beed,deb,few,acd>
return 5| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 2 votes
AnswersHow will you find if a string is a substring of another string in O(n) complexity. For example, "tl" is substring of bottle.
- Madan November 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 2 votes
AnswersPrint All common ancestor of Given Binary tree in O(n)
- NaiveCoder April 30, 2012 in India
without using Extra space.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 2 votes
AnswersGiven a sorted array, find a way to find the # of occurrence of a number
- aj June 09, 2015 in United States
for eg: [1, 1, 2, 3, 3, 3, 4, 5]
find # of occurrence of 3 in time better than O(n)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersThe text of question below is exactly given by Google interviewer. So they are owner of the text and I am just quoting them. I am not the author of the text below:
- amirtar May 05, 2015 in United States
"
Imagine a museum floor that looks like this:
.#.G.
..#..
G....
..#..
G == Museum Guard
# == obstruction/impassable obstacle
. == empty space
Write a piece of code that will find the nearest guard for each open floor space. Diagonal moves are not allowed. The output should convey this information:
2#1G1
12#12
G1223
12#34
You may choose how you want to receive the input and output. For example, you may use a 2-d array, as depicted here, or you may use a list of points with features, if you deem that easier to work with, as long as the same information is conveyed.
"| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Ideas Math & Computation - 0of 2 votes
AnswersA river separates two banks, there are 3 men and 3 lions on one side that need to be taken across using a boat that can carry 2 entities at a time(irrespective of being a lion and man), subject to the condition that at no point can you have more number of lions than men on any bank, as then the lions would eat the man/men. Solve the puzzle. Then code it to make it a generic program that solves the puzzle for X men and Y lions.
- me December 27, 2008
3-3 is easy, generalization is a bit problematic.| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Brain Teasers - 0of 2 votes
AnswersWrite a function return an integer that satisfies the following conditions:
- Obiwana March 10, 2014 in United States
1) positive integer
2) no repeated digits, eg., 123 (valid), 122 (invalid)
3) incremental digit sequence, eg., 1234 (valid) 1243(invalid)
4) the returned integer MUST be the smallest one that greater than the input. eg., input=987, return=1023
function signature could be like this:
String nextInteger(String input)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 2 votes
AnswersGiven API:
- jiangok2006 July 26, 2012 in United States
int Read4096(char* buf);
It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file.
The return is the number of chars read.
Todo: Use above API to Implement API
"int Read(char* buf, int n)" which reads any number of chars from the file.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 2 votes
AnswersHow many Fibonacci numbers exists less than a given number n.Can you find a function in terms of n , to get the number of fibonacci number less than n.
- Rahul Sharma January 13, 2016 in United States
Example : n = 6
Answer: 6 as (0, 1, 1, 2, 3, 5)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 2 votes
AnswersOn a 2-D grid, the positions (x,y) of 3 persons are given. Find the meeting point such that sum of distances of each person from meeting point is minimized.
- Andy2000 September 04, 2012 in United States
Now generalize this to N persons and solve.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersLongest Common Prefix from N strings of max length "m".
- Ajeet March 14, 2011
I gave a naive approach of O(n.m) and O(m.logn) with some adjustments but Interviewer wanted something O(n+m) or better than O(n.m).
Please suggest solutions.
eg:
Flower
Flow
Flight
Output:
Fl| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersFind the k-th Smallest Element in Two Sorted Arrays. I followed the algorithm from this post, http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
But it does not handle the case where there are duplicates? Does anyone know how to do that? Also, in Java, how should we reduce the size of the arrays? I used the code below, but did not work.
- Guy February 20, 2014 in United Statespublic static int kthSmallest2(int[] a, int[] b, int k, int a_left, int a_right , int b_left, int b_right) { if (a_left==a_right) return b[k-1]; else if (b_left==b_right) return a[k-1]; int m = a_right-a_left, n=b_right-b_left; int i = (int)((double)m / (m+n) * (k-1)); // i can be any number // make sure i + j = k - 1 // int i = (a_left+a_right)/2 + k/2; // i can be any number int j = k - 1 - i; int bj_1 = 0, ai_1 = 0; if (i==0) { ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound else { ai_1 = a[i-1]; } if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound else { bj_1 = b[j-1]; } if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j] return a[i]; if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i] return b[j]; if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must // reside before kth smallest, so also update k. // also exclude b's upper bound, since they are all greater than kth element. return kthSmallest2(a, b, k, i+1, a.length-1, 0,j-1); else return kthSmallest2(a, b, k, 0, i-1, j+1, b.length-1); }
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersGiven a list of pies (and the number of slices in each pie) calculate the maximum number of slices that nPeople could receive if each person got the same amount of slices and did not get slices from more than 1 pie.
- Dinkleberg May 09, 2016 in United Statespublic int getMaxSlices(List<Integer> pieSlices, int nPeople) { // return answer }
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersYou are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit. For example, integer 2048 is represented in the stream as 8, 4, 0, 2.
- autoboli May 30, 2015 in United States
Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.
Example:
s_a: 8 4 0 2
s_b: 4 2 0 1
result: '1024'| Report Duplicate | Flag | PURGE
Google - 0of 2 votes
AnswersDesign an optimised algorithm to solve snakes and ladders with the least amount of roles possible under the assumption that you get whatever role you want when you role the dice.
- abc March 26, 2015 in United Kingdom for Graduate| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 0of 2 votes
Answersgiven an array of n elements, find if there is a subset of 3 elements sum up to value T with time complexity O(nlgn).
- Algo November 09, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersYou are given 4 integer numbers. Using each number once and only once with any operators from +, -, *, /, (, ), build an expression that evaluates to 24.
- CodeConquer April 22, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 0of 2 votes
AnswersGiven an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].
- Rahul Sharma February 26, 2015 in India
**Example:**
For n=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
How can we figure out minimum number of swaps in most effective way ?| Report Duplicate | Flag | PURGE
Google SDE-2 - 0of 2 votes
AnswersInput : A Perl program file
- Seeker September 25, 2013 in United States
We need to modify the file to have a max of 80 characters per line and create a new perl file.
Problem is we need to use "/" wherever we split the line and also, the split MUST happen at a place with white space. (ASSUMPTION - No is >75 characters)| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm Perl Python - 0of 2 votes
AnswersA robot on a plane has 2 types of commands:
1. move forward by X units (X is integer 0 <= X <= 10000 )
2. rotate by X degrees (X is integer in range [-180, 180] )
A robot looks likedef robot(commands): while True: for command in commands: execute(command)
Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.
Example:
- emb June 06, 2016 in United States[move(10), rotate(180), move(10)] -> answer is yes [move(10), rotate(45), move(10), rotate(-45), move(10), rotate(45)] - answer is no
| Report Duplicate | Flag | PURGE
Google Software Developer Brain Teasers - 0of 2 votes
AnswersGIven a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word doesn't fit in the same line, it should move to the next line. Find an efficient solution for this. For eg.
- rucknrull July 14, 2016 in United States
List of words: { "Do", "Run" }
Number of columns: 9
Number of rows: 2
First row: "Do Run Do" (7 letters + 2 spaces fit into 9 columns)
Second row: "Run Do" (Only 2 words fit into 9 columns)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersGiven a string of characters, find the longest legal word. A generic method to check word legality is given.
- tgerg2009@my.fit.edu November 06, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 2 votes
AnswersWrite a routine that does secret santa in O(N) time. I don't really understand what it means by 'does secret santa' actually.
- Guy January 29, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersEach leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an "AND" or an "OR" gate associated with it. The value of an "AND" gate node is given by the logical AND of its two children's values. The value of an "OR" gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree.
- game January 21, 2010
It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion).
Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that?
Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersGiven a set of horizontal and vertical line segments, find the number of squares formed by them?
- uj.us October 04, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 2 votes
AnswersPrint all the different possible subsets suming the given number
- guysackman21 March 21, 2015 in India
Ex:
Input:4
Output:
1111
112
121
112
13
31| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 2 votes
AnswersFor a stream of insertions and deletions, recall that x[j] = #insertions - #deletions of element j.
- ALgeek November 17, 2011 in India
Given such a stream satisfying x[j] >= 0 for all elements j, let
A = { j : x[j] > 0 }
Determining whether A is empty is easy: just check if the sum of all x[j]'s equals 0 (which is easily doable in a stream).
Problem: devise a small memory streaming algorithm to determine if |A| = 1.
Extensions: What about higher sizes of A? What if the promise is not satisfied and we define A to be the set of j's with x[j] not equal to 0.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 2 votes
AnswersWrite algorthim to determine the total time to make ice cream and when it leaves the store.
- google_me_honey March 12, 2015 in United States
Consist of an order time, order number, and ice cream type.
“ice cream Type” is an integer: 0 for combo, 1 for vanilla. Order numbers are increasing.
We have three machines for making ice creams.
It takes 45 seconds to make a combo ice cream and 15 for vanilla. Can only make one ice cream at a time.
Need to determine total time to make ice cream and time the ice cream leaves the store (delivered).
In: order_time,order_num,ice_cream_type
Out: order_num,depart_time,total_time| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm