Google Interview Questions
- 1of 1 vote
AnswersGiven a directed graph G, write a program to detect the cycle in it.
- jp January 06, 2011| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 1of 1 vote
AnswersFind all triplet that sum to a given value in an array of integers, given that the array is too big to fit into memory
- intuiti July 19, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 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 - 1of 1 vote
AnswersGiven a list points on a 2d plane, find
- ajay.raj November 01, 2017 in United States
largest rectangular area that can be formed
for the rectangle only considers those parallel to x and y| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGenerate a random number with UNIFORM DISTRIBUTION between [0,n) where n is given and excluded list is given. The randomly generated number should belong to the range [0, n) but should be excluded from the given excluded list. For example, n = 10 and excluded list ={2,3,0} then the random number should be from {1,4,5,6,7,8,9} such that any number from the list {1,4,5,6,7,8,9} has UNIFORM probablility of occuring
- xyz July 31, 2017 in United States for NEST| Report Duplicate | Flag | PURGE
Google Software Developer - 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 - 1of 1 vote
Answerslongest common subsequnce: given two lists, find the longest sublist (in order) that is the same
- adam2008 February 22, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersLiar, Liar
- David June 28, 2011
As a newbie on a particular internet discussion board, you notice a distinct trend among its veteran members; everyone seems to be either unfailingly honest or compulsively deceptive. You decide to try to identify the members of the two groups, starting with the assumption that every senior member either never lies or never tells the truth. You compile as much data as possible, asking each person for a list of which people are liars. Since the people you are asking have been around on the board for a long time, you may assume that they have perfect knowledge of who is trustworthy and who is not. Each person will respond with a list of people that they accuse of being liars. Everyone on the board can see that you are a tremendous n00b, so they will grudgingly give you only partial lists of who the liars are. Of course these lists are not to be taken at face value because of all the lying going on.
You must write a program to determine, given all the information you've collected from the discussion board members, which members have the same attitude toward telling the truth. It's a pretty popular discussion board, so your program will need to be able to process a large amount of data quickly and efficiently.
Input Specifications
Your program must take a single command line argument; the name of a file. It must then open the file and read out the input data. The data begins with the number of veteran members n followed by a newline. It continues with n chunks of information, each defining the accusations made by a single member. Each chunk is formatted as follows:
<accuser name> <m>
followed by m lines each containing the name of one member that the accuser says is a liar. accuser name and m are separated by some number of tabs and spaces. m will always be in [0, n]. All member names contain only alphabetic characters and are unique and case-sensitive.
Example input file:
5
Stephen 1
Tommaso
Tommaso 1
Galileo
Isaac 1
Tommaso
Galileo 1
Tommaso
George 2
Isaac
Stephen
Output Specifications
Your output must consist of two numbers separated by a single space and followed by a newline, printed to standard out. The first number is the size of the larger group between the liars and the non-liars. The second number is the size of the smaller group. You are guaranteed that exactly one correct solution exists for all test data.
Example output:
3 2| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of Integers, find out how many combinations in the array, satisfy the equation x+y+z=w, where x,y,z and w belong to the array and idx(x)<idx(y)<idx(z)<idx(w). Elements are unique.
- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Arrays - 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 - 1of 1 vote
AnswersGiven a sorted distinct array of integers and a key K. C closest elements to K are in range [L,R] inclusive, L<=R. Return L as the left index of C closest elements to K.
- anonymous August 04, 2017 in United States
For example:
A = [1, 2, 5, 8, 9, 13]. K = 8 and C = 4. The result L = 3 because 4 closest elements to 8 are [5, 8, 9, 13]| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 1of 1 vote
AnswersFind two strings are meta string or not
- ashishsaraswat.iips April 18, 2017 in India
for eg:-
Converse
Conserve
are meta strings because if we swap s and v in the string both string will become equal. If swapping of more than one pair can be done then it is not a meta string| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersInsert a element in a sorted circular linked list
- zealswap March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite code to convert a hex string to a byte buffer
- AM January 13, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Bit Manipulation - 1of 1 vote
AnswersLonely Pixel
- acoding167 April 22, 2019 in United States
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersFind top 10 most frequent words in the past hour, day and month from twitter service. Given a streaming data such as tweets from twitter service, the objective is to find the top 10 frequent words in the past hour, day and past month at any instant of time.
- Pedro August 07, 2018 in United States for Maps| Report Duplicate | Flag | PURGE
Google Software Developer - 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
AnswersWrite a class to take in a large arbitrary number, also provide a function to increment the number. The number will be passed on as an array of integers.
- pushpinder2751 June 17, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersLet's discuss on topic "solution to string problems using suffix tree & suffix array"
- jobseeker July 05, 2011| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersYou need read a lot of records, you don't know how many records here
- yizhang2004 July 17, 2009
before you complete it. After you read all those records, you need select
one record randomly.In another words, every record has same chance to be
selected. The memory is limited, that means you cannot store all those
records at one time.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou have a table :
- mukesh.scorp October 23, 2019 in United States
Rule1 Rule2 Rule3 Value
A1 B2 C3 40
A1 B1 C1 20
A2 B2 C2 10
A1 B1 C1 40
* B1 * 20
A5 B2 * 10
Now if I have a condition A1 && B2 && C3 i will get output as 40.
If I input A1 && B1 && C1 I will get two results 40 and 20 here there the rule is ambiguous.
"-" in table means any rule, 5th row matches with any row with B1 as rule2, so there is also ambiguity in result.
Now given that table as input (m * n) where n is number of available rules combination (here its 6) and m rules (3 in this case) , output if the table is ambiguous i.e it will output two different result for same query.| Report Duplicate | Flag | PURGE
Google Backend Developer Algorithm - 1of 1 vote
AnswersGiven a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.
- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x axis, every square on their y axis, and every square that lies in their diagonal (think of a Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…
- ad09 October 16, 2016 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersI was asked in an interview: You are given a dump file of IPv4 addresses. You are to find 4 most common occurring subnets. Lets say an IP address if of type a.b.c.d you have to find most common occurring four subnets of the form,
a.*.*.*
a.b.*.*
a.b.c.*
a.b.c.d
Here * matches anything.
My first solution was build an in memory hashtable. Given an IP address a.b.c.d split it as ["a","b","c","d"] and add "a", "a.b", "a.b.c", "a.b.c.d" to the hash table and count it. [There are optimizations possible like considering the entire IP address as a 32 bit unsigned integer and count it with masks and shifts]
Then the question got extended: "assume you can never hold everything in memory, how would you solve it?" Now, the very first solution that I could say was to do an external sort and then count it.
The next solution I gave was to split the IP addresses into buckets. The algorithm was,while there is an IP IP <- an IP address a <- first quadruple push IP to bucket[a]
The bucket which has maximum elements would give me the a.*.*.* solution. Now take each bucket and do the same. Even though this might give the correct result, in worst case I might end up having 255^4 buckets.
- miscanon July 15, 2016 in United States
This is indeed an open ended question with more than one correct answer. What would be the best way to solve this?| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 1of 1 vote
AnswersGiven a BST and a number x, find two nodes in the BST whose sum is equal to x. You can not use extra memory like converting BST into one array and then solve this like 2sum.
- yoyiyoshi November 14, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersEveryone knows that finding a loop in the single linked list is using runner and follower method. Could you provide mathematical proof of correctness for it and why it works. I said something like induction hypothesis. Someone help me with the correct answer.
- Madan November 27, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 1 vote
AnswersDesign a web counter to give how many hits per second, per minute and per hour (i.e., what kind of data structure and algorithm would you use to do this?).
- herakleides October 24, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
Answersyou have a bag full of airplane tickets with various destinations. given two destinations find those tickets in the bag and give the cheapest routing in the least time possible
- code.monkey July 29, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
- aonecoding4 January 30, 2019 in United States
Follow-up: If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?| Report Duplicate | Flag | PURGE
Google Software Engineer