Google Interview Questions
- -3of 3 votes
AnswersModify the following code:
def GenerateGraph(data): d = {} g = Graph() for word in data: for i in range(len(word)): bucket = word[:i] + '_' + word[i+1:] if bucket in d: d[bucket].append(word) else: d[bucket] = [word] for v in d.keys(): for word1 in d[v]: for word2 in d[v]: if word1 != word2: g.addEdge(word1,word2) return g
The objective is to find all combination of words by changing one letter at a time and adding to the graph if word exists in the dictionary.
- newbiepython January 28, 2018 in United States
We need to rewrite a different logic for the above code.| Report Duplicate | Flag | PURGE
Google Software Developer Python - 1of 1 vote
AnswersGive a string [] words,
- ajay.raj January 26, 2018 in United States
Find the shortest string [] containing the keyword inside.
example:
words: sky cloud google search sky work blue
keywords: sky blue
return: sky work blue| Report Duplicate | Flag | PURGE
Google Principal Software Engineer - 1of 1 vote
AnswerGiven an array, find the number of tuple such that A [i] + A [j] + A [k] = A [l] in an array, where i <j <k <l.
- ajay.raj January 26, 2018 in United States| Report Duplicate | Flag | PURGE
Google Data Engineer - 1of 1 vote
AnswerGiven a n-nary tree, check whether it is a mirror of itself (ie, symmetric around its center).
- ajay.raj January 26, 2018 in United States
class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}| Report Duplicate | Flag | PURGE
Google Jr. Software Engineer - -2of 2 votes
AnswerImagine a scenario where there are N cars on an infinitely long single-lane road. Each car has a unique, permanent integer speed ranging between 1 and N, inclusive (units are irrelevant). The cars can be placed in any order along the road and then told to start driving indefinitely. Let's assume that the cars are traveling from right-to-left. So the leftmost car is at the front. Given an ordering of N cars, construct an algorithm to return an array of cluster sizes
- ajay.raj January 26, 2018 in United States
N=4
[2, 4, 1, 3] -> [2, 2]
[2, 5, 4, 3, 1] -> [4, 1]
followup:
New car speed = N+1. Given an ordering of N cars, construct an algorithm to return an array of arrays of cluster sizes that will arise when the N+1 car is inserted. The ith row in the outer array corresponds to the cluster sizes that exist when the N+1 car is inserted into the ith index
new car speed = 5
[2, 4, 1, 3] -> [[1, 2, 2], [3, 2], [3, 2], [2, 3], [2, 3]]| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswersGiven one string s1, and then insert one char into this string at any place, to get s2, find the inserted char
- ajay.raj January 25, 2018 in United States
Could you do it in logn time| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGive you a 2xN board and two kinds of tiles: 1x2 (two squares across), 2x1 (two squares up) Ask how many ways you can fill the board.
** ** * * * * ** **
Follow up is the new four kinds of tiles: L shape in different angle, , ask you how many kinds of tiles are now six
- ajay.raj January 23, 2018 in United States| Report Duplicate | Flag | PURGE
Google Data Engineer - 0of 0 votes
Answersgive a binary matrix, 0 on behalf of the sea, 1 on behalf of the land, the val also represents the height of the altitude, if a cell is originally on land and is also surrounded by eight neighbor are on land, that cell become 2, each cell and its eight neighbor elevation cannot differ by more than 1. Return to the highest altitude can take altitude (special case is if the entire matrix is 1, then it is unlimited)
- ajay.raj January 23, 2018 in United States| Report Duplicate | Flag | PURGE
Google Data Engineer - 0of 0 votes
AnswerIn the range of 0-n, return all the numbers that in the reverse can be mistaken for another number. E.g. 18 -> 81. The corner case is not counting the same number, such as 101 and not 0 at the end of the figure such as 60 (because 09 is not 9)
- ajay.raj January 23, 2018 in United States
Public List<Integer> getNum(int n)| Report Duplicate | Flag | PURGE
Google Backend Developer - 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 - 0of 0 votes
AnswerGive a binary tree, each node has an extra information, that is, how many children he has,
Find the kth node val in the inorder transversal ,
Followup how to insert a node, such that this newly added node become the Nth node of the inorder binary tree's traversal
- ajay.raj January 21, 2018 in United Statesclass TreeNode{ int val; int NumberOfchildren; TreeNode left; TreeNode right; public TreeNode(int val){ this.val = val; } } public static int findKthOfInorder(TreeNode root, int k) {
| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswersGive a weighted n-nary tree and find the longest path from the root node to the leaf node
- ajay.raj January 21, 2018 in United States
class Node {
int id;
// connected node id, edge weight
Map <Integer, Integer> edges;
}| Report Duplicate | Flag | PURGE
Google Data 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 - 0of 0 votes
AnswersGiven a binary matrix, count the number of square that can be formed by all 0s
- ajay.raj January 20, 2018 in United States| Report Duplicate | Flag | PURGE
Google Data Engineer - 0of 0 votes
Answersgiven a string p, called order, such as abc, means a in front of b, and so on
- ajay.raj January 20, 2018 in United States
given a second string s, to determine whether it is follow the order of p, return boolean,
example If aaa return true,
If cba is false
If aaxyc is true, the letters that have not been seen in the order are skipped| Report Duplicate | Flag | PURGE
Google Data Engineer - 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 - 0of 0 votes
AnswersGiven a string as a datastream Iterator<Character>, find the length of the longest substring without repeating characters
- ajay.raj January 18, 2018 in United States
public String longestUniqueChars(Iterator<Character> chars)| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswerGiving start string and end string, determine if start string can finally reach to the same as end string with below rules.
- ajay.raj January 18, 2018 in United States
For example:
"R L _ _ L R L"
"_": the space is empty
"L": this can only swap with the empty letter _ on its left side
"R": this can only swap with the empty letter _ on its right side
So, "R L _ _ L R L" can change to "R L _ L _ R L" , and can continue change to (if you want) "R L L _ _ R L". from: 1point3acres.com/bbs
The question is given these rules and the start string and end string, could we change the start string to end string (unlimited # moves as long as it is valid).
For example:
"R _ _ L R _ R _L"
can be changed to
"_ R L _ _ R R L _"| Report Duplicate | Flag | PURGE
Google Java Developer - 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 - 1of 3 votes
Answersgiven a list of points in a rectangular coordinate system, seeking any two points, such that all the remaining points will be in only one side of the line.
- ajay.raj January 15, 2018 in United States| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswersGive a string, finds all duplicate substrings of length k
- ajay.raj January 13, 2018 in United States| Report Duplicate | Flag | PURGE
Google Backend Developer - -2of 2 votes
AnswerGive an array such as [1,2,2,2,0] every time you can jump 1 to a [i] step,
- ajay.raj January 13, 2018 in United States
If you can jump to 0, return false
if you go out to return true| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswerA group of people goes to eat together, each pay is not the same, then after they go home later, they each use mutual transfer so that everyone pay the same money.
- ajay.raj January 13, 2018 in United States
input is an int array that each person pay, Ask who the amount of money was paid when the transfer was done, such as B -> A $ 3, C -> A $ 1.| Report Duplicate | Flag | PURGE
Google Backend Developer - 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 - 0of 0 votes
Answersfind the last index of the last duplicate number in a sorted array
- ajay.raj January 11, 2018 in United States
ex
input: 1,2,5,6,6,7,9
output: 4(index)| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswersGiven a string, check if it is can be reorganized such that the same char is not next to each other, If possible, output a possible result
- ajay.raj January 11, 2018 in United States
example
input: google
one possible output: gogole| Report Duplicate | Flag | PURGE
Google Backend Developer - 0of 0 votes
AnswerGiven a dictionary, generate the shortest string, both palindrome and pangram.
- ajay.raj January 05, 2018 in United States
Each word can be used only once and unlimited words can be used.| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGive you a pattern (digit in the pattern matches the corresponding
- ajay.raj January 05, 2018 in United States
number of letters,
letter means match the letter itself),
a string to determine whether match:
ex:
abc -> 'abc' true
'1oc3' -> 'aoczzz', 'bocabc' true| Report Duplicate | Flag | PURGE
Google SDE1 - 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
Answersassuming there is a freeway, n cars on the road, each car has a different integer speed, but are in the 1-n range. Now give you an array that represents the speed of each car. The starting order of the vehicle is the order of the array, ask the final formation of several clusters, the size of each cluster is how much? It can be understood that, although the vehicle speed is different, but even behind the car faster than the previous car, because you cannot pass, the last must only travel at the speed of the previous car, which formed a cluster. For example [2,4,1,3], finally [2,4] is a cluster, [1,3] is a cluster.
- ajay.raj January 04, 2018 in United States
Follow up is now suppose you want to add a car, the speed of the car than other large, but not sure the car's starting order, so that the final output of each possible cluster (List of List). Requirements can be adjusted and call the previous function, but can only be called once| Report Duplicate | Flag | PURGE
Google SDE1
Open Chat in New Window