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());
}

- Anonymous May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kurskk141 May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- milo May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- first_user May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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));
}

- first_user May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aryan May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aryan May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What are you talking about?

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

My solution is right.

You are wrong.

- first_user May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry my return statement should be

return ans.push_back(a);

not return ans.push_back(i);

- first_user May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- first_user May 02, 2012 | Flag
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

- Vinit Saini May 03, 2012 | Flag Reply
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

- vinit.saini.ynr May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for your comments. Future comments are welcome.

- Anonymous May 04, 2012 | Flag
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

- Anonymous May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is correct answer.

Some LOSER has downvoted many answers... perhaps one the other answerers.

- Anonymous May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please note that this is the correct answer. Google for addition chain. Computing shortest addition chain is an NP Hard problem.

- jagadish1989 June 24, 2012 | Flag
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;
}

- Learn Android: http://learnandroideasily.blogspot.in/ May 02, 2012 | Flag Reply
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.

- Manas May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would be a O(n2) algo.

- Manas May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aryan May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aryan May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Manas May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Manas May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Manas May 03, 2012 | Flag
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");
list.add(curr);
while(curr != 1)
// for(int k = 0 ;k<9;k++)
{
if(curr%2 == 0)
{
curr = curr/2;
list.add(curr);
}else
{
curr = curr/2 + 1;
list.add(curr);
--curr;
list.add(curr);
}
}
System.out.println("list : "+ list);
System.out.println("list : "+ list.size());
}
}

- NEO May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Anonymous May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Const May 02, 2012 | Flag
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) {
System.out.print("\nAdded "+ lim);
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.

- a.smith May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- a.smith May 02, 2012 | Flag
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)

- rahul449 May 02, 2012 | Flag Reply
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.

- Terry May 07, 2012 | Flag Reply
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.

- epsilon May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- MAtrix May 20, 2012 | Flag Reply
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 ?

- Anonymous June 12, 2012 | Flag Reply
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];

- LLY May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Arun May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- milo May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- NEO May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- RossM May 03, 2012 | Flag
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

- avimonk May 02, 2012 | Flag Reply
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..

- jai May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very good solution. Thanks NEO

- Qing May 02, 2012 | Flag


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