Google Interview Questions
- 1of 1 vote
AnswersThere is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.
- shivamdurani220 October 09, 2018 in United States
You can keep inputting the password, the password will automatically be matched against the last n digits entered.
For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.
Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.| Report Duplicate | Flag | PURGE
Google SDE-2 - 1of 1 vote
AnswersDetermines whether two strings containing backspace keys are the same.
- ajay.raj December 17, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersFind the shortest path between a start node and end node in a undirected +ve weighted graph.
You are allowed to add at max one edge between any two nodes which are not directly connected to each other.
ex:
From | To | Weight
1 2 2
1 4 4
2 3 1
3 4 3
4 5 1
start node = 1, end node = 5.
extra edge weight = 2.
- JerryGoyal October 15, 2016 in United States1----(2)----2 | | | | (4) (1) | | | | 5-(1)-4----(3)----3 In this case answer would be 3 (from 1 - > 5 - > 4) Solution: 1----(2)----2 /| | / | | (2)/ (4) (1) / | | / | | 5-(1)-4----(3)----3
| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersHow would you design and implement a large social network's (G+ or fb) friend recommendation system ?
- P December 08, 2011 in India| Report Duplicate | Flag | PURGE
Google Large Scale Computing - 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 - 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 - 1of 1 vote
AnswersImplement multithreaded rm -r <folder>, i.e recursively delete files/folder under <folder> by walking through it and assume there can be billions of files under folder and you can only delete folder if all contents in it are first deleted
- Erik August 17, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersRound 5:
- aonecoding August 03, 2017 in United States
Given a set of synonyms such as (fast, quick), (fast, speedy), (learn, study), decides if two sentences were synonymous.
(The sentences were structurally the same and has the same number of words in them.
The synonymous relation [fast ~ quick] and [fast ~ speedy] does not necessarily mean [quick ~ speedy].)
Follow-up:
If the synonymous relation passes down so that [fast ~ quick] and [fast ~ speedy] implies [quick ~ speedy], decide if two sentences were synonymous.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersLast Monday phone interview of G.
- aonecoding May 27, 2017 in United States
Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 1of 1 vote
AnswersGiven multiple strings like "candy", "carry", "dummy", etc. These strings are stored as c3y, c3y and d3y etc. Write a function which returns a boolean if the string (like "carry" is unique in the dictionary)
- AirWind April 15, 2016 in United States
bool
isUniqueDictionaryWord(char *str)
If the strings are in a file and you load it when the program loads, how will you store it ?| Report Duplicate | Flag | PURGE
Google Software Engineer Hash Table - 1of 1 vote
AnswersCreate a maze.
- marinalepi March 06, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Problem Solving - 1of 1 vote
AnswersImplement memmove .
- siri.paddu December 05, 2012 in United States
Dont use extra memory.
How to optimise it further?| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersYou have a plot with a limited amount of points on it.
Find the cluster of points, which contains the biggest amount of point grouped together.
Conditions:
The cluster means, that points are placed not farther than 5 units (Can be measured px, cm, etc.) between each other. The distance is calculated by where|x1-x| < 5
and
|y1-y| < 5
The cluster should contain at least 3 points.
- denis.zayats May 30, 2019 in United States
If there are a few clusters with the same amount of points - return all of them.
Example:
The points are:
(15,116), (1345, 123), (456, 11), (34, 17), (19, 112), (556, 111), (454, 15), (12, 120).
In this case, the best cluster is (15,116), (19, 112), (12, 120)| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 1of 1 vote
Answersgiven a string, and integer k, check if this string contain all the binary string of length k
- ajay.raj November 24, 2017 in United States
For example, k is 2, then 00,10,01,11.
Followup 1, find a string that can contain all binary string of length k.
Followup 2, find a shortest string that can contain all binary string of length k.| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
Answerswrite a function that randomly return only odd number in range [min, max)
- ajay.raj April 11, 2017 in United States
public int getRandomOdd(int min, int max){}| Report Duplicate | Flag | PURGE
Google Software Developer - 1of 1 vote
AnswersGiven a sparse matrix, implement below two methods:
- starlord September 01, 2016 in United States
void set(int row, int col, int val) /*Update value at given row and col*/
int sum(int row, int col) /*give sum from top left corner to given row, col sub-matrix*/| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersDesign a locking mechanism for a distributed system .
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Software Design - 1of 1 vote
AnswersDesign a data structure which should have following operation. Insert, Delete, Random access
- hm August 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 1of 1 vote
AnswersAll Google search queries from all over the world are logged into a file.Now this file has billions of search queries in all languages which are interleaved.
- Sachin March 05, 2009
Select 1 million Hindi queries from this file, such that all the Hindi entries in the file have equal probability of getting picked.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Large Scale Computing - 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 - 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 - 1of 1 vote
Answersclass EncodingChecker {
- ajay.raj December 17, 2017 in United States
EncodingChecker (String pattern) {...} // constructor
boolean isEncoded (String s) {...} // for any string s, check whether s is encoded from pattern, see below
}
pattern = 'abcabc'
s = '123123' -> True
= 'cbzabc' -> False
= 'xyzxyz' -> True
Second question: If the pattern is not one but one million, how to write isEncoded?| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGiven a function that returns 0 and 1 with a probability of fifty percent, use this function to generate a random number between a and b with uniform distribution
- ajay.raj December 02, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersRound 4:
- aonecoding August 03, 2017 in United States
Implement a class Employment with these 3 methods: assignManager(p1, p2): assign p1 as p2's manager. beColleague(p1, p2): make p1 and p2 peer colleagues. isManager((p1, p2): decide if p1 is the manager of p2.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven the village of a map represented as a 2D grid containing houses,bushes and open-spaces, write a program to find a point for conducting a meeting in the map. Such point should be minimum from all the houses in the village.
Eg.# # # # # # # A # # B # # # # # # # C # # # # # #
# -> represents the bushes
- angry_scorpion November 10, 2016 in United States
A, B, C -> position of houses
I provided a O(n*a*b) approach, where n-> no. of houses , a,b->dimensions of the grid.
The interviewer asked me for some special cases. Can it be done more efficiently?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersConsider the problem of neatly printing a paragraph on a printer. The input
- neo July 14, 2011
text is a sequence of n words of lengths l1, l2, . . . , ln, measured in
characters. We want to print this paragraph neatly on a number of lines that
hold a maximum of M characters each. Our criterion of “neatness” is as
follows. If a given line contains words i through j, where i ≤ j , and we
leave exactly one space between words, the number of extra space characters
at the end of the line is M − j +i − Sum(lk)(from k = i to j) , which must
be nonnegative so that the words fit on the line. We wish to minimize the
sum, over all lines except the last, of the cubes of the numbers of extra
space characters at the ends of lines. Give a dynamic-programming algorithm
to print a paragraph of n words neatly on a printer. Analyze the running
time and space requirements of your algorithm.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer 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 directed graph and a node , find the shortest cycle in a graph with given node .
- saurabh January 23, 2019 in India| Report Duplicate | Flag | PURGE
Google Software Developer Coding