## Google Interview Questions

- 0of 0 votes

AnswersGiven a list of 2d points, if any two points have distance(straight line) <= k , group them together. For example. [P1,P2,P3], P1 to P2 <=k, P2 to p3<=k, p1 to p3>k. they are still in the same group. (distance relationship is chainable ) ask how many groups can you find ? I can think of N^2 time complexity with union and find. but how to do better than that? maybe NlogN or O(N)?

- laoen November 30, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - -1of 1 vote

AnswersGiven a set of horizontal and vertical line segments, find the number of squares formed by them?

- uj.us October 04, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer - 2of 2 votes

AnswersA mobile phone company wants to deploy network of cell towers to provide good signal coverage for its customers. But it doesn't want to have too many towers because they can interfere with one another. All towers are laid out over a 2-dimensional surface and that towers have same sized circular signal zone. You can determine whether their signal zones will overlap in 0 1) time. Give a parallel algorithm for choosing maximal subset of towers that cover non-overlapping areas.

- MaryJane August 19, 2019 in United States

I was not sure if this can be solved using DP?| Report Duplicate | Flag | PURGE

Google Software Engineer - 1of 1 vote

AnswersCard Game

- acoding167 July 12, 2019 in United States

Card game rule: the hand is drawn from a pack of cards (no jokers).

Play cards ONLY when they are

1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).

2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).

Find out whether the player is able to play the whole hand given.

e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.

[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.| Report Duplicate | Flag | PURGE

Google Software Engineer - 1of 1 vote

AnswersGiven a list L of video names and their watch rates, write a function that will return the videos with the top 10 watch rates. Video names may appear more than once.

- neer.1304 July 03, 2019 in United States

Example:

L = [(‘abc’, 10), (‘def’, 15), (‘ghi’, 10), (‘abc’, 12), …, (‘xyz’, 100)]

The function should return [‘xyz’, ‘abc’, …, ‘def’, ‘ghi’]| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswersWrite a function that takes a list L and returns a random sublist of size N of that list. Assume that the indexes must be in increasing order. That is, you cannot go backwards.

- neer.1304 July 03, 2019 in United States

Example:

L = [1, 2, 3, 4, 5]

N = 3

The function should return one of these lists:

[1, 2, 3]

[1, 2, 4]

[1, 2, 5]

[1, 3, 4]

[1, 3, 5]

[1, 4, 5]

[2, 3, 4]

[2, 3, 5]

[2, 4, 5]

[3, 4, 5]| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswerConsider an undirected tree with N nodes, numbered from 1 to N. Each node has a label associated with it, which is an integer value. Different nodes can have the same label. Write a function that, given a zero indexed array A of length N, where A[j] is the label value of the (j + 1)-th node in the tree and a zero-indexed array E of length K = (N – 1) * 2 in which the edges of the tree are described, returns the length of the longest path such that all the nodes on that path have the same label. The length is the number of edges in that path.

- neer.1304 July 03, 2019 in United States

Example:

A = [1, 1, 1, 2, 2]

E = [1, 2, 1, 3, 2, 4, 2, 5]

This tree is shown below. A node follows the form label, value.

----------1, 1

-----1, 2 1, 3

2, 4 2, 5

The function should return 2, because the longest path is 2->1->3, and there are 2 edges in this path.

Assume that 1 <= N <= 1000 and each element of the array A is an integer in the range [1, 1000000000].| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswersGiven a string A consisting of n characters and a string B consisting of m characters, write a function that will return the number of times A must be stated such that B is a substring of the repeated A. If B can never be a substring, return -1.

- neer.1304 July 03, 2019 in United States

Example:

A = ‘abcd’

B = ‘cdabcdab’

The function should return 3 because after stating A 3 times, getting ‘abcdabcdabcd’, B is now a substring of A.

You can assume that n and m are integers in the range [1, 1000].| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven 1-D list of co-ordinates determine if interval (a,b) is covered

- neer.1304 July 03, 2019 in United States

Ex - [(2,5), (5,7),(1,4)] and interval = (1,6)

return true

Explanation - Points 1 to 6 lies in list of interval given 1 to 4. 2 to 5 and 5 to 7.

[(1,4),(6,7),(2,5)] and interval - (1,6)

return false

Explanation - Distance between 5 to 6 is not covered in the list given so return false| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswerCompare two documents(string array) based on n grams.

- neer.1304 July 03, 2019 in United States

e.g doc1 – Today is Sunday.

doc2 – Today is Saturday

if n = 2 then number of duplicates is 1 (Today is)

if n = 1 then number of duplicates is (Today, is)

if n = 3 duplicates is 0| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven a bench with n seats and few people sitting, tell the seat number each time when a new person goes to sit on the bench such that his distance from others is maximum

- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.

- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswerGiven an infinite chessboard, find minimum no. of steps for a knight to reach from the origin to (x, y).

- neer.1304 July 03, 2019 in United States

Extension A list of forbidden coordinates are introduced where knight can’t reach. Handle this in your code. Make sure the infinite loop is handled since the board is infinite.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven a matrix of people(denoted by small alphabets) and bikes(denoted by capital alphabets), find the nearest bike for a given person.

- neer.1304 July 03, 2019 in United States

How will you change your solution if you have to find bikes for a set of people? (assuming multiple bikes can be at the same distance from 1 person)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven an array of n integers, find the lexicographically smallest subsequence of length k.

- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven a list of player names and their scores – {Carl, 70; Alex, 55; Isla, 40}, design a data structure that can support following modules in optimal time-

- neer.1304 July 03, 2019 in United States

i) updateEntry(string name)

