Google Interview Questions
- -7of 9 votes
AnswersGiven a file with a set of space separated numbers in a file write a program to remove duplicate rows. Two rows are duplicate if they contain the same numbers regardless of the order in which they occur. Constant time algorithm expected. LogN time is not good enough.
- hsantosh71 June 15, 2013 in United States
Given file:
1 2 3 4 5
3 6 7 8 9
2 4 7
1 5 3 2 4
Answer expected:
1 2 3 4 5
3 6 7 8 9
2 4 7| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -2of 4 votes
AnswersGiven 7 letter tiles and a dictionary of valid words, return the set of words that can be generated using 1-7 of those tiles.
- guotutu June 14, 2013 in United States for Youtube
Example:
letter tiles: SAPAPER
word dictionary: A AA AAA APE PEA PARE PEAR FEAR SPARE APPEARS REAPPEARS
would return: A AA APE PEA PARE PEAR SPARE APPEARS| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersEmployees in my company are complaining about elevator, saying its too slow... Lift operates for 50 floors
- anonymous June 14, 2013 in United States
I hire you and you have to tell me what is the problem and solutions to it.
Input:
Motor can't be changed
You can't get a new elevator as its too costly.
Get 5 matrices you would collect and how would you use them.| Report Duplicate | Flag | PURGE
Google Applications Developer - 0of 0 votes
AnswersHow would you design a movie search engine.
- anonymous June 14, 2013 in India
Think about both abstract and specific questions. How would you answer each of them.
ex: get me romantic movies, latest movies, movies with fight of no more than 10 mins.| Report Duplicate | Flag | PURGE
Google Applications Developer - 5of 5 votes
AnswersGiven a set of numbers, find the longest subset with consecutive numbers be it any order.
- anonymous June 14, 2013 in India
Input:
S = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11, 3}
we have 2 consecutive sets
s1 = {1, 2, 3, 4, 5}
s2 = { 8, 9, 10, 11}
Ans.
s1 = {1, 2, 3, 4, 5}| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 33of 39 votes
AnswersGiven an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
- LAP June 10, 2013 in United States
* The sub-arrays should not overlap.
eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16
I gave him o(n^2) algorithm but he was not satisfied.| Report Duplicate | Flag | PURGE
Google Algorithm - 6of 6 votes
AnswersIn a certain language which has same alphabets as in english language (ie. a-z), but the order of the alphabets is different (for eg 's' is the first character, 'g' is second, and likewise). Given a dictionary of this new language (which has words arranged according to new alphabetical order), FInd out the order of alphabets in this language.
- sgarg June 09, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Google SDE1 Software Engineer / Developer SDE-2 Algorithm - -3of 3 votes
Answersd1 = a1*x1 + b1*x2 + c1*x3
- 9tontruck June 07, 2013 in United States
d2 = a2*x1 + b2*x2 + c2*x3
d3 = a3*x1 + b3*x2 + c3*x3
Knowing all of a,b,c,d, find x1, x2, x3. As you might notice, this is high school math. But it's hard to write the code for solving it.
/*
/a1 b1 c1| /x1| /d1|
|a2 b2 c2|*|x2|=|d2|
|a3 b3 c3/ |x3/ |d3|
*/
double A[3][3], X[3], D[3];
X[0] = ?
X[1] = ?
X[2] = ?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a 2D rectangular matrix of boolean values, write a function which returns whether or not the matrix is the same when rotated 180 degrees.
- nr June 06, 2013 in United States for maps| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
AnswersGiven a 'friendship' graph, how would you generate friend suggestions for people, and how would you distribute the data across machines?
- nr June 04, 2013 in United States for google map| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 1of 1 vote
AnswersDesign a counter across all Google's servers.
- nr May 29, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersYou are given a doubly linked list and an array of references to nodes on the linked list. How many "blocks" are there present in the linked list?
- Aasen May 27, 2013 in United States
A "block" is defined as a group of nodes on the list with references directed at them and adjacent to eachother.
For example
[node #0] -><-[node#1] -><-[node#2] -><-[node#3]
node[] nodes = {ref_to_node#0, ref_to_node#2, ref_to_node#3};
Is two blocks because the first block is at node #0.
Node #1 has no incomming reference. Node #2 and Node #3 have references are are adjacent so it's just one block.
Implement using JAVA: Hint: You can try using a HashMap.
Thanks.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 0of 0 votes
AnswersGive me real time application of BST.....
- nr May 23, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 8of 10 votes
AnswersEliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
- jeso May 18, 2013 in Switzerland
Examples:
abc -> ac
ac->''
react->rt| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 0of 0 votes
AnswersAdd a number to array and if there is carry increase array size.
- msgsmg May 14, 2013 in United States
----------------------------------------------------------------------
For example input = {7,3,5,3,9} convert this to number 73539, add 1 so it becomes 73540 and convert to array {7,3,5,4,0}.
Array can be of any length, so you can't always represent array in form of in-built number format. So you have to do this summation in-place. Also, how would you increase array size in-case input = {9,9,9} so output = (1,0,0,0}
Assume, all elements of arrays are between 0 and 9.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersData-structure and algorithm used in Load Balancer??
- nr May 06, 2013 in United States
Explaining algorithm write code for it| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - -2of 2 votes
AnswersConsider a city with 50 locations each numbered from 0 to 49. Mr. XYZ runs a taxi service in a city. He has 25 Taxi’s to service the passengers. When passenger needs a taxi he makes a call to Mr. XYZ and give details like his current location as a source, and where he is willing to travel as a destination. He also tells max time he can wait for a taxi. In return Mr. XYZ either allocate a taxi to the passenger or tell him request can’t be satisfied within the given max_waiting time. Allocated taxi travels from its current location to the passengers pick-up point i.e. the source. This travel is termed as non revenue travel. Mr. XYZ charge passenger only for the distance from source to the destination. After dropping passenger to the destination taxi waits for call from Mr. XYZ to serve next passenger.
- surendrasalke4u May 01, 2013 in India
Let’s assume we know all TaxiHireRequests in advance. We also know the distance and time to travel between any two locations in the city.
Write a program which will choose the taxi’s such that sum of non_revenue distance travelled by all the Taxi’s is minimum and the number of unsatisfied requests are minimized. Also print the total non_revenew distance and number of unsatisfied requests.
pseudo helper structures.
struct TaxiHireRequest{
int Time Of Request;//Number of seconds from 12AM
int Source; // an int from 0 to 49
int Destination;// an int from 0 to 49
int Maximum waiting time // in seconds;
}[200]
struct Taxi{
int location;//an int from 0 to 49
bool isHired//true or false
}[25]
int Distance[50][50];
int Time[50][50];
// Extend the structure whenever required.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 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 - 0of 0 votes
AnswersFlatten a List<List<Integer>> in Java and implement the hasNext() and next() methods.
- Ana April 23, 2013 in United States
e.g. [[6,8],4] should return true when at 6, 8 and false at 4.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 0 votes
AnswersGiven a directed acyclic graph.How to represent it in the relational database for efficient retrieval of all the children nodes and all the parents of any node.(ex a->b here b is child of a and a is parent of b)
- ANONU April 14, 2013 in India| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGiven a string.Find the longest substring in it such that the substring contains only 2 unique characters.Ex- aabbcbbbadef Ans-bbcbbb
- ANONU April 14, 2013 in India| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersIn a party there are n different-flavored cakes of volume V1, V2, V3 ... Vn each. Need to divide them into K people present in the party such that
- ANONU April 14, 2013 in India
- Each member of party gets equal volume of cake (say V, which is the solution we are looking for)
- A given member should get a cake of single flavour only i.e. You cannot distribute parts of different flavored cakes to same member.
- Minimum volume of cake gets wasted after distribution so that means a maximum distribution policy| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersWrite a C program to search for a given pattern from various files in a directory without using grep or any other inbuilt command
- sharmapeeyush121 April 12, 2013 in India for Only_me| Report Duplicate | Flag | PURGE
Google Program Manager Unix - 4of 4 votes
AnswersI Got this Crazy Question on PHONE INTERVIEW AT GOOGLE:
- hhh April 11, 2013 in United States
Design and implement a class to generate random numbers in an arbitrary probability distribution given by an array of integer weights, i.e. for int[] w return a number, n, from 0 to w.length - 1 with probability w[n] / sum(w). Using an existing random number generator with a uniform distribution is permitted.
Example distribution:
w = 1, 2, 3, 2, 1
Example probabilities:
w / sum = 1/9, 2/9, 1/3, 2/9, 1/9
Example results:
n = 0, 1, 2, 3, 4
Documentation:
Class java.util.Random
public int nextInt(int n)
Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.
Parameters:
n - the bound on the random number to be returned. Must be positive.
Returns:
the next pseudorandom, uniformly distributed int value between 0 (inclusive) and n (exclusive) from this random number generator's sequence
Throws:
IllegalArgumentException - if n is not positive| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 0 votes
AnswersFind the most frequently occurring element in a BST. In this BST we can have leftnode<=rootnode<=rightnode.
- iwanna April 09, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 8of 8 votes
AnswersWrite a function which returns kth element from the tail in a linked list.
- hasan.tanpinar April 04, 2013 in United States| Report Duplicate | Flag | PURGE
Google Intern Linked Lists