## Google Interview Questions

- 0of 0 votes
Give a binary tree, each node has an extra information, that is, how many children he has,

Find the kth node val in the inorder transversal ,

Followup how to insert a node, such that this newly added node become the Nth node of the inorder binary tree's traversal`class TreeNode{ int val; int NumberOfchildren; TreeNode left; TreeNode right; public TreeNode(int val){ this.val = val; } } public static int findKthOfInorder(TreeNode root, int k) {`

- 0of 0 votes
Give a weighted n-nary tree and find the longest path from the root node to the leaf node

class Node {

int id;

// connected node id, edge weight

Map <Integer, Integer> edges;

}

- 1of 1 vote
Google

1st round

Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.

Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,

then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,

Prob(ball3) = 70% ;

Follow-up:

Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.

- 0of 0 votes
Given a binary matrix, count the number of square that can be formed by all 0s

- 0of 0 votes
given a string p, called order, such as abc, means a in front of b, and so on

given a second string s, to determine whether it is follow the order of p, return boolean,

example If aaa return true,

If cba is false

If aaxyc is true, the letters that have not been seen in the order are skipped

- 2of 2 votes
Find whether string S is periodic.

Periodic indicates S = nP.

e.g.

S = "ababab", then n = 3, and P = "ab"

S = "xxxxxx", then n = 1, and P = "x"

S = "aabbaaabba", then n = 2, and P = "aabba"

follow up:

Given string S, find out the P (repetitive pattern) of S.

- 0of 0 votes
Given a string as a datastream Iterator<Character>, find the length of the longest substring without repeating characters

public String longestUniqueChars(Iterator<Character> chars)

- 0of 0 votes
Giving start string and end string, determine if start string can finally reach to the same as end string with below rules.

For example:

"R L _ _ L R L"

"_": the space is empty

"L": this can only swap with the empty letter _ on its left side

"R": this can only swap with the empty letter _ on its right side

So, "R L _ _ L R L" can change to "R L _ L _ R L" , and can continue change to (if you want) "R L L _ _ R L". from: 1point3acres.com/bbs

The question is given these rules and the start string and end string, could we change the start string to end string (unlimited # moves as long as it is valid).

For example:

"R _ _ L R _ R _L"

can be changed to

"_ R L _ _ R R L _"

- 1of 3 votes
Round3 Google

For N light bulbs , implement two methods

I. isOn(int i) - find if the ith bulb is on or off.

II. toggle(int i, int j) - i <= j. Switch state (switch on if it's off, turn off if it's on) of every bulb in range i to j.

All bulbs are off initially.

- 1of 3 votes
given a list of points in a rectangular coordinate system, seeking any two points, such that all the remaining points will be in only one side of the line.

- 0of 0 votes
Give a string, finds all duplicate substrings of length k

- -2of 2 votes
Give an array such as [1,2,2,2,0] every time you can jump 1 to a [i] step,

If you can jump to 0, return false

if you go out to return true

- 0of 0 votes
A group of people goes to eat together, each pay is not the same, then after they go home later, they each use mutual transfer so that everyone pay the same money.

input is an int array that each person pay, Ask who the amount of money was paid when the transfer was done, such as B -> A $ 3, C -> A $ 1.

- 2of 2 votes
/**

* Google

* Given a list of non-negative numbers and a target integer k,

* write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

**/

- 0of 0 votes
find the last index of the last duplicate number in a sorted array

ex

input: 1,2,5,6,6,7,9

output: 4(index)

- 0of 0 votes
Given a string, check if it is can be reorganized such that the same char is not next to each other, If possible, output a possible result

example

input: google

one possible output: gogole

- 0of 0 votes
Given a dictionary, generate the shortest string, both palindrome and pangram.

Each word can be used only once and unlimited words can be used.

- 1of 1 vote
Give you a pattern (digit in the pattern matches the corresponding

number of letters,

letter means match the letter itself),

a string to determine whether match:

ex:

abc -> 'abc' true

'1oc3' -> 'aoczzz', 'bocabc' true

- 2of 2 votes
Google

Given an array a[] and an integer k, a[i] means flower at position a[i] will blossom at day i. Find the first day that there are k slots between two blooming flowers.

- 1of 1 vote
Google

Given a string that represents time like "15:31", find the next time that is formed by the numbers in the string(a number can be used more than once). For "15:31", the answer should be "15:33".

- 0of 0 votes
assuming there is a freeway, n cars on the road, each car has a different integer speed, but are in the 1-n range. Now give you an array that represents the speed of each car. The starting order of the vehicle is the order of the array, ask the final formation of several clusters, the size of each cluster is how much? It can be understood that, although the vehicle speed is different, but even behind the car faster than the previous car, because you cannot pass, the last must only travel at the speed of the previous car, which formed a cluster. For example [2,4,1,3], finally [2,4] is a cluster, [1,3] is a cluster.

Follow up is now suppose you want to add a car, the speed of the car than other large, but not sure the car's starting order, so that the final output of each possible cluster (List of List). Requirements can be adjusted and call the previous function, but can only be called once

- 0of 0 votes
There is a stream of data <Symbol, timestamp, price>, and possibly also Correction Data <Symbol, timestamp, price> and then addData (symbol, timestamp, price) and correctData , Update minPrice, maxPrice, recentPrice in these two functions.

- 0of 0 votes
Give you a bunch of data <key, value, expiredTime>, design a data structure storage.

About the idea, based on Map solution.

class NewMap {

Map <Integer, Integer> data = new HashMap <> (); // store key-value pairs

Map <Integer, Integer> expired = new HashMap <> (); // store key-expired pairs

}

Then implement the three functions get (), put (), expire ().

- 0of 0 votes
how to implement the standard JSON.stringify and JSON.parse method

- 0of 0 votes
design a zigzag iterator, implement the prev() and hasPrev function

- 0of 0 votes
Fibonacci asked if you want to query 1-2 ^ 32 any one but the memory can only remember 2 ^ 20 number of how to do O (1) query

- 0of 0 votes
on a bench, sitting a number of people, and now come up a person, how to find a seat that is farthest from other people,

- 0of 0 votes
0 change to 01,1 change to 10.

Line 0 is 0, the first line is 01, the second line is 0110, the third line 01101001. . . Keep asking what is the vale at kth row and jth col

- 0of 0 votes
Assuming your budget is N, you need to buy a rectangular land. Give a matrix of land prices and ask what is the largest area available for buying land. Land prices must be non-negative. For example, the budget is 11.

`1 2 3 1 0 1 4 2 1 9 10 4 The output should be. 1 2 3 0 1 4`

Such a matrix, because 1 +2 +3 +0 +1 +4 = 11. And the largest area.

- 1of 1 vote
The grid is n by m. Each cell contains a unique number on it. Maga is at the left-top and wants to go to right-bottom. But there is a condition. Maga can go through only two way - right and down. And the path of your move is called the nodes you have passed through over them. The path is called the most beautiful if the following condition is satisfied: The sorted of the path has to be lexicographic smallest as possible as. Output the most beautiful path for given grid.

Input:

In the first line you are given two numbers: the dimensions of grid - n and m. The next n lines contains m numbers. Each number is unique.

Output:

Output the most beautiful path.`4 2 3 1`

Return 1 2 4

There are 2 ways to reach at (2,2) cell. The pathes are 4, 3, 1 or 4, 2, 1 respectively. So The most beautiful of them is 4, 2, 1 because if looking the sorted of them it looks like these : 1, 3, 4 and 1, 2, 4 respectively. So 1, 2, 4 is lexicographic smaller than the other. So the ans is 1 2 4.