Google Top Interview Puzzles

Hi Friends,


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.

    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.

84 comments:

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

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

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

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

    ReplyDelete
  5. 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 <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;
    }

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

      Delete
    2. never mind. my bad. wasn't thinking when i asked the question.

      Delete
  6. 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... :)

    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

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

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

    ReplyDelete
  9. There are some more here
    http://interviewfairy.com/google
    Used those when I was interviewing with G.

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

    ReplyDelete
  11. #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.

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

    ReplyDelete
  13. Hi Chaitu,

    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.

    ReplyDelete
  14. #1 and #5 are essentially equal, #5 seems more complicated since the equation proposes division and forbids it at the same time.

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

    ReplyDelete
  16. Thanks Mr. Anonymous, it's better to reveal your identity,

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

    ReplyDelete
  17. 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 <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);
    }

    ReplyDelete
  18. 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;

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

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

    ReplyDelete
  21. Sorry the comment above is actually about problem 8.

    ReplyDelete
  22. 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!

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

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

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

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

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

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

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

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

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

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

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

    ReplyDelete
  34. 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<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;
    }

    ReplyDelete
  35. For #18
    Maintain a heap of size 10 and then use this heap to delete any smaller items you encounter while traversing the array

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

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

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

    ReplyDelete
  38. Problem 21_th part (b)

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

    ReplyDelete
  39. 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!

    ReplyDelete
  40. I 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.

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

    ReplyDelete
  41. 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);
    }
    }

    ReplyDelete
  42. 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);
    }
    }

    ReplyDelete
  43. 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;
    }
    }

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

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

    ReplyDelete
  46. in classical egg problem ,
    i need to try only 8 drops is sufficient
    suppose
    20,40,60,80,90,95,98,99

    regards
    mritunjaya

    ReplyDelete
  47. total 8 drops

    ans-
    20
    40
    60
    80
    90
    95
    98
    99

    Best Regards
    java ds algo guru

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

    ReplyDelete
  49. #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]

    ReplyDelete
  50. #13

    Using Hash With Chaining.

    ReplyDelete
  51. # 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))

    ReplyDelete
  52. Question 1.
    We 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])

    ReplyDelete
  53. For 17th question here is better solution
    given 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

    ReplyDelete
  54. 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
  55. @Chandan: Dude any idea how LOG and ANTILOG are found in any language??? I guess the complexity would be far worse than O(n) :)

    ReplyDelete
  56. There's a detailed account of Google's APM position interview at www.ferozeh.com

    ReplyDelete
  57. Swagatika
    For 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]);

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

    Regards,

    Swetha Naveen

    ReplyDelete
  59. Not sure if the following are right?

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

    ReplyDelete
  60. question number 5

    #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]);
    }
    }

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

    ReplyDelete
  62. For Q 11,..
    consider 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.

    ReplyDelete
  63. thanq very much for this collection,.. :)

    ReplyDelete
  64. For Q1:
    assume 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;

    ReplyDelete
  65. These questions are very good in standerd and i think everyone should try to solve them.
    "Very Good Quetions"

    ReplyDelete
  66. To Solve Problem 2:
    i.e. How to get K random numbers from N number linked list.
    http://www.techuser.net/randpermgen.html

    ReplyDelete
  67. These are great questions! Thanks for sharing..

    Common Interview Questions

    ReplyDelete
  68. For question #16 (and #22):

    There 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

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

    10
    /
    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);
    }

    ReplyDelete
  70. Solution 1,5 in Java
    public 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)

    ReplyDelete
  71. 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].
    http://anandtechblog.blogspot.com/2010/09/given-array-of-numbers-replace-each.html

    ReplyDelete
  72. # 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

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

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

    Similar concept can be used to find fifth MAXIMUM
    http://anandtechblog.blogspot.com/2010/12/find-kth-min-element-of-tree.html

    ReplyDelete
  74. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
    http://anandtechblog.blogspot.com/2010/06/give-minimum-number-of-coins_19.html

    ReplyDelete
  75. Write a function to find the middle node of a single link list.
    http://anandtechblog.blogspot.com/2010/08/middle-element-of-linked-list.html

    ReplyDelete
  76. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
    http://anandtechblog.blogspot.com/2011/06/all-stack-operation-in-constant-time-o1.html

    ReplyDelete
  77. Thanks for sharing, I will bookmark and be back again

    Interview Questions India

    ReplyDelete
  78. Hi

    I 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

    ReplyDelete
  79. question 13th:

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

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

    Upcoming Bank Exams

    ReplyDelete