Google Interview Questions
- 0of 0 votes
AnswersBest Time To Sell Stock but with 1 restriction: after you sell your stock, you cannot buy stock on next day.
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer 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 - 0of 0 votes
AnswersHow can you read from disc such that you optimize the latency of the data read/writes?
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Computer Architecture & Low Level - -1of 1 vote
AnswersTwo political parties are contesting in the elections in the N number of states in the country. Each party wins some seats every year in each state. After the current elections are over we have the result of both the parties with their number of seats won in each state.
- Avinash Paritala November 21, 2015 in India
The two parties are considered equal if they win the same number of seats in the N states in any order. Otherwise, they are considered unequal. Input/Output Specifications
INPUT: 1) It is an array of N integers depicting number of seats won by party one in each state. 2) It is an array of N integers depicting number of seats won by party two in each state. 3) An integer containing number of states (N).
OUTPUT: Equal/Unequal/Invalid
Equal: if political parties are equal Unequal: if political parties are unequal Invalid: if any party has invalid number of seats in any state
Examples
Example 1:
Two parties contested in seven states Seats won by party one in all the seven states: {12,11,5,2,7,5,-11} Seats won by party two in all the seven states: {5,12,5,7,11,2,11} The party two has an invalid number of winning seats(-11). So the output will be "Invalid".
Input :
1) {12,11,5,2,7,5,-11}
2) {5,12,5,7,11,2,11}
3) 7
Output: Invalid
Example 2:
Two parties contested in seven states Seats won by party one in all the seven states: {12,11,5,2,7,5,11} Seats won by party two in all the seven states: {5,12,5,7,11,2,11} Both the parties are equal because they have got 11(2 times each), 5(2 times each),7( 1 time each), 2(1 time each), 12( 1 time each other outputs (0 times each).
Input :
1) {12,11,5,2,7,5,11}
2) {5,12,5,7,11,2,11}
3) 7
Output: Equal
Example 3:
Input :
{12,11,5,2,7,5,11}
{5,0,5,7,11,2,11}
7
Output: Unequal| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 4 votes
AnswersGiven that you have a graph with an even number of points, how do you find two points that equally subdivide the graph?
- Ray November 21, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a list of integers, find the highest value obtainable by concatenating these together.
- GAGA November 20, 2015 in United States
For example, given 9, 918, 917 - The answer is 9918917.
But given 1,112,113 - The answer is 1131121| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersRahul is playing a very interesting game. He has some N different type of match boxes. All match boxes may have different number of matchsticks (S1, S2, S3... Sn).
- Avinash Paritala November 19, 2015 in India
Rahul chooses two random numbers F and K. K should be less than N. The game is that Rahul wants to select any K match boxes out of N match boxes such that total number of matchsticks in these K selected match boxes should be multiple of F.
At the sametime Rahul wants that sum matchsticks of all the selected match boxes should be minimum possible.
Input Specifications:
1) Array S = {S1,S2,S3,...Sn} of size N corresponding to the number of match sticks in N matchboxes(0<=N<=1000}
2) F-Value (as explained above)
3) K-Value ( as explained above)
Output:
1 2 3 4 5 Here 3 is the number of matchsticks in matchbox I II III IV V minimum possible total number of matchsticks such that the conditioned explained in the problem statement is satisfied. Output -1 if it is not possible or invalid input.
For example, there are 5 match boxes i.e., N = 5
Let's say K is 3 (Rahul has to choose any 3 matchboxes)
Let's say F is 5(sum of matchsticks in 3 selected matchboxes should be multiple of 5).
Rahul can choose II, III and V matchboxes which would give the total sum of 10 which is multiple of F i.e., 5. And 10 is the minimum possible matchsticks possible in the above case.
So you have to answer the minimum possible matchstick(sum of the matchsticks in the selcted matchboxes) but the conditions given above should be satisfied.| Report Duplicate | Flag | PURGE
Google Software Engineer - 4of 4 votes
AnswersYou are given two arrays of length M and N having elements in range 0-9.Your task is to create maximum number of length K from elements of these two arrays such that relative order of elements is same in the final number as in the array, they are taken from i.e. If two elements a,b are taken from array1 and and a comes before b in array1 so in the final number a should come before b (Relative order kept same) .
- Rahul Sharma November 18, 2015 in United States
Example: N=4 and M =6
Array1 = { 3 , 4 , 6,5}
Array2 ={9,1,2,5,8,3}
Suppose K = 5, then number will be {9,8,6,5,3}
You can see {9,8,3} are taken from array2 in the same order as they are in Array2. Similarly {6,5} are taken from Array1 in the same order and number 98653 is maximum possible number.| Report Duplicate | Flag | PURGE
Google Research Scientist Algorithm - 3of 3 votes
AnswersI had two interviews with Google
- sameer November 17, 2015 in India
first) one with US person...he asked decent question with lot of hints...experience : positive
and
then second) interview with person from India...I prepared for one month but he asked me very tough one graph/tree question...never gave single hint and based on that one question he judged my seven years of experience in Software Development (I never experienced what they say...Google looks for approach and not final answer)
Q.1 : Arrange array in wave form A1 > a2 < a3 > a4 ...
O(n.log-n) (Note: its not A1 >= A2)
Q.2 : Given Graph with Tree characteristics, find one node as root so that height of tree will be minimum| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersConsider a setup where a program is continuously receiving floats as inputs (a stream of numbers). Write a method that at any given time returns a moving average. That is the average of the last K numbers received. If the method is called before the program has received K numbers, simply return the average of however many numbers have been received thus far.
- Ray November 15, 2015| Report Duplicate | Flag | PURGE
Google Jr. Software Engineer Algorithm - 2of 2 votes
AnswersData structure which supports both map operations and array operations without time complexity penalty.
- Ray November 14, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Data Structures - 0of 0 votes
AnswersGiven an active stream of sorted arrays, how would you merge them efficiently?
- Ray November 14, 2015 in Canada| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersWhat is the fastest way to compute cube root?
- Ray November 14, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite func repeat(e, n).
- ab123 November 12, 2015 in United States
Args:
e: any object
n: a number of times
Returns:
an iterator producing the element e n times| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Data Structures - 0of 0 votes
AnswersImplement ReentrantLock using simple locks.
- Ray November 09, 2015| Report Duplicate | Flag | PURGE
Google SDE1 Threads - 0of 2 votes
AnswersGiven a string of characters, find the longest legal word. A generic method to check word legality is given.
- tgerg2009@my.fit.edu November 06, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 5of 5 votes
AnswersGiven an infinite stream of characters and a list L of strings, create a function that calls an external API when a word in L is recognized during the processing of the stream.
- ragmo2223 November 05, 2015 in United States
Example:
L = ["ok","test","one","try","trying"]
stream = a,b,c,o,k,d,e,f,t,r,y,i,n,g.............
the call to external API (let's call it some function callAPI()) would be called when the 'k' is encountered, again when the 'y' is encountered, and again at 'g'.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a large that consists of millions of lines, retrieve only the first and last lines.
- adelabarra24 November 05, 2015 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 5of 5 votes
AnswersGiven a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number.
- pandacoder October 30, 2015 in United States
E.g., prime set = {2, 3}
expressible number = {1,2,3,4,6,8, 9, 12...}
non-expressible number = {5, 10... }
The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersSuppose we have two CPUs, each has an L1 cache associated with it. An L2 cache is shared by the two CPUs, and it requests data from DRAM:
- lou October 27, 2015 in United States
|CPU0| |CPU1|
|L1Cache0| |L1Cache1|
|Shared L2C|
|DRAM|
Let's say CPU0 and CPU1 send out a write signal at the same time:
- At timestamp 0, CPU0 sends a wr request - write address A to 0;
- Also at timestamp 0, CPU1 sends a wr request - write address A to 1;
- At timestamp 0, all of the L1/L2 caches are empty, i.e. write req will result in a miss in the cache;
- At timestamp 0, data in address A in DRAM is 100;
- Cache coherency protocol is MOESI.
What will the values be after these two writes complete? In L1, L2 and DRAM? and what are the states in each cache?| Report Duplicate | Flag | PURGE
Google Systems Design Engineer Computer Architecture & Low Level - 6of 6 votes
AnswersGiven an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array.
- PradeepN October 27, 2015 in United States
Brute force is obvious, but must be done faster than O(n^2)
Ex. [3,4,5,9,2,1, 3]
Return [3, 2, 1, 0, 1, 1, 0]
First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersGiven a set of values 0-9, return all permutations of that set of length n. Example: n=2, set ={2,3,4} Return: {2,2}, {3,3}, {4,4}, {2,3}, {3,2}, {3,4}, {4,3}, {2,4}, {4,2}
- PradeepN October 27, 2015 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersFind a counter example proving that the following substring algorithm is incorrect:
- awayes October 20, 2015 in United Statesconst char* findSubstr(const char* str, const char* substr) { int len = strlen(str); int substrlen = strlen(substr); int j = 0; const char* result = NULL; for (int i = 0; i < len; ++i) { if (str[i] != substr[j]) { j = 0; result = NULL; } else { if (j==0) result = &str[i]; ++j; if (j >= substrlen) break; } } return result; }
| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersGiven an array of "array range", return an optimized array by deleting subarrays.
- dark_knight October 19, 2015 in United States
NOTE: Array range (2,6) represents (2,3,4,5,6)
INPUT: [(2,6),(3,5),(7,21),(20,21)]
OUTPUT: [(2,6),(7,21)]
Reason: (3,5) is a subarray of (2,6) and (20,21) is a subarray of (7,21)| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 0of 0 votes
Answers2. VeryLongInt
- siva.sai.2020 October 18, 2015 in India
Design a class which can add and subtract integers up to 1000 digits. You can make the following assumptions
No need to handle overflow or underflow (extra credit if you do)
Copy constructor is available
“+” and “-” are binary operators| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
Answers1. Balanced Parentheses
- siva.sai.2020 October 18, 2015 in India
Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string
A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.
Implement
int MinNumInsersertionsForBalancing(const string& s)| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersHow would you go about testing a distributed system such as Gmail, before releasing it to the public. How would you simulate realistic server load?
- Ray October 17, 2015 in United States| Report Duplicate | Flag | PURGE
Google Intern Distributed Computing - 0of 0 votes
AnswersYou have some money in your bank account, the only function to withdraw money is uint16 Withdraw(uint16 value), if the value is greater than the money you have it returns 0, otherwise it withdraws the requested amount and returns the "value"
- mike.radula October 13, 2015 in United States
Write a function that withdraws all your money.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersRearrange characters in a string so that no character repeats twice.
- pcinterview October 10, 2015 in United States
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 5 votes
AnswersThere are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers.
- xblwyc October 07, 2015 in United States
1. the swap can happen between any two position.
2. E.g. AABCCDB -> AADCCBB, ans is 1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm