reddevildan

 Profile Answers by reddevildan 

• Dec 5th, 2007

 

If space is not limited, we can use a open hash table.

1.  The hash key will be the i + j (col + row).
2.  We firstly insert each matrix element in a column, eg. 11, 21,31,12,....... for 3x4 matrix in the example
3.  where there is same hash key, the element is added as a queue

4.  in 2nd example, the hash table will look like:
       2:  a11
       3:  a21, a12
       4:  a31, a22, a13
       5:  a32, a23, a14
       6:  a33, a24
       7:  a34

After the hash table, the solution is obvious now.  We can simply read the table from key 2 - 7 in order.  The elements have already ordered as well.  To build this hash table, we only need O(n) time which is a good linear speed.

There might be better solution.  Let me know.  I am interested in this question as well.

GOOD LUCK to everyone's interview!!

RedDevilDan

Daskiller

 Profile Answers by Daskiller Questions by Daskiller

• Dec 6th, 2007

 

I found the following solution, whick works but I think it is not the best. I think a better way is to do it in a recursively way.

        int p = m > n ? m:n;
        for (int j = 0; j < p;j++)
        {
            for (int i=j;i>=0;i--)
            {
            if (j-i < n & i < m)
                Display(mat[i][j-i] + " ");
            }
        }
        
        int k =0;
        for (int i = p;i >k;k++)
        {
            for (int j = k+1, l = 1;j<p;j++,l++)
            if (i-l < m && j < n)
                Display(mat[i-l][j] + " ");
        }

Ashish.Shekhar

 Profile Answers by Ashish.Shekhar 

• Mar 1st, 2008

 

I think I have a simpler method,

#include <stdio.h>

#define M 3
#define N 4

main(){
         int a[M][N] = {{1, 2, 3, 4},
                               {5, 6, 7, 8},
                               {9,10,11,12}};

         int i, j, t;
         for( t = 0; t<M+N; ++t)
              for( i=t, j=0; i>=0 ; --i, ++j)
                     if( (i<M) && (j<N) )
                             printf("%d ", a[i][j]);
         return 0;
}

where M, N and the array can be user defined.

guitarfox

 Profile Answers by guitarfox 

• Jun 19th, 2008

 

My answer is similiar to Ashish.Shekhar 's.

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int m, n;
    cout << "Enter height of matrix" << endl;
    cin >> m;
    cout << "Enter width of matrix" << endl;
    cin >> n;
   
    int i = 1;
    int j = 1;
    while( (j + i ) <= (m + n) )
    {
        while ( j > 0 && i > 0 && j <= n && i <= m)
        {
            cout << "a" << i << j << " ";
            i -= 1;
            j += 1;
        }
        i += j;
        j = 1;
        if( i >= m )
        {
            j += i - m;
            i = m;
        }
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

it's only that I used a while loop instead of a for loop.  (loops.)

either way, this algorithm runs in O(m * n), I really doubt that there exists any method that runs faster.

As per hash table or other external storage or even recursion, I don't think they are cheaper than simply using two variables... (j and i )

charlypa

 Profile Answers by charlypa 

• Jun 19th, 2009

 

define two varibles initial_x and initial_y 

define another two varibles x and y

int initial_x =  m;

int initial_y = n;

while (x != m && y! =n)

{

print (x,y)

x--;

y++;

// Traverse downwards first

if (initial_x<m)

{

initial_x++;

}

// Travesrse upwards next

else

{

initial_y++;

}

x = initial_x;

y= initial_y;

Amit Verma

• Feb 21st, 2015

 

A very basic solution and easy to understand

Code
span style="color: #666666;">" "" ";; 


                                r--;


                                c++;


                                


                        }


                }


        }