Interview Questions 20

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.


About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

5 Responses to Interview Questions 20

  1. Divya says:

    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

    • Balaji says:

      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.

      • Divya says:

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

    • Prateek Caire says:

      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

  2. kaka says:

    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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: