## Google Interview Questions

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

AnswersGiven an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

- Vijay November 17, 2017 in India

Example : Array : 2,5,6,7,8,8,9

Target number : 5

Output : 5

Target number : 11

Output : 9

Target Number : 4

Output : 5| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm Arrays Coding Data Structures - 0of 0 votes

AnswersGive a list of the company's Mergers and Acquisitions relationships, for example

- ajay.raj November 16, 2017 in United States

[

["baidu", "ofo"],

["mobike", "alibaba"],

]

Said baidu acquired ofo, mobike acquired Alibaba.

Seeking the longest of a M & A chain. No cycle| Report Duplicate | Flag | PURGE

Google Backend Developer - 1of 1 vote

AnswersYou are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be erased in the binary tree and return the resulting forest in the form of an array of every root node.

- ajay.raj November 13, 2017 in United States

Follow up:

What if this is a Binary Search Tree? (In this case you are given a list of nodes that should be erased instead of the function.) Does it make the problem simpler or more complicated or just the same?| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersYou are given an arbitrary number of graphs using sets such as {a,b,c,d,a}, {a,b,a}, {e,f,g,h,e}... etc. Assume each element at position x_i in a set has a directed edge to x_{i+1}. so a-->b, b-->c etc. Write a program that selects a subset of at mot k vertices that contains at least one vertex from every directed cycle in the graph.

- jablaboo November 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google - 0of 0 votes

AnswersWrite a program that always produces a two-way Euler tour that can be drawn such as it does not cross itself at any vertex.

- jablaboo November 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google - 0of 0 votes

Answerslet's say you're given an arbitrary list of relations r1 and r2 from objects in a set of arbitrary size. find the size of th largest subset with the property that no two are related. for e.g., given set S = {a,b,c,d,e,f} and relations {a,d}, {b,c}, {a,c}, {a,e}, find the subset of S such that no two a connected.

- jablaboo November 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google Trees and Graphs - 0of 0 votes

AnswersThere are n bus lines, known bus stops by bus, the bus is bi-direction, ask from station A to station B at least a few transfers.

- ajay.raj November 10, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersWrite all the possible numbers returned from a calculator pad where a start number move in a L direction in any directions(1-2moves)

- wingchuihk November 08, 2017 in United States

ie. From calculator pad. Start from 8 --> go in L shape (2up, 1right), and it returns 3

ie. Start from 2, (move 2 down, 1 left), it will be 7

ie. Start from 2(move 2 down, 1 right), it will be 9

ie. Start from 7(move 1 left, 2 up), it will be 2

ie. Start from 7(move 1 up, 2 left), it will be 6| Report Duplicate | Flag | PURGE

Google SDET Java - 0of 0 votes

Answersthe longest unique value path in a graph

- ajay.raj November 06, 2017 in United States

/**

* Definition for undirected graph.

* class UndirectedGraphNode {

* int label;

* List<UndirectedGraphNode> neighbors;

* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

* };

*/

public class Solution {

public int findLongestUniqueValuePath(List<UndirectedGraphNode> node) {

}

}| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven an array of length n + 1, containing elements 1 through n and a space,

- ajay.raj November 04, 2017 in United States

Requires the use of a given swap (index i, index j) function to sort the array,

You can only swap the gap and a number, in the end, put the gap at the end| Report Duplicate | Flag | PURGE

Google SDE1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window