Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
5
of 5 vote

Are you sure in second example? Maybe, it should be:
1 2 4 7 11 16 22 29 37
3 5 8 12 17 23 30 38
6 9 13 18 24 31 39
10 14 19 25 32 40
15 20 26 33 41
21 27 34 42
28 35 43
36 44
45

if yes, code in C++ looks like this:

#include <iostream>
#include <cstring>
#include <climits>
using namespace std; 

int main(){
    int N;
    int  start = 1;
    int  cur = 0;

    cin >> N;
    for(int i=0; i + start <=N; i++){
        start += i;
        cur = start;
        for (int j = i; j+cur <= N; j++){
            cur = cur+j;
            cout << cur << " ";
        }
        cout << endl;
    }

}

- Igor October 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Igor - Its cool but how have you thought about this solution?

- var October 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@var, What do you mean?

- Igor October 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I convert your code to Java with a few modifications as the followings:

static void printIt(int[] cs) {
		int start = 0, cur = 0;
		int len = cs.length;
		for (int i = 0; i + start <= len; i++) {
			start += i;
			cur = start;
			for (int j = i; j + cur <= len; j++) {
				cur = cur + j;
				if(cur< len)
				System.out.print("[" + cs[cur] + "]");
			}
			System.out.println();
		}
	}

- Anonymous October 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is pretty much the same solution with number formatting and lines limit
though instead of
01 02 04 07 11 15 19 23 27 31 35 39
03 05 08 12 16 20 24 28 32 36 40 43
06 09 13 17 21 25 29 33 37 41 44
10 14 18 22 26 30 34 38 42 45
we'll get
01 02 04 07 11 15 19 23 27 31 35 39 43
03 05 08 12 16 20 24 28 32 36 40 44
06 09 13 17 21 25 29 33 37 41 45
10 14 18 22 26 30 34 38 42

public static void printSimple (int[] array, int linesMax) {

	int maxLength = 0;
	int maxPow = 1;
	for (int i = 0; i < array.length; i++) {
		int tmp = array[i] / maxPow;
		while (tmp > 0) {
			maxLength++;
			maxPow *= 10;
			tmp /= 10;
		}
	}
	
	String format = "%0" + maxLength + "d ";
	
	int startnext = 0;
	for (int incstart = 1; incstart <= linesMax; incstart++) {
		int i = startnext;
		startnext += incstart + 1;
		for (int inc = incstart; inc <= linesMax; inc++) {
			System.out.format (format, array[i]);
			i += inc;
		}
		while (i < array.length) {
			System.out.format (format, array[i]);
			i += linesMax;
		}
		System.out.println ();
	}
}

- Anonymous October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

- Language: C++
- Strategy:
assumptions: our array items follow an arithmetic progression with offset = 1.


Sequence #1:
We notice that each displayed line is a sequence of this type ("labeled x-axis sequence"):
s is the first term on the line
k is a value that will increment from line to line

s, s+k+1,s+k+1+2, s+k+1+2+3, s+k+1+2+3+4, .....up to s+k+1+2+...+m

such that s+ k+1+2+3+4...+m is the last term <= n (n is the last term in the original array)

Now that we can display one line, how do we increment value s and value k from line to line?
We notice that the first term for each new line is part of a sequence of this type (labeled "y axis sequence"):
s is the starting element of the array

s, s+2, s+2+3, s+2+3+4, s+2+3+4...+m

where s+2+3+4...+m is last term <= n (n is the last item of the array).
Also k, is incremented from line to line.

So after noticing these two sequences.
now it is a matter of incrementing the starting number of each line using "x-axis sequence" until we hit a value that is > n; in which case you start a new line with a new starting element calculated using the "colum-wise sequence" above and incrementing k.

Example with dataset [0...8]
starting s = 1;
starting k = 0;
first line

s, s+k+1, s+k+1+2, s+k+1+2+3 => 1, 1+0+1, 1+0+1+2, 1+0+1+2+3 => 1, 2, 4, 7

next element in sequence above would be > 8, go to next line and set new s = s+2 = 3, k=1

s, s+k+1, s+k+1+2 => 3, 3+1+1, 3+1+1+2 => 3, 5, 8

