Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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();
}
}
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 ();
}
}
- 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++;
}
}
}
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).
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.
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.
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");
}
}
}
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
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++;
}
}
- 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++;
}
}
}
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()
#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;
}
}
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++;
}
}
}
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;
}
/**
*
* @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);
}
}
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());
}
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:
}
- Igor October 21, 2014