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 - 0of 0 votes
AnswersTwo sum problem
- xyz November 14, 2019 in United States for Load Balancer| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswersWas 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 - 0of 0 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 - -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 - 1of 1 vote
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 - 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
Open Chat in New Window