Google Interview Questions
- 4of 4 votes
AnswersGiven an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.
- Gaurav Shah March 17, 2015 in United States for Chrome Team
eg:
[1,4,5,2,3]
o/p:
[1,4,2,5,3]
Soln proposed:
Step 1:Sort The array -> O(nlogn)
Step 2:Use 2 indices: one starting at leftmost index and other at rightmost index.
and populate the new array alterntely using the left pointer(index) first and then the right pointer and then increment the pointer used. till both the pointers meet/cross each other. -> O(n).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven a list of integers, find the highest value obtainable by concatenating these together.
- GAGA November 20, 2015 in United States
For example, given 9, 918, 917 - The answer is 9918917.
But given 1,112,113 - The answer is 1131121| Report Duplicate | Flag | PURGE
Google - 4of 4 votes
AnswersReturn the length of longest possible chunked palindrome string.
- AlgoBaba December 08, 2016 in United States
Examples :
Input : VOLVO
Output : 3
Explanation :
(VO)L(VO)
Input : merchant
Output : 1
Explanation : No chunks possible.
Input :
ghiabcdefhelloadamhelloabcdefghi
Output : 7
Explanation :
(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersYou are given an unsorted sequence of integers 'a'. Find the longest subsequence 'b' such that elements of this subsequence are strictly increasing numbers. Elements in the subsequence 'b' must appear in the same relative order as in the sequence 'a'. You may assume that 'a' can fit to the memory.
- autoboli February 24, 2015 in United States
Example:
input: a = [-1 2 100 100 101 3 4 5 -7]
output: b = [-1 2 3 4 5]| Report Duplicate | Flag | PURGE
Google - 4of 4 votes
AnswersYou are given an array of integers 'a' that can fit in a memory. Write a method that retuns an array of the same lenght such that each element 'i' of this array is a sum of 'a' except the element a[i]. You are not allowed to use '-' operator.
- autoboli January 13, 2015 in United States| Report Duplicate | Flag | PURGE
Google - 4of 4 votes
AnswersGiven the relative positions (S, W, N, E, SW, NW, SE, NE) of some pairs of points on a 2D plane, determine whether it is possible. No two points have the same coordinates.
- united November 02, 2014 in United States
e.g., if the input is "p1 SE p2, p2 SE p3, p3 SE p1", output "impossible".| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersYou are given a scrambled input sentence. Each word is scrambled independently, and the results are concatenated. So:
- merlinme October 25, 2016
'hello to the world'
might become:
'elhloothtedrowl'
You have a dictionary with all words in it. Unscramble the sentence.| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer String Manipulation - 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 - 4of 4 votes
AnswersQuestion: Two players A and B are playing a game. Pots of gold, each with
- kiran.sanni October 28, 2014 in United States
varying number of coins are placed in a single line. The rules of the game are:
1) Players play turn by turn.
2) On each turn a player can pick a pot of gold from either end of the line. He
gets all the gold in that pot. The next pot of gold on that end is now available
for picking.
What is the maximum number of gold can the first player get ?| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 4of 4 votes
Answersdesign a method which consumes an integer and output the corresponding column number in Microsoft Excel ( ex. A, B, C......Z, AA, AB....ZZ....)
- chandeepsingh85 September 25, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven a string return the longest palindrome that can be constructed by removing or shuffling characters.
- enkadi13 July 22, 2016 in United States
Example:
'aha' -> 'aha'
'ttaatta' -> ' ttaaatt'
'abc' -> 'a' or 'b' or 'c'
'gggaaa' -> 'gaaag' or 'aggga'
Note if there are multiple correct answers you only need to return 1 palindrome.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersYou are given two arrays of length M and N having elements in range 0-9.Your task is to create maximum number of length K from elements of these two arrays such that relative order of elements is same in the final number as in the array, they are taken from i.e. If two elements a,b are taken from array1 and and a comes before b in array1 so in the final number a should come before b (Relative order kept same) .
- Rahul Sharma November 18, 2015 in United States
Example: N=4 and M =6
Array1 = { 3 , 4 , 6,5}
Array2 ={9,1,2,5,8,3}
Suppose K = 5, then number will be {9,8,6,5,3}
You can see {9,8,3} are taken from array2 in the same order as they are in Array2. Similarly {6,5} are taken from Array1 in the same order and number 98653 is maximum possible number.| Report Duplicate | Flag | PURGE
Google Research Scientist Algorithm - 4of 4 votes
AnswersGiven an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersConsider the array 3 5 7 6 3.
- Gaile April 10, 2014 in United States
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= 2.
Output:
(0,0) (1,1) (2,2) (3,3) (4,4) (5,5)
(0,1) (1,2) (1,3) (2,3)
Example slices: 3 5, 5 7, 1 3, 2 3.
The following link
https://codility.com/media/train/solution-count-bounded-slices.pdf
has O ( n ) solution. But couldn't understand the O (n ) solution. Could some one explain with an example?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
Answersgiven an 2D matrix M, is filled either using X or O, you need to find the region which is filled by O and surrounded by X
- smit February 14, 2014 in India
and fill it with X.
example 1:
X X X X X
X X O O X
X X O O X
O X X X X
Answer :
X X X X X
X X X X X
X X X X X
O X X X X
example 2:
X X X X X
X X O O X
X X O O O
O X X X X
answer 2:
X X X X X
X X O O X
X X O O O
O X X X X| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.
Example:Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5
Edit: Thanks, wangchenClark0512, forgot about C to D
- djway August 18, 2016 in United States
Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.
Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 4of 4 votes
AnswersGiven N pens and n caps . Sort them. you cant compare pens with other pens and caps with other caps
- Anonymous July 29, 2011| Report Duplicate | Flag | PURGE
Google - 4of 4 votes
AnswersHow to serialize strings and pass it over the network and de-serialize the string? The string may contain any possible character out of 256 valid characters.
- rya November 13, 2010
The interviewer tried to give a hint "how do you escape characters in a string" !
Should the answer be use serializable in Java? Or is there a specific algorithm?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven an non-negative int array and target number, check if the target can be equal to the sum of non-negative multiples of the numbers in the array.
- ajay.raj March 17, 2017 in United States
For example, I have three numbers 6,9,20. Ex: n = 47 then it can be determined that 47 = 9*3 + 20
n=23 then there are no combinations.
public boolean combinationSum(int[] nums, int target) {
}| Report Duplicate | Flag | PURGE
Google SDE1 - 4of 4 votes
AnswersGiven an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersYou are given 2 documents. We want to know how similar they are through N-Grams.
- um01 June 20, 2015 in United States
Given an input n (n = number of word in the Ngram) and two documents(strings) find the intersection of the NGrams of two document.
E.g doc1 = 'This is a dog'
doc2 = 'This is a cat'
n = 3
Ngrams for doc1 = 'This is a', 'is a dog'
Ngrams for doc2 = 'This is a', 'is a cat'
Output 'This is a'
Find a efficient way and give its complexity.| Report Duplicate | Flag | PURGE
Google Software Engineer - 4of 4 votes
AnswersFind the median of 2 sorted arrays
- Partha November 10, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 4of 4 votes
Answers/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
Find if a given binary tree has duplicate sub trees.
followup:
Find all duplicate subtrees in a binary tree
- ajay.raj March 03, 2017 in United StatesFor example, 1 / \ 2 3 / / \ 4 2 4 / 4 The following are two duplicate subtrees: 2 / 4 and 4 Therefore, return [ [2,4], [4] ].
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersFeb On-site Google
- aonecoding March 10, 2018 in United States
DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.
You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.
Follow-up: optimize 2d DP to 1d DP of linear extra space.
Follow-up: what if some cells are blocked
System Design
Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.
Interviewer seemed to be expecting more but time ran out.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a list of queries and their counts, write a function that returns one of the queries at random such that over time it returns an equal distribution based on the counts provided in the input.
- Rando May 17, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersWhat happens when you type in shell
list=$(ls)
Interviewer expected the list of system-calls made, file-descriptors involved etc.
- Moony April 29, 2014 in United States| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Unix - 3of 13 votes
AnswersIn a language, there are only 4 characters ‘h’, ‘i’,’r’, ‘e’. and we have to write a function which takes a string as input and returns whether the given input string is a “valid word” or not.
- hugakkahuga October 23, 2013 in India
Definition of valid word :
1. A given word is a valid word if it is of the form h^n i^n r^n e^n where n >=1. (eg: hhiirree)
2. Valid words has concatenation property i.e. if w1 and w2 are valid words w1w2 is also a valid word.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 11 votes
AnswersGiven a binary representation of an integer say 15 as 1111, find the maximum longest continous sequence of 0s. The twist is it needs to be done in log N. I could think of O(N) solution. but couldn't go for log(N).
- TapeRecordia October 24, 2013 in United States
For example. 10000101
the answer should be 4, because there are 4 continouos zeroes.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 5 votes
AnswersGiven a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
- Phoenix December 02, 2014 in United States
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 5 votes
AnswersProblem Statement
- nirajkantsinha March 13, 2015 in United States
Diameter
The diameter of a graph is the maximum shortest path between any two nodes.
At the beginning, there is a simple grpah contains exactly 1 node. Then we add new nodes one by one to the graph. Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists.
We want to find the diameter of the graph each time we add a new node. Note that each edge cost 1.
Input Format:
First line of the input contains one integer N, indicating how many new nodes we will add.
Then following N lines. The ith line contains an integer X, which means we add the ith node and an edge connecting the Xth node and ith node.
The original node is the 0th node.
Output Format:
Output N lines. The ith line is an integer indicating the diameter of the graph after adding the ith node.
Constraints:
0 < N <= 100000
0 <= Xi < i
i is counting from 1
Sample Input:
5
0
0
1
1
1
Sample Output:
1
2
3
3
3
Explanation:
Firstly the graph contains only node 0. The first line of output is 1 because the diameter becomes 1 when node 1 is added and connected to node 0. Diameter becomes 2 after adding node 2 to node 0. Then adding node 3, 4, 5, all of them are connecting to node 1, caculate the shortest path of all pairs of nodes, the maximum shortest path is 3, so the last 3 lines of output are all 3.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm