I gathered some of the important and top interview questions of Google from different people interviews. I hope This post helps those who are preparing for the Google Interview.

- There
is an array A[N] of N numbers. You have to compose an array Output[N]
such that Output[i] will be equal to multiplication of all the elements
of A[N] except A[i]. For example Output[0] will be multiplication of
A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from
A[2] to A[N-1].

Solve it without division operator and in O(n).

- There
is a linked list of numbers of length N. N is very large and you don’t
know N. You have to write a function that will return k random numbers
from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()

(return either 0 or 1)

2. It should be done in O(n).

- Find
or determine non existence of a number in a sorted list of N numbers
where the numbers range over M, M >> N and N large enough to span
multiple disks. Algorithm to beat O(log n) bonus points for constant
time algorithm.

- You are given a game of Tic Tac Toe.
You have to write a function in which you pass the whole game and name
of a player. The function will return whether the player has won the
game or not. First you to decide which data structure you will use for
the game.You need to tell the algorithm first and then need to write
the code.

Note: Some position may be blank in the game? So your data structure should

consider this condition also.

- You
are given an array [a1 To an] and we have to construct another array
[b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only
constant space and the time complexity is O(n). No divisions are
allowed.

- How do you put a Binary Search Tree in an array in a efficient manner.

Hint :: If the node is stored at the ith position and its children are at

2i and 2i+1(I mean level order wise)Its not the most efficient way.

- How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

Note :: You should not use use any extra space. i.e sorting Binary Search Tree

and storing the results in an array and listing out the fifth element.

- Given
a Data Structure having first n integers and next n chars. A = i1 i2 i3
... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the
elements of the array ass A = i1 c1 i2 c2 ... in cn

- Given
two sequences of items, find the items whose absolute number increases
or decreases the most when comparing one sequence with the other by
reading the sequence only once.

- Given That One of the
strings is very very long , and the other one could be of various
sizes. Windowing will result in O(N+M) solution but could it be better?
May be NlogM or even better?

- How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

- Lets
say you have to construct Google maps from scratch and guide a person
standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you
do the same ?

- Given that you have one string of length
N and M small strings of length L . How do you efficiently find the
occurrence of each small string in the larger one ?

- Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree

Hint: Some kind of pointer handling with In Order Traversal - anybody in for

writing some code

- You
are given a small sorted list of numbers, and a very very long sorted
list of numbers - so long that it had to be put on a disk in different
blocks. How would you find those short list numbers in the bigger one?

- Suppose
you have given N companies, and we want to eventually merge them into
one big company. How many ways are theres to merge?

- Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?

- Write
a program for displaying the ten most frequent words in a file such
that your program should be efficient in all complexity measures.

- Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

- Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

- Given an array,

i) find the longest continuous increasing subsequence.

ii) find the longest increasing subsequence.

- Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

- Write a function to find the middle node of a single link list.

- Given
two binary trees, write a compare function to check if they are equal
or not. Being equal means that they have the same value and same
structure.

- Implement put/get methods of a fixed size cache with LRU replacement algorithm.

- You
are given with three sorted arrays ( in ascending order), you are
required to find a triplet ( one element from each array) such that
distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

Please give a solution in O(n) time complexity

- Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

### Comments (52) -

*
*Name*

E-mail*

Website

Country
[Not specified]
Afghanistan
Albania
Algeria
Argentina
Armenia
Australia
Austria
Azerbaijan
Bahrain
Bangladesh
Belarus
Belgium
Belize
Bolivia
Bosnia and Herzegovina
Brazil
Brunei Darussalam
Bulgaria
Cambodia
Canada
Caribbean
Chile
Colombia
Costa Rica
Croatia
Czech Republic
Denmark
Dominican Republic
Ecuador
Egypt
El Salvador
Estonia
Ethiopia
Faroe Islands
Finland
France
Georgia
Germany
Greece
Greenland
Guatemala
Honduras
Hong Kong S.A.R.
Hungary
Iceland
India
Indonesia
Iran
Iraq
Ireland
Islamic Republic of Pakistan
Israel
Italy
Jamaica
Japan
Jordan
Kazakhstan
Kenya
Korea
Kuwait
Kyrgyzstan
Lao P.D.R.
Latvia
Lebanon
Libya
Liechtenstein
Lithuania
Luxembourg
Macao S.A.R.
Macedonia (FYROM)
Malaysia
Maldives
Malta
Mexico
Mongolia
Morocco
Nepal
Netherlands
New Zealand
Nicaragua
Nigeria
Norway
Oman
Panama
Paraguay
People's Republic of China
Peru
Philippines
Poland
Portugal
Principality of Monaco
Puerto Rico
Qatar
Republic of the Philippines
Romania
Russia
Rwanda
Saudi Arabia
Senegal
Serbia and Montenegro (Former)
Singapore
Slovakia
Slovenia
South Africa
Spain
Sri Lanka
Sweden
Switzerland
Syria
Taiwan
Tajikistan
Thailand
Trinidad and Tobago
Tunisia
Turkey
Turkmenistan
U.A.E.
Ukraine
United Kingdom
United States
Uruguay
Uzbekistan
Venezuela
Vietnam
Yemen
Zimbabwe

biuquote

Notify me when new comments are added

function showRecaptcha() {
Recaptcha.create('6LcdSNgSAAAAAD5RUMC5Fty0sWim27jvOX7AHkT4', 'recaptcha_placeholder', {
theme: 'white',
lang: 'en',
tabindex: 8
})
}
var rc_oldonload = window.onload;
if (typeof window.onload != 'function') {
window.onload = showRecaptcha;
}
else {
window.onload = function() {
rc_oldonload();
showRecaptcha();
}
}
<!--//
function registerCommentBox(){
BlogEngine.comments.flagImage = BlogEngine.$("ctl00_cphBody_CommentView1_imgFlag");
BlogEngine.comments.contentBox = BlogEngine.$("ctl00_cphBody_CommentView1_txtContent");
BlogEngine.comments.moderation = true;
BlogEngine.comments.checkName = true;
BlogEngine.comments.postAuthor = "Admin";
BlogEngine.comments.nameBox = BlogEngine.$("txtName636917719033514026");
BlogEngine.comments.emailBox = BlogEngine.$("ctl00_cphBody_CommentView1_txtEmail");
BlogEngine.comments.websiteBox = BlogEngine.$("ctl00_cphBody_CommentView1_txtWebsite");
BlogEngine.comments.countryDropDown = BlogEngine.$("ctl00_cphBody_CommentView1_ddlCountry");
BlogEngine.comments.captchaField = BlogEngine.$('ctl00_cphBody_CommentView1_hfCaptcha');
BlogEngine.comments.controlId = 'ctl00$cphBody$CommentView1';
BlogEngine.comments.replyToId = BlogEngine.$("ctl00_cphBody_CommentView1_hiddenReplyTo");
}
//-->
// this ensures coComment gets the correct values
coco =
{
tool: "BlogEngine",
siteurl: "http://intearview.com/",
sitetitle: "Fresh Interview Stories",
pageurl: location.href,
pagetitle: "27 Google Interview Questions",
author: "27 Google Interview Questions",
formID: "aspnetForm",
textareaID: "ctl00$cphBody$CommentView1$txtContent",
buttonID: "btnSaveAjax"
}
function toggle_visibility(id, id2) {
var e = document.getElementById(id);
var h = document.getElementById(id2);
if (e.style.display == 'block') {
e.style.display = 'none';
h.innerHTML = "+";
}
else {
e.style.display = 'block';
h.innerHTML = "-";
}
}
Add comment

biuquote

- Comment
- Preview

Let P be the number of divisions.

When we get to the right divison,we need 100/P more steps to get to the right floor in the division.

hence P + (100/P) must be minimized.

differentiating and equating to 0 we get P =10. which is the optimal value.

Maintain a heap of size 10 and then use this heap to delete any smaller items you encounter while traversing the array

I've solved Item 26 (triplet search).

The idea is simple -- we're holding an iterator for each array, and on every step we're moving forward on that which has the least value (this is the same algorithm as for `merge' stage in mergesort). Also on every step the distance is calculated between current items and compared to the current minimum.

I've checked my solution against the brute-force implementation and results are the same.

The implementation is in C++:

int distance(int a, int b, int c) {

return max(abs(a - b), max(abs(a - c), abs(b - c)));

}

template

pair

min_dist(

I a, I b, I c,

typename iterator_traits

::difference_type size > result = ) {

I first[] = { a, b, c };

pair

make_pair(

distance(*a, *b, *c),

vector

(first, first + 3));

for (

I i = a, j = b, k = c;

i != a + size && j != b + size && k != c + size;

) {

const int d = distance(*i, *j, *k);

if (d < result.first) {

result.first = d;

result.second[0] = i;

result.second[1] = j;

result.second[2] = k;

}

if (*i <= *j && *i <= *k)

++i;

else if (*j <= *i && *j <= *k)

++j;

else

++k;

}

return result;

}

arr = [1, 2, 3, 4, 5, 'A', 'B', 'C', 'D', 'E']

N = arr.length / 2

for i in (0...N-1)

arr.insert(2*i+1, arr.delete_at(N+i))

end

print arr

Thanks for your help.

Your interpretation of the rotateBy1 not what I meant, and also I found an error in my code.

Heres the implementation in C:

void rotateBy1(int* arr, int from, int to) {

int tmp = arr[to];

memmove(arr+from+1,arr+from,(to-from)*sizeof(int));

arr[from]=tmp;

}

main()

{

arr[]={NULL,1,2,3,4,'a','b','c','d'};

int N=4;

for (inti=1;i (lt) N;i++) { /* Note: i(lt)N - I cant post the less than sign due to html formatting errors! */

rotateBy1(arr,2*i,N+i); /* Note: N+i=2*i+N-i}

}

This works.

Anyway, I've converted your pseudocode to Ruby, and it doesn't seem to work, unless I've misinterpreted what you wrote. Here's the code:

def rotateBy1(arr, i, j)

tmp = arr[j]

arr.delete_at(j)

arr.insert(i, tmp)

end

# Start with nil to make array indices 1-based

arr = [nil, 1, 2, 3, 'A', 'B', 'C']

N = (arr.length-1) / 2

for i in (1..N)

rotateBy1(arr, 2*i, 2*i + N-1)

end

puts arr

max(int(100/N)+N-1, int(100/N)+100-N*int(100/N))

As once can see with calculation, this gives a min value of 19 for all N in 8,9,10,11,12. So we can follow the process as suggested with any of these N, all of which give the same worst case behaviour, though other considerations (e.g. the probability distribution of the floor number where the eggs break) would force a choice amongst these, but that is a much much more complex problem!

arr[2xN]

for i=1..N

rotateBy1 arr[2*i,2*i+N-1]

// assume arr index starting from 1

where

rotateBy1 arr[i,j]:=

tmp=arr[j]

move arr[i,j-1]->arr[i+1,j]

arr[i]=tmp

The solution proposed by marijn may well have cost O(n^2) due to the recursion to find the source for the swap; O(n(n+1)/2 ) would be more precise.

I think a cost O(nlogn) can be achieved doing a simple quicksort. Since the position of the pivot is very well known O(nlogn) is always achieved in practice.

Another simple way to put it: if we divide the array in four sections:

[X,Y|A,B]

we need to swap them like this

[X,A|Y,B]

and do recursion to resolve [X|A] and [Y|B] separately. Divide and conquer.

i) Take two variables Pf(product forward) and Pb(Product backward). Initialise them with 1

ii) Initialise Output array O[n] by all 1's.

iii) Now write output in O[n] such that.

Pf=Pf * A[i-1];

O[i] = Pf; where i goes from 1 to n

and similarly while going backward:

Pb = Pb * A[j+1];

O[j] = Pb; where j goes from n-1 to 0.

So in one scan i.e. O(n) we can get the required array O[n].

if ((t == NULL) || (*counter == 0)) return;

It should be:

if (t == NULL) return;

in order to print all values and of course one could stop analysing more node when counter <= 0

if ((t == NULL) || (*counter <= 0)) return;

Passing two variables as references: maximum and counter.

I have used this tree as an example:

http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg

The code in C... ooopppps.

-------

#include

typedef struct node_t node_t;

struct node_t

{

int value;

node_t *left;

node_t *right;

};

void

find_nth_maximum (node_t *t, int *max, int *counter)

{

if ((t == NULL) || (*counter == 0)) return;

find_nth_maximum (t->right, max, counter);

*counter = *counter - 1;

if (*counter == 0)

{

*max = t->value;

}

printf ("%d ", t->value);

find_nth_maximum (t->left, max, counter);

}

int

main (int argc, char *argv[])

{

node_t v_1 = { 1, NULL, NULL };

node_t v_4 = { 4, NULL, NULL };

node_t v_7 = { 7, NULL, NULL };

node_t v_13 = { 13, NULL, NULL };

node_t v_6 = { 6, &v_4, &v_7 };

node_t v_14 = { 14, &v_13, NULL };

node_t v_3 = { 3, &v_1, &v_6 };

node_t v_10 = { 10, NULL, &v_14 };

node_t v_8 = { 8, &v_3, &v_10 };

int max = 0;

int counter = 5;

printf ("reverse order: ");

find_nth_maximum (&v_8, &max, &counter);

printf ("\nmax: %d\n", max);

}

thanks for the answer. am definitely not the google material

my answer was not based on any mathematical equation. i just thought that i should break the number of intervals (10,20,30....) & the number of floors in each interval in the equal half for best result. so 10 was obvious choice keeping the floors in each interval constant.

again, thanks for your answer.. its cool.

elt_prod = product of all elements

Output[x] = e^( ln( elt_prod ) - ln( A[x] ) )

**proof**

elt_prod = product of all element

a = A[x]

Output[x] = elt * 1/a

= elt * a^-1

ln( Output [x] ) = ln(elt_prod * a^-1)

= ln(elt_prod)+ ln(a^-1)

= ln(elt_prod)- ln(a)

e^(ln(Output[x])) = e^(ln(elt_prod)-ln(a)

therefore,

Output[x] = e^(ln(elt_prod) - ln(a))

Using Hash With Chaining.

rite solution?

product = 1

for i = 0 to n

Product*=A[i];

B[i] = product;

for i = 1 to N

B[i] >>= i;

Print B[n]

Having seen the sort of questions they ask I can say with almost 100% certainty that they wouldn't hire me.

Oh well, there's always Yahoo.

var data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, "A", "B", "C", "D", "E", "F", "G", "H", "I", "J"];

function rearrange(data) {

var length = data.length / 2;

function swap(i, j) {

var tmp = data[i];

data[i] = data[j];

data[j] = tmp;

}

function elementFor(i) {

if (i % 2)

return Math.floor(i / 2) + length;

else

return i / 2;

}

function source(i) {

result = elementFor(i);

while (result < i)

result = elementFor(result);

return result;

}

for (var i = 0; i < data.length; i++)

swap(i, source(i));

}

rearrange(data);

alert(data);

It goes over the elements, and swaps every one of them with the element that should be there. Sometimes, that element has already been moved, so its position is determined recursively.

http://interviewfairy.com/google

Used those when I was interviewing with G.

ans-

20

40

60

80

90

95

98

99

Best Regards

java ds algo guru

equation is

(1 + (d-1)) + (1 + (d-2)) + --- >= 100

so from that d will be 14 not 13

here is the detailed view if it 14 drops

14 ---> 1 + 13

14 + 12 + 1 (27th) --- > 1 + 1 + 12

27 + 11 + 1 (39) -----> 1 + 1 + 1 + 11

39 + 10 + 1 (50) -----> 1 + 1 + 1 + 1 + 10

50 + 9 + 1 (60) --- > 1 + 1 + 1 + 1 + 1+ 9

60 + 8 + 1 (69) -----> 6 + 8

69 + 7 + 1 (77) ----> 7 + 7

77 + 6 + 1 (84) ---- > 8 + 6

84 + 5 + 1 ( 90) ----> 9 + 5

90 + 4 + 1 (95) ---> 10 + 4

95 + 3 + 1(99) ---> 11 + 3

99 + 2 + 1 (102) ---> 12 + a2

i need to try only 8 drops is sufficient

suppose

20,40,60,80,90,95,98,99

regards

mritunjaya

here is the solution

Let "d" be the number of drops required to find out the max floor.we need to get the value of d.

let's say if we drop from height d then if it breaks then we have d-1 floors to check for the second egg . so max of "d" drops, so first we will drop it from height "d" if it doesn't break at a height "d" then we are left with "d-1" drops,so lets drop it from d + 'd-2' + 1 height suppose if it break there then you are left with 'd-2' drops.

and so on until that sum is less than 100, it's like a linear search,

in equations,

(1+d) + (1+(d-1))+ (1+(d-2)) + .... >= 100

here we need to find out d

from the above equation

(1+d) ((1+d) + 1)/2 >= 100

x(x+1)/2 > = 100

from above x is 14

but we need d value

so d will be 13.

Post your comments,

i dont know whether my approach/answer is correct or not, but this is what i think. there may be a better way to do it...

as i can break only two eggs, the solution differs from conventional binary methods; like i start with 50th floor, then go on converging the possible floors.

i could start with 50th floor. if egg breaks, start from 1st floor & go on till u get the the floor from where the next egg breaks. Else if it doesnt, try 75th floor converging the scope to 25 floors, either 51-75 or 76-100. but in the worst case you will end-up taking 50 tries (if the floor was 49th). does it sound good? nah..

i would probably try something like this.. take sq root of 100, ie 10. start with 10th floor; if egg breaks, u've to test 1st through 9th floors. so total 10 takes. if it doesnt, go to 20th floor. if it breaks the target is among 11-19, try one by one..

in the same way, i go till 90th floor, it still doesnt break try 100th floor. if it still doesnt ...forget it...it wont break..(well it took 10 tries to know this). & if it does break when dropped from 100th floor, the target is in 91-99 range.

we have already taken 10 tries (10th, 20th, ..., 100th flr) & now 91st thru 99th, 9 more tries, if it is the worst case floor ie 99th. so worst case takes 19 chances. (i'd like to coin two stupid terms...excuse them.... BEST WORST CASE:9th floor (10 tries), WORST WORST CASE:99th floor(19 tries))

why i chose 10. well you try with 5 or 15

please put your comments.

thanks

log(n) solution:

N numbers

k disks

disk capacity = N / k

disk[i][j] = jth value in ith disk

value(i) = ith number (same as disk[i / y][i % y], where y = N / k)

so

def num_exists(num):

lo = 0

hi = N - 1

while (lo < hi):

mid = (lo + hi) / 2

midval = value(mid)

if num == midval:

return true

elif num < midval:

hi = mid - 1;

else:

lo = mid + 1

return False

# does not exist

return false

outlist = new int[k];

i = 0;

Node *temp = start;

// first get the first k items so we

// have something to start off with

for (;temp && i < k;temp = temp->next)

{

outlist[i] = temp->value;

}

// then randomly modify the

// outlist

for (;temp; temp = temp->next)

{

if (irand() == 1)

{

outlist[rand() * k] = temp->value;

}

}

#include

#define N 5

int main(void)

{

unsigned int data[N] = { 1, 2, 3, 4, 5 },

result[N], product, i;

result[0] = 1;

for (i = 0, product = 1; i < N - 1; i++)

{

product *= data[i];

result[i + 1] = product;

}

for (i = N - 1, product = 1; i > 0; i--)

{

product *= data[i];

result[i - 1] *= product;

}

for (i = 0; i < 5; i++)

printf("%d ", result[i]);

return 0;

}

{

int accum = -1;

return n >= 0 ? find_nth(node, n, accum) : NULL;

}

static TNode *find_nth(TNode *node, int n, int &accum)

{

if (!node)

return NULL;

TNode *out = find_nth(node->left, n, accum);

if (accum == n)

{

return out ? out : node;

}

else if (accum == n - 1)

{

accum++;

return node;

}

else

{

// check the right subtree

accum++;

return find_nth(node->right, n, accum);

}

}

Can be done easily in o(n) time and 2 *n extra space.

Arr1[n] and Arr2[n] are the two extra space arrays while Arr[n] is the original array

Arr1[i] = Arr[0] *Arr[1]* ... *Arr[i]

while

Arr2[i]= Arr[n-1]*Arr[n-2] ..Arr[i]

now final Arr[i] = Arr1[n] - ( (Arr[i]-1)*Arr1[i-1] *Arr2[i+1])

Handle Arr[0] and Arr[n] Separately like Arr[0] would be Arr2[1] while Arr[n] would be Arr1[n-1].

N! /2!

class TNode

{

public:

int value;

TNode *left;

TNode *right;

};

static TNode *find_nth(TNode *node, int n)

{

int accum = -1;

return n >= 0 ? find_nth(node, n, accum) : NULL;

}

static TNode *find_nth(TNode *node, int n, int &accum)

{

if (!node)

return NULL;

TNode *out = find_nth(node->left, n, accum);

if (accum == n)

{

return out ? out : node;

}

else if (accum == n - 1)

{

accum++;

return node;

}

else

{

accum++;

return find_nth(node->right, n, accum);

}

}

you will get it def..this time make sure you act

It can be solved in O(n), with an extra space of 4294967296 (range of the integers). Take an array of this much size, initialize with an character 'a'. Take the 'i'th elt from the 4 Billion array, if it's value is 'j' go to jth index of this newly created array and change it's value ot 'b'. In the last look at all the indexes of newly created array whose value is 'b', are the number which has occurred more than once.

Note: I used 'a' and 'b' rather then 1 and 0 since size of char is one byte so will be able to save some space.

This can be done,without creating any new array also. But in that solution. One have to swap the numbers. Order will again be same (0(n)).

Answer ::

Build a suffix tree (can be done in O(n) using Ukkonnen's algorithm) for the large string.

Now having done this bit of _preprocessing_ you could for each of the m smaller strings

search in O(length of small string time) for an occurrence in the suffix tree.

Did you solve the problem before seeing the answer?? let people know the solution you got.

Longest increasing subsequence is done in O(n log n).

Let P be the number of divisions.

When we get to the right divison,we need 100/P more steps to get to the right floor in the division.

hence P + (100/P) must be minimized.

differentiating and equating to 0 we get P =10. which is the optimal value.

Answer ::

Consider 2 points A and B and a line L which is equidistant from both A and B.

if L does not intersect the line segment AB, then L must be parallel to AB.

if L does intersect AB, then L must pass through the midpoint of AB, also any line through the midpoint has this property.

So given A,B,C not all collinear, consider the midpoints X,Y,Z.

Pick any two points from X,Y,Z and consider the line joining them. It is equidistant from all three points.

Thus there are exactly three lines.

Did you solve the problem before seeing the answer?? let me know the answer you got...