Yahoo Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
This problem can be simplified by considering each coil to be a sequence of moves where each move is a pair of direction (up, down, left, right) and distance (1,2,3,...). For n=1 the sequences for each coil are:
U2 R2 D3
D2 L2 U3
For n=2 they are:
U2 R2 D4 L4 U6 R6
D2 L2 U4 R4 D6 L6
We observe a simple pattern. The direction follows the repeating sequence U, R, D, L for coil #1 and D, L, U, R for coil #2. The distance follows the sequence 2,2,4,4,6,6,...,2i,2i (except the last 2 values are 2i-1 when n is odd). We can use this simple pattern to our advantage. Code follows:
public class YahooCoils {
public static void main(String[] args) {
dumpcoils(1);
dumpcoils(2);
dumpcoils(3);
dumpcoils(4);
}
static void dumpcoils(int n) {
int a[][] = new int[4*n][4*n];
initializeMatrix(a, n);
dumpcoil(2*n, 2*n - 1, 0, a);
dumpcoil(2*n - 1, 2*n, 2, a);
}
static void initializeMatrix(int a[][], int n) {
int k = 1;
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < a[0].length; ++j) {
a[i][j] = k++;
if (n <= 2) {
System.out.print(String.format("%02d", a[i][j]) + " ");
}
else {
System.out.print(String.format("%03d", a[i][j]) + " ");
}
}
System.out.print("\n");
}
}
static void dumpcoil(int i, int j, int step, int a[][]) {
int distance = 2;
int k = 0;
while (i < a.length && j < a.length && i >= 0 && j >= 0) {
System.out.print(a[i][j] + " ");
switch (step % 4) {
case 0:
--i;
break;
case 1:
++j;
break;
case 2:
++i;
break;
case 3:
--j;
break;
}
k++;
if (k == distance) {
k = 0;
++step;
if (step % 2 == 0) {
distance += 2;
}
}
}
System.out.print("\n");
}
}
This code prints the first coil, also with tests for n = 1 or 2
public class MatrixCoil {
int[][] matrix;
public int[] coil1;
public int[] coil2;
MatrixCoil(int n){
matrix = new int[4*n][4*n];
int num=1;
for(int i=0;i<matrix.length;i++) {
for(int j=0;j<matrix[i].length;j++) {
matrix[i][j] = num++;
System.out.print(num + " ");
}
System.out.println("");
}
}
public void printCoil() {
int tn = (matrix.length*matrix.length)/2;
coil1 = new int[tn];
coil2 = new int[tn];
// start of first coil
int ci = matrix.length/2;
int cj = matrix.length/2-1;
System.out.println("ci " + ci);
System.out.println("cj " + cj);
int step = 0;
int index=0;
coil1[index] = matrix[ci][cj];
while(index<tn-1) {
step+=2;
for(int i=0;i<step&&index<tn-1;i++) {
// decrement ci
index++;
ci--;
coil1[index] = matrix[ci][cj];
if(ci==0) break;
}
for(int i=0;i<step&&index<tn-1;i++) {
// increment cj
index++;
cj++;
coil1[index] = matrix[ci][cj];
if(cj==matrix.length-1) break;
}
step+=2;
for(int i=0;i<step&&index<tn-1;i++) {
// increment ci
index++;
ci++;
coil1[index] = matrix[ci][cj];
if(ci==matrix.length-1) break;
}
for(int i=0;i<step&&index<tn-1;i++) {
// decrement cj
index++;
cj--;
coil1[index] = matrix[ci][cj];
if(cj==0) break;
}
}
for(int i=0;i<coil1.length;i++) {
System.out.print(coil1[i] + " ");
}
System.out.println("");
for(int i=0;i<coil2.length;i++) {
System.out.print(coil2[i] + " ");
}
}
}
and tests
import org.testng.Reporter;
import org.testng.annotations.Test;
import static org.testng.Assert.assertEquals;
@Test
public class MatrixCoilTest {
public void shouldPrintCoil() {
MatrixCoil mc = new MatrixCoil(1);
mc.printCoil();
assertEquals(10,mc.coil1[0]);
assertEquals(16,mc.coil1[7]);
}
public void shouldPrintCoil2() {
MatrixCoil mc = new MatrixCoil(2);
mc.printCoil();
assertEquals(36,mc.coil1[0]);
assertEquals(64,mc.coil1[31]);
}
}
int[][] matrix;
public void getMatix(int n){
matrix = new int[4*n][4*n];
int num=1;
for(int i=0;i<matrix.length;i++) {
for(int j=0;j<matrix[i].length;j++) {
matrix[i][j] = num++;
}
}
}
public int[] lower_coil_rotate = {-1,1,1,-1};
public int[] upper_coil_rotate = {1,-1,-1,1};
public int[] getMap(int[] arr, int size){
int[] lc_map = new int[size-1];
int move=0;
for (int i = 0, side =1; i < lc_map.length; i++, side++) {
if(side > 4) side = 1;
if(side % 2 == 1 ){
move+=2;
}
if(move >= size)move = size-1;
lc_map[i] = arr[side-1]*move;
}
return lc_map;
}
public void print(int x, int y, int[] path, int size){
System.out.print(" "+matrix[x][y]);
for (int p = 0; p < path.length; p++) {
int xdes = x+path[p];
if (x > xdes) {
for (int i = x-1; i >= xdes; i--) {
System.out.print(" "+matrix[i][y]);
}
}else{
for (int i = x+1; i <= xdes; i++) {
System.out.print(" "+matrix[i][y]);
}
} x = xdes; p++;
if( p >= path.length)break;
System.out.print(" -> ");
int ydes =y+path[p];
if (y > ydes) {
for (int j = y-1; j >= ydes; j--) {
System.out.print(" "+matrix[x][j]);
}
}else{
for (int j = y+1; j <= ydes; j++) {
System.out.print(" "+matrix[x][j]);
}
} y = ydes;
System.out.print(" -> ");
}
}
public static void main(String args[]) throws Exception {
SolutionTest solution = new SolutionTest(); solution.getMatix(2);
int[] lc = solution.getMap(solution.lower_coil_rotate, 8);
solution.print(4, 3, lc, 8);
int[] uc =solution.getMap(solution.upper_coil_rotate, 8);
System.out.println();
solution.print(3, 4, uc, 8);
}
def spiral(arr, cord1, cord2, n, r1, c1, r2, c2):
if n <= 0:
return
for i in range(n):
cord1.append(arr[r1][c1])
r1 += 1
r1 -= 1
c1 += 1
for i in range(n - 2):
cord1.append(arr[r1][c1])
c1 += 1
c1 -= 1
r1 -= 1
for i in range(n):
cord2.append(arr[r2][c2])
r2 -= 1
r2 += 1
c2 -= 1
for i in range(n - 2):
cord2.append(arr[r2][c2])
c2 -= 1
c2 += 1
r2 += 1
spiral(arr, cord2, cord1, n - 2, r2, c2, r1, c1)
arr = [
[1, 2, 3, 4, 5, 6, 7, 8],
[9, 10, 11, 12, 13, 14, 15, 16],
[17, 18, 19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30, 31, 32],
[33, 34, 35, 36, 37, 38, 39, 40],
[41, 42, 43, 44, 45, 46, 47, 48],
[49, 50, 51, 52, 53, 54, 55, 56],
[57, 58, 59, 60, 61, 62, 63, 64]
]
cord1 = []
cord2 = []
n = len(arr)
spiral(arr, cord1, cord2, n, 0, 0, n - 1, n - 1)
cord1.reverse()
cord2.reverse()
print cord1
print cord2
import java.util.Scanner;
public class Micro1 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int n;
Scanner sca=new Scanner(System.in);
System.out.println("enter the value of n");
n=sca.nextInt();
int i,j;
int b[][]=new int[4*n][4*n];
int a=1;
for(i=0;i<4*n;i++)
{for(j=0;j<4*n;j++)
{b[i][j]=a;
a++;
System.out.print(+b[i][j]);System.out.print("\t");}System.out.println("");}
int c1[]=new int[8*n*n];
int c2[]=new int[8*n*n];
int p=0,q=0;
for(j=0;j<4*n;j++)
{for(i=0;i<4*n;i++)
{if(j<n)/*if j<n all in c2 */
{c2[p]=b[i][j];p++;}
else if(j>=n&&j<2*n)
if(i>=3*n){c2[p]=b[i][j];p++;}
else{c1[q]=b[i][j];q++;}
else if(j>=2*n&&j<3*n)
if(i>=n){c2[p]=b[i][j];p++;}
else{c1[q]=b[i][j];q++;}
else if(j>=3*n){c1[q]=b[i][j];q++;}
}
}
for(i=0;i<8*n*n;i++){System.out.print(+c1[i]);System.out.print("\t");}
System.out.println();
for(i=0;i<8*n*n;i++){System.out.print(+c2[i]);System.out.print("\t");}
}}
import java.util.Scanner;
public class Micro1 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int n;
Scanner sca=new Scanner(System.in);
System.out.println("enter the value of n");
n=sca.nextInt();
int i,j;
int b[][]=new int[4*n][4*n];
int d=1;
for(i=0;i<4*n;i++)
{for(j=0;j<4*n;j++)
{b[i][j]=d;
d++;
System.out.print(+b[i][j]);System.out.print("\t");}System.out.println("");}
int c[]=new int[4*n];
int c1[]=new int[(8*n*n)];
int c2[]=new int[(8*n*n)];
int p=0,q=0,s=1;c[2*n]=1;c[(2*n)-1]=1;
for(i=(2*n)-2;i>=0;i--){c[i]=c[i+1]+2;}
for(i=(2*n)+1;i<4*n;i++){c[i]=c[i-1]+2;}
int a=0;
for(i=0;i<4*n;i++)
{for(j=0;j<4*n;j++)
{if(j>=s&&j<=(s+c[i])-1)
{if(i==0||i%2==0){c1[p]=b[i][j];p++;a=0;}
else{c2[q]=b[i][j];q++;a=1;}}
else{if(a==0){{c2[q]=b[i][j];q++;a=1;}}
else{{c1[p]=b[i][j];p++;a=0;
}a=0;if(i<(2*n)-1){s++;}
else{s--;}
}
for(i=0;i<(8*n*n);i++){System.out.print(+c1[i]);System.out.print("\t");}
System.out.println();
for(i=0;i<(8*n*n);i++){System.out.print(+c2[i]);System.out.print("\t");}
}}
import java.io.*;
import java.util.*;
class Matrix
{
public static void main(String[] args)
{
int count=0;
Scanner sc= new Scanner(System.in);
System.out.println("Enter your choice n=");
int n=sc.nextInt();
int p=4*n,q=4*n;
int a[][]=new int[p][q];
for(int i=0;i<p;i++){
for(int j=0;j<q;j++)
{ //Function for generating Random Numbers.
a[i][j]=(int) (Math.random() * 89 + 10);
System.out.print(a[i][j]);
System.out.print(" ");
count++;
if(count==4*n){
System.out.println("\n\n ");
count=0;
}
}
}
int c=(4*n)/2,c1=c-1,c2=4*n-1,count1=0;
// This is for Upper Coil.
System.out.println("\nThis is Uppercoil------->\n");
for(int x1=c;x1>=0;x1--){
System.out.print(a[x1][c-1]);
System.out.print(" ");
}
for(int x2=c;x2<c2;x2++){
System.out.print(a[0][x2]);
System.out.print(" ");
}
for(int x3=0;x3<=c2;x3++){
System.out.print(a[x3][c2]);
System.out.print(" ");
}
// This is for Lower Coil.
// int c=(4*n)/2,c1=c-1,c2=4*n-1,count1=0;
System.out.println("\n\nThis is LowerCoil------->\n");
for(int x4=c1;x4<=c2;x4++){
System.out.print(a[x4][c]);
System.out.print(" ");
}
for(int x5=c1;x5>0;x5--){
System.out.print(a[c2][x5]);
System.out.print(" ");
}
for(int x6=c2;x6>=0;x6--){
System.out.print(a[x6][0]);
System.out.print(" ");
}
System.out.println(" ");
}
}
public class Print2Coils {
/**
* @param args
*/
public static void main(String[] args) {
int r,c,i=1;
int n = 2;
int a[][] = new int[4*n][4*n];
for(r=0;r<4*n;r++){
for(c=0;c<4*n;c++){
a[r][c] = i;
i++;
}
}
for(r=0;r<4*n;r++){
for(c=0;c<4*n;c++){
System.out.print(a[r][c]+" ");
}
System.out.println();
}
print2Coils(a,4*n);
}
private static void print2Coils(int[][] a, int n) {
printCoil(a,n/2,n/2-1,1,n);
System.out.println();
printCoil(a,n/2-1,n/2,-1,n);
}
private static void printCoil(int[][] a, int r, int c, int i, int n) {
int x = 0;
int y = 0;
int z = 2;
System.out.print(a[r][c]+" ");
while(true){
while(x<z){
r = r-i;
if(r<0||r>=n)
break;
System.out.print(a[r][c]+" ");
x++;
}
if(r<0||r>=n)
break;
while(y<z){
c=c+i;
if(c<0||c>=n)
break;
System.out.print(a[r][c]+" ");
y++;
}
if(c<0||c>=n)
break;
x=y=0;
z=z+2;
i=-i;
}
}
}
#include<stdio.h>
int max(int x,int y){
if(x > y)
return x;
else
return y;
}
int min(int x,int y){
if(x > y)
return y;
else
return x;
}
int main(){
int i,j,ii,jj,flag,flag1,flag2,n,inc;
int a[8][8];
n=8;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=n*i+j+1;
i=n/2;
j=n/2-1;
inc = 2;
flag = 0;
flag1=1;
flag2 = 1;
printf("\nCoil 1:");
while(flag1){
switch(flag)
{
case 0:
if(flag2){
ii=i;
flag2=0;
}
else
ii=i-1;
for(;ii>=max(i-inc,0);ii--)
printf("%d ",a[ii][j]);
i=i-inc;
if(i < 0)
flag1=0;
flag = 1;
break;
case 1:
for(jj=j+1;jj<=min(j+inc,n-1);jj++)
printf("%d ",a[i][jj]);
j = j+inc;
if(j >= n)
flag1=0;
flag = 2;
inc+=2;
break;
case 2:
for(ii=i+1;ii<=min((i+inc),n-1);ii++)
printf("%d ",a[ii][j]);
i=i+inc;
if(i >= n)
flag1=0;
flag = 3;
break;
case 3:
for(jj=j-1;jj>=max(j-inc,0);jj--)
printf("%d ",a[i][jj]);
j = j-inc;
flag = 0;
if(j < 0)
flag1=0;
inc+=2;
break;
}
}
printf("\nCoil 2:");
i=n/2-1;
j=n/2;
inc = 2;
flag = 0;
flag1=1;
flag2 = 1;
while(flag1){
switch(flag)
{
case 2: for(ii=i-1;ii>=max(i-inc,0);ii--)
printf("%d ",a[ii][j]);
i=i-inc;
if(i < 0)
flag1=0;
flag = 3;
break;
case 3:
for(jj=j+1;jj<=min(j+inc,n-1);jj++)
printf("%d ",a[i][jj]);
j = j+inc;
if(j >= n)
flag1=0;
flag = 0;
inc+=2;
break;
case 0:
if(flag2){
ii=i;
flag2=0;
}
else
ii=i+1;
for(;ii<=min((i+inc),n-1);ii++)
printf("%d ",a[ii][j]);
i=i+inc;
if(i >= n)
flag1=0;
flag = 1;
break;
case 1:
for(jj=j-1;jj>=max(j-inc,0);jj--)
printf("%d ",a[i][jj]);
j = j-inc;
flag = 2;
if(j < 0)
flag1=0;
inc+=2;
break;
}
}
return 0;
}
By using OO think:
public class InterleavedCoils {
public void printCoils(int i) {
int[][] a = this.generateArray(i);
for (int row=0; row<4*i; row++) {
for (int line=0; line<4*i; line++)
System.out.print(a[row][line] + " ");
System.out.println("");
}
Coordinate start = new Coordinate();
start.setX(0.0);
start.setY(0.0);
this.printRings(a, start);
start.setX(a.length-1.0);
start.setY(a.length-1.0);
this.printRings(a, start);
}
/**
* 4xi代表行数和列数
* @param i
* @return
*/
private int[][] generateArray(int i) {
int s = 4*i;
int[][] a = new int[s][s];
int r=0,l=0;
for (int j=1; j<=s*s; j++) {
a[r][l]=j;
if(l==s-1) {
l=0;
r++;
} else l++;
}
return a;
}
private void printRings(int[][] a, Coordinate start) {
int len = a.length;
Coordinate next = new Coordinate();
List<Integer> list = new ArrayList<Integer>();
if ((start.getX()==0.0&&start.getY()==0.0) || (start.getY()==a.length-1&&start.getX()==a.length-1)) { // 起始点要么x=0且y=边长-1,要么y=边长-1且x=边长-1
for (int time=1; time<len; time++) {
// System.out.println("原始起点:"+ start.getX() + " , " + start.getY() + " : " + time);
int direction = this.getDirection(start, time);
int step = len-2*(time/2); // 记录步长(1上;2下;3左;4右)
if (list!=null && !list.isEmpty()) {
} else { // 第一步
if (start.getX()==0.0) { // 刚开始要把点往上移一点
next.setX(-1.0);
next.setY(start.getY());
} else {// 刚开始要把点往下移一点
next.setX((double)len);
next.setY(start.getY());
}
}
next = this.move(list, step, direction, a, next);// next点为转弯点
}
} else ;
// System.out.print("交错线圈:");
for (int i=0; i<list.size(); i++)
System.out.print(list.get(i)+" ");
System.out.println("");
}
/**
* 根据最起始坐标和轮回次数来判断这轮的方向
* @param start
* @param time
* @return
*/
private int getDirection(Coordinate start, int time) {
int direction = 0;
if (start.getX()==0.0) {
switch (time%4) {
case 1:
direction=2;
break;
case 2:
direction=4;
break;
case 3:
direction=1;
break;
case 0:
direction=3;
break;
}
} else {
switch (time%4) {
case 1:
direction=1;
break;
case 2:
direction=3;
break;
case 3:
direction=2;
break;
case 0:
direction=4;
break;
}
}
return direction;
}
/**
* 本轮移动步数
* @param list 返回list
* @param step 走的步数
* @param direction 走的方向,1 - 上;2 - 下;3 - 左;4 - 右.
*/
private Coordinate move(List<Integer> list, int step, int direction, int[][] array, Coordinate start) {
Coordinate next = new Coordinate();
switch(direction) {
case 1: // 向上
int x = start.getX().intValue()-1;
int y = start.getY().intValue();
for (int i=x; i>x-step; i--) {
list.add(array[i][y]);
next.setX((double)i);
next.setY((double)y);
}
break;
case 2: // 向下
x = start.getX().intValue()+1;
y = start.getY().intValue();
for (int i=x; i<x+step; i++) {
list.add(array[i][y]);
next.setX((double)i);
next.setY((double)y);
}
break;
case 3: // 向左
x = start.getX().intValue();
y = start.getY().intValue()-1;
for (int j=y; j>y-step; j--) {
list.add(array[x][j]);
next.setX((double)x);
next.setY((double)j);
}
break;
case 4: // 向右
x = start.getX().intValue();
y = start.getY().intValue()+1;
for (int j=y; j<y+step; j++) {
list.add(array[x][j]);
next.setX((double)x);
next.setY((double)j);
}
break;
}
return next;
}
/**
* @param args
*/
public static void main(String[] args) {
InterleavedCoils coil = new InterleavedCoils();
coil.printCoils(2);
}
}
- outspacecode December 16, 2012