# Interview Questions 20

December 24, 2010 5 Comments

Most problems in this post are adopted from Antonio Gulli’s coding playground.

1. Write a function that output the size of highest sub square matrix of 1s in matrix of 0s and 1s

For ex:

0 1

0 0

Output: 1

0 0 0

0 1 1

0 1 1

Output: 2

2. Input: Array of integers, A[0], A[1], …, A[n]

An operation is defined to have all A[i] altered by 1, i.e., A[i]++/A[i]–. Note whether A[i] is increased or decreased is independent from other elements in A.

Question: return the minimum number of operations to make all elements in A[i] be equal. If it is impossible, return -1;

3. Given N arrays containing values between 0 to x, what data structure would you use to store these arrays so that when given a test array ‘t’ find the closest array in N that has highest number of elements in ‘t’? Also what algorithm would you use to find the closest array. N could be in the order of 1000. x could be between [100,1000]

4. Given a triangle ABC and a point P, device an algorithm for understanding whether P is inside or outside the triangle.

5. Given an Array A, with very large size N find the element which appears 5/8 of times.

6. Device an infrastructure for storing data in Facebook. There are 500M users and let’s assume the average number of friends is 100. Each user can post a message, or can read all the fresh messages produced by her friends.

7. Devise an algorithm for suggesting friends in Facebook.

8. You are given a blue segment S of length n. There are n points p_i (0 <= i < n) distributed uniformly at random. You mark in red all the segments connecting points p_i and p_j what would be the predominant colour in S after that?

9. A 'Document' is defined as a collection of 'Fields'. Some fields can be optional. A 'Field' can be a first-order type (int, char, float), or an array of first order types.

Write the code to serialize and de-serialize a collection of 'Documents'

10. Given an expression E of n numbers with *, + operations and no precedence among the operators, identify the set of parenthesis which maximize the results for E.

2. calculate mean of array. if the mean is not an integer then return -1 else return sum of deviations from mean ie sigma i<-0 to n-1 abs| mean-a[i]|.

4 area of triangle PAB + PBC + PCA= ABC

Why would we return -1 if the mean is not an integer ?

For example, if array is 1,2 , the mean being 1.5, ans is 1 and not -1. I think in this case we have to find for both the sum of differences with ceil and floor and return the minimum of the two.

The answer would never be -1 I think.

yes i was wrong there. I think we need to find median and return the sum of deviation of all elements from the median.

Target val must be (max + min)/2 rather than mean. such target val require min number of continuos decrements of max and continuos increments of min. rest of the elements can increment/decrement based on value greater or less than target val

For 5th ques.

we can use map to store the frequency of the numbers and then check if there is any element whose frequency is 5/8 times of N.

Can we do any thing better ? I can’t think if any other solution