## Google Interview Questions

- 0of 0 votes
You are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0.

A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise)

Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)

e.g.

2 1 1 2 -> crosses

1 2 3 4 -> doesn't cross

- 0of 0 votes
Integer Array Ques:

Given an integer array of variable length like so [9, 8, 8, 3] where each item in array could be 0 to 9, write a function that would take would interpret the array [9, 8, 8, 3] as a number 9883 and increment it by 1. The return of the function would be an integer array containing the addition like so [9,8,8,4]. No zeros in the first position like [0,1,2,3]. I initially suggested a possible solution of process to convert the integer array to String then convert to Integer or Long and then do the addition of 1 and then convert it back to integer array. That is not allowed when the interviewer change the ques. to not allow that.

- 0of 0 votes
Given unsigned integer 'x', write an algorithm thet returns unsigned integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance |x-y| is minimized.

Example:

x: 01

y: 10

Note that one bit is set and 'x' is not equal 'y'. You may assume that x is positive integer between zero and 2^32-2;

- 0of 0 votes
Write function to determine if given unsigned 32-bit number is a power of 3

`int is_power_of_3(uint32_t n)`

return 1 if yes, 0 otherwise.

e.g.`is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0`

Expected the answer not to be straightforward loop, but something faster.

- 0of 0 votes
There is a graph which has 1 source and 1 sink(destination node)

In between those 2 nodes there are n levels of nodes. At each level there are exactly m nodes.

Every node of level i is connected to every node of level i+1 (All edges go in forward direction)

Find total no. of paths between source and sink.

This was basic question. Then he tweaked it by adding few more edges.

Now there were some additional edges. Now sdges can go from any lower level to any higher level. That is not just from i to i+1..

can be from i to i+2 or i +3 so on...

(such bouncing edges were added only in the n levels not from or to (to src or sink)

Now find number of paths?

- 2of 2 votes
Suppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.

The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.

- 0of 0 votes
Given an array consisting of N Numbers.

Divide it into two Equal(it is important) partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum.

If number of elements are odd difference in partition size can be at most 1.

- -1of 1 vote
The question inside the link.

The pictures below contain a message in a secret code.

You will need to program to decode this message and to discover the password.

http://tsofen2015ms.azurewebsites.net/

- 1of 1 vote
Write all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5] in at least O(n^2) complexity

- 0of 0 votes
Design a data structure which should have following operation. Insert, Delete, Random access

- 0of 0 votes
Given 2 large number A and B, create a new number C using the digits from A which needs to be grater than B.

e.g. A = 5281, B = 7443

C = 8125.

- 5of 5 votes
Given a binary N X N matrix, return the size of the largest '+' of ones.

input:

0 0 0 0

1 1 0 1

1 1 1 1

1 1 1 0

output:

5

(binary search is not allowed)

- 0of 0 votes
List of 2D points: (x1, y1), (x2, y2) … (xN, yN) - N 2D points.

Each two points define a 2D line.

create an algorithm which returns a list of all unique 2D lines, which you can build using pairs of points from the list.

- 0of 0 votes
Given n light bulbs, write two methods.

isOn(i) to determine if a light bulb is on

toggle(start, end) to toggle all the light bulbs in the range

One caveat, write toggle so that it is less than O(n) complexity

- 0of 0 votes
Write a function called deepCopy that takes an object and creates a deep copy of it.

var newObj = deepCopy(obj);

(can't use JSON, can't use prototype)

- 3of 3 votes
I came across this problem online.

> Given an integer:N and an array int arr[], you have to add some

> elements to the array so that you can generate from 1 to N by using

> (add) the elements in the array.

Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers.

For example:

N=6, arr = [1, 3]

1 is already in arr.

add 2 to the arr.

3 is already in arr

4 = 1 + 3

5 = 2 + 3

6 = 1 + 2 + 3

So we return 1 since we only need to add one element which is 2.

Can anyone give some hints?

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

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

- 1of 1 vote
how would you design a microwave for the blind?

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

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

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