Google Interview Questions
- 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
AnswersGiven 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
AnswerGiven 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
AnswerGiven 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
AnswersGiven 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
AnswersA 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 - -1of 1 vote
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 - 2of 2 votes
AnswersWe 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
AnswersHi there,
- xyz June 08, 2019 in United States
I'm using a Debian 8 system running Strongswan 5.2 to connect to Cloud VPN, but I'm seeing a large amount of packets being dropped. I'm not sure if the problem is on my side, so I need help debugging from the Google side.
11:44:15.127845 IP (tos 0x8, ttl 64, id 0, offset 0, flags [DF], proto ESP (50), length 1500)
204.154.94.43 > 104.198.99.16: ESP(spi=0x926a1ba9,seq=0x5fc78e8), length 1480
11:44:15.127846 IP (tos 0x0, ttl 64, id 0, offset 0, flags [DF], proto ESP (50), length 1500)
204.154.94.43 > 104.199.117.182: ESP(spi=0x2afc306c,seq=0x9753df), length 1480
11:44:15.127848 IP (tos 0x8, ttl 64, id 0, offset 0, flags [DF], proto ESP (50), length 1500)
204.154.94.43 > 104.199.124.50: ESP(spi=0x442d978a,seq=0xaae89d4), length 1480
Any ideas?
n3)Please explain briefly how you identified the correct solution, and if there were any other possibilities that you considered?| Report Duplicate | Flag | PURGE
Google Technical Support Engineer - 0of 0 votes
AnswersHi,
- xyz June 08, 2019 in United States
My virtual machine is talking to our on-premise Hadoop cluster and we have observed connections dropped by the VM after approximately 15 minutes after being established. We have tried tweaking our cluster and the VPN, but it did not work. We have also disabled any firewall or NAT: our cluster is connected directly to the Internet. We ran a TCP packet capture on one of our routers and we do see the following:
408 7.963058 178.124.133.65 172.16.72.34 TCP 66 http > 42867 [FIN, ACK] Seq=312 Ack=11 Win=14592 Len=0 TSval=3673141343 TSecr=234006479
409 7.963204 172.16.72.34 178.124.133.65 TCP 66 42867 > http [FIN, ACK] Seq=11 Ack=313 Win=15744 Len=0 TSval=234006482 TSecr=3673141343
410 7.995556 178.124.133.65 172.16.72.34 TCP 66 http > 42867 [ACK] Seq=313 Ack=12 Win=14592 Len=0 TSval=3673141351 TSecr=234006482
Please help, this is a fault in your network, I need a solution ASAP!
n1) If you were to troubleshoot / debug this issue, what areas would you look into to resolve the issue?
n2) Please explain briefly how you identified the correct solution, and if there were any other possibilities that you considered?| Report Duplicate | Flag | PURGE
Google Technical Support Engineer - 3of 3 votes
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 - 0of 0 votes
AnswersFind the location of BCD in String S.
- bottleneck56 June 01, 2019 in United States
Given for example S = BCXXBXXCXDXBCD, then the result should be [[4,7,9],[11,12,13]
find BCBC in String S = BCXXBXCXBCBC
the result should be [[0,1,4,6],[8,9,10,11]]| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersYou have a plot with a limited amount of points on it.
Find the cluster of points, which contains the biggest amount of point grouped together.
Conditions:
The cluster means, that points are placed not farther than 5 units (Can be measured px, cm, etc.) between each other. The distance is calculated by where|x1-x| < 5
and
|y1-y| < 5
The cluster should contain at least 3 points.
- denis.zayats May 30, 2019 in United States
If there are a few clusters with the same amount of points - return all of them.
Example:
The points are:
(15,116), (1345, 123), (456, 11), (34, 17), (19, 112), (556, 111), (454, 15), (12, 120).
In this case, the best cluster is (15,116), (19, 112), (12, 120)| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 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 - 0of 0 votes
AnswersGiven a list of files. Return all the unique lines from all files.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerGiven a set of points, find the smallest rectangle by area.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven N shop coordinates on a 2-d plane, Find the nearest shop from a man whose coordinates are given.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGive you a text file, remove duplicated lines.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersA string consists of ‘0’, ‘1’ and '?'. The question mark can be either '0' or '1'. Find all possible combinations for a string.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven two two integer arrays. Find the longest common subsequence.
- acoding167 May 12, 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