the next element in sequence above = 8, display it and set new s = (s+2)+3 = 6, k = 2

s	=> 6

next element in the sequence above is 6+2+1 which is >8, so calculate new s= (s+2+3)+4
and the new s turns out to be > 8, which indicates that any element on this line after this value is > 8.

The code below assumes an array with consecutive integers, but it can easily be used on any type of array if instead of manipulating values, we manipulate their indexes.


Code:

#include <cstdlib> 
#include <iostream> 

#define N  45 //8 //45
using namespace std; 
void diagonal(int start, int end);

int main (int argc, char ** argv) { 
	//generate data
	int size = N;
	//call function to display in diagonal
	diagonal(1, size);
}
void diagonal (int beginning, int end){ 
	int number = beginning; 
	int start = number;
	int xIncrement = 1; 
	int previousXIncrement = 1;
	int yIncrement = 2;
	while (number <= end) { 
		printf ("%u ", number);
		if ((number + xIncrement) > end) { 
			//go to next line
			//reset some parameters
			printf ("\n");
			//the starting number of the current row is the new start
			//the increment along the y-axis is updated
			start = start + yIncrement;
			number = start;
			yIncrement++;
			//now we increment starting from the previous original increment but + 1
			//the increment along x-axis is updated too
			xIncrement = previousXIncrement + 1;
			previousXIncrement++ ;		
		}
		else { 
			number = number + xIncrement;
			xIncrement++;
		}	
	}
}

- nathaliekaligirwa October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I liked this solution but it does not solve the problem..

This solution increases the row count as given in problem statement also does not reduce the inc counter at the End.

If you notice increment counter should reduce from 4 to 3 at the end. for example after 40 it expected to print 43 not 44.

Number of rows (4 in this example) should also be an input, number of column should be calculated (12 in this example).

- dd.metro October 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh I see, I assumed a pure diagonal solution, sorry about that. I will look into this solution. However, one way I can think of is to put a condition such as: don't let the y-axis increment go over 4, and once it is over 4, the x-axis increment should not change unless we are at the end in which case it decrements and don't let the number of items per row go over 12.

- nathaliekaligirwa October 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

OK, after much thought the easiest answer would be to have an unrestricted number of columns (same solution as PavPS proposed).
If the number of columns is restricted:
Approach #1:
- if the number of columns > max number of columns and if the value that was supposed to go on that column is < last element of array, pass down the value to the next column.
That means if we are on the last column or the next value > last element in array, we have to check if there is a value that was passed down. If there is, display it and check again if you need to pass down another value.

#Approach two:
Store values in arrays, each one representing a row and then display them one by one (space complexity is terrible though).

The implementation might be trickier for the first approach but this is the best I could come up with.

- nathaliekaligirwa October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class patrn
{
public static void main(String a[])
{
int cnt=0,n=45,c=0,s=0,is=0;
for(int i=1;cnt<n;i++)
{
c=c+i;
is=i;
for(int j=1;c<=n;j++)
{
if(j==1)
{
s=c;
}
System.out.print(c+"\t");
cnt++;
//try{Thread.sleep(1000);}catch(Exception e){}
c=c+(is++);
}
c=s;
System.out.printf("\n");
}
}
}

- krishnan October 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> values;
	for (int i = 1; i <= 45;++i)
		values.push_back(i);

	const int RowCount = 4;
	for (int start = 0, majorStep = 2, row = 0; row < RowCount; start+= min(RowCount,majorStep), ++majorStep, ++row)
	{
		for (int k = start, minorStep = majorStep-1; k < values.size(); k+= min(RowCount,minorStep), ++minorStep)
			cout << setw(2) << values[k] << " ";
		cout << endl;
	}

Outputs:

1  2  4  7 11 15 19 23 27 31 35 39 43 
 3  5  8 12 16 20 24 28 32 36 40 44 
 6  9 13 17 21 25 29 33 37 41 45 
10 14 18 22 26 30 34 38 42

The output above is a little bit different (regarding the last rows) but the diagonal idea is the same

- PavPS October 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just a little simpler to read

