## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

static void generate_sequence(int A)
{
int seq[]=new int[100];
for(int i=0;i<100;++i)
seq[i]=0;
int k,j=0;
while(A>=2 && j<100)
{
if(A%2==0)
{
seq[j++]=A/2;
A/=2;
}
else
{
seq[j++]=A-1;
A=A-1;
}
}
System.out.println("Shortest Possible sequence will be as:");
for(k=0;seq[k]!=0;++k)
System.out.print(seq[k]+" ");
System.out.println("\nnumber of factors used will be as:"+k+"");
}

Here the idea is that we have to consider two cases :
1) if the number n is odd then i am dividing it as (n-1) and 1 as 1 is anyhow there in the sequence so only an even factor (n-1) is introduced.
2) if the number n is even then simply divide it as (n/2) and (n/2) so in this too effectively one factor will be introduced.

Complexity of it will be O(lgA)
Please suggest if any improvement is possible

Comment hidden because of low score. Click to expand.
0

Awesome.
Great Logic.

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

nitin, good solution but how do we prove that your solution will produce smallest sequence?

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.

### 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.