Google Interview Questions
- 0of 2 votes
AnswersGiven an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].
- Rahul Sharma February 26, 2015 in India
**Example:**
For n=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
How can we figure out minimum number of swaps in most effective way ?| Report Duplicate | Flag | PURGE
Google SDE-2 - 3of 3 votes
AnswersFind popular item in sorted array of natural numbers.
- dreamchaser1984 February 25, 2015 in United States
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.| Report Duplicate | Flag | PURGE
Google Principal Software Engineer 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 - 2of 2 votes
AnswersConsider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.
- eng.ahmed.moustafa February 23, 2015 in United States
What is the minimum number of bits required to send the sequence?
Hint: It is not 6 x 52| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 0of 0 votes
AnswersOn a table there are four papers, one with the letter X written on top, one with the letter Y written on top, one with the number 1 written on top, and one with the number 2 written on top. Every paper has one of those letters on one side and one of those numbers on the other side. To prove that a paper with the letter x contains even number on the other side, what is the minimum number of conditions we have to check?
- LeetJile February 23, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Brain Teasers - 0of 0 votes
AnswersHow would you get all of the unique IDs out of a single file? What if it was a very large file?
- LeetJile February 23, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Knowledge Based - 0of 0 votes
AnswersWrite a function that takes an array of numbers and returns the maximum and minimum values.
- trophygeek February 21, 2015 in United States
Give BigO for runtime.
(This is a basic coding question. There are no real tricks or shortcuts.)| Report Duplicate | Flag | PURGE
Google Software Engineer Coding - 0of 0 votes
AnswersWrite a function that would print all positive numbers smaller than n that can be expressed as the sum of two cubes in two different ways. Bonus: calculate the complexity of that function.
- demonix February 17, 2015 in United States
For example, 1729 is one such number because 1729 = 1^3 + 12^3 = 9^3 + 10^3.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 0of 0 votes
AnswersWrite code that would parse an expression that is similar to BASH brace expansion. Best illustrated with an example: the expression "(a,b,cy)n,m" would be parsed into an array of the following strings:
- demonix February 12, 2015
an
bn
cyn
m
You can assume that the input will always be valid.
Hint: the expression can nest. Therefore, "((a,b)o(m,n)p,b)" parses into:
aomp
aonp
bomp
bonp
b| Report Duplicate | Flag | PURGE
Google Software Engineer Intern String Manipulation - -1of 1 vote
AnswersFrom a list of integer intervals, write a function to minimize the number of overlapping or consecutive ones.
- chudir-vai February 08, 2015 in United States
Test Input: [4, 8], [3, 5], [-1 2], [10, 12]
Test ouput: [-1, 8], [10,12]| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 0of 0 votes
AnswersSuppose you are in the middle of Africa, each machine is on an Edge network, and each packet between the machines costs $1.00. Write a solution that minimizes the cost.
- shing.zhao February 03, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Network - 0of 0 votes
AnswersYou given and instruction called DBNZ ( Decrement and Branch if Not Zero)
- srcnaks February 02, 2015 in -
which can be used as "DBNZ X L10".
This instruction decrement X by one and checks X, if X is not zero than branches line 10,
if it is zero than continue to next instructions.
By using DBNZ instruction implement CLEAR instruction.
CLEAR can be used as "CLEAR X" which means set X to zero.
By using DBNZ and CLEAR instructions implement NEGATE instruction
NEGATE can be used as "NEGATE X Y" which means set Y to negative of X ( Y = -X)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Assembly - 1of 3 votes
Answersdesign and implement a calculater that can calculate expressions like:
- srcnaks February 02, 2015 in -
+ 2 4
* 8 ( + 7 12)
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )
(PS:all items are space delimetered.)
Example answers
+ 2 4 => 2 + 4 = 6
* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Problem Solving Stacks String Manipulation Trees and Graphs - 2of 2 votes
Answersthere are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)
- srcnaks February 02, 2015 in -
Write two methods called "getNumber" and "requestNumber" as follows
Number getNumber();
boolean requestNumber(Number number);
getNumber method should find out a number that did not assigened than marks it as assiged and return that number.
requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.
design a data sturucture to keep those numbers and implement those methods| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Hash Table - 0of 0 votes
Answersdesign a video thumb up/down system at youtube scale. how to concurrent read/write, persistence, store, update....etc.
- rjrush January 30, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer System Design - 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 - 8of 8 votes
Answers1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
- Pointer January 27, 2015 in United States for Autocomplete
for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
the question is to find the max qaz.
it can be solved simply using 2 loops which takes time of O(n^2).
that's ok but how can we solve this problem in O(nlogn).
I have an approach and know the algorithm I got during the interview but it take a 40 of me to find it and write the code, but it was hard to think about it during the interview in that way.
I want to know if somebody can think and write the code in less than 20 minutes !!!| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersWrite a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).
- Anonymous January 27, 2015 in Israel
The stream ends with the special pair {0,0}.
The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights sum when stream has ended).
Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption.
Example: If this was the stream: {1,2},{2,2},{3,4},{4,10}, then id 2 would be returned with probability 1/9.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete":
- Anonymous January 27, 2015 in Israel
The method that receives a string representing a partial URL typed by the user and returns a vector of all possible completions of this partial URL (prefix).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a binary search tree and a positive integer K. Return the K-th element of the tree.
- Anonymous January 27, 2015 in Israel
No pre-processing or modifying of the tree is allowed.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 3of 3 votes
AnswersYou are given an array of distinct numbers. You need to return an index to a "local minimum" element, which is defined as an element that is smaller than both its adjacent elements. In the case of the array edges, the condition is reduced to one adjacent element.
- Anonymous January 27, 2015 in Israel
Reach a solution with better time complexity than the trivial solution of O(n).
If there are multiple "local minimums", returning any one of them is fine.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersYou are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.
- Anonymous January 27, 2015 in Israel
Examples:
9 --> 1 (9 = 3^2)
8 --> 2 (8 = 4^2 + 4^2)
15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2)
First reach a solution without any assumptions, then you can improve it using this mathematical lemma: For any positive integer N, there is at least one representation of N as 4 or less squares.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given a double linked list and an array of pointers to elements in this list (no assumptions can be made on the array - number of pointers, order and duplicates allowed).
- Anonymous January 27, 2015 in Israel
Return the number of sequences of elements (groups of consecutive elements), pointed by the array.
For example, if this is the array (number relates to index in the list, not the actual pointer value): 9,1,3,7,8,5,2.
Then output is 3, representing these sequences: [1,2,3], [5], [7,8,9]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 2 votes
Answers2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
- JY January 24, 2015 in -
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 13of 13 votes
AnswersA book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurences 'k' of certain digit 'd' in this string.
- autoboli January 16, 2015 in United States
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occure five times in that string.
Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersYou are given a String of number characters (S), like the following for example:
- SK January 15, 2015 in United States
"132493820173849029382910382"
Now, let's assume we tie letters to numbers in order such that:
A = "0"
B = "1"
C = "2"
...
M = "12"
N = "13"
...
Y = "24"
Z = "25"
Write an algorithm to determine how many strings of letters we can make with S, by converting from numbers to letters.| 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 - 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 - 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