public void printDiag(char[] x){
	    int start = 0;
	    int inc =1;
	    while(start<x.length){
	        printLine(x, start, inc);
	        System.out.println();
	        start+= ++inc;
	    }
	}

	private void printLine(char[] x, int start, int inc){
	    while(start<x.length){
	        System.out.print(x[start] +"\t");
	        start += inc++;
	    }
	}

- engzizo October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Language: C++
- Strategy:
assumptions: our array items follow an arithmetic progression with offset = 1.


Sequence #1:
We notice that each displayed line is a sequence of this type ("labeled x-axis sequence"):
s is the first term on the line
k is a value that will increment from line to line

s, s+k+1,s+k+1+2, s+k+1+2+3, s+k+1+2+3+4, .....up to s+k+1+2+...+m

such that s+ k+1+2+3+4...+m is the last term <= n (n is the last term in the original array)

Now that we can display one line, how do we increment value s and value k from line to line?
We notice that the first term for each new line is part of a sequence of this type (labeled "y axis sequence"):
s is the starting element of the array

s, s+2, s+2+3, s+2+3+4, s+2+3+4...+k

where s+2+3+4...+m is last term <= N (N is the last item of the array).
Also k, is incremented from line to line.

So after noticing these two sequences.
now it is a matter of incrementing the starting number of each line using "x-axis sequence" until we hit a value that is > N; in which case you start a new line with a new starting element calculated using the "colum-wise sequence" above and incrementing k.

Example with dataset [0...8]
starting s = 1;
starting k = 0;
first line
s, s+k+1, s+k+1+2, s+k+1+2+3 => 1, 1+0+1, 1+0+1+2, 1+0+1+2+3 => 1, 2, 4, 7
next element in sequence above would be > 8, go to next line and set new s = s+2 = 6, k=1
s, s+k+1, s+k+1+2 => 3, 3+1+1, 3+1+1+2 => 3, 5, 8
the next element in sequence above = 8, display it and set new s = (s+2)+3 = 6, k = 2
s => 6
next element in the sequence above is 6+2+1 which is >8, so calculate new s= (s+2+3)+4
and the new s turns out to be > N, which indicates that any element on this line after this value is > N.

The code below assumes an array with consecutive integers, but it can easily be used on any type of array if instead of manipulating values, we manipulate their indexes.



Code:

#include <cstdlib> 
#include <iostream> 

#define N  45 //8 //45
using namespace std; 
void diagonal(int start, int end);

int main (int argc, char ** argv) { 
	//generate data
	int size = N;
	//call function to display in diagonal
	diagonal(1, size);
}
void diagonal (int beginning, int end){ 
	int number = beginning; 
	int start = number;
	int xIncrement = 1; 
	int previousXIncrement = 1;
	int yIncrement = 2;
	while (number <= end) { 
		printf ("%u ", number);
		if ((number + xIncrement) > end) { 
			//go to next line
			//reset some parameters
			printf ("\n");
			//the starting number of the current row is the new start
			//the increment along the y-axis is updated
			start = start + yIncrement;
			number = start;
			yIncrement++;
			//now we increment starting from the previous original increment but + 1
			//the increment along x-axis is updated too
			xIncrement = previousXIncrement + 1;
			previousXIncrement++ ;		
		}
		else { 
			number = number + xIncrement;
			xIncrement++;
		}	
	}
}

- Anonymous October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    cin>>N;
    int i, j;
    int start = 1;
    i=0; j=0;
    while(start<=N)
    {
        int k = start;
        int lvl = j;
        while(k<=N)
        {
            cout<<k<<" ";
            lvl++;
            k = k + lvl;
        }
        cout<<endl;
        j++;
        start = start+j+1;
    }
    return 0;

}

- Anonymous October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def main():
	maxn = 45
	num = 1
	colhead = 1
	coljump = 2
	rowjump = 1
	
	while True:
		if num > maxn:
			break
		print('{:02d}'.format(num), end = ' ')
		if num + rowjump > maxn:
			colhead += coljump
			num = colhead
			rowjump = coljump
			coljump +=1
			print()
		else:
			num += rowjump
			rowjump+=1

if __name__ == '__main__':
	main()

- . October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package main
import "fmt"

