Microsoft student Interview Question
StudentsCountry: United States
one could try swapping. swap(a[i][j],a[j][i]). with the symmetricity of the swap you run only for half the matrix...
alternatively if we can use map-reduce...go for it..
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).
#include <iostream>
using namespace std;
int n=4;
void reverse(int,int,int**);
int main() {
// Start typing your code here...
cout << "Hello world!" << endl;
int** arr=new int*[4];
for(int i=0;i<4;i++)
arr[i]=new int[4];
int count=0;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
arr[i][j]=count;
cout<<arr[i][j]<<" ";
count++;
}
cout<<endl;
}
for(int i=0;i<4;i++)
reverse(i,i,arr);
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
cout<<arr[i][j]<< " ";
}
cout<<endl;
}
return 0;
}
void reverse(int i,int j,int** arr){
int x;
if(j==n)
return;
x=arr[i][j];arr[i][j]=arr[j][i];arr[j][i]=x;
reverse(i,j+1,arr);
}
If its an array, the task is pretty easy. Following code would do.
{
for (i=0; i<n; i++){
for(j=i; j<n; j++){
swap (array[i][j], array[j][i]);
}
}
}
But its million * million operation and on a FILE.
Here we have to read chunks (say 512*512) from file in an array (buffer), perform swap(row, column) operation on array.
Now we have million/512 chunks in a row and same in a column.
Again we have to apply swap (row * column) on these chunks.
The question was to see if a candidate can scale a small solution to a very big data set which is not easy to handle. Getting exact position or data set(chunk) as we require here from a file can be tricky.
I think its about scalability.. the most appropriate answer here IMO will be to first ask the interviewer how the data is stored in file. How we can access data..After that if possible get row i and column i , swap...upto n. If we cannot access row and column like that. we need to do this in small fragments .. the question here is not only for swaps in O(n) i think its also about no of file operations.
IF O(n) is required - Use a map.
Key => column
Value => Appended data from each row
Split each row and append the column data to the map. After millionth pass, you just have to write them out.
public int[,] MoveRowsToColumns(int [,]mat , int m, int n)
- red September 11, 2012{
if (m <= 0 || n <= 0)
{
throw new Exception("invalid rows/cols");
}
for (int i = 0; i < m; i++)
{
for (int j = i; j < n; j++)
{
int val = mat[i,j];
mat[i,j] = mat[j,i];
mat[j, i] = val;
}
}
return mat;
}