## Google Interview Questions

- 1of 1 vote
Given a string "2-4a0r7-4k", there are two dashes which we can split into 3 groups of length 1, 5, 2.

If we want each group to be length 4, then we get "24A0-R74k"

Given a String A and an int K, return a correctly formatted string.

IF A is "2-4A0r7-4k" and B is 4, string is "24A0-R74K"

IF K is 3, string is "24-A0R-74K" as the first grp could be shorter.

- 0of 0 votes
Given an n-ary tree, find the longest sequence in it. The sequence doesn't end to start at the root. It can go from leaf to leaf.

- 0of 0 votes
Given an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x axis, every square on their y axis, and every square that lies in their diagonal (think of a Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…

- 0of 0 votes
Find the shortest path between a start node and end node in a undirected +ve weighted graph.

You are allowed to add at max one edge between any two nodes which are not directly connected to each other.

ex:

From | To | Weight

1 2 2

1 4 4

2 3 1

3 4 3

4 5 1

start node = 1, end node = 5.

extra edge weight = 2.`1----(2)----2 | | | | (4) (1) | | | | 5-(1)-4----(3)----3 In this case answer would be 3 (from 1 - > 5 - > 4) Solution: 1----(2)----2 /| | / | | (2)/ (4) (1) / | | / | | 5-(1)-4----(3)----3`

- 0of 0 votes
Given an un-directed weighted graph G(V,E), find the minimum weight between two given nodes X & Y

(i.e. sum of weights of edges between X & Y).

You can add an extra egde with weight W between any two nodes in the graph exactly one time (if required).

- 1of 1 vote
Let's say I have a word "I love chicken", I can break the number of characters in each word, like so: [1] [4] [7]

[1,4] [4,7], [1,4,7].

Now let's say I have a max = 5. The phrases with equal or fever than 5 characters are "[I], [love], and [I, love]. The longest phrase is [I,love], which contains 2 words.

Complete the Length function given. It has 2 parameters:

1) An array of integers, named array

2) A maximum number, named max.

int Careercup( int [] array, int max) {

}

Example test case 1:

[3,1,2,3]

4

Output expected : 2

- 1of 1 vote
Find the largest and smallest number in a list. The list is stored as two sections, one in ascending order and the other in descending order.

input [ 2 3 4 5 6 7 10 9 8 7]

smallest : 2

Largest 10

- 2of 2 votes
Given an Array A with n elements. Pick maximum number of elements from given array following the rule:

1. We cannot pick A[i] and A[j] if absolute value of (A[i] - A[j]) > absolute value of (i - j)

Example: {13,5,4}

Ans: 2

Pick 5 and 4.

- 0of 0 votes
Implement method:

`Lìst<Range> getRanges(Lìst<Shard> shards, Lìst<Key> keys)`

That returns list of ranges. Each range represents multiple keys aggregated over a shard:

n-keys —> 1-shard —> l-range

Method should return no more than 1 range per shard that spans all keys or their parts belonging to this shard.

Each of the ‘Range` , 'Shard’ and ‘Key’ classes have ‘end’ and ‘start’ fields of int type, where ‘start’ is inclusive and ‘end’ is exclusive.

Example:`1—9, 12—59, 100—999 <— shards (input) 2—3, 6—8, 11—20, 200—220 <— keys (input) 2—8, 12—20, 200—220 <— ranges (output)`

- 0of 0 votes
http://www.geeksforgeeks.org/find-water-in-a-glass/

- 3of 3 votes
Find the minimum of every sub-array of size k in an array of size n.

O(n) solution required.

- 0of 0 votes
http://www.geeksforgeeks.org/find-water-in-a-glass/

- 2of 2 votes
Find the minimum of every sub-array of size k in an array of size n.

O(n) solution required.

- 0of 0 votes
Searching for a string in a DOM tree. A complete working solution was required. Assume you have any string matching algorithm available.

(Based on Ctrl+F search in chrome)

- 0of 0 votes
Searching for a string in a DOM tree. A complete working solution was required. Assume you have any string matching algorithm available.

(Based on Ctrl+F search in chrome)

- 1of 1 vote
Given a directed graph G, duplicate the graph using minimum space.

- -1of 1 vote
Follow up on complexity

- 2of 2 votes
Given two integer arrays list1 and list2 and an int target value. WAP to check if there exists such a sum, where one number taken from list1 and other from list2 to add up to become the target value. Return true if so, else return false.

- 1of 1 vote
Given a sparse matrix, implement below two methods:

void set(int row, int col, int val) /*Update value at given row and col*/

int sum(int row, int col) /*give sum from top left corner to given row, col sub-matrix*/

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

- 4of 4 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`

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

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

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

- -6of 8 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 4 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?

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

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