Google Interview Questions
- 2of 2 votes
AnswersGiven a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).
- ankit3600 June 14, 2016 in India
Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.
Note: all coordinates are real numbers
(a,b)
|----------------------------------------------|
|.......................................................|end
|.......................................................|
|start................................................|
|.......................................................|
|----------------------------------------------|(c,d)
Edit: You have to avoid sensors.
Also u can move in any direction any time.| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersGiven two string S1 and S2. S1 contains from A-Z and S2 contains A-Z, * and ?
- darklight December 28, 2012 in India
Where * means any character 0 or any number of times
Where ? means any character 0 or 1 number of times
Write a program to determine whether S2 matches S1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersThere are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.
- crowdx February 12, 2019 in India
Given N and number of players from each country and size K. Find the maximum number of teams you can form.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersWe have N gas stations, and we are given all the distances between each pair of station. So we have nC2 distances provided to us. For example if I have 3 stations namely A, B, C the distances provided will be AB, AC, BC. We have to find the exact position of each gas station provided with these nC2 distances.
- logan9 August 05, 2017 in United States
eg. we have 5 stations so 5C2 distances are given in random order - 10, 20, 70, 80, 30, 20, 100, 70, 50, 90
Output the exact positions of gas stations A, B, C, D, E
i.e
A - 0
B - 10
C - 30
D - 80
E - 100
refer this image for more clarity
https://drive.google.com/open?id=0BxPkptdH01OBZzEwX29iRGI4cEU| Report Duplicate | Flag | PURGE
Google Software Engineer Problem Solving - 2of 2 votes
AnswersGiven a string "2-4a0r7-4k", there are two dashes which we can split into 3 groups of length 1, 5, 2.
- J@sper October 20, 2016 in United States
If we want each group to be length 4, then we get "24A0-R74k"
Given a String A and an int K, return a correctly formatted string.
IF A is "2-4A0r7-4k" and B is 4, string is "24A0-R74K"
IF K is 3, string is "24-A0R-74K" as the first grp could be shorter.| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 2 votes
AnswersCount the number of set bits for an 32 bits integer. How to improve the process for the second time use if the memory is unlimited?
- Andy2000 September 04, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
Answers[redacted]
- tohhubeta September 02, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersFind the longest common prefix in a list of phrases. For instance; "i love all dogs", "i love cats" should return "i love".
- tamaracmike July 08, 2015 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 2 votes
AnswersGiven an Array A with n elements. Pick maximum number of elements from given array following the rule:
- chan alex September 25, 2016 in United States
1. We cannot pick A[i] and A[j] if absolute value of (A[i] - A[j]) > absolute value of (i - j)
Example: {13,5,4}
Ans: 2
Pick 5 and 4.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersYou are given a binary search tree and a positive integer K. Return the K-th element of the tree.
- Anonymous January 27, 2015 in Israel
No pre-processing or modifying of the tree is allowed.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 2 votes
AnswersAn array of integers of size n-1, all the elements are form [1,n]. Find the missing number. You can read only one bit in one operation, ie, to read A[i], you need to perform log(A[i]) operations.
- binu May 28, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays Bit Manipulation - 2of 2 votes
AnswersGiven a Pattern and a dictionary, print out all the strings that match the pattern.
- ad09 August 02, 2016 in United States
where a character in the pattern is mapped uniquely to a character in the dictionary ( this is what i was given first).
e.g 1. ("abc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "cdf"
2. ("acc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "too", "paa"| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 2 votes
Answers1. Balanced Parentheses
- siva.sai.2020 October 18, 2015 in India
Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string
A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.
Implement
int MinNumInsersertionsForBalancing(const string& s)| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
Answers2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
- JY January 24, 2015 in -
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 2 votes
AnswersYou are given a text file that has list of dependencies between (any) two projects in the soure code repository. Write an algorithm to determine the build order ie. which project needs to be build first, followed by which project..based on the dependencies.
- enok August 18, 2014 in United States
Bonus point: If you can detect any circular dependencies and throw an exception if found.
EX: ProjectDependencies.txt
a -> b (means 'a' depends on 'b'..so 'b' needs to be built first and then 'a')
b -> c
b -> d
c -> d
Then the build order can be
d , c, b, a in that order| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFor a given node in binary search tree find a next largest number in search tree.
- zealswap March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersA soda water machine,press button A can generate 300-310ml, button B can generate 400-420ml and button C can generate 500-515ml, then given a number range [min, max], tell if all the numers of water in the range can be generated.
- mario87 December 18, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersEngineers at Google have decided to call any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) as Walprimes. Thus -21, -30, 0, 5, 14 etc are Walprimes, while -121, 1, 143 etc. are not Walprimes.
- geekofthegeeks October 26, 2013 in India
Now, consider a n-digit integer d1d2d3..dn. Between any 2 consecutive digits you can place either a (+) sign, a (-) sign or nothing. So, there are 3n-1 different expressions that can be formed from it. Some of the expressions so formed may evaluate to a Walprime. For example, consider the 6 digit integer 123456: 1 + 234 - 5 + 6 = 236, which is a Walprime, but 123 + 4 - 56 = 71, which is not a Walprime.
Your task is to write a program to find the no. of expressions (out of the possible 3n-1 expressions) that evaluate to a Walprime, for a given input. Note that leading zeroes are valid. For example, if the input is 1202004, it can be split as 12 + 020 - 04 etc. Also, the input itself can contain leading zeroes.
Input format: (Read from stdin)
The first line of input contains a single integer 'T' denoting the no. of test cases.
Each of the following 'T' lines contain a single string 's' (of length 'n') denoting an input for which you need to find the no. of valid expressions evaluating to a Walprime.
Output format: (Write to stdout)
Output exactly 'T' integers (one per line), where the ith line denotes the no. of valid expressions that evaluate to a Walprime for the ith input string. Since the output can be large, print all the quantities modulo 1000000007.
Sample testcase:
Input:
2
011
12345
Output:
6
64
Explanation:
For the first test case, s = "011". There are 32 = 9 valid expressions that can be formed from this string, namely {0+11, 0-11, 0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1, 011} . Out of these 9 expressions, only the following 6 of them evaluate to a Walprime: {0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1}.
Constraints:
There are 3 data sets.
For the first data set (5 points) -
1
For the second data set (10 points) -
1
For the third data set (15 points) -
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven an array and is rotated n number of times find the number where the peak happens. The array is sorted in increasing order. Follow up question: how will you rearrange them in normal sorted order.
- madhur.eng June 03, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
Answers1000 elements in one bag and 1 million elements in another. how do you find common elements among them. Also give the complexity of your solution.
- sivaji8 September 27, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersDesign a data structure where the following 3 functions are optimised:
- P October 28, 2011 in India
1. Insert(n)
2. GetRandomElement()
3. Remove(n)
Write a class, and implement the functions. Give complexity of each of these ..| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Application / UI Design - 2of 2 votes
AnswersThere are n+1 loading docks. a permutation of boxes 1->n is placed on the first n. there is a fork that can move one box to an empty location at a time. Give an algorithm to sort then boxes with minimum number of moves.
- ad09 August 05, 2016 in United States
Follow up: minimum distance| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersYou are given printouts from an algorithm which ran over an unsorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.
- tested.candidate March 22, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersWrite code to get maximum and second maximum element of a stack. The given function should be in O(1) complexity . Later extend for finding kth max in O(1).
- Nascent November 08, 2014 in India| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersYou are given a grid, with points on the intersections (think a map of streets, people are standing on random corners). Write code to calculate the point on the grid that is the shortest distance from every point on the grid.
- chandeepsingh85 September 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 2of 2 votes
AnswersDesign an LRU cache with all the operations including getting the least recently used item to be O(1).
- Anonymous November 06, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given two arrays - A & B. The length of the arrays is the same - N. The values in the arrays are integers from 0 to N - 1 in random order and no number is repeated. You need to list a sequence of two-element swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.
- tested.candidate March 21, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a 2D rectangular matrix of boolean values, write a function which returns whether or not the matrix is the same when rotated 180 degrees.
- nr June 06, 2013 in United States for maps| Report Duplicate | Flag | PURGE
Google SDE1