ii) getEntryFromRank(int rank)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven an input stream of boolean values, design a data structure that can support following modules in optimal time-

- neer.1304 July 03, 2019 in United States

i) setTrue(index)

ii) setFalse(index)

iii) setAllTrue()

iv) setAllFalse()

v) getIndex(index)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

- neer.1304 July 03, 2019 in United States

Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?

Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven a stream of integers, a value k and a value w, consider the integers in the window w and chop off greater k and smaller k elements from the window w. From the remaining elements, compute the average.

- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersImplement the version control map system which takes the snapshot of the versions of data. Implement the following functions:

- neer.1304 July 03, 2019 in United States

put(key, value) -> puts the value again the key in the latest version of the map

get(key) -> get the value of the key for the latest version of the data

snapshot() -> take a snapshot and increment the version

getValVersion(version id, key) -> return value of the key of the particular version| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswerGiven various subsequences of an array, print the overall array:

- neer.1304 July 03, 2019 in United States

Example: [1, 3, 5], [1, 3, 9], [9, 5]

Array : [1, 3, 9, 5]| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswerA graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted edges given in K. If it creates a path, we have to discard the edge.

- neer.1304 July 03, 2019 in United States

Example: N = 4; K = {(1, 4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersYou are given 2 strings which are exactly same but 1 string has an extra character. Find that character.

- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswerYou are given an array of million numbers and provided a range of index (say left, right). For multiple queries, each with input left and right indexes, output the maximum in that range.

- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven (x, y) coordinates, create a function such that each coordinate is uniquely mapped to an integer. Also make sure that given an integer, you should be able to find (x, y) coordinates. So F(x, y) = z and also that inverse F(z) = (x, y).

- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswerWe have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get

- neer.1304 July 03, 2019 in United States

this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Input : k = 2, A = {10, 10, 10, 10}

Output : 20.

Here we can divide the boards into 2

equal sized partitions, so each painter

gets 20 units of board and the total

time taken is 20.

Input : k = 2, A = {10, 20, 30, 40}

Output : 60.

Here we can divide first 3 boards for

one painter and the last board for

second painter.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswerSelect a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).

- acoding167 June 19, 2019 in United States

Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

AnswersGiven range of routing numbers, determine which bank it belongs to.

- neer.1304 June 08, 2019 in United States

Ex-

I/p -(123400,123500, BOA), (12538, 12548, GCU)…

For 123450 - Output BOA

12540 - Output GCU| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven two two integer arrays. Find the longest common subsequence.

- acoding167 June 02, 2019 in United States

eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]| Report Duplicate | Flag | PURGE

Google Software Engineer - 5of 5 votes

AnswersTree Game

- aonecode May 17, 2019 in United States

class TreeNode {

TreeNode parent; //parent node

TreeNode left; //left child

TreeNode right; //right child

}

Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.

The player who eventually owns more nodes wins the game.

Player A and B each claims a node at first.

After the first round, a player will only be able to claim a node adjacent to any node owned by himself.

A tree node is adjacent to its parent, left right and right child.

A node owned cannot be re-claimed.

End game when all nodes are owned.

If player A gets the first claim at node N, find whether it is possible for player B to win.

If yes, find out which node player B should claim at his first move.

Follow up: if player B takes the first hand instead, which node should he pick?| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm

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

Open Chat in New Window