Amazon Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
how you figured out that loop needs to be executed for 2*n-1 times??
Can you pls explain the algo?
@jane: Let me explain you this with an example:
For n = 5,
Upper Triangle:
------------------------------
0: arr[0][0]
1: arr[0][1] arr[1][0]
2: arr[2][0] arr[1][1] arr[0][2]
3: arr[0][3] arr[1][2] arr[2][1] arr[3][0]
4: arr[4][0] arr[3][1] arr[2][2] arr[1][3] arr[0][4]
Lower Triangle:
------------------------
5: arr[1][4] arr[2][3] arr[3][2] arr[4][1]
6: arr[4][2] arr[3][3] arr[2][4]
7: arr[3][4] arr[4][3]
8:arr[4][4]
so for n = 5, the lop iterates from 0 to 8(ie 0 to 2n-2)
/* This just prints the upper triangle.
Similar logic can be applied to
print the lower triangle too */
public void getUpperTri(int n) {
int val = 0;
for(int i=1;i<=n;i++) {
val++;
for(int j=1;j<=i;j++) {
if(i%2==1) {
if(j!=1) {
val -= n-1;
}
} else {
if(j!=1) {
val += n-1;
}
}
System.out.println(val);
if(i%2==0 &&i==j) {
val += n-1;
}
}
}
}
Waste a lot of char on preparation stuff
#include <iostream.h>
#include <cstdlib>
int main ()
{
int N,c,k,h,m,n,x,j,i=0;
char b[9];
std::cin>>b;
sscanf(b,"%d",&N);
c=k=m=x=1;h=N-1;
n=N;
for(;x<=N*N;h=-h,k+=c)
{
std::cout<<x<<" ";
x+=h>0?m:n;
for(j=0;j<k;j++,x+=h)std::cout<<x<<" ";
if (k==N-1){m=N;n=1;c=-1;}
}
}
given T(n) is n th number in the output sequence:
T(n) = T(n-1) + d(n)
d(n) is anther sequence having following pattern:
0 1 (N-1) N -(N-1) -(N-1) 1 (N-1) (N-1) (N-1) N ...
^0 -(N-1) ^1 (N-1) ^2 -(N-1) ^3 (N-1)
once the number of |N-1| increases to N-1, the number of IN-1| starts to decrease at the next repeat.
Also 1 and N inbetween those (N-1)s has following pattern:
..1..N..1..N..1 (N-1 times of |N-1|) 1...N..1...N...1...
or
..1..N..1..N..1..N (N-1 times of |N-1|) N..1...N..1...N...1...
Reason:
given N=3
We have
1 2 3
4 5 6
7 8 9
if we move right on the top or bottom edge of matrix
1+1==> 2
2+1 ==>3
x+1 ==> the right neighbor of x
similarly
on the left and right edges:
x+N==> the element below x
if we move along diagonals
x+(N-1) ==> move toward bottom-left
x-(N-1) ==> move toward top-right
public static void zigzagShow(int input){
int[][] matrix=new int[input][input];
int beginSet=1;
for(int i=0;i!=matrix.length;i++){
for(int j=0;j!=matrix.length;j++){
matrix[i][j]=beginSet++;
}
}
boolean direct=false;
//direct==true, show from top-right to bottom-left
//direct==false, show from bottom-left to top-right
int index_x=0;
int index_y=0;
while(!(index_x==input-1&&index_y==input-1)){
System.out.print(matrix[index_x][index_y]+" ");
if(direct){
try{
matrix[index_x+1][index_y-1]=matrix[index_x+1][index_y-1];
}
catch(Exception e1){
try{
matrix[index_x+1][index_y]=matrix[index_x+1][index_y];
}
catch(Exception e2){
index_y++;
direct=!direct;
continue;
}
index_x++;
direct=!direct;
continue;
}
index_x++;
index_y--;
}
else{
try{
matrix[index_x-1][index_y+1]=matrix[index_x-1][index_y+1];
}
catch(Exception e1){
try{
matrix[index_x][index_y+1]=matrix[index_x][index_y+1];
}
catch(Exception e2){
index_x++;
direct=!direct;
continue;
}
index_y++;
direct=!direct;
continue;
}
index_x--;
index_y++;
}
}
System.out.println(matrix[index_x][index_y]);
}
/* This just prints the upper triangle.
Similar logic can be applied to
print the lower triangle too */
public void getUpperTri(int n) {
int val = 0;
for(int i=1;i<=n;i++) {
val++;
for(int j=1;j<=i;j++) {
if(i%2==1) {
if(j!=1) {
val -= n-1;
}
} else {
if(j!=1) {
val += n-1;
}
}
System.out.println(val);
if(i%2==0 &&i==j) {
val += n-1;
}
}
}
}
public static int[] a14486004(int n, int[][] arr) {
int[] seq = new int[n * n];
int x = 0;
int y = 0;
int indx = 0;
boolean dir = true;
int d = 1;
int d1 = 0;
for (int i = 0; i < 2 * n - 1; i++) {
int s = x - y;
if (s<0){
s *= -1;
}
for (int j = 0; j < s; j++) {
seq[indx] = arr[y][x];
if (dir) {
x++;
y--;
} else {
x--;
y++;
}
indx++;
}
seq[indx] = arr[y][x];
indx++;
if (s == n - 1) {
d = 0;
d1 = 1;
}
if (dir) {
x += d;
y += d1;
} else {
x += d1;
y += d;
}
dir = dir ? false : true;
}
return seq;
}
// using C#.
// some functions' implementation are ignored: print, overloading != for class Node.
class Node
{
public:
int x;
int y;
}
void f(int n)
{
Node a = new Node(0,0);
Node last = new Node(n-1, n-1);
while(a!=last)
{
Traverse1st(a); //print the first stroke of Z
Traverse2nd(a); //print the second stroke of Z
Traverse3rd(a); //print the third stroke of Z
if(a!=last)
{
Traverse4th(a); //print the reverting stroke
}
}
print(a);
}
void Traverse1st(Node a)
{
print(a);
if(a.x<n-1)
{
a.x++;
}
else
{
a.y++;
}
}
void Traverse2nd(Node a)
{
print(a);
while(a.x>0 && a.y<n-1)
{
a.x--;
a.y++;
print(a);
}
}
void Traverse3rd(Node a)
{
print(a);
if(a.y<n-1)
{
a.y++;
}
else
{
a.x++;
}
}
void Traverse4th(Node a)
{
print(a);
while(a.x<n-1 && a.y>0)
{
a.x++;
a.y--;
print(a);
}
}
#include<iostream.h>
using namespace std;
int main()
{
int n,flag=0,i,j,k=2;
cout<<"Enter n:(n>=3)";
cin>>n;
while(n<3)
{
cout<<"Enter a valid Value:";
cin>>n;
}
int number = 1;
int loop_count = 4*n-5;
int ac;
cout<<number<<" ";
for(i=1;i<=loop_count;i++)
{
if(i%2==0)
{
if(i>loop_count/2+1)
{
ac = i/2 - k;
k = k+2;
}
else
ac = i/2;
for(j=0;j<ac;j++)
{
if(i%4==0)
number-=(n-1);
else
number+=(n-1);
cout<<number<<" ";
}
}
else
{
if(i == loop_count/2+2 && n%2 == 0)
flag = 0;
else if(i==loop_count/2+2 && n%2 != 0)
flag = 1;
if(flag == 0)
{
number+=1;
flag = 1;
}
else
{
number+=n;
flag = 0;
}
cout<<number<<" ";
}
}
}
i =0, dir = upright, turn = righ
while(i=0;i<2n-2;i++)
switch(dir)
upright:
if(x+1<n && y-1>=0)
print (x,y);
x++;y--;
else
turn==right:doTurn(right)?doTurn(down);
dir = downleft;
turn==right:turn=down?turn=right;
downleft:
if(x-1>=0 && y+1<n)
print (x,y);
x--;y++;
else
dir = upright;
turn==right:doTurn(right)?doTurn(down);
dir = upright;
turn==right:turn=down?turn=right;
doTurn(turn)
if(turn==right)
if(y+1<n)
y++;
if(turn==down)
if(y+1<n)
x++;
Move right when at top or bottom edge. move down when at left edge or right.
following is the code. Order of conditional statements should be reserved.
public void traverse_zigzag(int size)
{
traverse_recurse(size-1, 0,0, true);
}
private void traverse_recurse(int limit, int i, int j, boolean flag) {
int val = (i*(limit+1))+(j+1);
System.out.println(val);
if(val == (limit+1)*(limit+1))
{
return;
}
if(i==0 & flag)
{
traverse_recurse(limit, i, j+1, !flag);
}
else if(i==limit & !flag)
{
traverse_recurse(limit, i, j+1, !flag);
}
else if(j==0 & !flag)
{
traverse_recurse(limit, i+1, j, !flag);
}
else if(j==limit & flag)
{
traverse_recurse(limit, i+1, j, !flag);
}
else if(flag)
{
traverse_recurse(limit, i-1, j+1, flag);
}
else if(!flag)
{
traverse_recurse(limit, i+1, j-1, flag);
}
}
- pranaymahajan August 14, 2012