27 Google Interview Questions

Tags: | Posted by Admin on 8/31/2008 12:55 PM | Comments (52)
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.

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

  21. Given an array,

    i) find the longest continuous increasing subsequence.

    ii) find the longest increasing subsequence.

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

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

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

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

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

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

Monroe on 8/28/2008 1:49 AM I guess the eggs question can be solved by the following method.

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.
Marcus on 8/28/2008 4:07 AM For #18
Maintain a heap of size 10 and then use this heap to delete any smaller items you encounter while traversing the array
Malcolm on 8/28/2008 6:25 AM Hi all,

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
) {
  I first[] = { a, b, c };
  pair > result =
    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;
}
Lombard on 8/28/2008 8:43 AM For 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.
Lloyd on 8/28/2008 11:01 AM How come no one has answered Q 11? My friend contends that the answer is either zero or infinity.
Lionel on 8/28/2008 1:19 PM Few solutions are posted at placementsindia.blogspot.com/.../...interview.html
Lincoln on 8/28/2008 3:37 PM Actually, my interpretation was exactly what you meant. Here's a new version of the Ruby code with your bug fixes.

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.
Lane on 8/28/2008 5:55 PM Hi, I agree with the syntax.
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.
Lambert on 8/28/2008 8:13 PM In 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".

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
Kimball on 8/28/2008 10:31 PM Hi 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.
Trevor on 8/29/2008 12:49 AM Vardhan, 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?
Kendrick on 8/29/2008 3:07 AM Sorry, the above comment was made without looking at Chaitu's solution with decreasing steps, which is correct!
James on 8/29/2008 5:25 AM 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:

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!
Finbar on 8/29/2008 7:43 AM For prob 8 how about this solution (pseudocode):

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
Farrell on 8/29/2008 10:01 AM Marijn'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 generate the desired output in-place, no swapping needed!
Ellery on 8/29/2008 12:19 PM Sorry the comment above is actually about problem 8.
Egil on 8/29/2008 2:37 PM For problem 7.
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.
Durwin on 8/29/2008 4:55 PM Ans for Q1#

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].
Driscoll on 8/29/2008 7:13 PM Sorry, this is wrong:

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;
Dixon on 8/29/2008 9:31 PM 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).

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);
}
Dirk on 8/29/2008 11:49 PM 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.
Denley on 8/30/2008 2:07 AM #1 and #5 are essentially equal, #5 seems more complicated since the equation proposes division and forbids it at the same time.
Malcolm on 8/30/2008 4:25 AM # 1 really simple answer:

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))
Damon on 8/30/2008 4:25 AM Hi Chaitu,

thanks for the answer. am definitely not the google material Smile

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 Smile keeping the floors in each interval constant.

again, thanks for your answer.. its cool.
Cyril on 8/30/2008 6:43 AM I wrote down some of the questions I was asked in interviews for linux sysadmin positions.
Lombard on 8/30/2008 6:43 AM #13

Using Hash With Chaining.
Conan on 8/30/2008 9:01 AM #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.
Lloyd on 8/30/2008 9:01 AM #5

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]
Leroy on 8/30/2008 11:19 AM I've heard about Google's crazy interview questions. They must have a right laugh at some of the answers they get.
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.
Chandler on 8/30/2008 11:19 AM A solution to the 7th problem, in JavaScript:

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.
Carver on 8/30/2008 1:37 PM There are some more here
http://interviewfairy.com/google
Used those when I was interviewing with G.
java ds algo guru on 8/30/2008 1:37 PM total 8 drops

ans-
20
40
60
80
90
95
98
99

Best Regards
java ds algo guru
mritunjaya on 8/30/2008 3:55 PM in classical egg problem ,
i need to try only 8 drops is sufficient
suppose
20,40,60,80,90,95,98,99

regards
mritunjaya
Calvert on 8/30/2008 3:55 PM there was some mistake in the above solution,

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
Farrell on 8/30/2008 6:13 PM sorry for double posting all... getting used to the windows...
Barry on 8/30/2008 6:13 PM 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.

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,
Ellery on 8/30/2008 8:31 PM For Q 3:

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
Austin on 8/30/2008 8:31 PM 26. Classic Egg Problem:
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... Smile

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

please put your comments.

thanks
Addison on 8/30/2008 10:49 PM 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:

#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;
}
Durwin on 8/30/2008 10:49 PM For the one about k random items form a linklist with N items (N is very large):

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;
}
}
Adam on 8/31/2008 1:07 AM Question 1:

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].
Dixon on 8/31/2008 1:07 AM 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
{
// check the right subtree
accum++;
return find_nth(node->right, n, accum);
}
}
Cyril on 8/31/2008 3:25 AM For finding the nth item in a BST:

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);
}
}
abby on 8/31/2008 3:25 AM For Q15

N! /2!
Antony on 8/31/2008 5:43 AM N!/2!
Chandler on 8/31/2008 5:43 AM I think you might you answered the questions right away Smile ...may be you need some acting Laughing ...atleat i think you prepared well..try one more time.

you will get it def..this time make sure you act Smile
George on 8/31/2008 8:01 AM For the 16th:

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)).
Carver on 8/31/2008 8:01 AM 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!
Adriana on 8/31/2008 10:19 AM Problem 21_th part (b)

Longest increasing subsequence is done in O(n log n).
Leon on 8/31/2008 10:19 AM For the 12th Question in the list

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.
Mike on 8/31/2008 12:37 PM For the 10th Question in the list

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...
Aaron on 8/31/2008 12:37 PM I guess the eggs question can be solved by the following method.

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.

Add comment




  Country flag
biuquote
  • Comment
  • Preview
Loading