## Google Interview Questions

- 0of 2 votes
Given 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].

**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 ?

- 1of 1 vote
Find popular item in sorted array of natural numbers.

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.

- 4of 4 votes
You 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.

Example:

input: a = [-1 2 100 100 101 3 4 5 -7]

output: b = [-1 2 3 4 5]

- 1of 1 vote
Consider 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.

What is the minimum number of bits required to send the sequence?

Hint: It is not 6 x 52

- 0of 0 votes
On 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?

- 0of 0 votes
How would you get all of the unique IDs out of a single file? What if it was a very large file?

- 0of 0 votes
Write a function that takes an array of numbers and returns the maximum and minimum values.

Give BigO for runtime.

(This is a basic coding question. There are no real tricks or shortcuts.)

- 0of 0 votes
Write 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.

For example, 1729 is one such number because 1729 = 1^3 + 12^3 = 9^3 + 10^3.

- 0of 0 votes
Write 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:

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

- 0of 0 votes
From a list of integer intervals, write a function to minimize the number of overlapping or consecutive ones.

Test Input: [4, 8], [3, 5], [-1 2], [10, 12]

Test ouput: [-1, 8], [10,12]

- 0of 0 votes
Suppose 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.

- 0of 0 votes
You given and instruction called DBNZ ( Decrement and Branch if Not Zero)

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)

- 3of 3 votes
write an algorithm to find sum of numbers which are smaller than N and divisible by 3 or 5

Example:

N = 9 => 3 + 5 + 6 = 14

N = 10 => 3 + 5 + 6 + 9 = 23

- 0of 0 votes
design and implement a calculater that can calculate expressions like:

+ 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

- 1of 1 vote
there are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)

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

- 0of 0 votes
design a video thumb up/down system at youtube scale. how to concurrent read/write, persistence, store, update....etc.

- 0of 0 votes
Warm-up question: Write a function that prints all ASCII characters. You are not allowed to use for/while loop.

- 3of 3 votes
1. 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.

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 !!!

- 1of 1 vote
Write a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).

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.

- 1of 1 vote
Write a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete":

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).

- 1of 1 vote
You are given a binary search tree and a positive integer K. Return the K-th element of the tree.

No pre-processing or modifying of the tree is allowed.

- 1of 1 vote
You 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.

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.

- 0of 0 votes
You are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.

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.

- 0of 0 votes
You 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).

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]

- 1of 1 vote
2D matrix with 0s and 1s. Try to find out how many countries in this matrix?

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

- 6of 6 votes
A 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.

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

- 2of 2 votes
You are given a String of number characters (S), like the following for example:

"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.

- 0of 0 votes
you have experience with a 3x3 Sudoku.Think about 2*2 sudoku:

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.

- 4of 4 votes
You 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.

- 0of 0 votes
Given two binary trees, A and B,

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