## Google Interview Questions

- 0of 0 votes
Check if two integers are equal without using any comparison operators.

- 0of 0 votes
Find how many numbers of length n are there such that each number is at least 4 smaller/greater than the number before and after it.

Eg: if n = 5, such numbers are 39518, 15951, etc.

- 0of 0 votes
You should transform an structure of multiple tree from machine A to machine B. It is a serialization and deserialization problem, but i failed to solve it well.

You could assume the struct is like this:`struct Node{ string val; vector<Node*> sons; }`

and in machine A, you will given the point to root Node, and in machine B,you should return a pointer to root Node.

- 0of 0 votes
how would you design a microwave for the blind?

- 0of 0 votes
How would you increase Youtube revenue?

- 0of 0 votes
How much is Youtube Revenue

- 0of 0 votes
Write a program in that determines the members and parents of nested groups without using recursion.

These are the requirements.

1. A group can have 0 or more members.

2. A group can be member of one or more groups

3. A group can be member of itself.

4. If there is a path from a group either directly or through multiple hops, then that user is considered as member of the group.

5. A group can have users or groups as members

EX: Input looks like this`var groupMembers = new Dictionary<string, HashSet<string>> { { "G4", new HashSet<string> { "U1","G1"} }, { "G1", new HashSet<string> { "G2","G3","G6"} }, { "G3", new HashSet<string> { "G3","G5"} }, { "G2", new HashSet<string> { "G4","U2"} }, { "G5", new HashSet<string> { "U2","G6"} }, { "G6", new HashSet<string> { "U3"} }, };`

Signature of function is:

`private List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)`

You need to make sure that you take care of cycles in the graph and not go into infinite recursion.

Output should look like a list of groups where a group is as follows.`private class MyGroup { public string Identity { get; set; } public Dictionary<string, MyGroup> MemberOf { get; set; } public Dictionary<string, MyGroup> Members { get; set; } public HashSet<string> Users { get; set; } public MyGroup(string name) { this.Identity = name; this.MemberOf = new Dictionary<string, MyGroup>(); this.Members = new Dictionary<string, MyGroup>(); this.Users = new HashSet<string>(); } }`

Each group object should contain all the groups it's a memberOf (directly or indirectly), all the groups that are it's members (directly or indirectly) and all users that are it's members.

- 0of 0 votes
Given a string representing relative path write a function which normalizes this path (i.e. replaces "..").

Example:

input: \a\b\..\foo.txt

output: \a\foo.txt

- 0of 0 votes
You are given an array representing integer. Write a function which increments this integer.

Example: input [1,2,3] (represents 123) -> output [1,2,4]

- 1of 1 vote
Given an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).

- 1of 1 vote
Find a duplicates in an array of length n. The values are positive integers in the range between 1 .. n-1

- 0of 0 votes
You have an array of integers. Each integer in the array should be listed three times in the array. Find the integer which does not comply to that rule.

- 1of 1 vote
Count triangles in an undirected graph where a triangle is a unique set of three vertices connected to one another.

- 0of 0 votes
In 5 minutes write a code which checks if a given number is a power of two.

- 0of 0 votes
Check if two given words are anagrams of each other.

- 1of 1 vote
Given two sorted arrays find the element which would be N-th in their merged and sorted combination.

- 1of 1 vote
Given a BST with unique values find in a given tree a value closest to a given value X.

- 0of 0 votes
How would you store the relations in a social network like Facebook and implement a feature where one user receives notifications when their friends like the same things as they do?

- 0of 0 votes
Design the front end of Google Calendar

- 0of 0 votes
Design YouTube view-counting feature

- 0of 0 votes
Design Google Suggest

- 0of 0 votes
Design Gmail backend (data storage and API)

- 5of 7 votes
The "surpasser" of an element in an array is defined as the number of elements that are to the "right" and bigger than itself.

Example:

Array:

[2, 7, 5, 5, 2, 7, 0, 8, 1]

The "surpassers" are

[5, 1, 2, 2, 2, 1, 2, 0, 0]

Question: Find the maximum surpasser of the array.

In this example, maximum surpasser = 5

- 2of 2 votes
Find the longest common prefix in a list of phrases. For instance; "i love all dogs", "i love cats" should return "i love".

- 2of 2 votes
Given a binary tree, implement an iterator that will iterate through its elements.

- 7of 7 votes
You are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows:

If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'.

You are not allowed to use any conditional operator (including ternary operator).

Follow up: Solve the problem without utilizing arithmetic operators '+ - * /'.

- 0of 2 votes
Given a List of Strings, return the number of sets of anagrams.

For instance, given:

<abc,cab,dac,beed,deb,few,acd>

return 5

- 1of 1 vote
Design a cache module for an image server. The server accepts image requests from users and sends them back the images. The cache should always hold in-memory the 10 most recently requested images. The cache should also support multiple requests simultaneously

- 2of 2 votes
Design an application which sends the user the 10 closest hotels based on his geo location.

When i asked roughly how many hotels in total are we talking about, i was asked to estimate how many hotels are there in the world...

- 4of 4 votes
You are given 2 documents. We want to know how similar they are through N-Grams.

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.