Software Engineering Interview Questions - 12

Q1. Given N points in a 2-Dimensional space, find a point (x, y) which minimizes the sum to all the given points.

Hint: Its an important problem studied in operations research as facility location problem.  The problem has a variety of form. The above problem is Ferment Weber Problem.

a) For L1 norm (also see Lp space, Normed Vector Space from linear algebra), its the median that minimizes the sum. See the derivative of an absolute function for an insight.

b) For L2 or Euclidean distance  ( see Euclidean Space for more details), there is no closed form solution as discussed in Ferment Weber Problem.

Note: See the difference from centroid as used in k-means clustering or centre of mass.


Q2.  Design an algorithm to count the number of binary strings of size n that can be formed with the constraint that a 0  has a 1 in its immediate left.

Example:  101010 -> Right
                001010 ->Wrong

Hint: F(n) = F(n-1) + F(n-2)
        Let's suppose that the rightmost bit is 0. Then the 2nd rightmost bit has to be 1. This gives F(n-2) binary strings. If the rightmost bit is 1. Then, we get F(n-1) binary strings.




Q3.  Given a matrix  MxN of numbers, find the sub-matrix with the largest sum.

Hint: 2-Dimensional Kadane Algorithm

Flow of execution:

Input Matrix

      C1   C2   C3  C4  C5  C6
R1
R2
R3
R4
R5

Compute Sum1


                                  C1   C2   C3  C4  C5  C6
R1
R1+R2
R1+R2+R3
R1+R2+R3+R4
R1+R2+R3+R4+R5

Perform 1-D Kadane for each row from row R1 to R5.

Compute Sum2.

                              C1   C2   C3  C4  C5  C6
--
R2
R2+R3
R2+R3+R4
R2+R3+R4+R5

Perform 1-D Kadane for each row from R2 to R5.

...... Continue
Complexity O(N^3)

Q4. Given a matrix MxN with 0's and 1's where 0 means a lake and 1 means land, design an algorithm to find the shortest path from [0, 0] to [1, 1].

Hint: Use flood fill algorithm which is similar to a Breadth First Search on a graph.



Q5. Given a sorted array of numbers where each number is repeated multiple times, design an algorithm to find the first occurrence of a given number.

Hint: Binary search


Q6. Given an array of numbers where every number except one is repeated, efficiently find the number.

Hint: Use XOR


Q7.  Design an algorithm to find two non-repeating numbers in an array where other numbers are repeated.

Hint:  Use XOR with Divide and Conquer. An XOR of all the numbers is only the XOR of the two non-repeating numbers. Take a set bit of the result.  Le it be the kth bit. This bit is set because the corresponding bits in the non-repeating numbers are opposite. Now divide all the numbers into two groups, one having the kth bit as 0 and the other having kth bit as 1. Take XOR of each of the groups. The resultants are the non-repeating numbers.

X & ~(X-1) gives the least significant set bit. (X-1) has the property to shift the least significant set bit to left.

The idea can be recursively used to find k non-repeating numbers.


Q8.  Given an array of numbers where all the numbers are repeated odd number of times except one which is repeated even number of times, design an algorithm to find the number which is repeated even number of times. 


Q9.  Given an array of numbers where some numbers occur only ones, some are repeated twice and only one number occur thrice, design an algorithm to find the number that occur thrice.


Q10. Given an array of numbers where all number occur three times except one which occur only once, design an algorithm to find the number that occur only once.