Google Interview Questions
- 3of 3 votes
AnswersGiven two sorted arrays find the element which would be N-th in their merged and sorted combination.
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersAs an input, you have points on a 2D graph. You aim to find a straight line that can fit as my points as possible. Return, the maximum number of points you can fit.
- Bobika December 05, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersFind whether string S is periodic.
- aonecoding January 20, 2018 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
follow up:
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersHow would you design transfer of data packets from NY to Tokio?
- gbabun April 26, 2011
First I thought of traveling salesman problem where weight of connections between nodes is throughput of network. This problem is NP which lead just to interviewers reply that I should care about design of system, recovery of data and acknowledge whether data has been transferred.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Computer Architecture & Low Level - 3of 3 votes
Answers/**
- aonecoding January 13, 2018 in United States
* Google
* Given a list of non-negative numbers and a target integer k,
* write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
**/| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answers1 year exp. Interviewed at Cambridge, MA
- aonecoding July 11, 2017 in United States
Round1
LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.
Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.
Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Follow-up: decode with utf-16. It took quite a while for me to understand the rules.
Round4
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 Algorithm - 3of 3 votes
Answersn points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.
- Casper November 17, 2016 in United States
Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer C++ - 3of 3 votes
AnswersGoogle
- aonecoding January 05, 2018 in United States
Given an array a[] and an integer k, a[i] means flower at position a[i] will blossom at day i. Find the first day that there are k slots between two blooming flowers.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGoogle full-time phD candidate w/ work experience.
- aonecoding June 22, 2017 in United States
Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?
Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)
Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.
Q4.
Design merchandising product data storage service| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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 - 2of 10 votes
AnswersHow many times “Hello World” is printed by following program?
- whatsmyname1993 October 22, 2013 in India
int main()
{
if(fork() && fork())
{
fork();
}
if(fork() || fork())
{
fork();
}
printf(“Hello world”);
return 0;
}
a. 16
b. 20
c. 24
d. 64| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Operating System - 2of 4 votes
AnswersGiven a sorted array of integers, write a function that will return the number with the biggest number of repetitions.
- GeorgyBoy December 30, 2013 in Israel
(Asked to refine the solution to be more efficient)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays Coding Data Structures Problem Solving Sorting - 2of 4 votes
AnswersThere is an array of 3-tuple, in the form of (a, 1, 5). The first element in the tuple is the id, the second and third elements are both integers, and the third is always larger than or equal to the second. Assume that the array is sorted based on the second element of the tuple. Write a function that breaks each of the 3-tuple into two 2-tuples like (a, 1) and (a, 5), and sort them according to the integer.
- Nobody September 11, 2014 in United States
E.g. given (a, 1, 5), (b, 2, 4), (c, 7, 8), output (a, 1), (b, 2), (b, 4), (a, 5), (c, 7), (c, 8).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 4 votes
AnswersPartition a set of numbers into two such that difference between their sum is minimum, and both sets have equal number of elements.
- anonymous August 16, 2011
For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff = 17-13=4.
Does greedy work here? First sorting, and then picking smallest and largest to fall in set 1, and picking 2nd smallest and 2nd largest to fall in set 2.
I was asked to prove which I failed :(| Report Duplicate | Flag | PURGE
Google - 2of 4 votes
AnswersGiven a dictionary, and a list of letters ( or consider as a string), find the longest word that only uses letters from the string. [I didn't meet this question, what's the best solution?]
- Obiwana March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 4 votes
AnswersHow do you find the greatest 1000 elements in a list of a million elements? No other information given. What would be the runtime? Hint: You can do better than O(n log n). I didn't realize but it could be possible with Tree or Heaps.
- Ana April 23, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 4 votes
AnswersWe have a long string. We label some substrings with tags.
- Bill December 10, 2015 in United States
- A tag entry is [startIndex, endIndex, tag].
- Query: 1 or more tags
- Output: all blocks/ranges with all queried tags.
Example tag entries:
[23, 72, 0] // label [23, 72) with tag 0
[34, 53, 1] // label [34, 53) with tag 1
[100, 128, 0]
Query and Output:
0 => [23, 72], [100, 128]
0,1 => [34,53] // [34, 53) matches both tag 0 and 1
Give an efficient algorithm. Please describe your algorithm before posting code.
**Edit**: To add some difficulties, partial overlap is treated the same as full overlap, ONLY the overlapped part matches both tags. E.g. if we have entries:
[23, 72, 0] // label [23, 72) with tag 0
[10, 53, 1] // label [34, 53) with tag 1
Query and Output:
0,1 => [23,53] // [23, 53) matches both tag 0 and 1
Minor detials: Note in the comments we used open range on the right, i.e. if the string named "str", [23, 72, 0] includes str[23] but NOT str[72]; and there's no overlap between the following entries:
[23, 72, 0]
[10, 23, 0]| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 2of 4 votes
AnswersYou are given a matrix n rows, m columns where each row is sorted in increasing order. Find median of the overall elements. What is the time complexity?
- emb September 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 4 votes
AnswersWrite a method to return first five 10 digit prime numbers.
- saudip100 July 22, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 4 votes
AnswersGiven a complete binary tree, Find a Max element
- sLion June 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures - 2of 4 votes
AnswersGiven a sequence of numbers such that A[0] >= A[1] and A[N-1] >= A[N-2] find at-least one triplet such that A[n-1] >= A[n] <= A[n+1]. Better than linear time is expected.
- hsantosh71 June 15, 2013 in United States
Example: 9 8 5 4 3 2 6 7
Answer: 3 2 6| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 4 votes
AnswersGiven a screen with all pixels having one of two colors. Now I will click on a random pixel.
- X July 04, 2013 in United States
Then that pixel & all the adjacent pixels with same color should change the color to the second color.
adjacent = vertically or horizontally above or blow.
Edit: Question seem to be not clear to some ppl. Giving an ex:
Given below & clicked on 2nd row, 2nd col
W B W W B W
B B W W B W
W B B B W B
W B W W B B
Covert to
W W W W B W
W W W W B W
W W W W W B
W W W W B B| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 2of 4 votes
AnswersFind the minimum of every sub-array of size k in an array of size n.
- vgupta.2119 September 18, 2016 in India
O(n) solution required.| 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 - 2of 4 votes
AnswersDescription
- programming.kingdom June 07, 2015 in United States
A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate.
Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall.
For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.
In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.
Input
There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.
Output
The output contains one line for each data set, formatted as shown in the sample output.
Sample Input
4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1
Sample Output
The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 4 votes
AnswersImplement HashTable in java , especially hash function that should take care of any type of keys. The key may be integer or String or Object. But based on that the hash function should find index in the hashArray
- sivaji8 November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 4 votes
AnswersRound3 Google
- aonecoding January 16, 2018 in United States
For N light bulbs , implement two methods
I. isOn(int i) - find if the ith bulb is on or off.
II. toggle(int i, int j) - i <= j. Switch state (switch on if it's off, turn off if it's on) of every bulb in range i to j.
All bulbs are off initially.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
AnswersFind all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.
- aonecoding January 27, 2017 in United States
You may assume the codes given is valid.
Input is a single string, e.g.
String codes =
“/* file created by aonecode.com\\n” +
“ welcome to the tech blog*/ \\n” +
“//main method\\n” +
“public static void main(String[] args) { \\n“ +
“ System.out.println(“//welcome”); //output\\n” +
“}”
Output is a list of strings
List<String> ret =
[
“ file created by anecode.com\n welcome to the tech blog”,
“main method”,
“output”
]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
AnswerCongrats to aonecode's member F.L.
- aonecoding November 03, 2017 in United States
Got offers from - Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!
Thanks for sharing the interview experience with us.
Youtube Interview
- Phone: Find anagrams of string A from string B (sliding window)
- Phone: Find if two frames in a screen are equal. Frames may overlap. (equal method)
Onsite:
- LC41 first missing positive
- LC499+LC505 The maze
- LC161 one edit distance
- Similar to hangman but make guesses based on a dictionary.
Assume a dictionary has words - {house, morse, jesus} and ‘morse’ is the answer. If your first guess is ‘house’, output will be ‘_o_se’, which indicates 3 letters are correct. (Here the arrangement of letters does not matter. Your guess can be ‘co’ and if answer is ‘ok’ then the output is gonna be ‘_o’ which indicates letter ‘o’ in answer. )
Try to get the answer with minimum guesses.
(Interviewer expects pre-processing the dictionary. Key: letter; Value: frequency. Begin with combinations of most frequent letters first)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
Answerinterviewed by senior engineer
- aonecoding April 13, 2017 in United States
Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
Follow-up If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm