Google Interview Questions
- -1of 1 vote
AnswersReverse a linked list
- James666 June 06, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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 - 1of 1 vote
AnswersPrint (or return) the longest movie title found by successively matching the last and first words in each title, joining to form new titles, given a file containing a list of movie titles.
- gsgy11 April 30, 2018 in United States
For example: 'OF MICE AND MEN' and 'MEN IN BLACK' join to form 'OF MICE AND MEN IN BLACK'.
You could further join 'OF MICE AND MEN IN BLACK' wth 'BLACK MASS' to form 'OF MICE AND MEN IN BLACK MASS'.
The longest title I found (at 143 characters is): WENT TO CONEY ISLAND ON A MISSION FROM GOD BE BACK BY FIVE WIVES THREE SECRETARIES AND ME WITHOUT YOU CANT TAKE IT WITH YOU WERE NEVER LOVELIER| Report Duplicate | Flag | PURGE
Google Software Engineer - 4of 4 votes
AnswersFeb On-site Google
- aonecoding March 10, 2018 in United States
DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.
You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.
Follow-up: optimize 2d DP to 1d DP of linear extra space.
Follow-up: what if some cells are blocked
System Design
Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.
Interviewer seemed to be expecting more but time ran out.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGoogle Fucked up question.
- hprem991 February 21, 2018 in United States
Given a random list of appointments (Start Date , End Date). Find all the appointments that are colliding.
This pretty easy looking question screwed me up today.There are tons of edge cases, I couldn't complete em all and 45 minutes pass like 15 minutes while explaining and coding same time.| Report Duplicate | Flag | PURGE
Google Software Engineer Coding - 0of 0 votes
AnswersImplement a function that takes two strings, s and x, as arguments and finds the first occurrence of the string x in s. The function should return an integer indicating the index in s of the first occurrence of x. If there are no occurrences of x in s, return -1.
Example:
For s = "AGoogleInterviewIsAwesome" and x = "IA", the output should be
strstr(s, x) = -1;
For s = "AGoogleIsAwesome" and x = "IsA", the output should be
strstr(s, x) = 10.
Apparently, my solution was not efficient enough with string lengths that are 2000+:
- btmakusha February 19, 2018 in United States for Searchint findFirstSubstringOccurrence(String s, String x) { int sLen = s.length(); int xLen = x.length(); int tracker = 0; if (sLen == xLen) { if (s.equals(x)) { return 0; } else { return -1; } } else { if (xLen >= 1) { for (int index = 0; index < sLen; index++) { if (s.charAt(index) == x.charAt(tracker)) { tracker++; if (tracker == xLen) { return index - (xLen - 1); } } else { index -= tracker; tracker = 0; } } } } return -1; }
| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersWrite a function that takes two numbers as strings and returns the result as a string:
- NA February 12, 2018 in UK
mul(l string, r string) : string
Assume the numbers might be too large to be parsed into a variable of any numeric type the language has.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGive a decimal number, such as 123. Asking a total of smaller num than 123 made up by 1 and 0 composed of decimal numbers.
- ajay.raj February 06, 2018 in United States
111, 110, 101, 100, 11, 10, 1, 0.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersTo a word, and a map, map which is a word, ask this if a word is smash able? That is, you can smash one letter each time, and the rest of the letters can form a single word (the new word is still in the map) until it is completely hit.
- ajay.raj February 06, 2018 in United States
For example: sprint -> print -> pint -> pit -> it -> i -> ""| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersMinimum number of swaps of chars in only one string to make two strings the same
- ajay.raj February 02, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven a function that reads 4096 bytes from a file. write a new function which takes in a buffer and the number of bytes to be read from the user and uses the given function to write values into the buffer.
- fox January 22, 2018 in United States
//given
//returns the number of bytes read
private int read4k(int[] buffer, int offset)
//TODO:
// it should return the bytes read
public int readIntoBuffer(int[] buffer, int byteCount);| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswerGoogle
- aonecoding January 20, 2018 in United States
1st round
Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.
Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,
then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,
Prob(ball3) = 70% ;
Follow-up:
Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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 - 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 - 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
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 - 0of 0 votes
Answerdesign a zigzag iterator, implement the prev() and hasPrev function
- shuibizai10 December 26, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Java - 1of 1 vote
AnswersGiven an extremely large file that contains parenthesis, how would you say that the parenthesis are balanced?
The file cannot fit in the memory. How would you process the file and how would you store the intermediate results.
Walk me through the entire algorithm.
- CodeNinja December 14, 2017 in United StatesExamples: {[()]}, {[](){}}, [] are some valid examples.
| Report Duplicate | Flag | PURGE
Google Software Engineer Stacks - 0of 2 votes
AnswersGiven a matrix of each element is the height of the location, the side of the matrix has a river height h, water diffuse matrix results,
- ajay.raj December 14, 2017 in United States
Follow up If there is a place where there is not drowning a person and a dog, people want to reach the dog's position without water, the river is highly uncertain,
Ask the maximum height h such that the number of steps taken by a person is less than or equal to a given k. Traverse the height h,| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersConsider there is a streaming service, which outputs Log object to your service. The Log object has fields like {timeStamp, userId, hashtag(used in the tweet), @userAddressUsedInTweet} etc. Imagine this streaming service has very high QPS. Design your service in such a way that it can output top K userId's within a configurable time window(example: last 1 hour, last 24 hour etc). This service should be extendable to get any top K category (Example: TopK userId's, TopK hashtags etc). What would you use to design such a service. Top K is defined by its frequency, example: 1,2,3,4,1,2,1,2,1,1,5 are the userIDs then the top 2 users are userId 1 and 2.
- lks December 08, 2017 in United States
@EdgeCase:
1. Take into consideration how to store data in that window to get the topK user's.
2. The service should be highly available and should return the results quickly
3. Design and implement this service| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersC * R 2-D array, there are R, G, B, Y four types of elements, if no vertical and horizontal has three adjacent elements are the same type, then the 2-D array is valid
- ajay.raj December 07, 2017 in United States
Let write a function to determine whether a 2-D array is valid.
follow-up how to generate such a valid 2-D array| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
Answers
- ajay.raj December 06, 2017 in United StatesGive an Node { Node getLeft (); Node getRight (); String toString (); } Give a root node Node root * / \ + - / \ / \ 1 2 3 4 Return (1 + 2) * (3-4) If (1 + 2) + (3 + 4) does not need to be bracketed Only leaf nodes are numbers followup Give you * + 12-34 to return this tree
| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersA city bus station information, example, bus No. 1 stops at abcd station, bus No. 2 stops at cefg station. Then a-d you only need to take No. 1, thus return 1, a-g is 2, because you need to transfer at station c,
- ajay.raj December 01, 2017 in United States
ask for a minimum bus you need to take to reach to another station. You can design any data structures.| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersGiven a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.
- md.lisul.islam November 22, 2017 in United States
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersWrite code to find unmatched parentheses and return it in the below format:
- 1080ti November 18, 2017 in United States
((a) -> -10a1
(a)) -> 0a1-1
(((abc))((d))))) -> 000abc1100d111-1-1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.
- Vijay November 17, 2017 in India
Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5
Target number : 11
Output : 9
Target Number : 4
Output : 5| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays Coding Data Structures - 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