Google Interview Questions
- 0of 0 votes
AnswersGiven a sorted array of n integers, pick up k elements so that the minimal difference between consecutive elements is maximal (that is choose the elements to maximize the quantity min(a[i+1] - a[i]))
- Anonymous March 26, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven array of integers , return an index such that it devides the array in 2 parts ,i.e.sum of all elements which are left side of the index = sum of all elements which are right side of the index. Do in linear time.
- Anonymous March 15, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 0of 0 votes
AnswersGiven a set of schedules with Start and End times, cluster the ones which have a collision in time. The clusters can have more than two schedules and have to be unique. Do it efficiently.
- HopeForLiving July 17, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a target sum, populate all subsets, whose sum is equal to the target sum, from an int array.
- milincjoshi September 28, 2017 in United States
For example:
Target sum is 15.
An int array is { 1, 3, 4, 5, 6, 15 }.
Then all satisfied subsets whose sum is 15 are as follows:
15 = 1+3+5+6
15 = 4+5+6
15 = 15| Report Duplicate | Flag | PURGE
Google Software Developer - 0of 0 votes
AnswersYour input is a double array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.
- talal.nabulsi5 August 27, 2017 in United States
Ex:
input is {3,4,5,1} --> output: 72
input is {1,1,1,5} --> output: 15
Follow up, if there are numbers <0| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 0of 0 votes
Answerswrite a function to generate a random 4 digit unique even number, the four digits cannot be the same, 1234 is valid, but 1134 is not valid
- ajay.raj April 13, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGiven two binary trees, A and B,
- SK January 12, 2015 in United States
we can define A as a subset of B if the root of A exists in B and if we can superimpose A on B at that location without changing B. (That is, the subtrees from the root of A and the node in B that is the same as the root of A are the same),
Example:
A:
5
4 7
B:
6
5 12
4 7 8 10
A is a subset of B in this case.
B1:
6
5 12
4 7 8 10
1
A is still a subset of B1, even though B1 extends one more level than A.
Write an algorithm to determine if one tree is a subset of another tree| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersYou are given a string FOOFIGHTERS. You have to come up with an algorithm that will compress this string.
- KevinK February 21, 2014 in United States
You also have to make sure that you are not using extra memory. For example: FOOFIGHTERS will be compressed as FO2FIGHTERS. You should not use another array or bitfield to keep a frequency count for the individual letters.| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 0of 0 votes
AnswersAdd a number to array and if there is carry increase array size.
- msgsmg May 14, 2013 in United States
----------------------------------------------------------------------
For example input = {7,3,5,3,9} convert this to number 73539, add 1 so it becomes 73540 and convert to array {7,3,5,4,0}.
Array can be of any length, so you can't always represent array in form of in-built number format. So you have to do this summation in-place. Also, how would you increase array size in-case input = {9,9,9} so output = (1,0,0,0}
Assume, all elements of arrays are between 0 and 9.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersHow would you implement an infinite counter?
- rodrigoreis22 January 22, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a number represented as an array of digits, plus one to the number.
- superffeng September 27, 2012 in United States for Site reliabilty
ie. 1000 is [1,0,0,0] result is [1,0,0,1]| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 0of 0 votes
AnswersMain Question:
- mudit.f2004912 October 11, 2011 in United States
Design a parallel Breadth First Search algorithm for a directed weighted graph.
Basically you need to find the minimum cost to reach to a node from the starting node <given>. (Just save the optimum cost and not the optimum path). Calculate and output the optimum reachability cost for all the nodes from a given starting point.
Implement in C with openMP.
1. How about using DFS or Shortest path first instead. Would these algorithms perform better than BFS with parallel implementation. Yes/No Why?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Distributed Computing - 0of 0 votes
AnswersInsert a node into a circular linked list.
- Anonymous June 27, 2011
This CLL is sorted. So, if the CLL is like 1->2->4->6->1
you will be asked to input a node 3 and it must come between 2 and 4.
Write a program for this in C++ or JAVA| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 0of 0 votes
AnswersWrite a program to print a 2-D array spirally- i.e, starting at a corner and spiraling inwards.
- Anonymous April 28, 2011
Reverse the bits of an integer| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersA large file containing strings. How do you find number of unique strings? Write code...
- vi December 13, 2010
FOLLOW UP: What hash function would you use?
FOLLOW UP: If hash cannot fit in the memory, what can you do...assuming only one machine.
FOLLOW UP: What if external sorting is also expensive...?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite code in C,C++ or java to find whether a given binary tree is mirror image of itself??
- Manish October 17, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 0of 0 votes
AnswersConvert a min heap to BST without changing its structure and of course no extra space .
- Anonymous October 17, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven preorder and inorder traversal of tree, write the code to form binary tree from given traversal.
- rahul August 01, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersfind the Nth largest node in a BST
- nixu09 February 12, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 0 votes
AnswersIdentify the regular expression in a given string such that the pattern does not repeat. For example, to identify the pattern 'foo' only once in an input.
- Anonymous October 06, 2008
'jhkhfoojkkj' should be identified right
'kjhfooaaaaafoo' should not be| Report Duplicate | Flag | PURGE
Google Software Engineer in Test String Manipulation - 0of 0 votes
AnswersGiven a puzzle of letters/ characters e.g.
- Anonymous September 18, 2008
a e r o p s
b h a r l s
w r i s l o
a s n k t q
Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the second column and slow in the third row wrapped around.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 0 votes
AnswersGiven a binary tree & the following TreeNode definition, return all root-to-leaf paths.
Definition of TreeNode:public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = this.right = null; } }
EXAMPLE
Given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: [ "1->2->5", "1->3" ]
From Lint Code - http://www.lintcode.com/en/problem/binary-tree-paths/
- johndifini October 29, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersWarm-up question: Write a function that prints all ASCII characters. You are not allowed to use for/while loop.
- autoboli January 27, 2015 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
Answersyou have experience with a 3x3 Sudoku.Think about 2*2 sudoku:
- Rahul Sharma January 13, 2015 in India
The array has 4 rows and 4 columns.
The numbers 1, 2, 3 and 4, each appears exactly once in each row.
The numbers 1, 2, 3 and 4, each appears exactly once in each column.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 1, 2.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 3, 4.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 1, 2.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 3, 4.
Your task is:
1. Count all possible different solutions of the 2*2 sudoku.
2.Print all solutions.
3.Store all solutions.| Report Duplicate | Flag | PURGE
Google SDE-2 - 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 - 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 - 0of 0 votes
AnswersWrite function that takes two integers m and n respectively. The function should flip the nth bit of m, counting from the LSB and return the resulting value.\
- llmorex February 05, 2012 in United Kingdom
By flip, the interviewer meant change 0 to 1 and 1 to 0. For instance, if you were passed in 8 and 3.
Convert 8 to binary and you have 1000, now we flip the 3rd bit and we have 1100, then we convert this back to decimal(which would be 12)and return the answer.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array 1 to N , how many permutations of it will be Min -Heap of of N! possible permutations
- anynomous July 16, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer