Google Interview Questions
- 0of 0 votes
AnswersWrite a method echo such that
- MaYanK July 29, 2010
e.g.
i/p : cat
o/p : catcac
i/p : max
o/p : maxmam| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 0of 0 votes
AnswersGiven an array of numbers, find the longest alternating subsequence. That is, a subsequence [a1, a2, a3, ..., ak] where a1 > a2, a3 < a2, a4 > a3, ... or vice versa (Graphically looks like /\/\/\... or \/\/\/\....
- emb March 19, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersGiven an arbitrary tree starting at “root” where each node contains a pair of values (x, y), write a boolean function find(Node root, int x, int y) that returns true iff
- Basu March 08, 2016 in United States
* x is equal to a value "x" of any node n1 in the tree
* and y is equal to a value "y" of any node n2 in the tree
* and both n1 and n2 are at the same level in the tree
boolean find(Node root, int x, int y)
Example:
(1,120)
/ | \
/ | \
/ | \
(5,15) (30,70) (80,110)
/ | \ |
/ | \ |
/ | \ |
(35, 40) (45,50) (55, 65) (90, 100)
boo == true
find(root, 45, 100) == true
find(root, 30, 100) == false
find(root, 30, 70) == true
find(root, 70, 30) == false| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answersc = ‘a’
- zyfo2 December 26, 2012 in United States
w = “apple”
c covers w, iff w contains c.
c_set = {‘a’, ‘b’, ‘c’, ‘g’}
w_set = {‘apple’, ‘ibm’, ‘cisco’, ‘google’}
c_set covers w_set, iff every w in w_set is covered by some c in c_set.
Given c_set and w_set, Whether w_set is covered by c_set?
Follow up: if w_set is fixed say a book, how to determine whether a c_set covers this w_set?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersDesign a queue (FIFO) using only stacks (LIFO). The only supported operations on the stack are: Push(), Pop() and IsEmpty(). The final queue had to implement the operations Queue() and Dequeue(). The program had to be efficient and handle exceptions.
- Anonymous August 15, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures Algorithm - 0of 0 votes
AnswersYou have two BST, you have to merge them into a single BST, inplace and linear time.
- Anonymous March 26, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersconvert a binary tree to binary search tree inplace. We cant use any extra space.
- Abhilash H February 22, 2011| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 0of 0 votes
AnswersGiven an array of integers, find out number of ways in which you can select increasing subsequences of length k(k<=n).
- kaira February 11, 2011
for eg array is 1 4 6 2 5 & k=3
then the answer is :- 1 4 5, 1 2 5,1 4 6, 1 2 6,
so ways are 5
he first made me to write a recurrence then asked me to memoize that| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of n numbers (A1, A2, A3....An)(where Ai can be positive or negative, i=1 to n), find the value of maximum sum of all sub-array's sums, such that these numbers (in the sub-array) are continious in the given sample.
- FirstTimer1234 October 20, 2010
Example:
-1,1,3,-1
The max value for the sub-array is 4. The continious sub-array is 1,3
If the input was 1,-1,-1,3
then our answer is 3 since 1 and 3 are not continious| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersFind kth smallest element from an unsorted array in linear time. worst case complexity should be O(n+k)
- Anonymous October 17, 2010
where n is array size.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a sum s, and an integer n as an input, find all possible combinations that sum up to s. For example:
- Raj September 24, 2010
If s = 5, and n = 2, then output should be
0+5, 1+4, 2+3, 3+2, 4+1, 5+0
If s = 5, and n = 3, then output should be
0+0+5, 0+1+4, 0+2+3, 0+3+2, 0+4+1, 0+5+0, 1+0+4, 1+1+3, 1+2+2...2+0+3, 2+1+2...5+0+0
and so on for n = 4, 5...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersgive an array, remove all the 'a's and add one 'd' after each 'b', do it in O(n)...
- Anonymous March 06, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersImagine you have a row of numbers like below(a traiangle) .By starting at the top of the triangle find the maximum number in each line and sum them up example below
- Avinash Paritala November 25, 2015 in India
5
9 6
4 6 8
8 7 15
Answer I.e. 5+9+8+7 = 29
writw a code to find the maximum total from top to bottom. Assume triangle can have at most 100000 rows.
Input Output specifications
Input Specification
A string of n numbers (where 0<=n<=10^10)
eg.5#9#6#4#6#8#0#7#1#5
Output Specification
A sum of the max numbers in each line (as string ) or Output invalid in case of invalid input/triangle
Examples
eg1.
Input :5#9#6#4#6#8#0#7#1#5
Output:29
eg 2 .
Input :5#9#6#4#6#8#0#7#1
Output:invalid
eg 2 .
Input :5#9##4#6#8#0#7#1
Output:invalid| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersYou have some money in your bank account, the only function to withdraw money is uint16 Withdraw(uint16 value), if the value is greater than the money you have it returns 0, otherwise it withdraws the requested amount and returns the "value"
- mike.radula October 13, 2015 in United States
Write a function that withdraws all your money.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersWrite a method that combines an array of iterators into a new one, such that, e.g. for input [A B C] where:
- CodeConquer April 22, 2015 in United States
A.next() returns a1, a2, respectively;
B.next() returns b1;
C.next() returns c1, c2, c3, respectively;
The new iterator will return elements in this order: a1 b1 c1 a2 c2 c3.| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 0of 0 votes
AnswersYou are given heights of n candles .
- Rahul Sharma March 11, 2015 in India
First day you lit one candle
second day you need to lit two candles
Third day you need to lit three candles
..........
........
till possible.
After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.
So you need to tell the maximum number number of days , you can carry on lighting the candles.
Example : there are three candles of heights {2 , 2 ,2 }
Answer : 3
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 0of 0 votes
AnswersDesign an algo to decide if the GO game is over. i.e.
- thefunnyclick1990 December 23, 2014 in United States
Given a boolean matrix, write a code to find if an island of 0's is completely surrounded by 1's.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven an arraylist of N integers,
- united November 13, 2014 in United States
(1) find a non-empty subset whose sum is a multiple of N.
(2) find a non-empty subset whose sum is a multiple of 2N.
Compare the solutions of the two questions.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answerswrite the most efficient (in terms of time complexity) function getNumberOfPrimes which takes in an integer N as its parameter.
- adam2008 February 22, 2013 in United States
to return the number of prime numbers that are less than N
Sample Testcases:
Input #00:
100
Output #00:
25
Input #01:
1000000
Output #01:
78498| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersGiven a two balanced binary search trees.Merge both the trees so that it will form again a balanced binary search tree.
- kumar June 01, 2011 in -
(NOTE: Request for correction: should the input bst s have same number of nodes? if the input bst s have unequal nodes, we cant necessarily build a balanced bst for the result )| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a tree in which each node is an integer and an array with a set of integers, determine if all the elements of the array are present in the tree by visiting each node in the tree at most once.
- Anonymous October 14, 2009| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersGiven 1 byte. Write a function that checks that it have exactly 3 bits which equal to 1.
- noam.nta April 12, 2015 in United States| Report Duplicate | Flag | PURGE
Google Developer Program Engineer - 0of 0 votes
AnswersGiven a sorted doubly linked list, write an algorithm to convert this list into a binary search tree (BST). The BST will be used to represent a set. You may expect that client will use it to search for presence of a key in the set.
You may assume that you are given the following Node implementation that you can not exted or modify:public class Node { public Node prev, next; public int key; }
You algorithm is not allowed to create any other instance of the Node.
- autoboli January 10, 2015 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersIntersection of two lists of unsorted integers.
- rodrigoreis22 January 22, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.
- bicepjai September 25, 2012 in United States for Google Engineering| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 0of 0 votes
AnswersGiven a n*n grid map that is parallel with x, y axis, the down left point is (0,0),the up right point is (n,n). Given n rectangles, the down left point and up right point are (x1,y1)(x1',y1'),..., (xn,yn)(xn',yn'). xn,yn,xn',yn',n are non-negative integers, and all rectangles are parallel with axis. Design a query which return, for a specific grid unit (x,y)(x+1,y+1), how many rectangles cover it? Minimize the time complexity of the query and the pre-processing. 1<n<1000
- gusuyucc September 24, 2012 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersGive two binary search trees, print the numbers of both together in ascending order
- testing August 27, 2011| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersSuppose we can compare two arrays like:
- wenxueqingnian April 15, 2011
{4,2,3} > {3,5,6}
{4,2,3} < {4,3,0}
In each move, you can only switch a number with one of its neighbor. Given an array and a number n, design an algorithm to make this array maximum using n moves. (needs clarification)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that
- 123 April 02, 2011
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible.
The sequence S1, S2, …, Sk is called an arithmetic progression if
Sj+1 – Sj is a constant| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm