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.

You can discuss these puzzles in comments.if you have any more Google puzzles which are interesting and frequently asking in interviews comment it, i will add to the above 27 puzzles.

For the 10th Question in the list

ReplyDeleteAnswer ::

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

For the 12th Question in the list

ReplyDeleteAnswer ::

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.

For the 16th:

ReplyDeleteIt 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)).

N!/2!

ReplyDeleteFor Q15

ReplyDeleteN! /2!

Question 1:

ReplyDeleteCan 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].

First one is easy: iterate through the array forwards, accumulating a product and storing it in the previous element. Then iterate through the array backwards, accumulating a product and multiplying it by the next element. Written in C to piss you all off:

ReplyDelete#include <stdio.h>

#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;

}

how is your solution O(n)? isn't it O(n^2) instead?

Deletenever mind. my bad. wasn't thinking when i asked the question.

Delete26. Classic Egg Problem:

ReplyDeletei 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

well kunal, i also want to ask you why did you chose 10, may be 5 is not the better option than 10, x is the better option.

ReplyDeletehere 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,

there was some mistake in the above solution,

ReplyDeleteequation 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

There are some more here

ReplyDeletehttp://interviewfairy.com/google

Used those when I was interviewing with G.

A solution to the 7th problem, in JavaScript:

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

#2 is a slight twist on something I read in the original programming perl book - finding an element of a list in O(n) time; you get to only read the list once.

ReplyDeleteI wrote down some of the questions I was asked in interviews for linux sysadmin positions.

ReplyDeleteHi Chaitu,

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

#1 and #5 are essentially equal, #5

ReplyDeleteseemsmore complicated since the equation proposes division and forbids it at the same time.I had one that wasn't on this list. 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.

ReplyDeleteThanks Mr. Anonymous, it's better to reveal your identity,

ReplyDeleteanyway, Thank you very much, i will add this question to the list.Please provide the solution also if you have.

For #7. I'm not sure if this is the solution, but we can write a general method to find the nth maximum with a reversed in-order traversal (i.e. right node and then left node).

ReplyDeletePassing 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 <stdio.h>

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);

}

Sorry, this is wrong:

ReplyDeleteif ((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;

Ans for Q1#

ReplyDeletei) 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].

For problem 7.

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

Sorry the comment above is actually about problem 8.

ReplyDeleteMarijn's proposal for question #8 (which he mistakenly refers to as #7) is wrong. First, he claims that this is a recursive solution, but there's no recursion in his code. Second, and more importantly, it does not give the correct answer! His code requires that the input array is in sorted order, i.e., that the integers are 1, 2, 3... and the characters are 'A', 'B', 'C'... But the problem does not assume sorted order! After all, if the input array were always sorted, then the problem would be trivial. You could simply

ReplyDeletegeneratethe desired output in-place, no swapping needed!For prob 8 how about this solution (pseudocode):

ReplyDeletearr[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

Re Kunal's solution for 26 (actually 27): The eggs problem. A better representation of the solution (to find the best worst worst case as per your nomenclature ;)) would be for an N for which you get the minimum value for:

ReplyDeletemax(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!

Sorry, the above comment was made without looking at Chaitu's solution with decreasing steps, which is correct!

ReplyDeleteVardhan, about your proposed solution for problem #8, I do not understand your syntax. Sometimes you reference arr as a one-dimensional array (e.g., arr[i]) while other times you reference it as a two-dimensional array (e.g., arr[i,j-1]). How many dimensions does your arr have?

ReplyDeleteHi Trevor, I took some liberty in the syntax since it is pseudocode. arr[i,j-1] basically means the sub-array from a[i] upto a[j-1] (a[] is 1D only). So, move arr[i,j-1]->arr[i+1,j] means right shifting the subarray by one position.

ReplyDeleteIn that case, you probably should have used a different syntax, such as arr[i..j-1], since the comma token is so often used to indicate multi-dimensional arrays. Or, since it was pseudocode, you could have simply written in English "right-shift the subarray by one position".

ReplyDeleteAnyway, 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

Hi, I agree with the syntax.

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

Actually, my interpretation was exactly what you meant. Here's a new version of the Ruby code with your bug fixes.

ReplyDeletearr = [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.

Few solutions are posted at http://placementsindia.blogspot.com/2007/12/solutions-to-few-google-top-interview.html

ReplyDeleteHow come no one has answered Q 11? My friend contends that the answer is either zero or infinity.

ReplyDeleteFor Q11, I would say the answer is 3. Pick a pair of points and find a line parallel to them. Then move the line, keeping it parallel, such that the distance between the line and the two points is the same as the distance to the third point. Repeat three times, choosing a different pair each time. That's 3 lines.

ReplyDeleteHi all,

ReplyDeleteI'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<typename I>

pair<int,vector<I> >

min_dist(

I a, I b, I c,

typename iterator_traits<I>::difference_type size

) {

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

pair<int,vector<I> > result =

make_pair(

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

vector<I>(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;

}

For #18

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

@ kunal Nice! this was really amusing! myself would never go downl the building to save some eggs!

ReplyDeleteI found some good technical interview google questions asked in interviews here.

I guess the eggs question can be solved by the following method.

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

Problem 21_th part (b)

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

I recently got rejected by Google. I went to an on-site interview in NYC. 6 people interviewed me. I missed only one question. The recruiter told me I got rejected because I was familiar with those problems. They can reject you for any reason. So take easy!

ReplyDeleteI think you might you answered the questions right away :) ...may be you need some acting :D ...atleat i think you prepared well..try one more time.

ReplyDeleteyou will get it def..this time make sure you act :)

For finding the nth item in a BST:

ReplyDeleteclass 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);

}

}

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

ReplyDelete{

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);

}

}

For the one about k random items form a linklist with N items (N is very large):

ReplyDeleteoutlist = 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;

}

}

For Q 3:

ReplyDeletelog(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

sorry for double posting all... getting used to the windows...

ReplyDeletein classical egg problem ,

ReplyDeletei need to try only 8 drops is sufficient

suppose

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

regards

mritunjaya

total 8 drops

ReplyDeleteans-

20

40

60

80

90

95

98

99

Best Regards

java ds algo guru

I've heard about Google's crazy interview questions. They must have a right laugh at some of the answers they get.

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

#5

ReplyDeleterite 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]

#13

ReplyDeleteUsing Hash With Chaining.

# 1 really simple answer:

ReplyDeleteelt_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))

Question 1.

ReplyDeleteWe can use logarithm and anti lograithm to solve

log(x/y) = logx- logy

Thus we avoid division :P

1st step we get product of all input array elements - O(n)

Say our product is P

2nd step

Then in another loop we calculate

Output[i]=Antilog(log P - log(Input[i])

For 17th question here is better solution

ReplyDeletegiven by Bentely

a) In the first pass read 4 billion integers and write those with a leading zero bit to one sequential file and those with a leading one bit to another file.

b)One of those two files contails at most two

billion integers, so we nextuse that file as the current input and repeat the probe process. But this time on second bit. It is O(n) solution

cheers,

Nagesh Ayyagari

Nagesh, your solution will not work. The duplicate integers could be in the larger set (the one with more than 2 billion integers). Note that the question does NOT say that the list of integers is sequential. It could contain 4 billion duplicates, for example.

ReplyDelete@Chandan: Dude any idea how LOG and ANTILOG are found in any language??? I guess the complexity would be far worse than O(n) :)

ReplyDeleteThere's a detailed account of Google's APM position interview at www.ferozeh.com

ReplyDeleteSwagatika

ReplyDeleteFor the question no1 :

int[] array = {3, 5, 7, 9, 4};

int len = array.length;

int[] out = new int[len];

for(int i = 0 ; i < len ; i++)

{

int mul = 1;

for(int j = 0 ; j < len ; j++)

{

if(i == j)

continue;

mul = mul * array[j];

}

out[i] = mul ;

}

for(int i = 0 ; i < len ; i++)

System.out.println(out[i]);

Thank you for providing the interview puzzles, i will try to solve the puzzles..

ReplyDeleteRegards,

Swetha Naveen

Not sure if the following are right?

ReplyDelete1. For the merger (Q16),

Let f(n) be the number of ways to merge n companies.

f(n) = (sum_{k=1..n-1} nCk * f(n) * f(k))/2

1/2 because k=i is symmetrical to k=n-i.

Basically, merge k, then n-k, then merge the resultant 2 companies.

2. For eggs (Q27),

Let F(n, m) be the number of drops needed if allowed to break m eggs.

Then,

F(n, 1) = n (need to go sequentially)

F(n, m) = 1 + min_k max(F(k, m-1), F(n-k-1, m))

both can be solved using dyn prog.

question number 5

ReplyDelete#include

#include

void main()

{

int a[5],i,n;

int b[5],mul=1;

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

scanf("%d",&a[i]);

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

mul=mul*a[i];

printf("multiplication of the array numbers=%d",mul);

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

{

b[i]=mul-((a[i%5]-1)*(a[(i+1)%5])*(a[(i+2)%5])*(a[(i+3)%5])*(a[(i+4)%5]));

printf("%d\n",b[i]);

}

}

Instead of partitioning the floors by 10, Start at the 14th floor, and then go up 13 floors, then 12, then 11, then 10, 9, 8, 7, 6, 5, 4 until you get to the 99th floor, then here. If the egg were to break at the 100th floor, it would take 12 drops (or 11 if you assume that it would break at the 100th floor). Say, for example, that the 49th floor was the highest floor, the number of drops would be the 14th, 27th, 39th, 50th (the egg would break on the 50th floor) plus the 40, 41,42,43,44,45,46,47,48, and 49th floor for a total of 14 drops.

ReplyDeleteFor Q 11,..

ReplyDeleteconsider the Line AB and draw a line through C parallel to line AB,..now drop a perpendicular from point C to line AB,...so now we can draw a line through the midpoint of the perpendicular and parallel to line AB,..which is equidistant from all points A,B,C..,...so following the same stat with other two lines BC and AC gives total THREE lines,...equidistant from A,B,C.

thanq very much for this collection,.. :)

ReplyDeleteFor Q1:

ReplyDeleteassume we have two more temp arrays P[N]={1} and RP[N]={1}

P[0]=A[0]; RP[N-1] = A[N-1];

for(i=1;i<N;i++)

P[i] *= P[i-1]* A[i];

for(i=N-2;i;i--)

RP[i]*= RP[i+1]*A[i];

//finally

Output[0] = 1 * RP[1];

for(i=1;i<N-1;i++)

Output[i] = P[i-1] * RP[i+1];

Output[N-1] = P[N-2] * 1;

These questions are very good in standerd and i think everyone should try to solve them.

ReplyDelete"Very Good Quetions"

To Solve Problem 2:

ReplyDeletei.e. How to get K random numbers from N number linked list.

http://www.techuser.net/randpermgen.html

These are great questions! Thanks for sharing..

ReplyDeleteCommon Interview Questions

For question #16 (and #22):

ReplyDeleteThere are N*(N-1)/2 possibilities to choose from for merging any two of the N companies, leaving (N-1) companies. Then the game begins again, starting with (N-1) companies. Thus the total number c of merging possibilities is:

c = N*(N-1)/2 * (N-1)*(N-2)/2 * ... * (N-(N-3))*(N-(N-2))/2.

which is (in pseudo code):

c = 1

for i = 0 ... (N-3)

c = c * (N-i) * (N-i-1) / 2

end

Q:14 It may fail in below case..!!

ReplyDelete10

/

4

\

15

I think below solution may work:

bool isthisBST(nodeptr root)

{

return isthisBSTUtil(root,INT_MIN, INT_MAX);

}

int isthisBSTUtil(nodeptr root, int min, int max)

{

if(root == NULL) return true; //empty tree is a bst

if(root-data < min || root->data >max) return false;

return (isthisBSTUtil(root->left, min, root->data) || isthis BSTUtil(root->right,root->data, max);

}

Solution 1,5 in Java

ReplyDeletepublic static void main(String arg[])

{

int a[]={1,2,3,4,5};

int output[]={1,1,1,1,1};

int left=1;

int right=1;

int n= a.lenght;

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

{

output[i]=output[i]*left;

output[n-i-1]=output[n-i-1]*right;

left=a[i]*left;

right=a[i]*right;

}

}

complexity is O(n) i.e. O(5)

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

ReplyDeletehttp://anandtechblog.blogspot.com/2010/09/given-array-of-numbers-replace-each.html

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

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

writing some code

http://anandtechblog.blogspot.com/2010/12/validate-binary-search-tree-google.html

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

ReplyDeleteSimilar concept can be used to find fifth MAXIMUM

http://anandtechblog.blogspot.com/2010/12/find-kth-min-element-of-tree.html

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

ReplyDeletehttp://anandtechblog.blogspot.com/2010/06/give-minimum-number-of-coins_19.html

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

ReplyDeletehttp://anandtechblog.blogspot.com/2010/08/middle-element-of-linked-list.html

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

ReplyDeletehttp://anandtechblog.blogspot.com/2011/06/all-stack-operation-in-constant-time-o1.html

Thanks for sharing, I will bookmark and be back again

ReplyDeleteInterview Questions India

Hi

ReplyDeleteI like this post:

You create good material for community.

Please keep posting.

Let me introduce other material that may be good for net community.

Source: Yahoo interview questions

Best rgs

Peter

question 13th:

ReplyDeletecreate a suffix tree on the bigger string O(n)

then search for smaller substring in the formed suffix tree. for each sub-string search takes O(L)(L-lenght of the substring) time.

so overall complexity becomes O(n+L*m)

really good and helpful information. I like it. Thank you for sharing.

ReplyDeleteUpcoming Bank Exams