Google Interview Questions
- 0of 0 votes
AnswersGiven a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths.
Ex: Given stringbanana
and array is
[bana, apple, banaba, bonanza, banamf]
and the outpost should be true as banana and banaba are one character difference.
- kpraveen420 October 03, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays String Manipulation - 8of 8 votes
AnswersGiven an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]
That is, implement the following naive algorithm faster than O(n^2)def naive_algorithm(lst, a, b): result = 0 for i in xrange(len(lst)): for j in xrange(i, len(lst)): if a <= sum(lst[i:j + 1]) <= b: result += 1 return result
Examples:
count([1,2,3], 0, 3) = 3 # [1], [2], [3], [1, 2], [3] count([-2,5,-1], -2, 2) = 3 # [-2], [-1], [-2, 5, -1]
You may assume that there are no overflows, that is sum(|x_i|) <= MAX_INT - 1
- emb September 26, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 5 votes
AnswersYou are given an array of n unique integer numbers 0 <= x_i < 2 * n
- emb September 23, 2015 in United States
Print all integers 0 <= x < 2 * n that are not present in this array.
Example:
find_missing([0]) = [1]
find_missing([0, 2, 4]) = [1, 3, 5] # because all numbers are [0, 1, 2, 3, 4, 5]
find_missing([]) = []
find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # because all numbers are [0, 1, 2, 3, 4, 5, 6, 7]
Quirks are about requirements:
Time complexity O(n) - BUT there should be some fixed constant C independent of size of input such that every element of array is written/read < C times, so radix sorting the array is a no go.
Space complexity O(1) - you may modify the initial array, BUT sorted(initial_array) must equal sorted(array_after_executing_program) AND you can't store integers outside range [0, 2n) in this array (imagine that it's an array of uint32_t).| Report Duplicate | Flag | PURGE
Google Software Engineer Brain Teasers - 1of 1 vote
AnswersYou are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour.
- aijackmoore September 21, 2015 in United States
e.g. 100207 100208 2
100305 100307 5
100207 100209 4
111515 121212 1
Answer: 100207
(Need to consider different scenarios like the time slots could be very sparse)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersCounting the islands.
- byPaco September 15, 2015 in United States
Given a map N x N, 2-D array
0 - sea
X - land
Land is connected by 4-Neighbor connections, i.e.: above, down, left and right.
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
0000000000000000000X000000000000000
000000000000000000XXX00000000000000
000XX000000000000000000000000000000
000XXXX0000000000000000000000000000
0000000X000000000000000000000000000
00000000000000000000000000000000000
000000000000000000000X0000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
Output of this map: 4 (totally 4 islands on the map)| Report Duplicate | Flag | PURGE
Google iOS Developer - 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 - 6of 6 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
Without modifying original structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 0of 0 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
To simplify you can modify the structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 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 - 2of 4 votes
AnswersYou are given a matrix n rows, m columns where each row is sorted in increasing order. Find median of the overall elements. What is the time complexity?
- emb September 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
Answersyou are on a biz trip and travelling from one city to another. you have a stack of unsorted flight boarding passes. only departure city and destination city are on the boarding pass. how do you find the first departure city and your final destination city, write the solution in javascript.
- codebind September 06, 2015 in United States| Report Duplicate | Flag | PURGE
Google Front-end Software Engineer JavaScript - 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 - 0of 0 votes
AnswersImplement a method for the following signature:
void * alignedAllocate(size_t sizeInBytes, size_t alignment) { }
The method should allocate memory for the given size and the pointer should be aligned.
For example ifp = alignedAllocate(1000,64);
p%8 should be 0.
- thewhatwhat September 05, 2015 in United States
Implement a second method that deleted the pointer give p.
Extend the delete method to handle multiple p's.| Report Duplicate | Flag | PURGE
Google Software Engineer C C++ - 8of 8 votes
AnswersYou are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0.
- emb September 04, 2015 in United States
A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise)
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn't cross| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersInteger Array Ques:
- cdude September 01, 2015 in United States
Given an integer array of variable length like so [9, 8, 8, 3] where each item in array could be 0 to 9, write a function that would take would interpret the array [9, 8, 8, 3] as a number 9883 and increment it by 1. The return of the function would be an integer array containing the addition like so [9,8,8,4]. No zeros in the first position like [0,1,2,3]. I initially suggested a possible solution of process to convert the integer array to String then convert to Integer or Long and then do the addition of 1 and then convert it back to integer array. That is not allowed when the interviewer change the ques. to not allow that.| Report Duplicate | Flag | PURGE
Google Android Engineer Arrays - 0of 0 votes
AnswersGiven unsigned integer 'x', write an algorithm thet returns unsigned integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance |x-y| is minimized.
- autoboli August 31, 2015 in United States
Example:
x: 01
y: 10
Note that one bit is set and 'x' is not equal 'y'. You may assume that x is positive integer between zero and 2^32-2;| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersWrite function to determine if given unsigned 32-bit number is a power of 3
int is_power_of_3(uint32_t n)
return 1 if yes, 0 otherwise.
e.g.is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0
Expected the answer not to be straightforward loop, but something faster.
- emb August 28, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Math & Computation - 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 - 3of 3 votes
AnswersSuppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.
- lucifer1986 August 28, 2015 in United States
The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.| Report Duplicate | Flag | PURGE
Google Data Structures - 1of 1 vote
AnswersGiven an array consisting of N Numbers.
- smarthbehl August 25, 2015 in United States
Divide it into two Equal(it is important) partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum.
If number of elements are odd difference in partition size can be at most 1.| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersWrite all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5] in at least O(n^2) complexity
- dev123 August 24, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersDesign a data structure which should have following operation. Insert, Delete, Random access
- hm August 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 1of 1 vote
AnswersGiven 2 large number A and B, create a new number C using the digits from A which needs to be grater than B.
- hm August 21, 2015 in United States
e.g. A = 5281, B = 7443
C = 8125.| Report Duplicate | Flag | PURGE
Google Software Engineer Math & Computation - 7of 7 votes
AnswersGiven a binary N X N matrix, return the size of the largest '+' of ones.
- zaxven August 19, 2015 in United States
input:
0 0 0 0
1 1 0 1
1 1 1 1
1 1 1 0
output:
5
(binary search is not allowed)| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersList of 2D points: (x1, y1), (x2, y2) … (xN, yN) - N 2D points.
- zaxven August 19, 2015 in United States
Each two points define a 2D line.
create an algorithm which returns a list of all unique 2D lines, which you can build using pairs of points from the list.| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersGiven n light bulbs, write two methods.
- cup August 19, 2015 in United States
isOn(i) to determine if a light bulb is on
toggle(start, end) to toggle all the light bulbs in the range
One caveat, write toggle so that it is less than O(n) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersWrite a function called deepCopy that takes an object and creates a deep copy of it.
- shabgard August 13, 2015 in United States
var newObj = deepCopy(obj);
(can't use JSON, can't use prototype)| Report Duplicate | Flag | PURGE
Google Software Engineer JavaScript - 5of 5 votes
AnswersI came across this problem online.
- xiaoc10 August 07, 2015 in United States
> Given an integer:N and an array int arr[], you have to add some
> elements to the array so that you can generate from 1 to N by using
> (add) the elements in the array.
Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers.
For example:
N=6, arr = [1, 3]
1 is already in arr.
add 2 to the arr.
3 is already in arr
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3
So we return 1 since we only need to add one element which is 2.
Can anyone give some hints?| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 4of 4 votes
AnswersCheck if two integers are equal without using any comparison operators.
- coolProgrammer August 03, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Bit Manipulation - 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