Google Interview Questions
- 0of 2 votes
AnswersA robot on a plane has 2 types of commands:
1. move forward by X units (X is integer 0 <= X <= 10000 )
2. rotate by X degrees (X is integer in range [-180, 180] )
A robot looks likedef robot(commands): while True: for command in commands: execute(command)
Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.
Example:
- emb June 06, 2016 in United States[move(10), rotate(180), move(10)] -> answer is yes [move(10), rotate(45), move(10), rotate(-45), move(10), rotate(45)] - answer is no
| Report Duplicate | Flag | PURGE
Google Software Developer Brain Teasers - 3of 3 votes
Answers# take an array and print non over lapping in order pairs. example:
- thegeek21 June 05, 2016 in United States# [1,2,3,4] => input # output below is in order combination # (1234) # (1)(234) # (1)(23)(4) # (1)(2)(34) # (12)(34) # (12)(3)(4) # (123)(4) # (1)(2)(3)(4)
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a range [first, last], initially white. You need to paint it black.
For this purpose you have a set of triples
[(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).
Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible
Example:[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]
Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.
Another example:[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]
answer is -1, because it's impossible to color whole range.
- emb June 05, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 3of 3 votes
AnswersGiven an array of length N and an integer K, sort the array as much as possible such that no element travels more than k positions to its left - an element however can travel as much as it likes to its right.
- testing@123 June 01, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - -3of 3 votes
AnswersWrite program that takes integer, deletes one of two consecutive digits and return greatest of all results.
- josearturodelosangeles June 01, 2016 in United States| Report Duplicate | Flag | PURGE
Google Applications Developer Coding - 0of 0 votes
AnswersGiven deck of cards let se 50 cards, now all are thrown on a table, after throwing some cards of them are now with face up and some are with face down, tell the probability of sum of all the face up cards is divisible by 7.
- Ajay Kumar May 29, 2016 in United States for Google Docs
Assume cards from 1 to 10, Answer should be generic so that we can get results for any number of cards, don't compare cards with playing cards, cards can be numbered from 1 to n| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven k - which is the number of bits, print all the possible combinations of numbers formed by printing all numbers with one bit set, followed by two bits set, ... upto the point when all k-bits are set. They must be sorted according to the number of bits set, if two numbers have the same number of bits set then they should be placed as per their value.
- theconqueror May 27, 2016 in India
For example if K=3
Output:
000, 001, 010, 100,101, 110, 011, 111
0 bits set, followed by 1 bits set followed by 2 bits set followed by 3 bits set.| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersGiven an MxN matrix, determine whether a path can be drawn through every node in the matrix such that the end node is next to the start node, and each node is only touched once.
- geekofthegeeks May 23, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a binary tree, find the largest subtree having atleast two other duplicate subtrees .
- geekofthegeeks May 22, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven the following decoder, write the encoder. (The encoder should be written to compress whenever possible):
- geekofthegeeks May 22, 2016 in United States
p14a8xkpq -> p14akkkkkkkkpq
(8xk gets decoded to kkkkkkkk. The only other requirement is that encodings be unambiguous)
Note that the String can have any possible ascii character| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
Answersgiven 2 strings A and B. generate all possible solutions when B is merged in A.
- JerryGoyal May 22, 2016 in India
Ex: A = "hey"
B: "sam"
then solutions are :
heysam,hseaym,hesaym,sahemy etc.
notice that order should be the same for both of strings while merging.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 4 votes
AnswersTake an example of the traditional Iterator interface which has the following methods
- lks May 17, 2016 in United States
Interface Iterator<E>{
public boolean hasNext() {}
public E next() {}
public E remove() {}
}
You are given a list of iterators. You have to design a InterleaveIterator class which implements this
interface and implement the methods:
hasNext() and next()
such that these 2 methods returns interleaved values for the list of iterators:
Implement:
class InterleaveIterator<E> implements Iterator<E>{
@override
public boolean hasNext() {}
@override
public E next() {}
}
Example:
ArrayList<Integer> i1 = [1,2,3,4,5].iterator()
List<Node> i2 = [n1,n2].iterator()
Collection<E> i3 = [e1,e2,e3].iterator()
next() method of InterleaveIterator, should return in this sequence [1,n1,e1,2,n2,e3,3,e3,4,5]
Make this InterleaveIterator class generic and make sure that the class can accept a list of iterators
and interleave them| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 0of 2 votes
AnswersGiven a list of pies (and the number of slices in each pie) calculate the maximum number of slices that nPeople could receive if each person got the same amount of slices and did not get slices from more than 1 pie.
- Dinkleberg May 09, 2016 in United Statespublic int getMaxSlices(List<Integer> pieSlices, int nPeople) { // return answer }
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -15of 17 votes
AnswersIs Golang a good choice for coding interviews?
- amit April 20, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer - -16of 18 votes
AnswersDoes Google/Microsoft/Amazon/Facebook allow Golang in coding interviews?
- amit April 20, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersYou are given an scenario where there is an Worker object. Each Worker object has one mandatory field unique id workerId and their are few other non unique and not mandatory Ids : DeptId and UnitID.
- CareerCupUser1 April 16, 2016 in United States
Design an cache for your Worker objects considering the fact that most of the queries on your cache will be on unitId. If the there is an query for an Worker which is not available in your cache then that data will be fetched from the server.
Design an cache such that there will be minimum number of server calls. Imagine there are 100;s of such non unique ids non mandatory Ids in the Worker object and you have to design the cache so that your client can query on any given id with minimum calls to server.
Your Worker object looks like this:
Worker1=> workerid=1, deptId=>765, unitId=>123 Name=“” Surname=“” Data=“”
Worker2=> workerid=2 , deptId=>765 Name=“” Surname=“” Data=“”
Worker3=> workerid=3, unitid=>123 Name=“” Surname=“” Data=“”
so when your client queries using unitId getWorkersbyUnitId(123) it should return Worker1 and Worker3.
If query is on deptId 765 then it should return Worker1 and Worker2
You can assume there is never an query on individual workerId.
other information given while discussion is you can query the server using any id and all the worker objects of that id will be fetched by that single call: Example there are 10 workers associated with untId: 99 then server call to getserverUnitIdWorkers(99)-> will output list of 10 workers. Each unitId or any other non mandatory id has approximate 8 to 10 workers associated with it. And there are millions of such unitIds.| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Cache - 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 - 8of 8 votes
AnswersYou are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating red-black-red-black edges. That is, no path from root to leaf must contain sequential black-black edges or red-red edges.
- emb April 12, 2016 in United States
You are guaranteed that such spanning tree exists.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - -1of 1 vote
AnswersProvide a function that allow to compare two strings lexicography, having in mind that these words may contain digraphs (two letters together represents a single one i.e in Spanish ch is a single character ).
- urodba April 07, 2016 in United States
This in order to be able to sort a list of words.| Report Duplicate | Flag | PURGE
Google Software Developer Sorting - 1of 1 vote
AnswersA list L is too big to fit in memory. L is partially sorted. Partially sorted in a specific way: x-sorted L[i] < L[i+x]. Any element is at most x indices out of position.
- jss_777 March 30, 2016 in United States
You can look at the condition in a different way too..
L[i] >= L[i-x]
Sort the list L.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer - 9of 9 votes
AnswersGiven a packed file with 1Tb of 64-bit doubles (first 8 bytes are first double, next 8 bytes are next, etc) find the exact value of median. For simplicity assume the number of doubles is odd.
- emb March 19, 2016 in United States
You can't modify the file and you have only 8Gb of free memory.
Update: you may use no more than two passes through file and your algorithm shouldn't rely on some nature of file - it should work in all cases.| Report Duplicate | Flag | PURGE
Google Software Developer Coding - 0of 0 votes
AnswersGiven an array of numbers, find the longest alternating subsequence. That is, a subsequence [a1, a2, a3, ..., ak] where a1 > a2, a3 < a2, a4 > a3, ... or vice versa (Graphically looks like /\/\/\... or \/\/\/\....
- emb March 19, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersGiven a string S, print the longest substring P such that P > S lexicographically.
- emb March 16, 2016 in United States
You may assume that such substring exists.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an arbitrary tree starting at “root” where each node contains a pair of values (x, y), write a boolean function find(Node root, int x, int y) that returns true iff
- Basu March 08, 2016 in United States
* x is equal to a value "x" of any node n1 in the tree
* and y is equal to a value "y" of any node n2 in the tree
* and both n1 and n2 are at the same level in the tree
boolean find(Node root, int x, int y)
Example:
(1,120)
/ | \
/ | \
/ | \
(5,15) (30,70) (80,110)
/ | \ |
/ | \ |
/ | \ |
(35, 40) (45,50) (55, 65) (90, 100)
boo == true
find(root, 45, 100) == true
find(root, 30, 100) == false
find(root, 30, 70) == true
find(root, 70, 30) == false| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a 2D matrix of integers, sort it such that:
- every row is sorted in ascending order from left to right
- every column is sorted in ascending order from top to down
- all items in the same row are unique
You may assume the input matrix is always valid, meaning that such a sort is always possible.
For example:
for input matrix1 3 5 3 2 4
the output could be any of the following:
valid output #1:1 3 4 2 3 5
valid output #2:
1 2 3 3 4 5
valid output #3:
1 3 4 2 3 5
One kinda trivial solution is to sort the 2D matrix column wise. For example, you can push all items into a heap and pop one after another, putting it into the matrix column after column. This would be a `O(n lg n)` time complexity where `n` is the number of items in the matrix, i.e., `n = rows*cols`. Can you design a more efficient algorithm?
- zhtt2009 February 29, 2016 in United States
Follow-up: What if all items in the same column are also required to be unique?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersWrite SQL query to get the earliest flight from A to B.
- zyz February 23, 2016 in United States| Report Duplicate | Flag | PURGE
Google Analyst SQL - 1of 1 vote
AnswersGiven an input BST, find the minimum value difference between any two nodes in the tree.
- a.asudeh February 18, 2016 in United States
e.g:
....10
5 16
........12 20
answer: 2 (it happens between nodes 12 and 10)
describe the test cases you would use here?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 0of 0 votes
AnswersGiven a specific type of DAG that forms a pyramid (the links have up-down direction), in which the node labels are integer, find the path that has the maximum sum of node values. what is the time/space complexity of the algorithm?
- a.asudeh February 18, 2016 in United States
e.g:
3
/ \
9 4
/ \ / \
1 8 2
/ \ / \ / \
4 5 8 2
answer: <3,9,8,8>, sum = 3+9+8+8=28| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm