## Google Interview Questions

- 0of 0 votes
Design an algo to decide if the GO game is over. i.e.

Given a boolean matrix, write a code to find if an island of 0's is completely surrounded by 1's.

- 0of 0 votes
The latest reality show has hit the TV: “Cat vs. Dog”. In this show, a bunch of cats and dogs compete for the very prestigious Best Pet Ever title. In each episode, the cats and dogs get to show themselves off, after which the viewers vote on which pets should stay and which should be forced to leave the show.

Each viewer gets to cast a vote on two things: one pet which should be kept on the show, and one pet which should be thrown out. Also, based on the universal fact that everyone is either a cat lover (i.e. a dog hater) or a dog lover (i.e. a cat hater), it has been decided that each vote must name exactly one cat and exactly one dog.

Ingenious as they are, the producers have decided to use an advancement procedure which guarantees that as many viewers as possible will continue watching the show: the pets that get to stay will be chosen so as to maximize the number of viewers who get both their opinions satisfied. Write a program to calculate this maximum number of viewers.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with three integers c, d, v (1 ≤ c, d ≤ 100 and 0 ≤ v ≤ 500): the number of cats, dogs, and voters.

v lines with two pet identifiers each. The first is the pet that this voter wants to keep, the second is the pet that this voter wants to throw out. A pet identifier starts with one of the characters ‘C’ or ‘D’, indicating whether the pet is a cat or dog, respectively. The remaining part of the identifier is an integer giving the number of the pet (between 1 and c for cats, and between 1 and d for dogs). So for instance, “D42” indicates dog number 42.

Output

Per testcase:

One line with the maximum possible number of satisfied voters for the show.

Sample Input 1

2

1 1 2

C1 D1

D1 C1

1 2 4

C1 D1

C1 D1

C1 D2

D2 C1

Sample Output 1

1

3

- 0of 0 votes
given a vector of integers, v[i] represent the stock price on day i. Now you may do at most K transactions. you must sell your stock before you buy it again and that means you can NOT have two stocks at the same time. write a program to find max profit you can get.

- 0of 0 votes
There is a code with a runtime error. We add printf to display the value of a variable and we don't get the runtime error anymore. explain what the reason can be.

- 1of 1 vote
Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

You can assume each number in the array is a positive integer and not greater than 100

Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.

- 4of 4 votes
Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

You can assume each number in the array is a positive integer and not greater than 100

Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.

- 1of 1 vote
Given n number of legacy services with user data<userid, info, date>

Design an API to return user data in a given date range, it should collect data from each service and merge and return the data sorted by date.

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

input: increasing sequence of pair of numbers

per1: (1,5) (10, 14) (19,20) (21,24) (27,30)

per2: (3,5) (12,15) (18, 21) (23, 24)

ouput: (6,9) (16,17) (22,22) (25,26)

- 3of 3 votes
Question was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1.

Examples:

1) Pattern : "abba", input: "redbluebluered" should return 1.

2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.

3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

I can think of a brute-force solution for this question where we add the character in the pattern and n length of the string to a hashmap and recurse over the pattern array and string. But is there anything more efficient? This was a pretty difficult question in my opinion.

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

- 5of 5 votes
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

- 1of 1 vote
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?

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

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