## Google Interview Questions

- 2of 2 votes
You are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows:

If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'.

You are not allowed to use any conditional operator (including ternary operator).

Follow up: Solve the problem without utilizing arithmetic operators '+ - * /'.

- -1of 1 vote
Given a List of Strings, return the number of sets of anagrams.

For instance, given:

<abc,cab,dac,beed,deb,few,acd>

return 5

- 0of 0 votes
Design a cache module for an image server. The server accepts image requests from users and sends them back the images. The cache should always hold in-memory the 10 most recently requested images. The cache should also support multiple requests simultaneously

- 0of 0 votes
Design an application which sends the user the 10 closest hotels based on his geo location.

When i asked roughly how many hotels in total are we talking about, i was asked to estimate how many hotels are there in the world...

- 2of 2 votes
You are given 2 documents. We want to know how similar they are through N-Grams.

Given an input n (n = number of word in the Ngram) and two documents(strings) find the intersection of the NGrams of two document.

E.g doc1 = 'This is a dog'

doc2 = 'This is a cat'

n = 3

Ngrams for doc1 = 'This is a', 'is a dog'

Ngrams for doc2 = 'This is a', 'is a cat'

Output 'This is a'

Find a efficient way and give its complexity.

- 2of 2 votes
std C library has pow(x, n) function - implement that function

- 0of 0 votes
Given a sorted array and n, find the count of sum of 2 numbers greater than or equal to n

- 8of 8 votes
Given a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.

- 1of 1 vote
Given a sorted array, find a way to find the # of occurrence of a number

for eg: [1, 1, 2, 3, 3, 3, 4, 5]

find # of occurrence of 3 in time better than O(n)

- 0of 2 votes
Given a range of floats, find the range of size 1 with max num of elements

for eg: [-13.7, -14.5, -12.3, -12.5, -12.9]

one possible answer: [-12.3, -13.3]

- 1of 1 vote
Description

A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate.

Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall.

For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.

In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.

Input

There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.

Output

The output contains one line for each data set, formatted as shown in the sample output.

Sample Input

4 6

cs123 mt42 cs456 cs789

mt42 F 0

cs123 S 0

cs456 S 2 cs123 mt42

cs789 B 1 cs456

3 6

math1 comp2 comp3

comp3 S 1 comp2

math1 S 0

comp2 F 1 math1

4 3

m10 m20 c33 c44

m10 B 0

m20 B 0

c33 B 0

c44 B 0

-1 -1

Sample Output

The minimum number of semesters required to graduate is 5.

The minimum number of semesters required to graduate is 4.

The minimum number of semesters required to graduate is 2.

- 2of 2 votes
Given an array and is rotated n number of times find the number where the peak happens. The array is sorted in increasing order. Follow up question: how will you rearrange them in normal sorted order.

- 1of 1 vote
You are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit. For example, integer 2048 is represented in the stream as 8, 4, 0, 2.

Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.

Example:

s_a: 8 4 0 2

s_b: 4 2 0 1

result: '1024'

- -2of 2 votes
<Error>

- 0of 2 votes
i18n (where 18 stands for the number of letters between the first i and the last n in the word “internationalization,”) Wiki it.

Generate all such possible i18n strings for any given string. for eg. "careercup"=>"c7p","ca6p","c6up","car5p","ca5up","care4p","car4up","caree3p","care3up"..till the count is 0 which means its the complete string again.

- 1of 1 vote
Given an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO], please reconstruct the itinerary in order,

for example: [ CDG, MUC, LHR, SFO, SJC ].

//tickets can be represented as nodes

- 4of 4 votes
If a canoe can hold 2 kids and a max weight of 150 lbs, write a function that returns the minimum number of canoes needed, given a list of kids and their weights.

- 3of 3 votes
Given a list of queries and their counts, write a function that returns one of the queries at random such that over time it returns an equal distribution based on the counts provided in the input.

- 4of 4 votes
You are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome.

Expecting a O(nk) solution where n = number of works and k is length

There can be multiple pairs

- 1of 1 vote
Write a function which, given two integers (a numerator and a denominator), print the first N digits of a rational number. For example, for 5 / 3 with N=5, the result should be "1.66666". N=2: 1.66

- 0of 4 votes
you have a stream of bytes (1010101101011110100010......)to send over the net. but if you compress it. you will be charged less for less data usage. please try to compress it in a way that you can decompress at other end ahd you dont loss data

- 2of 2 votes
0 1 ?

? wildcard for 0 or 1

"01?"

010 011

Example:

01?0?

Will produce

01000

01100

01001

01101

- 0of 0 votes
In a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:

– Top speed: (150 + 10 * i) km per hour

– Acceleration: (2 * i) meter per second square.

– Handling factor (hf) = 0.8

– Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.

Here i is the team number.

The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.

All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.

Taking the number of teams and length of track as the input, Calculate the final speeds and the corresponding completion times.

- 3of 5 votes
Look at the sequence below:

1, 11, 21, 1211, 111221, 312211, ...

Write a code that receives n and returns the nth element of the sequence. If it gets 4 as input of the method it should return 1211.

- 0of 2 votes
The text of question below is exactly given by Google interviewer. So they are owner of the text and I am just quoting them. I am not the author of the text below:

"

Imagine a museum floor that looks like this:

.#.G.

..#..

G....

..#..

G == Museum Guard

# == obstruction/impassable obstacle

. == empty space

Write a piece of code that will find the nearest guard for each open floor space. Diagonal moves are not allowed. The output should convey this information:

2#1G1

12#12

G1223

12#34

You may choose how you want to receive the input and output. For example, you may use a 2-d array, as depicted here, or you may use a list of points with features, if you deem that easier to work with, as long as the same information is conveyed.

"

- 0of 0 votes
Given two binary trees ( not BST) , return true if both of them have same inorder else return false.

Eg.`B / \ A C`

`A \ B \ C`

Both of the trees have same inorder ( A-B-C) hence function will return true

P.S.

Please note, we can write inorder method call it once for first tree and then second tree, and finally compare both inorder.

We want to parallely do inorder on both tree, if there is mismatch between inorder nodes of both trees, we can stop the traversal and return false

- 0of 0 votes
Given a Binary search tree of integer values. return the count of nodes where all the nodes under that sub-tree lies between a given range [x, y]. assume there are more than 100,000 nodes

- 0of 0 votes
Bring up as many approaches: Your goal is to make faster web browser for phones. You can change the phones, the data center etc. There's a limited network bandwidth and the browsers from the companies can't be altered.

- 0of 0 votes
We've got Quad-trees making up a screen. Every box of the Quad-tree has either color white or black. How would you design the data structure of this Quad-tree?

And how would you count the number of pixels in a screen of a given color, given a Quad-tree?`int numberOfPixelsGivenColor(QuadTree* t, bool col)`

i used bool to specify white/black.

- 3of 3 votes
write a function:

`int median(int a, int b, int c)`

and then write another function:

`int median(int a, int b, int c, int min, int max)`