func main(){
	maxn := 45
	num,colhead,coljump,rowjump := 1,1,2,1
	
	for {
		if num > maxn {
			break
		}
		fmt.Printf("%02d ",num)
		if num + rowjump > maxn {
			colhead += coljump
			num = colhead
			rowjump = coljump
			coljump ++
			fmt.Println()
		} else {
			num += rowjump
			rowjump ++
		}
	}
}

- . October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

int main()
{

int i=1,n,k=1,m=0,flag=1,p=1,l=0;
scanf("%d",&n);


while(flag)
{

if(k>n)
{
flag=0;
}
else
{



for(i=k; i<=n; i++)
{


printf("%d\t",i);
i=i+m+l;


m=m+1;

}
printf("\n");

//printf("lvalue%d",l);

p=p+1;


}
k=k+p;
//printf("k value%d",k);
l=l+1;
m=0;



}


}

- satyajit October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

plz check my code if any problem let me know

- satyajit October 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DiagonalFormat {
	
	
	public static void main(String[] args) {
		
		int[] arr = {1,2,3,4,5,6,7,8};
		int start = 0;
		int inc = 1;
		for(int i=0;i<arr.length;i++) {
			
			printDiagonal(arr,start,  inc);
			inc = inc+1;
			 start += inc;
				
			System.out.println();
		
		}
		
	}
	
	static void printDiagonal(int[] arr , int start , int inc) {
			
		for(int i=start;i<arr.length;i++) {
			
			if(start>=arr.length)
				return;
			System.out.print(arr[start]);
			start += inc;
			inc++;
		}
		
	}

}

- shukad333 October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

plz check my code...if any problem let me know

- Anonymous October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have written code in C#

void printDiagonally(int max_int)
        {
            if (max_int < 0)
                return;

            int row_incrementer = 1;
            int row_start = 1;

            while (row_start <= max_int)
            {
                int col_incrementer = row_incrementer;
                int col_value = row_start;
                while (col_value <= max_int)
                {
                    Console.Write("{0} ", col_value);
                    col_value += col_incrementer;
                    col_incrementer++;
                }

                Console.WriteLine();
                row_incrementer++; 
                row_start += row_incrementer;                
            }

- JSDUDE October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Congrats you guys just did his homework for him

- Anonymous October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 *
 * @author alikatkar
 */
public class DiagonalPrint {

    private static final int MAX_ROW = 4;

    private static void print(int[] array) {

        if (array == null || array.length == 0) {
            return;
        }

        // In the question, there are only 4 rows
        StringBuilder[] rows = new StringBuilder[MAX_ROW];
        for (int i = 0; i < rows.length; i++) {
            rows[i] = new StringBuilder();
        }

        // distance from left corner
        int distance = 0;

        for (int i = 0; i < array.length; distance++) {

            rows[0].append(array[i++]).append(" ");

            for (int j = 0; i < array.length && j < distance && j < rows.length - 1; j++, i++) {
                rows[j + 1].append(array[i]).append(" ");
            }
        }

        for (StringBuilder sb : rows) {
            System.out.println(sb.toString());
        }
    }

    public static void main(String[] args) {

        int[] array = {1, 2, 3, 4, 5, 6, 7, 8};

        DiagonalPrint.print(array);

        array = new int[45];
        for (int i = 0; i < array.length; i++) {
            array[i] = i+1;
        }
        DiagonalPrint.print(array);
    }
}

- Ali Katkar October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printDiagonally(int[] dataset, int numLines) {
		StringBuilder lines = new StringBuilder();
		for (int line = 0; line < numLines; line++) {
			// beginning spacing for each line = lineNumber;
			int increment = line;
			// the starting element for a line = Σ (lineNumber)
			int counter = line + 1;
			int summation = 0;
			while (counter > 0) {
				summation += counter--;
			}
			int length = dataset.length;
			// elements in each line are printed until previous element + numLines > length
			for (int element = summation; element < length; element += increment) {
				lines.append(dataset[element] + " ");
				// for each subsequent element in a line, spacing++ until spacing = numLines
				if (increment != numLines) increment++;
			}
			lines.append("\n");
		}
		System.out.print(lines.toString());
	}

- Jeremy Gilreath January 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Any mention about number of rows and colums

- sk October 21, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More