Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
public void PrintSpiral(int[,] a)
{
int minx=0,maxx=a.GetLength(0)-1,miny=0,maxy=a.GetLength(1)-1;
bool directionx=true;
bool directiony=true;
while(maxx!=minx && maxy!=miny)
{
if(directionx==true && directiony==true)
{
int x1=minx;int x2=maxx;
int y=miny;
for(int i=x1;i<=x2;i++)
{
console.write(a[i,y]);
}
directiony=true;
directionx=false;
miny++;
}
if(directionx==false && directiony==true)
{
int x=maxx;
int y1=miny;int y2=maxy;
for(int i=y1;i<=y2;i++)
{
console.write(a[x,i]);
}
directiony=false;
directionx=true;
maxx--;
}
if(directionx==true && directiony==false)
{
int x1=maxx;int x2=minx;
int y=maxy;
for(int i=x1;i>=x2;i--)
{
console.write(a[i,y]);
}
directiony=false;
directionx=false;
maxy--;
}
if(directionx==false && directiony==false)
{
int x=minx;
int y1=maxy;int y2=miny;
for(int i=y1;i>=y2;i--)
{
console.write(a[x,i]);
}
directiony=true;
directionx=true;
minx--;
}
if(maxx==minx && maxy==miny)console.write(a[maxx,maxy]);
}
}
javascript code:
function Matrix(m, n , defaultValue, increaseDelta) {
var size = m*n;
this.m = m;
this.n = n;
var data = new Int32Array(size);
if(defaultValue) {
for(var i=0;i<size; i++) {
data[i] = defaultValue;
defaultValue += increaseDelta;
}
}
this.data = data;
}
Matrix.prototype = {
get: function(x,y) {
return this.data[x*this.n + y];
},
set: function(x, y, value) {
this.data[x*this.n + y] = value;
},
dump: function() {
var buff = [];
for(var x=0;x <this.m;x++){
for(var y=0; y<this.n; y++) {
buff.push(this.data[x*this.n +y]);
}
console.log(buff);
buff = [];
}
}
}
var TravelDir = {
right: {x: 0, y: 1},
left: {x: 0, y: -1},
up: {x: -1, y: 0},
down: {x: 1, y: 0}
}
function ClockWise () {
this.index = -1;
}
ClockWise.prototype = {
order: [TravelDir.right, TravelDir.down, TravelDir.left, TravelDir.up],
nextDir: function() {
var order = this.order;
var nextIndex = (this.index + 1) % order.length;
this.index = nextIndex;
return order[nextIndex];
},
movePoint: function(p) {
var dir = this.order[this.index];
return {
x : p.x + dir.x,
y : p.y + dir.y
};
}
}
function MatrixTraveller( matrix ) {
this.m = matrix;
}
MatrixTraveller.prototype = {
byColumn: function (){
var buff = [];
var matrix = this.m;
for(var y=0; y<matrix.n; y++) {
for(var x=0;x <matrix.m;x++) {
buff.push(matrix.get(x,y));
}
}
return buff;
},
byLine: function() {
var buff = [];
var matrix = this.m;
for(var x=0;x <matrix.m;x++) {
for(var y=0; y<matrix.n; y++) {
buff.push(matrix.get(x,y));
}
}
return buff;
},
byClock: function () {
var buff = [];
var matrix = this.m;
var visitMatrix = new Matrix(matrix.m, matrix.n);
var p = {x:0, y:0};
var director = new ClockWise();
var dir = director.nextDir();
while(true) {
var lastPoint = p;
while(this._validPoint(p, visitMatrix)) {
buff.push(matrix.get(p.x, p.y));
visitMatrix.set(p.x, p.y, 1);
lastPoint = p;
p = director.movePoint(p);
}
// here p is not a valid point
dir = director.nextDir();
p = director.movePoint(lastPoint);
// try again, if still not a valid point, to end
if(!this._validPoint(p, visitMatrix)) {
break;
}
}
return buff;
},
_validPoint: function(p, visitMatrix) {
var x = p.x, y = p.y;
var matrix = this.m;
if(x < 0 || x >= matrix.m || y < 0 || y >= matrix.n) {
return false;
}
return visitMatrix.get(x, y) === 0;
}
}
var x = new Matrix(5,4, 1, 1);
x.dump()
var t = new MatrixTraveller(x);
console.log(t.byLine(), t.byColumn());
console.log(t.byClock());
static void spiralPrint(int[][] a){
int i, k = 0, l = 0;
int m = a.length;
int n = a[0].length;
while (k < m && l < n)
{
/* Print the first row from the remaining rows */
for (i = l; i < n; ++i)
{
System.out.print(" " + a[k][i]);
}
k++;
/* Print the last column from the remaining columns */
for (i = k; i < m; ++i)
{
System.out.print(" " + a[i][n-1]);
}
n--;
/* Print the last row from the remaining rows */
if ( k < m)
{
for (i = n-1; i >= l; --i)
{
System.out.print(" " + a[m-1][i]);
}
m--;
}
/* Print the first column from the remaining columns */
if (l < n)
{
for (i = m-1; i >= k; --i)
{
System.out.print(" " + a[i][l]);
}
l++;
}
}
}
From GeeksforGeeks
#define ROW 3
#define COL 3
void printrow(int start,int end,int indxrw,int mtrx[ROW][COL],int ISFRWRD = 1)
{
int indxcl;
for(ISFRWRD?indxcl=start:indxcl=end;(ISFRWRD &&indxcl<end)||(!ISFRWRD &&indxcl>=start);ISFRWRD?indxcl++:indxcl--)
{
cout<<" "<<mtrx[indxrw][indxcl];
}
}
int main(int argc, char *argv[])
{
int mtrx[ROW][COL]={{1,2,3},{4,5,6},{7,8,9}};
cout<<"My View" <<endl;
for(int indxrw=0;indxrw<ROW;indxrw++)
{
//print in a particular way
if(indxrw==0)
{
printrow(0,3,indxrw,mtrx,1);
}
else if(indxrw == 1)
{
printrow(2,3,indxrw,mtrx,1);
}
else
{
printrow(0,2,indxrw,mtrx,0);
}
}
printrow(0,2,1,mtrx,1);
cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
This is the spiral traversal of matrix. Check this page on geeksforgeeks.com
- alex September 27, 2013