## Saturday, August 6, 2011

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.