Google Interview Questions
- 0of 0 votes
AnswersFormat a list of strings into a table.
- theeventrodie November 15, 2022 in United States
We have a style guide (for example, lines must be at most 80 characters wide). We have a tool that automatically
formats code to the style guide. One thing it can do is arrange lists of strings into a table. The strings in
each column are left-aligned to be more easily readable. It leaves no holes in the table except after the last
string in the last row (i.e. every cell contains a string, except possibly in the last row). Of course, the
strings remain in the original order.
Example:
W = 70 (characters)
S = [IsAudioBuffer, GetTimestamp, SetTimestamp, GetSampleRate, GetSampleSize, GetNumberOfChannels,
GetNumberOfSamples, GetDataBuffer, GetChannel]
We can format this as follows:
IsAudioBuffer GetTimestamp SetTimestamp GetSampleRate |
GetSampleSize GetNumberOfChannels GetNumberOfSamples GetDataBuffer |
GetChannel |
Given the list of strings, and a maximum number of characters per line, format the table using the maximum
number of columns without violating the line width constraint.| Report Duplicate | Flag | PURGE
Google String Manipulation - 0of 0 votes
AnswerLet’s say you are given with n electricity poles in a line. Each pole i has a flexible varying height from 1 to maximum MaxHeight(i) .
- deb~ August 17, 2022 in India
MaxHeights are defined in a separate array MaxHeight[1...n].
These poles can vary their size (expand to max height / shrink to lowest height 1) at any time.
You need to write code to find out the length of wire you would need to connect all these poles from top,
such that no matter how much is the current height of each pole, the wire should be able to connect all these poles from top.
What is the minimum wire length required to sufficiently connect these poles from top in any configurations of poles ?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersYou will be given matrix of 0 and 1
- dfsdfdsfd November 28, 2021 in Berling
100
100
if cell with value 0 has at least one 1 from up, down, left or right side then you have to convert this change it to 'b'.
if cell has value 'b' its bin cell
Find clothest distance from every cell to bin cell| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven an array of n strings with length m return true if there is one pair such that there is only one difference between the words, e.g, abcd and abce would yield true, but abcd and abdd would be false.
- jllangston November 24, 2021 in United States
I could not think in the space of the interview how to optimize the algorithm| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersWhen a person who knows it meets any other person, they immediately share the story with them.
- veeru June 25, 2021 in India
Initially, only person 1 knows the story. Given a list of meetings between people in a form of
(person_1_id, person_2_id, timestamp) construct a list of the persons who will know the story
at the very end.
Example: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 // The events could be out of order.
Person 2 will learn the story at the moment 100, person 3 — at the moment 300,
person 5 — in the moment 400. Person 4 will never learn the story. So the answer is [1, 2, 3, 5].
Eg2: [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2
where the first parameter is array of the Persons meet at particular timestamp, second parameter is the PersonId who knows the story first.
Output: [1, 2, 3]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 2 votes
AnswersDesign a graph problem, given an function getFriend(int user) which returns all the users 1st degree friends, write a function to check:
- ikf4 May 01, 2021 in India
1. whether two users are first-level, second-level and third-level connections
2. function that outputs a users 2nd degree and 3rd degree friends| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersYour input is a double array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.
- _M_ November 26, 2020 in India
Ex:
input is {3,4,5,1} --> output: 72
input is {1,1,1,5} --> output: 15
Follow up, if there are numbers <0
Already posted question ( 3yrs back)
my doubt is can we solve this using multiplication only ( special case 0 and 1 we need to use addition for these alone
ie. if ar[i]==1
max(result*ar[i-1]+1,result*ar[i+1]+1)
)| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer - 0of 0 votes
AnswersYou are in charge of designing a small, in-memory social network, with the basic functionality of adding friendship
- tassecarriere August 26, 2020 in United States
between two people via an AddFriendship function, and a GetSuggestedFriends function for a particular user in the
network. The criteria is to pick someone with whom the given user has the most number of friends in common.
Start by discussing the most suitable data structure, and implement all the objects and functions.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswerI was asked during a virtual onsite to design a chat server. I was interviewing for a senior software engineer position. Here are some of the requirements:
- codemonkey August 11, 2020 in United States
- real time communication.
- offline handling
- multi-device supports.
Luckily, I was well prepared for system design interview questions. Thanks to system design interview - an insider's guide book on amazon and system design primer. Still waiting for the response. Wish me luck!| Report Duplicate | Flag | PURGE
Google SDE-3 System Design - -1of 1 vote
AnswersYou are given a series of arithmetic equations as a string, such as:
- Manoj May 26, 2020 in India
y = x + 1
5 = x + 3
10 = z + y + 2
The equations use addition only and are separated by newlines. Return a mapping of all variables to their values. If it's not possible, then return null. In this example, you should return:
{
x: 2,
y: 3,
z: 5
}| Report Duplicate | Flag | PURGE
Google Software Engineer Problem Solving - 0of 0 votes
AnswersGiven a board game of N x M size. A domino is of size 1 x 2 and can be rotated to make it 2 x 1. A player can place a domino in any of the available position. When a player is not able to place a domino, he loses. An AI is created to play against the user. The AI selects a random position in the board and places the domino there. Improve this AI. What solution will be the best when board size is small and what if the board size is large.
- komorsad2 April 12, 2020 in India
Anyone has any idea how to have a solution to this problem?| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersDetect a horizontal line in a bitmap image. Assume there will be some utilities to process the black and white image. you just need to process the utility output and return the start and end indices of the horizontal line if any.
- ammuz February 17, 2020 in Germany| Report Duplicate | Flag | PURGE
Google - -1of 1 vote
AnswersGiven an array of sets find the one that does not belong:
- billybill January 03, 2020 in United States
example: [[a,b,c,d], [a,b,f,g], [a,b,h,i], [j,k,l,m]]
output: [j,k,l,m]
We can see above that the first three sets have a subset [a,b,c] and the last one does not. Note: There may be a case where the outlier set does have elements contained in the input group. In this case we have the find the set that has the least in common with the other sets.| Report Duplicate | Flag | PURGE
Google Software Engineer Sets - 2of 2 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 - 0of 0 votes
AnswersTwo sum problem
- xyz November 14, 2019 in United States for Load Balancer| Report Duplicate | Flag | PURGE
Google Backend Developer - 2of 2 votes
AnswerWas asked at GHCI Bangalore at their booth for a prize and perhaps hiring interns or experienced software developers.
- jaryya@hawk.iit.edu November 10, 2019 in India
Find the return value for N=100
int returnAns(int N){
int ans=0;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
ans +=((i & -i) == (j & -j)?1:0); //the question missed the condition and was returning a boolean, so I added it myself
}
}
return ans;
}
My answer: 0 ; their answer: 1610, hence got it wrong.
My explanation: I assumed negative of i in binary to be
simply represented by setting the MSB to 1 e.g. for 8 bit representation of 3: +3 is 0000 0011 and -3 is 1000 0011. In the inner loop the value of ans will always evaluate to 0 since Bitwise & of these i and -i or j and -j will always result into i and j respectively. (undergrad computer organization concept.)
Negative numbers can also be represented as 1s and 2's complement and in all modern machines by architecture its 2s complement.
Now if we assume 1's complement, +3: 0000 0011 and -3: 1111 1100. so bitwise & of these two is 0 and so the value of ans will always be incremented by 1. By two loops 100+99+98+97+...+1 = 100*101/2 (i.e. n*(n+1)/2)
Then 2's complement, which is the most relevant representation of signed binary numbers.
Odd numbers:
+3: 0000 0011 -3: 1111 1101 Binary & is 0000 0001.
For all even numbers:
+4: 0000 0100 and -4: 1111 1011+0000 0001 = 1111 1100 and Bitwise & of 4 and -4 is 0000 0100 which is 4.
So, in the innermost loop ans is incremented by 1 when i is odd and j is also odd. ie. when i is 1, 3, 5, 7... 97 and j is 3, 5, 7, 9,...,99 ans is added 1(return value of true ==) when calculated it comes to 1610.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 3of 3 votes
AnswersI was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:
- Jaysun October 26, 2019 in United States
There's a list of (x,y) points and a method getCircle with the following signature:
/**
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
*/
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.
The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 1 vote
AnswersYou have a table :
- mukesh.scorp October 23, 2019 in United States
Rule1 Rule2 Rule3 Value
A1 B2 C3 40
A1 B1 C1 20
A2 B2 C2 10
A1 B1 C1 40
* B1 * 20
A5 B2 * 10
Now if I have a condition A1 && B2 && C3 i will get output as 40.
If I input A1 && B1 && C1 I will get two results 40 and 20 here there the rule is ambiguous.
"-" in table means any rule, 5th row matches with any row with B1 as rule2, so there is also ambiguity in result.
Now given that table as input (m * n) where n is number of available rules combination (here its 6) and m rules (3 in this case) , output if the table is ambiguous i.e it will output two different result for same query.| Report Duplicate | Flag | PURGE
Google Backend Developer Algorithm - 0of 2 votes
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
Answersfind nearest word from the given non-english dictionary which is one off character. (could be non ascii characters)
- prathji October 01, 2019 in United States
for eg. dictionary contains { apple, pineapple, banana, orange }
if given word "applx" then return true, as applx matches with apple and only one character is off.
aplpe returns false| Report Duplicate | Flag | PURGE
Google Software Developer - 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 - 0of 0 votes
AnswersIf ads were removed from YouTube, how would you monetize it?--Associate account strategist, January 2016
- jerryalston11 August 18, 2019 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersA stream of data representing the price of a commodity is being read. The data is of the format (price:Int, timestamp:Option[Long]).
- abzy August 17, 2019 in India
If the timestamp is missing, it means the price has to be deleted.
If timestamp is old, it means the previous data with same timestamp has to be updated with this new price.
Else it's the new price of the commodity.
At any point of time the latest, max and min of the price has to be printed.
If the delete instruction is received through the stream, the min/max should be updated accordingly.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 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 - 3of 3 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
AnswersConsider 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