Google Interview Questions
- 2of 2 votes
Answers[Google On-site 2018 Winter]
- aonecoding4 November 28, 2018 in United States
Set Matrix Zeroes II
There are orbs on an NxM board ('O' denotes orb. 'X' denotes empty slot).
Whenever two orbs are in the same column or the same row, you get to erase one of them.
Try to erase as many orbs as possible.
Find the minimum number of orbs remained on board eventually.
e.g.
OXOXXO
XXXXXO
XXXXOX
erase (0,0) and get
XXOXXO
XXXXXO
XXXXOX
erase (2,0) and get
XXXXXO
XXXXXO
XXXXOX
erase (5,0) and get
XXXXXX
XXXXXO
XXXXOX
no more moves available. Return 2 e.g.
OXOXXO
XXXXXO
XXOXOX
erase(4,2), (2,2), (0,0), (2,0), (5,0)
Return 1
e.g.
OXOXXX
XOXXXO
XXXOOX
erase(0,0), (1,1), (3,2)
Return 3
Follow-up Build a solver for this board game that erases the as many orbs as possible.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswerRoulette -Gamblers Fallacy. start with $50, bet opposite color every time same color 4 in a row. loop 100 time or until $0. Suggest create roulette wheel object with history, a gambler object with maybe gamblingplan object. (you can find more detailed suggestions elsewhere)
- whoknows November 18, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersGiven a tree with n nodes. Each node has k coins, where 0 <= k <= n . There are total n coins on the tree.
- aonecoding4 November 18, 2018 in United States
The goal is to move the coins such that each node has exactly one coin. What's the minimum moves required?
Each move can only move one coin to an adjacent node.| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersYou have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in 5 boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum.
- parni November 01, 2018 in United States
You can only choose consecutive toffee packets to put in a box.| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersThe difference between move and forward in C++
- parni November 01, 2018 in United States| Report Duplicate | Flag | PURGE
Google C++ - -4of 4 votes
Answerbinary search
- James666 October 22, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersHow would you tell whether a graph has a node with n degree??
- shivamdurani220 October 11, 2018 in United States
tell your approach| Report Duplicate | Flag | PURGE
Google SDE-2 - 1of 1 vote
AnswersThere is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.
- shivamdurani220 October 09, 2018 in United States
You can keep inputting the password, the password will automatically be matched against the last n digits entered.
For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.
Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.| Report Duplicate | Flag | PURGE
Google SDE-2 - 6of 6 votes
AnswersGiven an array of integers, find out how many unique BST can be generated from the array.
- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Trees and Graphs - 1of 1 vote
AnswersGiven an array of Integers, find out how many combinations in the array, satisfy the equation x+y+z=w, where x,y,z and w belong to the array and idx(x)<idx(y)<idx(z)<idx(w). Elements are unique.
- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Arrays - 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?
- shivamdurani220 September 22, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Developer - 2of 4 votes
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.?
- shivamdurani220 September 15, 2018 in United States
please discuss approach first & then code it..| Report Duplicate | Flag | PURGE
Google SDE-2 - -1of 1 vote
Answers1. Try to find whats wrong with this code
- YoYo September 15, 2018
2. after fix it what is the out put
3 how to make this code more generic :D
Initial state of an array "a":
[[2, NULL, 2, NULL],
[2, NULL, 2, NULL],
[NULL, NULL, NULL, NULL],
[NULL, NULL, NULL, NULL]]
========
Main function:
FUNCTION foo()
FOR y := 0 to 3
FOR x := 0 to 3
IF a[x+1][y] != NULL
IF a[x+1][y] = a[x][y]
a[x][y] := a[x][y]*2
a[x+1][y] := NULL
END IF
IF a[x][y] = NULL
a[x][y] := a[x+1][y]
a[x+1][y] := NULL
END IF
END IF
END FOR
END FOR
END FUNCTION| Report Duplicate | Flag | PURGE
Google Technical Support Engineer - 5of 5 votes
AnswersYou are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
- john August 29, 2018 in United States. - Free path/road # - Building B - Google bike Employee location - (x, y) - (1, 2) . . . . . # . . E . . # # # # # . # . B . . . . . . . . . B
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -1of 1 vote
Answerwrite a main program to take snapshots of VMs
- samayragoyal990 August 10, 2018 in United States
Input: List of VMs(vmId: String), list of SLAs -> there is one-to-one mapping from VM to SLA
class SLA {
int freq_in_mins;
}
vm1 -> sla1{30 mins}
vm2 -> sla2{60 mins}
Constraints:
1) You can use takeSnapshot(vmId: String) -> Synchronous - I/O
2) If you start a snapshot of VM(with sla1) at time t0 and if it finishes at time t1, then the next snapshot should be scheduled at t1+sla1.freq_in_mins
vm1 at 00:00 and vm2 at 00:00
00:10 and 00:15
vm1 -> 00:10 + 30 = 00:40| Report Duplicate | Flag | PURGE
Google SDE-3 Coding - -1of 1 vote
AnswersGiven two string check if they can be made equivalent by performing some operations on one or both string.
- alex August 09, 2018 in United States
swapEven:swap a character at an even-numbered index with a character at another even-numbered index
swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index
Given : s="cdab" , x="abcd"
s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"
Given: s="dcba" , x="abcd"
no amount of operation will move character from an odd index to even index, so the two string will never be equals
Given: s="abcd" ,x="abcdcd"
x length to big so will never be equals| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersFind top 10 most frequent words in the past hour, day and month from twitter service. Given a streaming data such as tweets from twitter service, the objective is to find the top 10 frequent words in the past hour, day and past month at any instant of time.
- Pedro August 07, 2018 in United States for Maps| Report Duplicate | Flag | PURGE
Google Software Developer - 1of 1 vote
AnswersFind all triplet that sum to a given value in an array of integers, given that the array is too big to fit into memory
- intuiti July 19, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 7of 7 votes
AnswersGive an array A of n integers where 1 <= a[i] <= K.
- aonecoding July 12, 2018 in United States
Find out the length of the shortest sequence that can be constructed out of numbers 1, 2, .. k that is NOT a subsequence of A.
eg. A = [4, 2, 1, 2, 3, 3, 2, 4, 1], K = 4
All single digits appears. Each of the 16 double digit sequences, (1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2) ... appears. Because (1, 1, 2) doesn't appear, return 3.| Report Duplicate | Flag | PURGE
Google Solutions Engineer - 1of 1 vote
AnswersWrite a function that takes a magic number and a list of numbers. It returns true if it can insert add or subtract operations in the list of numbers to get the magic number. Otherwise, it returns false.
- Pedro July 11, 2018 in United States
For example:
f(10, [1,2]) = false. There's no way to add or subtract 1 and 2 to get 10.
f(2, [1,2,3,4]) = true. 1 + 2 + 3 - 4 = 2.
f(0, []) = true
f(1, []) = false
f(1, [1]) = true
f(0, [1]) = false| Report Duplicate | Flag | PURGE
Google Software Developer - 1of 1 vote
AnswersImplement a rate-limiter-like iterator and how to improve the space complexity
- sun2gz July 05, 2018 in United States
Given a <Word, TimeStamp> pair data type iterator as input. Implement an iterator based on it which can ignore the item if the same word has occurred in the past 10 seconds.
My implementation is to use a HashMap to memorize the word and its latest timestamp + 10s. For each new item, it will be checked against the HashMap to see if it has duplicated word occurred in the past 10s.
The interviewer asked me how to improve the space complexity if the string value varieties are infinite. He mentioned some boundary stuff.
Could anyone share some thoughts?| Report Duplicate | Flag | PURGE
Google Software Developer - 0of 0 votes
AnswersMulti -level cache system design with different storage in each level.
- ANONU June 22, 2018 in United States
Read Operation : – Minimum time to read a particular key from cache system. This should be followed by writing the key in all levels above it. Eg. if “key” is found at level ‘i’, add this key to cache present at 1 to i-1 level.
b. Write Operation: – Any write Operation should write in cache of all levels.
You can choose any algorithm for cache management like LRU, MRU.| Report Duplicate | Flag | PURGE
Google Java Developer Coding - -1of 1 vote
AnswersReverse a linked list
- James666 June 06, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answersthere is a 2d array and gbikes are located in that location. there is a person and he wants to know the nearest location of the bike which is available for him(there can be more than 1 nearest bike). person can only move left , right , up or down. output should be the distance in int.
- whoknows June 05, 2018 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersDesign a system like github.
- ANONU May 29, 2018 in India| Report Duplicate | Flag | PURGE
Google Java Developer Software Design - 1of 1 vote
AnswersA city represented by a rectangular matrix is divided into plot of lands, and the cost of each plot is known. Find the largest rectangular area of land we can buy, within a budget B.
- sachin323 May 27, 2018 in United States
4 6 7
3 5 2
2 4 5
B = 16| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersThe wildcard regex can include the characters * and + .
- alex May 17, 2018 in United States
‘+’ – matches any single character or empty character!
‘*’ – Matches any sequence of characters (including the empty sequence) For example,
Text = "baaabab":
regex = "ba*a++", output : true
regex = "ba*a+", output : true
regex = "a*ab", output : false
//empty string
Text=""
Regex= "+" , output : true| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 2of 2 votes
AnswersApril Google Interview 1/4
- aonecoding May 06, 2018 in Korea
A = a+b-c-a-b-c-a-b (Tree)
B = b+a+c+a+b-c+b (Tree)
is A equal to B| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersApril Google Interview 3/4
- aonecoding May 06, 2018 in Korea
Maze
N,M array
Level 1 0,0 to N-1,M-1 => Path exsits?
Level 2 if path exists then print path
Level 3 if path exists then print min cost path
Level 4 O(nm log mn) using Priority Queue.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm