## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> Generate(int A)
{
vector<int> v;
while (A > 1)
{
if (A%2 == 0)
{
v.push_back(A/2);
A = A/2;
}
else
{
v.push_back((A+1)/2);
v.push_back((A-1)/2);
A = (A-1)/2;
}
}
v.push_back(1);
reverse(v.begin(),v.end());
}``````

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

I use the same way,but I can't prove it is correct,Can you prove it?

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

I also use the same way. I also can't prove it! anyone?

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

I'm going to try to prove it... bare with me... I think the least sequence is the position of the MSB of the represented number. The reason for this is there are only two ways of incrementing the number.

1) adding the number to itself
2) adding all the numbers previous.

The quickest way to reach i is to double i with each step. Sounds like binary. The MSB of the binary representation is the corresponding number of sequences.

Take 42 for instance: MSB 101010 LSB

that means 32, 8, and 2 are asserted. So we need to create numbers add up to 32, 8 and 2 that still abide by the rules...

well we are given 1 to begin the sequence so we only need to create numbers up to 31 and 7 (32 - num's we have) ... what's 31's binary? 11111... which 7 is contained in... so we need 1, 2, 4, 8, 16, 32, 42 as the smallest subset.

I don't know how to better explain it but it's impossible to reach the target number faster than doubling each step until you have the MSB of the binary representation.

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

so a very simple representation

``````vector<int> findSequence (int a)
{
vector<int> ans;

for(int i = 1; i < a;)
{
ans.push_back(i);
i *= 2;
}

return (ans.push_back(i));
}``````

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

all of you are wrong
23= 1 2 3 5 6 11 12 23 using 1
23= 1 2 4 8 16 17 19 23 using 2
Correct Solution is

1 2 3 5 10 20 23

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

all of you are wrong
23= 1 2 3 5 6 11 12 23 using 1
23= 1 2 4 8 16 17 19 23 using 2
Correct Solution is

1 2 3 5 10 20 23

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

My solution would yield 1 2 4 8 16 23...

My solution is right.

You are wrong.

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

sorry my return statement should be

return ans.push_back(a);

not return ans.push_back(i);

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

my bad i missed the rule that it must be only TWO numbers, so yes my solution is wrong

Comment hidden because of low score. Click to expand.
2
of 4 vote

My Approach for this problem is as bellow:

Let given Number is 'N'

Step 1: Put N in the sequence.
Step 2: If 'N' is even, put N/2 in sequence.
Step 3: if 'N' is odd then put N-1 in sequence because our sequence will contain 1 and ((N-1)+1) < (N-1), So it will stratify both the conditions.
Step 4: Repeat the Step 2 and 3 until we get 1 in the sequence.

Example:
42 => 21 => 20 => 10 => 5 => 4 => 2 => 1

Comment hidden because of low score. Click to expand.
2
of 6 vote

My Approach is as bellow :

Step 1: Put the 'N' in the sequence.
Step 2: If 'N' is even, put N/2 in the sequence.
Step 3: If 'N' is odd, put N/2+1 and N/2 in the sequence
Step 4: take the last element in the sequence and repeat the Step 2 and 3, until we get 1 in the sequence.

Example :
42 => 21 => 11 => 10 => 5 => 3 => 2 => 1
15 => 8 => 7 => 4 => 3 => 2 => 1

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

15=>10=>5=>3=>2=>1

Your solution is like everyone else's, i think we need to do a recursive approach and think from the ground up

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

Oh for Odd number we have to take care special action.
In the previous approach if number is odd, then we are taking N/2+1 and N/2. which means our next will be N/2.

But if our odd number is divisible by 3 ( 3N => 2N + N ) then we can put 2*(N/3) and (N/3). which means, our next number will be N/3 which is less then N/2.

So the modify approach is :
if N is even then put N/2 in the list
else if N is divisible by 3 then put 2*(N/3) and (N/3)
else put N/2+1 and N/2

example :
15 => 10 => 5 => 3 => 2 => 1
27 => 18 => 9 => 6 => 3 =>2 => 1
42 => 28 => 14 => 7 => 4 => 3 => 2 => 1

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

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

This is apparently NP-Hard: Lookup addition chains on the web.

Also see wwwhomes uni-bielefeld de / achim / addition_chain.html

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

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

Comment hidden because of low score. Click to expand.
1
of 3 vote

``````#include <cstdlib>
#include <iostream>

using namespace std;

void fun(int n)
{

if(n==1)
return;
if(n%2==0)
{
fun(n/2);
cout<<" "<<n/2;

}
else
{
fun(n/2);
cout<<" "<<(n/2)+1<<" "<<n/2;

}

}
int main(int argc, char *argv[])
{
int n=2355;

fun(n);
cout<<" "<<n;

system("PAUSE");
return EXIT_SUCCESS;
}``````

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

I think we sould be able to solve it using BFS.

1. Consider each number i, from 1 to n, a vertex such that it has directed edges to all numbers from {i+1, ..., k} (k = 2i if 2i is less than n, else n). Weight of all these edges is 1.

2. Now run BFS starting with vertex 1, until you discover vertex n.

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

This would be a O(n2) algo.

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

not all of i + 1 to 2i could be in the solution Set. And it doesnt seem to be n Square too. -1

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

not all of i + 1 to 2i could be in the solution Set. And it doesnt seem to be n Square too. -1

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

Step 1 is creating a graph for given problem. i+1 to 2i edges point to possible numbers that we can be created from number at current vertex.

For time complexity, i think i can you give a much tighter bound, i.e., O(n(n + 2)/4) => O(n^2)

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

Here i have tried to give you a matrix re-presentation of the graph for which we need to run BFS. If we use adjacency list representation, we get a tighter bound of O(n(n+1)/2) for BFS on this graph.

1 2 3 4 5 6 7 8 9 10
------------------------------------------
1 | 0 1 0 0 0 0 0 0 0 0
2 | 0 0 1 1 0 0 0 0 0 0
3 | 0 0 0 1 1 1 0 0 0 0
4 | 0 0 0 0 1 1 1 1 0 0
5 | 0 0 0 0 0 1 1 1 1 1
6 | 0 0 0 0 0 0 1 1 1 1
7 | 0 0 0 0 0 0 0 1 1 1
8 | 0 0 0 0 0 0 0 0 1 1
9 | 0 0 0 0 0 0 0 0 0 1
10| 0 0 0 0 0 0 0 0 0 0

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

``````Matrix re-loaded:

1 2 3 4 5 6 7 8 9 10
------------------------------------------
1  | 0 1 0 0 0 0 0 0 0 0
2  | 0 0 1 1 0 0 0 0 0 0
3  | 0 0 0 1 1 1 0 0 0 0
4  | 0 0 0 0 1 1 1 1 0 0
5  | 0 0 0 0 0 1 1 1 1 1
6  | 0 0 0 0 0 0 1 1 1 1
7  | 0 0 0 0 0 0 0 1 1 1
8  | 0 0 0 0 0 0 0 0 1 1
9  | 0 0 0 0 0 0 0 0 0 1
10| 0 0 0 0 0 0 0 0 0 0``````

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

Please consider the header row in above matrix shifted towards right and aligned to data below

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

import java.util.ArrayList;
import java.util.List;

public class Test {

public static void main(String args[])
{
Integer positivenum = new Integer(15);
Integer curr = positivenum;
List list = new ArrayList<Integer>(20);
System.out.println("Hello Java \n\n");
while(curr != 1)
// for(int k = 0 ;k<9;k++)
{
if(curr%2 == 0)
{
curr = curr/2;
}else
{
curr = curr/2 + 1;
--curr;
}
}
System.out.println("list : "+ list);
System.out.println("list : "+ list.size());
}
}

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

int _tmain(int argc, _TCHAR* argv[])
{
int curr = 15;

vector<int> list;
list.push_back(curr);

while(curr != 1)
{
if(curr%2 == 0)
{
curr /= 2;
list.push_back(curr);
}else
{
curr = curr/2 + 1;

list.push_back(curr);
--curr;
list.push_back(curr);
}
}

return 0;
}

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

``````int _tmain(int argc, _TCHAR* argv[])
{
int curr = atoi(argv[1]);

vector<int> list;
list.push_back(curr);

while( curr > 1 )
{
if( curr % 2 )
{
curr = curr >> 1;

list.push_back(++curr);
list.push_back(--curr);
}else
{
curr = curr >> 1;

list.push_back(curr);
}
}

return 0;
}``````

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

public static void doList(int targetNumber, int[] list, int lim,ArrayList<Integer> ans) {

if(list[lim-1] == targetNumber) {
if(ans.size() > lim-1 || ans.size() == 0) {
ans.clear();
for(int i =0; i < lim ;i++) ans.add(list[i]);
}
return;
}
//Generate new lim elements from 0 to lim-1
for(int i = 0; i < lim; i++) {
list[lim] = list[lim-1] + list[i];
if(list[lim] > targetNumber) continue;
doList(targetNumber, list, lim + 1,ans);
}
}

Takes a billion years to run though. I am not sure what optimizations are possible.

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

Code complexity

Lets see ... for each n, this code spawns n calls.

this happens upto n times.
Sum( n! ) where n goes from 0 to 1.

so 2^n

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

``````void getSequence (int finalSum)
{
if (finalSum < 1)  cout << "Invalid input, this is not allowed";

stack <int> collector;
vector <stack <int > > result;

collector.push(1);
collector.push(2);
int currentSum = 0;
//populate all the possible sequences
populateSequence (finalSum, currentSum, collector, result);

//check at least one sequence found
if (result.size() == 0) {
cout << "No valid sequence can be generated";
}

//check the smallest sequence among all and dump from the vector (result)
return;
}

void populateSequence (int finalSum, int currentSum, stack <int> &collector, vector <stack <int > > &result)
{
if (finalSum == currentSum) {
result.push_back(collector);
return;
}

if (finalSum < currentSum) {
return;
}

int first_pre  = collector.top();
collector.pop();
int second_pre = collector.top();
collector.pop();
int temp_sum   = first_pre + second_pre;

collector.push(second_pre);
collector.push(first_pre);
collector.push(temp_sum);
populateSequence(finalSum, temp_sum, collector, result);
collector.pop();

temp_sum = first_pre + first_pre;
collector.push(temp_sum);
populateSequence(finalSum, temp_sum, collector, result);
collector.pop();

return;
}``````

I agree the code can be optimized further .
Time Complexity (n^2)
Space Complexity (number of possible sequence * log n)

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

There are too many answers to read one by one. Here's my solution.
Suppose the length of the shortest solution for integer n is f(n), so:

f(n) = f(n/2) + 1 + n%2.

This is good enough to find one shortest solution. Of course there would be other ways to make it right. Please let me know if I'm wrong.

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

``````int f(int num)
{
if(num==1)
{
cout<<1<<endl;
return 1;
}
int m,n=0;
if(num%2)
{
cout<<num<<endl;
num--;
n++;
}
n++;
cout<<num<<endl;
m=n+f(num/2);
return m;
}``````

any feedback is much appreciated.

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

``cout<< "ALL ANSWERS ARE WRONG :P ";``

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

for number 42 , why cant the sequence be : (1, 41,42 ) . May be i understood the problem incorrectly , can someone please correct if i am wrong ?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is incorrect.
If n =15, the output is [ 1,2,3,4,7,8]
However the shortest sequence should be [1,2,4,8];

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

I feel [1,2,3,4,7,8] is the right sequence for 15.

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

1,2,3,6,7,14,15 another solution

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

right sequence would be [15,10,5,3,2,1]

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

[1,2,4,8] is not a possible sequence for 15, no two of those numbers sum to 15.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Basically we can write the number n=a +b such that a>=b

Now for all a,b combinations we have to create the sequence and keep track the minimum.
We can break it into finding the minimum sequence of a(Recusrion) and then checking if b i subset of that a. Before going ahead and checking the minimum.

Way to optimise:- Since we may create a sequence for 'a' multiple times it is better to store it in memory[ Dynamic programming].

To illustrate lets take n=7

min(7)=min(min(6) +1, min (5)+2, min(4)+3)...= 1,2,4,6,7 || 1,2 ,3,3,7|| 1,2,3,5,7|| 1,2,3,4,7

min(6)=min(min(5)+1, min(4)+2, min(3))... = min[(1,2,4,5,6) , (1,2,4,6), (1,2,3,6)]= (1,2,4,6) && (1,2,3,6)

min(5)=min(min(4)+1, min(3)+2)....= (1, 2,4,5) || (1,2,3,5)

min(4)= 1 2 4
min(3)= 1 2 3
min(2)=1 2

Comment hidden because of low score. Click to expand.
-1
of 1 vote

for shotest you have take the sum of two largest whose sum<=desire value.so every tim keep on adding last element with itself.if it exceed the last value then chek the sum of the last no with the remaining no..

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

Very good solution. Thanks NEO

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.