## Google Interview Questions

- 0of 0 votes
Given a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.

Example:`Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5`

Edit: Thanks, wangchenClark0512, forgot about C to D

Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.

Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles

- 3of 3 votes
You are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.

Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)

Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.

Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)

The total run-time after returning everything should be O(n).

Examples:`Input: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45`

- 0of 0 votes
Given a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's

Example:

findStrings(3) returns 19

since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb

and the invalid combinations are:

abb,bab,bba,bbb,bbc,bcb,cbb,ccc

- -1of 1 vote
You have a bunch of light bulbs. Store them as you wish. Implement a function that tells you if the light is on or off given its index and another one that toggles the state of the light bulbs given a start and end index.

- 1of 1 vote
There are n+1 loading docks. a permutation of boxes 1->n is placed on the first n. there is a fork that can move one box to an empty location at a time. Give an algorithm to sort then boxes with minimum number of moves.

Follow up: minimum distance

- 1of 1 vote
Given a Pattern and a dictionary, print out all the strings that match the pattern.

where a character in the pattern is mapped uniquely to a character in the dictionary ( this is what i was given first).

e.g 1. ("abc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "cdf"

2. ("acc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "too", "paa"

- -1of 3 votes
I have been shortlisted through Google APAC for interview at google. My job profile is Trust and Safety Engineer. Which subjects should I concentrate more? What would be level of questions for Algorithmic questions

- -2of 2 votes
Follow-up to above question:

Can you augment a BST to return the number of elements with node values in a given range?

If not, what other data structure would work?

- 0of 0 votes
Write a function that takes as input an array of integers A, and two integers low and high.

Your function has to output pairs of indices: {(i,j), ...}

Where each pair of indices denotes that the subarray of A[i...j] has a sum in the range low <= sum <= high.

Apparently there are algorithms better than O(N^2).

- 0of 2 votes
You are currently in practice mode. This is a demo only.

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.

A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 8 elements:

A[0] = -1

A[1] = 3

A[2] = -4

A[3] = 5

A[4] = 1

A[5] = -6

A[6] = 2

A[7] = 1

P = 1 is an equilibrium index of this array, because:

A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]

P = 3 is an equilibrium index of this array, because:

A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]

P = 7 is also an equilibrium index, because:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0

and there are no elements with indices greater than 7.

P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

Write a function:

int solution(int A[], int N);

that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

Assume that:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

- 0of 0 votes
Problem : Christmas Tree

Chirag is a boy. And his one and only dream is to meet Santa Claus. He decided to decorate a Christmas tree for Santa on coming Christmas. Chirag made an interesting Christmas tree that grows day by day.

The Christmas tree is comprised of the following

Parts

Stand

Each Part is further comprised of Branches. Branches are comprised of Leaves.

How the tree appears as a function of days should be understood. Basis that print the tree as it appears on the given day. Below are the rules that govern how the tree appears on a given day. Write a program to generate such a Christmas tree whose input is number of days.

Rules:

If tree is one day old you cannot grow. Print a message "You cannot generate christmas tree"

Tree will die after 20 days; it should give a message "Tree is no more"

Tree will have one part less than the number of days.

E.g.

On 2nd day tree will have 1 part and one stand.

On 3rd day tree will have 2 parts and one stand

On 4th day tree will have 3 parts and one stand and so on.

Top-most part will be the widest and bottom-most part will be the narrowest.

Difference in number of branches between top-most and second from top will be 2

Difference in number of branches between second from top and bottom-most part will be 1

Below is an illustration of how the tree looks like on 4th day

https://s31.postimg.org/5s1txk4zf/christmas_tree.jpg

https://s32.postimg.org/i2c6i850l/christmas_tree_2.jpg

- 0of 0 votes
Given two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.

- 0of 0 votes
Given a dictionary and a string, find all the substrings that are valid words in dictionary.

I was thinking of a Trie solution but I'm not sure a Trie will work easily to match sub words that begin in the middle of the string.

- 1of 1 vote
Given a string return the longest palindrome that can be constructed by removing or shuffling characters.

Example:

'aha' -> 'aha'

'ttaatta' -> ' ttaaatt'

'abc' -> 'a' or 'b' or 'c'

'gggaaa' -> 'gaaag' or 'aggga'

Note if there are multiple correct answers you only need to return 1 palindrome.

- 0of 0 votes
A matrix is "Toepliz" if each descending diagonal from left to right is constant. Given an M x N matrix write the method isToepliz to determine if a matrix is Toepliz.

Example:

Input:

67892

46789

14678

01467

Output:

True

- 0of 0 votes
Find the index when slow and fast pointer meet in terms of n (length of list before cycle) and p ( length of loop in linked list).

Let me meeting index is q then we should be able to find value of q when we pass n& p , there shouldn't be any extra variable.

- 0of 0 votes
I was asked in an interview: You are given a dump file of IPv4 addresses. You are to find 4 most common occurring subnets. Lets say an IP address if of type a.b.c.d you have to find most common occurring four subnets of the form,

