## Google Interview Questions

- 0of 0 votes
`There are multiple rooms in a floor. There are one or more fire exits. Each door can be designed with an option of pull or push. For fire safety, a door should be designed so as to open (push) towards the fire exit. Design a data structure to represent the floor and door design. A person could start from any room and moves towards fire exit. Write an algorithm to check if all the doors are designed to be pushed towards fire exit.`

- 1of 1 vote
What is the maximum number of edges you could add to n vertexes to make a acyclic undirected graph?

Follow up:

What is the maximum number of edges you could add to n vertexes to make a acyclic directed graph?

- -1of 1 vote
Implement a vector-like data structure from scratch.

This question was to be done in C or C++.

Discussion topics:

1. Dealing with out of bounds accesses.

2. What happens when you need to increase the vector's size?

3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back

- 0of 0 votes
You have a sorted array containing the age of every person on Earth.

[0, 0, 0, 0, ..., 1, 1, ..., 28, 28, ..., 110, ...]

Find out how many people have each age.

- 0of 0 votes
Design a queue (FIFO) structure using only stacks (LIFO).

Code is not necessary.

Follow-up: provide a complexity analysis of push and remove operations.

- 2of 2 votes
Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.

Find the length of the shortest palindrome that you can create from S by applying the above transformation.

- -3of 3 votes
I think it's one system design question. Design one google's API, qps (query per second).

- 0of 0 votes
In gmail, while composing an email, upon adding a contact, related contacts are displayed. How would you implement that feature?

- Write an algorithm for that.

- What data structure would you use to store the weights?

- In what format would you persist this data?

- 1of 1 vote
We have words and there positions in a paragraph in sorted order. Write an algorithm to find the least distance for a given 3 words.

eg. for 3 words

job: 5, 9 , 17

in: 4, 13, 18

google: 8, 19, 21

...

...

Answer: 17, 18, 19

Can you extend it to "n" words?

Context: In Google search results, the search terms are highlighted in the short paragraph that shows up. We need to find the shortest sentence that has all the words if we have word positions as mentioned above.

- -3of 3 votes
There are N parking slots and N-1 cars. Everytime you can move one car. How to move these cars into one given order.

BTW: I got this question from internet but i could not figure it out partially because the description is kind of incomplete to me. Anyone knowing this question or the solution?

- 0of 0 votes
Given a BST and a number x, check whether exists two nodes in the BST whose sum equals to x. You can not use one extra array to serialize the BST and do a 2sum solver on it.

- -1of 3 votes
Given a map, each road has a value denoting how many hours it takes to travel from adjacent cities. Each city has its own holiday. If you arrive at the city during its holiday, you can get one gift. However, in each week, you can only travel one time. Now you are initially placed in one city at the beginning of this year, how do you plan your traveling to get the maximal gifts.

- 1of 1 vote
There are many tourist sites and each has their own holiday. If you arrive there during the holiday, you can gain one gift. It costs you many hours Wij traveling from site_i to site_j. What's more, you can only travel once in one week. Now you are initially placed in one site, how do you plan your routine in this year to gain most gifts.

- 1of 1 vote
Given a BST and a number x, find two nodes in the BST whose sum is equal to x. You can not use extra memory like converting BST into one array and then solve this like 2sum.

- 0of 0 votes
Given an arraylist of N integers,

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

- 0of 0 votes
You are given the toplogical information of a terrain in the following format - There are n points ( x_i , y_i ) and for each point (x_i , y_i ) the altitude h_i is given.

For any rectangle (axis parallel) defined by the x-y coordinates of

the corner points, we must answer the query about which is the highest altitude point lying within the rectangle.

Implement this using a range-query data-structure that answers such a

query in O( log^2 n) time

- 1of 1 vote
Write code to get maximum and second maximum element of a stack. The given function should be in O(1) complexity . Later extend for finding kth max in O(1).

- 0of 0 votes
You have a binary tree where each node knows the number of nodes in its sub-tree (including itself).

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

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

e.g., if the input is "p1 SE p2, p2 SE p3, p3 SE p1", output "impossible".

- 0of 0 votes
Given an array of integer, find the number of un-ordered pairs in that array, say given {1, 3, 2}, the answer is 1 because {3, 2} is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3, 2}, {3, 1}, {2, 1}.

Obviously, this can be solved by brute force with O(n^2) running time, or permute all possible pairs then eliminate those invalid pairs.

My question is does any body have any better solution and how would you do it because it seems like a dynamic programming problem. A snippet of code would be helpful

- 0of 0 votes
The third question is a brain teaser: if 1000 couples are to give birth to male and female babies(50% change each), and they would keep giving birth until they have a girl, what's the boy to girl ratio in 20 years

- 0of 0 votes
Given an array of object A, and an array of object B. All A's have

different sizes, and all B's have different sizes. Any object A is of the

same size as exactly one object B. We have a function f(A, B) to compare the

size of one A and one B. But we cannot compare between two A's or two B's.

Give an algorithm to match each A with each B.

- -2of 4 votes
2.

String encode(List<String> input);

List<String> decode(String input);

- -1of 3 votes
This is two questions I got from a google interview. Not very sure how to solve it. Any comments would be appreciated.

1.

interface RateLimit {

/** Sets the rate, from 1 to 1000000 queries per second */

void setQPS(int qps);

/** accept or reject a request, called when request is received */

boolean allowThisRequest();

}

brief example:

server instantiates your object, calls setQPS(1)

at at time t, user1 makes a request, allowThisRequest() returns true

at time t+0.01 sec, user2 makes a request, allowThisRequest() returns false

at at time t+1, user4 makes a request, allowThisRequest() returns true

at time t+5 sec, user3 makes a request, allowThisRequest() returns true

- 3of 3 votes
Question: Two players A and B are playing a game. Pots of gold, each with

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 ?

- -2of 2 votes
a left grow binary tree. Describe as below. (Transform from A to B)

A: B:

1 1

/ \ /

2 3 2 - 3

/ \ /

4 5 4 - 5

/ \ /

6 7 6 - 7

a left grow binary tree. Describe as below. (Transform from A to B)

A: B:

1 1

/ \ /

2 3 2 - 3

/ \ /

4 5 4 - 5

/ \ /

6 7 6 - 7

- 1of 1 vote
Use the shorest unique prefix to represent each word in the array

input: ["zebra", "dog", "duck",”dot”]

output: {zebra: z, dog: do, duck: du}

[zebra, dog, duck, dove]

{zebra:z, dog: dog, duck: du, dove: dov}

[bearcat, bear]

{bearcat: bearc, bear: ""}

- 2of 2 votes
Print combinations of strings from List of List of String

Example input: [[quick, slow], [brown, red], [fox, dog]]

Output:

quick brown fox

quick brown dog

quick red fox

quick red dog

slow brown fox

slow brown dog

slow red fox

slow red dog

- 3of 3 votes
Given a string (1-d array) , find if there is any sub-sequence that repeats itself.

Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated

2. abba <---- No, a and b follow different order

3. acbdaghfb <-------- yes there is a followed by b at two places

4. abcdacb <----- yes a followed by b twice

The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.

In the sense, it should be checked for every pair of characters in the string.

- 0of 2 votes
Write a program to implement Double Linked List from Stack with min. complexity.