## Google Interview Questions

- 0of 0 votes
Given a long string s and short strings t1, t2, t3 (which can have different length) find the shortest substring of s which contains t1, t2 and t3.

- 0of 0 votes
Implement an algorithm that takes a adjacency list and produces a topological sort of the vertices.

INPUT:

1 2

1 3

1 4

3 5

2 5

4 5

Returns:

1 2 3 4 5

- 0of 0 votes
Validate whether given string is valid JSON fromat string or not.

I/P: {a:b}

O/P: Yes Valid JSON

I/P: {a:b, c:d}

O/P: Yes Valid JSON

I/P: {a:b,c:{e:f}}

O/P Yes Valid JSON

I/P: {a}

O/p: not a valid json

I/P: {{a}}

O/P: not valid JSON

- 0of 0 votes
write a method that takes in 2 int arrays of any size and returns an array that calculates the sum of both.

for example, [1,2,3] and [2,3,4] will return [3,5,7]

Or [1,2,3] and [2,3,5,5] will return [2,4,7,8]

however, if it's like [9,9,2] and [0,1,3] you need to carry the sum so it returns as [1,0,0,5]

** SINGLE DIGIT ONLY

- 0of 0 votes
Imagine you have a row of numbers like below(a traiangle) .By starting at the top of the triangle find the maximum number in each line and sum them up example below

5

9 6

4 6 8

8 7 15

Answer I.e. 5+9+8+7 = 29

writw a code to find the maximum total from top to bottom. Assume triangle can have at most 100000 rows.

Input Output specifications

Input Specification

A string of n numbers (where 0<=n<=10^10)

eg.5#9#6#4#6#8#0#7#1#5

Output Specification

A sum of the max numbers in each line (as string ) or Output invalid in case of invalid input/triangle

Examples

eg1.

Input :5#9#6#4#6#8#0#7#1#5

Output:29

eg 2 .

Input :5#9#6#4#6#8#0#7#1

Output:invalid

eg 2 .

Input :5#9##4#6#8#0#7#1

Output:invalid

- 0of 0 votes
Given N balloons, if you burst ith balloon you get Ai−1∗Ai∗Ai+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.

Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions)

Hence if we have left or right boundary positions we multiply 1.

- 0of 0 votes
We have an iterator class as below:

`class CIterator { int Next(); //Returns the value of the next element in the iteration by advancing the iterator bool HasNext() const; //check whether any next element for the current iterator };`

We need a CPeekIterator class which is having below functionalities

`Class CPeekIterator { int Next (); //Same as CIterator does bool HasNext() const; //same as CIterator does int Peek(); // Returns the next element in the iteration without advancing the iterator };`

Write the CPeekIterator class

- 0of 0 votes
Write a bitmap class where we don’t have fixed size for the bitmap. Calculate the changed bits from previous instance to new instance in least iteration.

Real-time usage : In file systems we will scan only those parts changed from last save to new edit. At that time this bitmap should be used to scan the changed/added/removed parts.

- 0of 0 votes
Google is conducting a contest where they display a special doodle to the user

submitting the billionth query of the day. Design a system to achieve this. (NOTE:

Google has thousands of servers and each query can hit a different server).

Optimise it. How will you handle server failures?

- 0of 0 votes
Best Time To Sell Stock but with 1 restriction: after you sell your stock, you cannot buy stock on next day.

- 0of 0 votes
Design a locking mechanism for a distributed system .

- 0of 0 votes
How can you read from disc such that you optimize the latency of the data read/writes?

- 0of 0 votes
Two 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.

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

- -1of 1 vote
Given that you have a graph with an even number of points, how do you find two points that equally subdivide the graph?

- 2of 2 votes
Given a list of integers, find the highest value obtainable by concatenating these together.

For example, given 9, 918, 917 - The answer is 9918917.

But given 1,112,113 - The answer is 1131121

- 1of 1 vote
Rahul 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).

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.

- 2of 2 votes
You 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) .

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.

- 0of 0 votes
I had two interviews with Google

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

- 0of 0 votes
Consider 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.

- 0of 0 votes
Data structure which supports both map operations and array operations without time complexity penalty.

- 0of 0 votes
Given an active stream of sorted arrays, how would you merge them efficiently?

- 1of 1 vote
What is the fastest way to compute cube root?

- 0of 0 votes
Write func repeat(e, n).

Args:

e: any object

n: a number of times

Returns:

an iterator producing the element e n times

- 0of 0 votes
Implement ReentrantLock using simple locks.

- 0of 2 votes
Given a string of characters, find the longest legal word. A generic method to check word legality is given.

- 4of 4 votes
Given 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.

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'.

- 0of 0 votes
Given a large that consists of millions of lines, retrieve only the first and last lines.

- 5of 5 votes
Given a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number.

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.

- 0of 0 votes
Suppose 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:

|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?

- 4of 4 votes
Given an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array.

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