a.*.*.*

a.b.*.*

a.b.c.*

a.b.c.d

Here * matches anything.

My first solution was build an in memory hashtable. Given an IP address a.b.c.d split it as ["a","b","c","d"] and add "a", "a.b", "a.b.c", "a.b.c.d" to the hash table and count it. [There are optimizations possible like considering the entire IP address as a 32 bit unsigned integer and count it with masks and shifts]

Then the question got extended: "assume you can never hold everything in memory, how would you solve it?" Now, the very first solution that I could say was to do an external sort and then count it.

The next solution I gave was to split the IP addresses into buckets. The algorithm was,`while there is an IP IP <- an IP address a <- first quadruple push IP to bucket[a]`

The bucket which has maximum elements would give me the a.*.*.* solution. Now take each bucket and do the same. Even though this might give the correct result, in worst case I might end up having 255^4 buckets.

This is indeed an open ended question with more than one correct answer. What would be the best way to solve this?

- 1of 1 vote
GIven a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word doesn't fit in the same line, it should move to the next line. Find an efficient solution for this. For eg.

List of words: { "Do", "Run" }

Number of columns: 9

Number of rows: 2

First row: "Do Run Do" (7 letters + 2 spaces fit into 9 columns)

Second row: "Run Do" (Only 2 words fit into 9 columns)

- 0of 0 votes
Write a program for skyyscrapper?

http://www.conceptispuzzles.com/index.aspx?uri=puzzle/skyscrapers/techniques

- 0of 0 votes
List of string that represent class names in CamelCaseNotation.

Write a function that given a List and a pattern returns the matching elements.

['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo']

H -> [HelloMars, HelloWorld, HelloWorldMars, HiHo]

HW -> [HelloWorld, HelloWorldMars]

Ho -> []

HeWorM -> [HelloWorldMars]

- 0of 0 votes
You have rating (0-10) of the hotels per user in this format:

scores = [

{'hotel_id': 1001, 'user_id': 501, 'score': 7},

{'hotel_id': 1001, 'user_id': 502, 'score': 7},

{'hotel_id': 1001, 'user_id': 503, 'score': 7},

{'hotel_id': 2001, 'user_id': 504, 'score': 10},

{'hotel_id': 3001, 'user_id': 505, 'score': 5},

{'hotel_id': 2001, 'user_id': 506, 'score': 5}

]

Any given hotel might have more than one score.

Implement a function, get_hotels(scores, min_avg_score) that returns a list of hotel ids that have average score equal to or higher than min_avg_score.

get_hotels(scores, 5) -> [1001, 2001, 3001]

get_hotels(scores, 7) -> [1001, 2001]

*/

How to solve this in C++ and Python?

- 5of 5 votes
You are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.

Find number of 0-s in the given matrix.

Example:`0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4`

Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).

Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).

Nice job, @gen-y-s :)

- -7of 7 votes
Given set of characters and a dictionary find the minimum length word that contains all the word from the given word

- 1of 1 vote
Given an array of n integers. MaxPrefix is defined as count of elements those are greater than the element and in the right side of array wrt to the element. Write a program to give the max of MaxPrefix Ex. Input 10 -4 6 2 8 9 4 Output is 5

- 1of 1 vote
Write a class to take in a large arbitrary number, also provide a function to increment the number. The number will be passed on as an array of integers.

- 2of 2 votes
Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).

Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.

Note: all coordinates are real numbers

(a,b)

|----------------------------------------------|

|.......................................................|end

|.......................................................|

|start................................................|

|.......................................................|

|----------------------------------------------|(c,d)

Edit: You have to avoid sensors.

Also u can move in any direction any time.

- 0of 0 votes
Let "t" be a good number if "t" can be written as sum of 2 cubes in at least 2 distinct ways. Given n, write a method which prints all good numbers up to and including n.

- 0of 2 votes
A robot on a plane has 2 types of commands:

1. move forward by X units (X is integer 0 <= X <= 10000 )

2. rotate by X degrees (X is integer in range [-180, 180] )

A robot looks like`def robot(commands): while True: for command in commands: execute(command)`

Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.

Example:`[move(10), rotate(180), move(10)] -> answer is yes [move(10), rotate(45), move(10), rotate(-45), move(10), rotate(45)] - answer is no`

- 3of 3 votes
# take an array and print non over lapping in order pairs. example:

`# [1,2,3,4] => input # output below is in order combination # (1234) # (1)(234) # (1)(23)(4) # (1)(2)(34) # (12)(34) # (12)(3)(4) # (123)(4) # (1)(2)(3)(4)`

- 2of 2 votes
You are given a range [first, last], initially white. You need to paint it black.

For this purpose you have a set of triples

[(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).

Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible

Example:`[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]`

Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.

Another example:`[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]`

answer is -1, because it's impossible to color whole range.