Google Interview Questions
- 2of 2 votes
AnswerGoogle
- aonecoding January 20, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a binary matrix, count the number of square that can be formed by all 0s
- ajay.raj January 20, 2018 in United States| Report Duplicate | Flag | PURGE
Google Data Engineer - 0of 0 votes
Answersgiven a string p, called order, such as abc, means a in front of b, and so on
- ajay.raj January 20, 2018 in United States
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| Report Duplicate | Flag | PURGE
Google Data Engineer - 3of 3 votes
AnswersFind whether string S is periodic.
- aonecoding January 20, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a string as a datastream Iterator<Character>, find the length of the longest substring without repeating characters
- ajay.raj January 18, 2018 in United States
public String longestUniqueChars(Iterator<Character> chars)| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswerGiving start string and end string, determine if start string can finally reach to the same as end string with below rules.
- ajay.raj January 18, 2018 in United States
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 _"| Report Duplicate | Flag | PURGE
Google Java Developer - 2of 4 votes
AnswersRound3 Google
- aonecoding January 16, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 3 votes
Answersgiven 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.
- ajay.raj January 15, 2018 in United States| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswersGive a string, finds all duplicate substrings of length k
- ajay.raj January 13, 2018 in United States| Report Duplicate | Flag | PURGE
Google Backend Developer - -3of 3 votes
AnswerGive an array such as [1,2,2,2,0] every time you can jump 1 to a [i] step,
- ajay.raj January 13, 2018 in United States
If you can jump to 0, return false
if you go out to return true| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswerA 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.
- ajay.raj January 13, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Backend Developer - 3of 3 votes
Answers/**
- aonecoding January 13, 2018 in United States
* 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.
**/| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answersfind the last index of the last duplicate number in a sorted array
- ajay.raj January 11, 2018 in United States
ex
input: 1,2,5,6,6,7,9
output: 4(index)| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswersGiven 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
- ajay.raj January 11, 2018 in United States
example
input: google
one possible output: gogole| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswerGiven a dictionary, generate the shortest string, both palindrome and pangram.
- ajay.raj January 05, 2018 in United States
Each word can be used only once and unlimited words can be used.| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGive you a pattern (digit in the pattern matches the corresponding
- ajay.raj January 05, 2018 in United States
number of letters,
letter means match the letter itself),
a string to determine whether match:
ex:
abc -> 'abc' true
'1oc3' -> 'aoczzz', 'bocabc' true| Report Duplicate | Flag | PURGE
Google SDE1 - 3of 3 votes
AnswersGoogle
- aonecoding January 05, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answersassuming 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.
- ajay.raj January 04, 2018 in United States
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| Report Duplicate | Flag | PURGE
Google SDE1 - -1of 1 vote
AnswersThere 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.
- ajay.raj January 04, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswerGive you a bunch of data <key, value, expiredTime>, design a data structure storage.
- ajay.raj January 04, 2018 in United States
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 ().| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answershow to implement the standard JSON.stringify and JSON.parse method
- ajay.raj January 01, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerdesign a zigzag iterator, implement the prev() and hasPrev function
- shuibizai10 December 26, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Java - 0of 0 votes
AnswersFibonacci 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
- ajay.raj December 22, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerson a bench, sitting a number of people, and now come up a person, how to find a seat that is farthest from other people,
- ajay.raj December 22, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answers0 change to 01,1 change to 10.
- ajay.raj December 22, 2017 in United States
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| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersAssuming 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.
- ajay.raj December 22, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersThe 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
- ajay.raj December 22, 2017 in United States
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.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersTwo binary tree, to determine whether the two trees "similar", similar refers to the corresponding node in each tree in the left child and right child can be the same or in the opposite order, such as the following two trees, D, E where DE And DE can also be DE and ED, BC is the same, but the parent child relationship must be the same.
Followup is if left and right can be the same how to do,
- ajay.raj December 21, 2017 in United StatesA / \ B C / \ D E A / \ C B / \ D E
| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
Answersgiven n player competition, a bool canbeat (int a, int b) can return a whether beat b. Asked to return a sequence, the sequence only requires two adjacent to the front beat behind. Example, 1 beat 2, 2 beat 3, 3 beat 4, 3 beat 1, 4 beat 1 You can return "1234", that is, although 3,4 can beat 1, but not adjacent does not matter
- ajay.raj December 19, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGive a two-dimensional array, which represents the value of the jump to the four directions, asked whether from the upper left corner to the lower right corner, follow up the shortest distance
- ajay.raj December 19, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1