## Google Interview Questions

- 0of 0 votes
<Error>

- 1of 1 vote
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

- 2of 2 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.

- 3of 3 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 2 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

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

- 1of 3 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.

- 2of 2 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)`

- 0of 0 votes
Then the more difficult question was how I'd reverse this.

Implement function:`GetStringsfromNumeronym(numeronym){...}`

h3e -> {house, halle, hocke....}

- 0of 0 votes
Started out with simple question - to get warmed up:

Implement a function:`makeNumeronym(string s){...}`

Ex: house -> h3e, marcus -> m3s

- 0of 0 votes
You are given 4 integer numbers. Using each number once and only once with any operators from +, -, *, /, (, ), build an expression that evaluates to 24.

- 0of 0 votes
Write a method that combines an array of iterators into a new one, such that, e.g. for input [A B C] where:

A.next() returns a1, a2, respectively;

B.next() returns b1;

C.next() returns c1, c2, c3, respectively;

The new iterator will return elements in this order: a1 b1 c1 a2 c2 c3.

- 0of 0 votes
Simplify the implementation below as much as you can.

Even better if you can also improve performance as part of the simplification!

FYI: This code is over 35 lines and over 300 tokens, but it can be written in

5 lines and in less than 60 tokens.

קוד: בחר הכל

static int func(String s, char a, char b)

{

if (s.isEmpty()) return -1;

char[] strArray = string.toCharArray();

int i=0;

int aIndex=0;

int bIndex=0;

while (aIndex=0 && bIndex==0 && i<strArray.length)

{

if (strArray[i] == a)

aIndex=i;

if (strArray[i] == b)

bIndex=i;

i++;

}

if (aIndex != 0)

{

if (bIndex == 0)

return aIndex;

else

return Math.min(a, b);

}

else

{

if (bIndex != 0)

return bIndex;

else

return -1;

}

}

- 0of 0 votes
Given 1 byte. Write a function that checks that it have exactly 3 bits which equal to 1.

- 0of 0 votes
Write a function

bool fancy_shuffle(char* s);

which rearranges characters in the string given as input, in such a way that no same character occurs twice in a row (that is, next to each other).

If such rearrangement is not possible, the function should return false.

- 0of 0 votes
Given an array of numbers, find a pair whose sum is closest to zero.

- 0of 0 votes
You are given a log of wood of length `n’. There are `m’ markings on the log. The log must be cut at each of the marking. The cost of cutting is equal to the length of the log that is being cut. Given such a log, determine the least cost of cutting.

- 1of 1 vote
Design an optimised algorithm to solve snakes and ladders with the least amount of roles possible under the assumption that you get whatever role you want when you role the dice.

- 5of 7 votes
Given an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.

For Ex:

Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]

n -> 2

Out put -> [100, 0] or [100, 2]

Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2

- 0of 0 votes
This is a two part question related to Markov string generation.

Part 1: Read a training set of strings. For each character in any of the strings, calculate the probability of seeing that character and store it for later use. (this part is about coming up with the right data structure and correct probability calculation).

Part 2: Based on the training set from Part 1, generate a random string of length N.

- 0of 0 votes
Given an API ReadFromDisk() which returns a block of 256 bytes from disk. Implement the API Read(SizeInBytes) which reads SizeInBytes bytes from the disk by calling only ReadFromDisk. Notice that every call to ReadFromDisk() will read the next 256 bytes from disk.