Saturday, August 6, 2011

Google

Hi Guys,

Couple of weeks back i had onsite interview in Google. I thought to share my experience with you.

  • Find the largest continuous sequence present in the given array.
i/p 8 2 9 1 4 7 12 3 14 15 6
o/p 1 2 3 4

  • Find an element in the given matrix. Matrix is sorted in row as well column-wise.
    complexity constraint O(n).

  • Given an array of size N+1. Array contains the elements from domain 1 to N.
    Find the first repeated number in O(N) time complexity as well as O(1) Space complexity.

  • Describe the algorithm to generate the power set of a given set. write the code also.

  • Describe any two Design Patterns.

  • Describe virtual function.

  • Given a binary matrix of M*N . find the K*K sub matrix which has maximum number of 1's.

  • Expected value of reassigning the min variable in following code.
int min=a[0];
for(i=1; i
  • Given two sorted array A and B of size M and N. Find the K'th largest After combining A and B. Constraint Time complexity O(logn) space complexity O(1).

    • Discuss Master Theorem.

    • Given 2n points on a circle.find the number of ways to draw n non intersecting chords.