Google Interview Questions
- 1of 1 vote
AnswersGiven an 8x8 chess board, you have a bishop that moves from the current to the target position. write a code to find the minimum path from the current to the target position.
- AVK June 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 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
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 - 1of 1 vote
AnswersFrom the set of natural integer numbers
- CameronWills October 30, 2012 in United States
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}
Write an algorithm to compute the rearrangement of x that is closest to y but still greater than y. Both x and y have the same number of digits.
So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is greater than y = 2410 and closer than any other arrangements of x.
And whats the time complexity of this algorithm?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersA log of wood has n marks on it. Cost of cutting wood at a particular mark is proportional to the length of the log. The log of wood can be cut at all the marks. Find the optimal order of the marks where the log should be cut in order to minimize the total cost of cutting.
- brahmasani99 May 02, 2012 in India| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersGiven a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j.
- lyra_vega November 09, 2011 in -
Hint :- If the average of two numbers is not an integer then we can assume that they do not have an average.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven 2 arrays A,B, where x(A.length) < y(B.length), we want to
- An0nemous October 08, 2012 in -
insert (y - x) 0's to A at various places such that A*B is minimum. For instance, if A = (1, -1) and
B = (1,2, 3, 4), then inserting two 0's in the middle of A such that A = (1, 0, 0, -1) would minimize
A*B. I think he was looking for a dynamic problem solution.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.
- Vijay November 17, 2017 in India
Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5
Target number : 11
Output : 9
Target Number : 4
Output : 5| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays Coding Data Structures - 1of 1 vote
AnswersSuppose there were n numbers in an array S1, S2, S3, S4.......SN rearrange them in a such a way that they satisfy bellow property.
- Rahul Sharma November 24, 2013 in United States
S1<S2>S3<S4>......| Report Duplicate | Flag | PURGE
Google Intern - 1of 1 vote
AnswersYou are given n dices each with heads numbered from 1 to m. You are to throw the n dices and note down the sum of the numbers on each of the n dices. You'll be give a number x and its a win if the sum obtained is greater than x. The problem is the find out the winning probability given n, m and x.
- ALgeek September 28, 2012 in India
Note 1<=n<=100,
1<=m<=10,
m<=x<=n*m.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersA rooted binary tree with keys in its nodes has the binary search tree
- Rahul June 09, 2011
property (BST property) if, for every node, the keys in its left
subtree are smaller than its own key, and the keys in its right
subtree are larger than its own key. It has the heap property if, for
every node, the keys of its children are all smaller than its own key.
You are given a set of n binary tree nodes that each contain an
integer i and an integer j. No two i values are equal and no two j
values are equal. We must assemble the nodes into a single binary tree
where the i values obey the BST property and the j values obey the
heap property. If you pay attention only to the second key in each
node, the tree looks like a heap, and if you pay attention only to the
first key in each node, it looks like a binary search tree.Describe a
recursive algorithm for assembling such a tree| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Trees and Graphs - 1of 1 vote
AnswersGiven two binary trees ( not BST) , return true if both of them have same inorder else return false.
Eg.B / \ A C
A \ B \ C
Both of the trees have same inorder ( A-B-C) hence function will return true
- Anonymous April 25, 2015 in United States
P.S.
Please note, we can write inorder method call it once for first tree and then second tree, and finally compare both inorder.
We want to parallely do inorder on both tree, if there is mismatch between inorder nodes of both trees, we can stop the traversal and return false| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 1of 1 vote
Answerscalculate (x^y)%z without pow();
- changran52m July 23, 2013 in United States for youtube| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersGiven an N x M matrix having only positive values, we have to nullify the matrix i.e make all entries 0.
- anurag.gupta108 September 20, 2012 in United States
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time
Find the minimum number of operations required to nullify the matrix.
Note: no range of input was given| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a list L of video names and their watch rates, write a function that will return the videos with the top 10 watch rates. Video names may appear more than once.
- neer.1304 July 03, 2019 in United States
Example:
L = [(‘abc’, 10), (‘def’, 15), (‘ghi’, 10), (‘abc’, 12), …, (‘xyz’, 100)]
The function should return [‘xyz’, ‘abc’, …, ‘def’, ‘ghi’]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a string S, print the longest substring P such that P > S lexicographically.
- emb March 16, 2016 in United States
You may assume that such substring exists.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order.
- Ankul Garg August 28, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 1of 1 vote
Answers// For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
- samayragoyal990 February 24, 2019 in United States
// For example, for K = 8 and vector [2, 4, 5, 7], the solution is 5 ([2], [4], [2, 4], [2, 4, 5], [2, 5])
The time complexity should be O(n2). Approach and code was asked| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersSort a singly-linked list of unknown size using constant space.
- trunks7j March 25, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of n integers. MaxPrefix is defined as count of elements those are greater than the element and in the right side of array wrt to the element. Write a program to give the max of MaxPrefix Ex. Input 10 -4 6 2 8 9 4 Output is 5
- darklight June 19, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersFind a duplicates in an array of length n. The values are positive integers in the range between 1 .. n-1
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersWrite a function which, given two integers (a numerator and a denominator), print the first N digits of a rational number. For example, for 5 / 3 with N=5, the result should be "1.66666". N=2: 1.66
- Dan Shah May 13, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGiven a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y
- jobseeker June 16, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersReturn the pivot index of the given array of numbers. The pivot index is the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Input Array {1,2,3,4,0,6}
- umesh.shaw November 11, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 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 - 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 - 1of 1 vote
AnswersIn a party there are n different-flavored cakes of volume V1, V2, V3 ... Vn each. Need to divide them into K people present in the party such that
- ANONU April 14, 2013 in India
- Each member of party gets equal volume of cake (say V, which is the solution we are looking for)
- A given member should get a cake of single flavour only i.e. You cannot distribute parts of different flavored cakes to same member.
- Minimum volume of cake gets wasted after distribution so that means a maximum distribution policy| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersRandomly return a node in a binary tree, program in C/C++, and define the class or struct of the binary tree by yourself.
- superffeng April 20, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm