Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Hitesh, You made ur solution very simple and elegant. But, your code works without using two if condition within the while loop. May I know the reason? Did u found any counter scenario? The code works not only for nxn but also for nxm matrix.
This is a reverse spiral traversal problem. The tricky part is maintaining start and stop points, iterating solution by layers inward, and ensuring that you are referencing the array properly. Here is a java solution that runs in N^2 time and takes O(1) memory:
public void reverseSpiral(char[][] input){
int matrixSize = input.length; //this is the length of our NxN matrix (N)
int level = 0; //this is the layer we are on, think of an onion starting on the outside and working in
int levelStop;
//Make sure we account for odd N so that we get all layers ciel(N/2)
if(matrixSize % 2 == 0){levelStop = input.length/2;}
else{levelStop = input.length/2 + 1;}
while(level <= levelStop){ //loop till we reach levelStop
int mSize = matrixSize - 1 - level; //Set the max size, this shrinks with each level iteration till we reach middle
for(int i = mSize; i > level; i--){ //Traverse top-right to top-left
System.out.print(input[level][i]);
}
for(int i = level; i < mSize; i++){ //Traverse top-left to bottom-left
System.out.print(input[i][level]);
}
for(int i = level; i < mSize; i++){ //Traverse bottom-left to bottom-right
System.out.print(input[mSize][i]);
}
for(int i = mSize; i > level; i--){ //Traverse bottom-right to top-right
System.out.print(input[i][mSize]);
}
level++; //Move inward 1 level
}
For 4x4 matrix levelStop would be 2. It would have 2 levels. So while(level <= levelStop) won't go for execution thrice? Since level is 0 initially? Correct me if I am missing something here.
If the N value is odd, we need to print the center value of the matrix which is getting missed here. Following modification solves the issue
//Make sure we account for odd N so that we get all layers ciel(N/2)
if(matrixSize % 2 == 0){levelStop = input.length/2;}
else{levelStop = input.length/2 + 1;
odd_flag = true;}
Finally after the while block execution is done,
if(odd_flag == true){
int value = (matrixSize - 1)/2;
System.out.println(input[value][value]);
}
would print the left out value.
public class ClockWiseSpiralMatrix {
public static void main(String args[]) {
char[][] characterArray = { {'C', 'I', 'P', 'E'}, {'R', 'N', 'K', 'U'}, {'U', 'O', 'W', 'O'}, {'L', 'E', 'S', 'Y'}};
int top = 0;
int right = characterArray[0].length-1;
int bottom = characterArray.length-1;
int left = 0;
System.out.println(right + " " + bottom);
while(true){
for(int i = right; i >= left; i--)
System.out.print(characterArray[top][i]);
top++;
if(top > bottom || left > right)
break;
for(int i = top; i <= bottom; i++)
System.out.print(characterArray[i][left]);
left++;
if(top > bottom || left > right)
break;
for(int i = left; i <= right; i++)
System.out.print(characterArray[bottom][i]);
bottom--;
if(top > bottom || left > right)
break;
for(int i = bottom; i >= top; i--)
System.out.print(characterArray[i][right]);
right--;
if(top > bottom || left > right)
break;
}
}
}
public static void spiralPrint(int m,int n,char a[][]){
int i=0,k=0,l=0;
//k starting row index
//m ending row index
//l starting column index
//n ending column index
//i iterator
while(k<m && l<n){
//print the first row from the remaining rows
for(i=n-1;i>=l;i--){
System.out.print(a[k][i]+" ");
}
k++;
//print for the first row
for(i=k;i<m;i++){
System.out.print(a[i][l]+" ");
}
l++;
//print for the last r
if(k<m){
for(i=l;i<n;i++){
System.out.print(a[m-1][i]+" ");
}
m--;
}
//print for the last column
if(l<n){
for(i=m-1;i>=k;i--){
System.out.print(a[i][n-1]+" ");
}
n--;
}
}
}
char Matrix[][]={{'c','i','p','e'},{'r','n','k','u'},{'u','o','w','o'},{'l','e','s','y'}};
int rowtop=0;
int rowbottom=3;
int colleft=0;
int colright=3;
while(rowtop<rowtop || colleft<colright)
{
for (int i=colright;i>=colleft;i--)
{
System.out.println(Matrix[rowtop][i]);
}
rowtop++;
for(int i=rowtop;i<=rowbottom;i++)
{
System.out.println(Matrix[i][colleft]);
}
colleft++;
for (int i=colleft;i<=colright;i++)
{
System.out.println(Matrix[rowbottom][i]);
}
rowbottom--;
for(int i=rowbottom;i>=rowtop;i--)
{
System.out.println(Matrix[i][colright]);
}
colright--;
}
void printCounterClockwise(String[] check)
{
int index = 0;
String s = "";
while(index < check.length/2)
{
for(int i=check[0].length() - index - 1; i >= index; i--)
s+=check[index].charAt(i);
for(int i=index+1; i< check.length - index - 1; i++)
s+=check[i].charAt(index);
String next = check[check.length - index - 1].substring(index, check[0].length() - index - 1);
s+=next;
for(int i=check.length - index - 1; i >= index + 1; i--)
s+=check[i].charAt(check[0].length() - index - 1);
index++;
}
System.out.println(s);
}
public class Spiral {
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] c = {{'c','i','p','e'},{'r','n','k','u'},{'u','o','w','o'},{'l','e','s','y'}};
printTopLeft(c,0,c.length-1,1,c.length-1);
}
public static void printTopLeft(char a[][], int cleft, int cright, int rup, int rdown){
for(int j = cright; j >= cleft; j--){
System.out.print(a[rup-1][j]);
}
for(int i = rup; i <= rdown ; i++){
System.out.print(a[i][cleft]);
}
if(cright > cleft){
printBottemRight(a, cleft+1, cright, rup, rdown-1);
}
}
public static void printBottemRight(char a[][], int cleft, int cright, int rup, int rdown){
for(int j = cleft; j <= cright; j++){
System.out.print(a[rdown+1][j]);
}
for(int i = rdown; i >= rup ; i--){
System.out.print(a[i][cright]);
}
if(cright > cleft){
printTopLeft(a, cleft, cright-1, rup+1, rdown);
}
}
}
#include <iostream>
using namespace std;
int main()
{
char **arr;
int i,j,n;
cout<<"Enter the dimension of square matrix:";
cin>>n;
arr = new char*[n];
for(i=0;i<n;i++)
{
arr[i]=new char[n];
}
for (i=0;i<n;i++)
{
for(j=0 ;j <n;j++)
{
cout<<"Enter the ["<<i+1<<"]["<<j+1<<"] element:";
cin>>arr[i][j];
}
}
cout<<"\nThe Array you inserted is :-\n";
for (i=0;i<n;i++)
{
for(j=0 ;j <n;j++)
{
cout<<arr[i][j];
}
cout<<endl;
}
for(int layer=0;layer<n/2;++layer)
{
i =layer;
j =n - layer -1;
while(j>layer)
{
cout<<arr[layer][j];
--j;
}
while(i < n-layer-1)
{
cout<<arr[i][layer];
++i;
}
while(j<n-layer-1)
{
cout<<arr[n-layer-1][j];
j++;
}
while( i> layer)
{
cout<<arr[i][n-layer-1];
--i;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,start,end;
cin>>n;
start=0;
end=n-1;
vector<int> row;
vector<vector<int > > in;
for(int i=0;i<n;i++){
row.clear();
for(int j=0;j<n;j++){
cin>>temp;
row.push_back(temp);
}
in.push_back(row);
}
while(start<=end){
for(int i=end;i>=start;i--)
cout<<in[start][i]<<" " ;
for(int i=start+1;i<=end;i++)
cout<<in[i][start]<<" ";
for(int i=start+1;i<=end;i++)
cout<<in[end][i]<<" ";
for(int i=end-1;i>start;i--)
cout<<in[i][end]<<" ";
start++;
end--;
}
cout<<endl;
return 0;
}
package epic;
public class Rotate {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Rotate");
char[][] characterArray = { {'C', 'I', 'P', 'E'}, {'R', 'N', 'K', 'U'}, {'U', 'O', 'W', 'O'}, {'L', 'E', 'S', 'Y'}};
int l = 0;
int i,j,r = 4,t=0,b=4;
//print top row
while(l<r && t<b){
for(i=r-1; i>=t; i--){
j=t;
System.out.print(characterArray[j][i] + " ");
}
//print left column
for(i=t+1; i<b; i++){
j=l;
System.out.print(characterArray[i][j] + " ");
}
//print bottom row
for(i=l+1; i<r; i++){
j=b-1;
System.out.print(characterArray[j][i] + " ");
}
//print last column
for(i=b-2; i>t; i--){
j=r-1;
System.out.print(characterArray[i][j] + " ");
}
t++;
b--;
l++;
r--;
}
}
}
package p1;
import java.util.ArrayList;
public class matrix {
public static void main(String args[])
{
int k=1;
int[][] mat=new int[4][4];
for(int i=0;i<=mat.length-1;i++)
{
for(int j=0;j<=mat.length-1;j++)
{
mat[i][j]=k;
k=k+1;
}
}
int l=mat.length-1,m=0;
int s=1;
int len=(int) ((Math.pow(mat.length,2)));
boolean g=true;
ArrayList output=new ArrayList();
while(g)
{
if(s==1){
for(int i=l;i>=m;i--)
{
output.add(mat[m][i]);
if(output.size()==len)
{
g=false;
}
}
s=2;
m=m+1;
}
if(s==2)
{
for(int i=m;i<=l;i++)
{
output.add(mat[i][m-1]);
if(output.size()==len)
{
g=false;
}
}
s=3;
}
if(s==3)
{
for(int i=m;i<=l;i++)
{
output.add(mat[l][i]);
if(output.size()==len)
{
g=false;
}
}
s=4;
}
if(s==4)
{
for(int i=l-1;i>=m;i--)
{
output.add(mat[i][l]);
if(output.size()==len)
{
g=false;
}
}
s=1;
l=l-1;
}
}
System.out.println(output);
}
}
Matrix traversal. Another easy one. Don't care about odd N or even N, just count to N^2.
pair<int, int> nextDir(pair<int, int> dir) {
if (dir == pair<int, int>{0, -1}) return pair<int, int>{1, 0};
if (dir == pair<int, int>{1, 0}) return pair<int, int>{0, 1};
if (dir == pair<int, int>{0, 1}) return pair<int, int>{-1, 0};
if (dir == pair<int, int>{-1, 0}) return pair<int, int>{0, -1};
}
string spiral(vector<vector<char>> matrix) {
string ret;
if (!matrix.size()) return ret;
if (matrix.size() == 1) {
ret.push_back(matrix[0][0]);
return ret;
}
int row(0), col(matrix.size() - 1);
pair<int, int> dir{ 0, -1 };
for (int i = 0; i < matrix.size()*matrix.size(); ++i) {
ret.push_back(matrix[row][col]);
matrix[row][col] = 0;
row += dir.first; col += dir.second;
if (row < 0 || col < 0 || row == matrix.size() || col == matrix.size() || !matrix[row][col]) {
row -= dir.first; col -= dir.second;
dir = nextDir(dir);
row += dir.first; col += dir.second;
}
}
return ret;
}
public class Spiral {
public static void main(String[] args) {
// TODO Auto-generated method stub
char c[][] = new char[4][4];
c[0][0]='a';
c[0][1]='b';
c[0][2]='c';
c[0][3]='d';
c[1][0]='e';
c[1][1]='f';
c[1][2]='g';
c[1][3]='h';
c[2][0]='i';
c[2][1]='j';
c[2][2]='k';
c[2][3]='l';
c[3][0]='m';
c[3][1]='n';
c[3][2]='o';
c[3][3]='p';
spiral(c,4,0,3,'l');
}
public static void spiral(char [][]c,int size,int row,int col,char dir){
int count =0;
while(count<(size*size)){
if(col<0){
dir = 'd';
row++;
col++;
continue;
}
if(col>3){
dir = 'u';
row--;
col--;
continue;
}
if(row<0){
dir = 'l';
row++;
col--;
continue;
}
if(row>3){
dir = 'r';
row--;
col++;
continue;
}
if(c[row][col]==' '){
switch (dir){
case 'u':
dir = 'l';
row++;
col--;
break;
case 'd':
dir = 'r';
row--;
col++;
break;
case 'l':
dir = 'd';
row++;
col++;
break;
case 'r':
dir='u';
row--;
col--;
break;
}
continue;
}
System.out.print(c[row][col]+" ");
c[row][col]=' ';
switch (dir){
case 'l':
col--;
break;
case 'r':
col++;
break;
case 'u':
row--;
break;
case 'd':
row++;
break;
}
count++;
}
}
}
Using recursion:
Call the same function tweaking the parameters:
This is totally different from the solutions shared here, It worked for 2x2,3x3,4x4 matrix and please comment if you find any bug
public class SpiralMatrix {
public static void printData(char[][] mat, char dir, int start, int end, int constant ){
if(dir=='h'){
if(start<end){
for(int i=start;i<=end;i++)
System.out.print(mat[constant][i]);
}
else{
for(int i=start;i>=end;i--)
System.out.print(mat[constant][i]);
}
}
if(dir=='v'){
if(start<end){
for(int i=start;i<=end;i++)
System.out.print(mat[i][constant]);
}
else{
for(int i=start;i>=end;i--)
System.out.print(mat[i][constant]);
}
}
}
public static void traverse(char[][] mat, char dir, int start, int end, int constant ){
if(start<=0){
if(dir == 'h') System.out.println(mat[constant][end]);
else System.out.println(mat[end][constant]);
return;
}
printData(mat,dir,start,end,constant);
if((end==mat.length/2 || start==mat.length/2) && constant==mat.length/2){
return;
}
if(dir == 'h'){
if(start >= end)
traverse(mat,'v',constant+1,start,end);
else
traverse(mat,'v',constant-1,start,end);
}
else{
if(start >= end)
traverse(mat,'h',constant-1,end,end);
else
traverse(mat,'h',constant+1,end,end);
}
}
public static void main(String[] args){
char[][] mat = { {'C', 'I', 'P', 'E'}, {'R', 'N', 'K', 'U'}, {'U', 'O', 'W', 'O'}, {'L', 'E', 'S', 'Y'}};
for(int i=0;i<mat.length;i++){
for(int j=0;j<mat.length;j++){
System.out.print(mat[i][j] + " ");
}
System.out.println("");
}
traverse(mat,'h',mat.length-1,0,0);
}
}
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 4 19:26:44 2015
@author: praneethpuligundla
"""
def spiral(m,length,columnlength):
j=columnlength
i=0
count=0
while(i<length):
while(j>=count):
print m[i][j]
j-=1
i+=1
j+=1
while(i<=length):
print m[i][j]
i+=1
j+=1
i-=1
while j <=columnlength:
print m[i][j]
j+=1
j-=1
i-=1
while i >count:
print m[i][j]
i-=1
count+=1
length-=1
columnlength-=1
j=columnlength
i=count
matrix=[['C','I','P','E'],
['R','N','K','U'],
['U','O','W','O'],
['L','E','S','Y']]
matrix1=[['C','I','P','E','*'],
['R','N','K','*','U'],
['U','O','W','*','O'],
['L','E','S','*','Y']]
spiral(matrix1,3,4)
Can also do it iteratively:
public static void printSpiralMatrix(char[][] data) {
if(!validInput(data)) return;
int max = data.length - 1;
for(int i = max; i > 0; i -= 2) {
printBorder(data, (max - i)/2, max - ((max - i)/2));
}
System.out.println();
}
public static void printBorder(char[][] data, int min, int max) {
int i;
for(i = max; i >= min; i--) {
System.out.print(data[min][i]);
}
for(i = min + 1; i <= max; i++) {
System.out.print(data[i][min]);
}
for(i = min + 1; i <= max; i++) {
System.out.print(data[max][i]);
}
for(i = max - 1; i > min; i--) {
System.out.print(data[i][max]);
}
}
private static boolean validInput(char[][] data) {
if(data == null) return false;
for(int i = 0; i < data.length; i++) {
if(data[i] == null) return false;
}
return true;
}
public class SpiralMatrix {
final static int n = 5;
public static void main(String arg[]) {
int num = 0;
int [][] matrix = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
matrix[i][j] = num++;
}
}
printSpiralMatrix(matrix);
}
static void printSpiralMatrix(int[][] matrix) {
int iOddIncCounter = 0;
int iOddDecCounter = 1;
int jEvenIncCounter = 0;
int jEvenDecCounter = 0;
int i = 0, j = n;
for(int loop = 0; loop < (2*n-1); loop++){
if(loop%2 == 0) {
if((loop/2)%2 == 0) {
j = j-1;
int k = j;
for(; k >= jEvenDecCounter; k--){
System.out.print(matrix[i][k] + " ");
}
j=k+1;
jEvenDecCounter++;
}
else {
j = j+1;
int k = j;
for(; k<(n-jEvenIncCounter); k++){
System.out.print(matrix[i][k] + " ");
}
j=k-1;
jEvenIncCounter++;
}
}
else {
if((loop/2)%2 == 0) {
i = i+1;
int k = i;
for(; k < (n-iOddIncCounter); k++){
System.out.print(matrix[k][j] + " ");
}
i = k-1;
iOddIncCounter++;
}
else {
i = i-1;
int k = i;
for(; k >= iOddDecCounter; k--){
System.out.print(matrix[k][j] + " ");
}
i = k+1;
iOddDecCounter++;
}
}
}
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package interviews.epic;
/**
*
* @author venkatramreddykunta
*/
public class MatrixLevel {
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] c = {{'c','i','p','e'},{'r','n','k','u'},{'u','o','w','o'},{'l','e','s','y'}};
int level=0;
printTopLevels(c,level);
}
// c i p e < - start here
// r n k u
// u o w o
// l e s y
private static void printTopLevels(char[][] c, int level) {
printCurrentLevel(c,level);
}
// c i p e < - start here
// r u
// u o
// l e s y
private static void printCurrentLevel(char[][] c, int level) {
int i=0,lastIndex=c.length-level-1,startIndex=level;
if(level==c.length/2)
return;
// print top left <-top right
// i p e < - start here
for(i=lastIndex;i>startIndex;i--){
System.out.print(c[level][i]);
}
// c
// r
// u
// print top left - > bottom left
for(i=startIndex;i<lastIndex;i++){
System.out.print(c[i][level]);
}
// l e s
// print bottom left -> bottom right
for(i=startIndex;i<lastIndex;i++){
System.out.print(c[lastIndex][i]);
}
// u
// o
// y
// print bottom right to top right
for(i=lastIndex;i>startIndex;i--){
System.out.print(c[i][lastIndex]);
}
printTopLevels(c,level+1);
}
}
Try to convert spiral matrix into counter spiral...that would be far easy and fun learning.
- Hitesh Vaghani October 13, 2014// For 4 X 4 Matrix int m = 4, n = 0, k = 0, l = 4, i; /* k - starting row index m - ending row index l - starting column index n - ending column index i - iterator */ while(k < m && l > n) { for(i = l-1; i >= n; i--) cout<<a[k][i]<<" "; k++; for(i = k; i < l; i++) cout<<a[i][n]<<" "; n++; if(k < m) { for(i = n; i < l; i++) cout<<a[m-1][i]<<" "; m--; } if (l > n) { for (i = m-1; i >= k; --i) { cout<<a[i][l-1]<< " "; } l--; } }