Interview Question
Country: India
@Achintya: just to develop your idea further
1. remove integral part
2. use two arrays 'col_sums' and 'row_sums' to keep the sums of fractional parts along each column and row, resp.
in your example above:
row_sums = [1, 1, 2]
col_sums = [2, 1, 1]
now the problem reduces to finding a matrix A[i][j] of 0's and 1's where the column and row sums agree with the above arrays. There are many solutions possible.
For our example, we might have:
1 0 0 = 1
1 0 0 = 1
0 1 1 = 2
----------
2 1 1
or
0 1 0 = 1
1 0 0 = 1
1 0 1 = 2
----------
2 1 1
and so on. In fact we can put 1 at any position in the matrix as long as the row/col sums are preserved.
To make a deterministic algorithm out of this, we can use the following simple procedure (A[i][j] is the resulting matrix):
for(i = 0; i < n; i++) { // process each row
for(j = 0; j < row_sums[i]; ) { // place required # of 1's in row 'i'
if(col_sums[j] == 0) // all "slots" in this column are occupied
continue;
A[i][j] = 1;
col_sums[j]--; j++;
}
What on earth this question is? There is no way you can add a list of doubles and make sure that the sum will be an integer. In theory, 2.5 + 0.5 = 3. But no way you can be sure that the computer's representation of 2.5 and 0.5 is exactly 2.50000 and 0.50000.
Well, you are right from a certain point of view.
But if you want to solve the problem then it is better to think of the numbers as you do in classic arithmetic and in the implementation use an epsilon to compare two doubles (abs(x-y)<Eps) or think of the numbers as "Decimals" - capable of fixed point arithmetic without loosing precision.
At least this is what I'd do...
To start with consider a 2x2 matrix (A11, A12, A21, A22). Substracting X from A11 and A22 and adding X to A21 and A12 will keep the invariant property of the matrix given (sums of cols/rows give integer) whereever this 2x2 matrix is located in the original one.
If you apply this rule (where X is the fraction part of A11) recrusively you will end up with a matrix that has only integers.
Now the next step is to figure out how to do this to do this to end up with the ceil/floor values the original elements of the matrix.
I think an important part of the next step will be to consider that you can freely change the order of rows/column of these matrices and change the full row/col back after the transformations (sub/add/add/sub) applied.
The matrix contains numbers with fractions to make it interesting. All rows/cols add up to integers - sum of fractions per row/col is an integer (see many examples below)
Goal is to have only integers in the matrix, and the way to achieve it is to choose either ceiling or floor of the elements in the matrix (e.g. matrix element 1.32 -> 1 or 2, but nothing else) AND keep the sums (rows/cols) as it was in the original matrix.
And interesting issue is what could we do with elements that are already integers (my guess nothing), or with negative numbers.
The invariant of this question is as follows:
Sum of the fractions being floored = 1 - (Sum of fractions being ceiled).
Oh, bother :)
You hit it hard on my head - in spite I am not sure it is the best algorithm - that a simple BACKTRACKING will do the job. Forget about being efficient, but will solve the problem.
BACKTRACKING: Convert all elements to either ceiling or floor and check if the matrix is still OK (adding up the rows/cols). It is brute force but surely an algorithm that works although it is a "bit" exponential.
I think the questions says this
0.33 1.67
0.67 1.33
The sum of both row1 and row2 is 2.00 (integer 2)
The sum of column 1 is 1.0(integer 1)
The sum of column 2 is 3.0(integer 3)
answer:
0.0 2.0
1.0 1.0
Made A[0,0] floor , A[0,1] ceiling , A[1,0] ceiling , A[1,1] floor
olution is quite complicated...but can work....
let first remove all the integral part of the elements so..
1.2 3.4 2.4
3.9 4.0 2.1
7.9 1.6 0.5
this left with
0.2 0.4 0.4 = 1 R1
0.9 0.0 0.1 = 1 R2
0.9 0.6 0.5 = 1+1 R3
------------ |
1+1 1 1 = 4
C1 C2 C3
and always sum of rows shud be equal to sum of columns..
now let the cell is Aij then check if Ri has how many number of 1's in it and correspondingly number of 1's in Cj. if both have atleast one number of 1's, then cancel one 1 from each of them and ceil Aij. else if any of the Ri or Cj has not have any 1 left then, floor it...its only a optimal solution using greedy approach...
But this would work in any case.
Solution is quite complicated...but can work....
- Achintya December 16, 2011let first remove all the integral part of the elements so..
1.2 3.4 2.4
3.9 4.0 2.1
7.9 1.6 0.5
this left with
0.2 0.4 0.4 = 1 R1
0.9 0.0 0.1 = 1 R2
0.9 0.6 0.5 = 1+1 R3
------------ |
1+1 1 1 = 4
C1 C2 C3
and always sum of rows shud be equal to sum of columns..
now let the cell is Aij then check if Ri has how many number of 1's in it and correspondingly number of 1's in Cj. if both have atleast one number of 1's, then cancel one 1 from each of them and ceil Aij. else if any of the Ri or Cj has not have any 1 left then, floor it...its only a optimal solution using greedy approach...
But this would work in any case.