Google Interview Questions
- 1of 1 vote
AnswersGiven a function randBetween (double d1, double d2), return a random double between d1 and d2,
- ajay.raj December 06, 2017 in United States
returns a random point in a rectangle.
Give a bunch of rectangles, using randBetween to print a random point in the rectangle
follow up: What to do if you call this func many times| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersThe two arrays [1,2,3,4,5], [2,3,4,5,6] find the first subfix and the second prefix the same longest case, such as the example is [2, 3,4,5]
- ajay.raj December 06, 2017 in United States
Length of 4.
Followup: how to do two-dimensional array, how to optimize.| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGiven Two string, ask whether they can become the same after just one swap of two chars in one string.
- ajay.raj December 06, 2017 in United States
For example:
"abcd", "bacd" Yes, you can swap ab in the first string to make it the same as the second string
"abcd", "adbc" can not
Follow-up, given Two string, ask whether they can become the same after N swaps of two chars in one string g, assuming that the swap does not overlap.
(str [0] <-> str [2] str [2] and str [0] will not be swapped with other locations)| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersAn art museum has the shape of a square and it contains N*N rooms. Some of the rooms are open and they contain art, other rooms are locked. There are guards in some of the open rooms. The museum's administration is afraid of a break in and they would like to evaluate how well the guards are positioned in the open rooms inside the museum. Precisely, they wish to know for each open room what is the distance to the colest guard. This distance is the min number of rooms a guard needs to pass through to reach that room. The guards can only move through the open rooms North, South, East and West and they can't leave the museum.
- ajay.raj December 05, 2017 in United States
'.' is for open room 'G' is for open room where a guard is '#' is for a locked room Noboday can enter or pass through thesse rooms.| Report Duplicate | Flag | PURGE
Google SDE-3 - 0of 0 votes
AnswersThere is a ball on the nth stairs, and it wants to get to the ground(level 0). There are some sticky stairs, and once the ball lands on the sticky stair, it is stuck and can never move.
- ajay.raj December 05, 2017 in United States
During odd turns, you can jump down 1, 2, or 4 stairs. During even turns, you can jump down 1, 3, 4 stairs.
Return the number of ways you can get to ground.| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswerYou are in the upper left corner, sitting in a boat, you want to reach to the lower right corner, but the matrix has a certain height at each location (i, j), and the boat can only go through the cell with water in it, looking for the earliest time that the boat can reach from the upper left corner coordinates (0,0) to the lower right coordinates (n-1, n-1). Each day, water goes up by one height unit
- ajay.raj December 03, 2017 in United States| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswerChoose a random point from one single rectangle.
- ajay.raj December 03, 2017 in United States
Choose a random point from multiple rectangles, if there isno overlapping among them.
Choose a random point from multiple rectangles, if there isoverlapping among them.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswerGiven a string of size n consisting of 0s and/or 1s.you have to perform k queries and there are two types of queries possible.
- vejon December 02, 2017 in United States
"1"(without quotes): Print length of the longest substring with all '1'.
"2 X"(without quotes): where X is an Integer between 1 to n.In this query, you will change character at Xth position to '1' (it is possible that the character at ith position was already '1')
Input Format:
First Line of input contains n and k, where n is string length and k is the number of queries.
Next line contains a string of 0's and/or 1's of length n.
Each of next k lines contains query of any one type (i.e 1 or 2).
Output Format: For each query of type 1, print in new line the maximum size of subarray with all 1's.
Example Input:
5 7
00000
1
2 3
1
2 5
1
2 4
1
Example Output:
0
1
1
3| Report Duplicate | Flag | PURGE
Google Software Developer - 0of 0 votes
Answersgiven a html file, compare if two html file show the same contents.
- ajay.raj December 02, 2017 in United States
Eg.
<html> <body> <p> H <i> ello </ i> </ p> <body> </ html> is typed as "Hello \ n" without regard to <i> , "\ n" because of <p>
follow up: what if the string is very long| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
Answersgiven a binary matrix of 01s, each time you click a point (i, j), the bit of the same row and column are all flipped.
- ajay.raj December 02, 2017 in United States
check if a matrix can be all 0s after many of this operation.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerdesign a sweeping robot, there are three functions:
- ajay.raj December 02, 2017 in United States
move (), which returns boolean value
turn_left (k), which make robot turns left k times.
turn_right (k), which make robot turns right k times.
Design an algorithm to make robot clean up all room. Timecomplexity, linear in term of room space.| Report Duplicate | Flag | PURGE
Google SDE1 - -1of 1 vote
AnswersGiven a graph, each node may have one or more children, updating the value of a child node is not less than the parent node.
- ajay.raj December 02, 2017 in United States
follow-up each child node may have one or more parent nodes,| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGiven a function that returns 0 and 1 with a probability of fifty percent, use this function to generate a random number between a and b with uniform distribution
- ajay.raj December 02, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersJudge if two arrays has the same pattern,
- ajay.raj December 02, 2017 in United States
The definition is the relative relationship between each number and other numbers are the same, such as 132, 354, the first number is less than the second, the first less than the third, the second is greater than the third,
So is the same,
132,352 is not the same, because the first 132 is less than the third, the first 352 is greater than the second,
follow up, the array may concern duplicates| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersA city bus station information, example, bus No. 1 stops at abcd station, bus No. 2 stops at cefg station. Then a-d you only need to take No. 1, thus return 1, a-g is 2, because you need to transfer at station c,
- ajay.raj December 01, 2017 in United States
ask for a minimum bus you need to take to reach to another station. You can design any data structures.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswerThe topic is to design a data structure to store employee relationships.
- ajay.raj December 01, 2017 in United States
For example, A is B's direct manager, there is an operation is "" set_manager "," A "," B ">.
For example, B is a colleague of C <"set_peer", "B", "C">
At this point, we do this with <query_manager "," A "," B "> and we get True, which means that A is B's manager (either direct or indirect).
This is true if we have <"query_manager", "A", "C">, because C is a coworker for B, so A is also C's manager. That is, there is a transitive relationship between colleagues.
Follow up, such as query <"query_manager", "A", "D"> (D this person has not been initialized), what to do. Conflict how to do
For example, A is a direct manager of B, E is a direct manager of C, which is set_peer (B, C), there will be conflicts, B and C direct manager should be the same person,
E and A are two people, there are contradictions here.| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
Answergiven a dictionary, output the longest List <String>. The result of a String is the previous String add a character at any position.
- ajay.raj December 01, 2017 in United States
example: {i, in, ing, sing, sting, string}| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswersFind a “local minimum” in a binary tree
- ajay.raj December 01, 2017 in United States
a local min is a node whose value is smaller than that of any other nodes that are connected to it| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
Answers1. merge intervals with value
- ajay.raj December 01, 2017 in United States
PD: there are a series of continuous intervals, and each interval has a value. Initially, the ith
interval is (i - 1, i - 1), merge these intervals and return the result.
Merge Rule:
a. We can only merge the ith interval with i-1 th or i + 1 interval. The value of new interval is the
mean of these two original intervals.
b. Define cost as absolute difference of two neighboring intervals,
every time merge two intervals with the smallest cost.
c. If the smallest cost exceeds a threshold t, then stop.
d. There may be multiple valid result, just return one.
for example:
value: 3 7 6 5 1
intervals: (0,0) (1,1) (2,2) (3,3) (4,4)
threshold: t = 2
first iteration:
min cost = |7 - 6| = 1, notice that |6 - 5| is also okay.
after merging:
value: 3 6.5 5 1
intervals: (0,0) (1,2) (3,3) (4,4)
second iteration:
min cost = |6.5 - 5| = 0.5
after merging:
value: 3 5.75 1
intervals: (0,0) (1,3) (4,4)
second iteration:
min cost = |3 - 5.75| = 2.75 > t = 2, stop
return [(0,0), (1,3), (4,4)]| Report Duplicate | Flag | PURGE
Google Java Developer - 1of 1 vote
AnswersGive all n cities the distance between them, and then you have to follow all the cities in the order of small to large index of the city, which means you must visit the cities in ascending order, and now you can choose not to visit k cities (k < n), ask choose not to go to which k cities can make the path shortest? Return the shortest journey.
- ajay.raj November 30, 2017 in United States
int findShortestPath(int[][] matrix, int k){
}| Report Duplicate | Flag | PURGE
Google SDET - 0of 0 votes
AnswersGenerate a random MxN starting board. It cannot have 3 or more pieces in a
- ajay.raj November 28, 2017 in United States
row (horizontally or vertically) of the same color. K colors.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersImplement a rate limiter attribute/decoration/annotation on top of an API endpoint. caps to N requests per minute with a rolling window (implement from scratch / test / compiling + working code. Was made to write the code in front of a computer.
- xyz November 28, 2017 in United States| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer - 0of 0 votes
Answersgive a list of cities a to city b the price of air tickets for example
- ajay.raj November 25, 2017 in United States
a b 100 $
b c 200 $
e f 200 $
...
Now let you from city x to city y, you cannot transfer more than twice between the two city, find the cheap flight from x to y, follow up print out the flight| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswersGas station problem, give you a starting point A and End B. An array of oil prices at each gas station index represents the location of each gas station. MPG = V, find the minimum cost of gas from A to B
- ajay.raj November 25, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
Answersgiven a string, and integer k, check if this string contain all the binary string of length k
- ajay.raj November 24, 2017 in United States
For example, k is 2, then 00,10,01,11.
Followup 1, find a string that can contain all binary string of length k.
Followup 2, find a shortest string that can contain all binary string of length k.| Report Duplicate | Flag | PURGE
Google SDE1 - 3of 3 votes
AnswersGiven a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.
- md.lisul.islam November 22, 2017 in United States
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an array which is in ascending order till some point and then descending order till end. find peak element
- careercupuser November 22, 2017 in United States| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 0of 0 votes
AnswersGiven a tree find shorted path to a specified element from root. Actual question is different but theory behind it is same.
- careercupuser November 22, 2017 in United States| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 0of 0 votes
AnswersWrite code to find unmatched parentheses and return it in the below format:
- 1080ti November 18, 2017 in United States
((a) -> -10a1
(a)) -> 0a1-1
(((abc))((d))))) -> 000abc1100d111-1-1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answersgive a bunch of job dependency, such as A-> B, A -> C, B-> D, and so on, implement two interfaces.
- ajay.raj November 17, 2017 in United States
The first one is get_next_stage, which returns jobs in parallel for the next phase. The second is job_done, which tells you which job completed.| Report Duplicate | Flag | PURGE
Google SDE1