Amazon Interview Question for SDE1s


Country: India
Interview Type: Phone Interview




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

Answer to this question is Either sumof(N) -1 orr Sumof(N) depends if sum of initial A steps sumof(A) is Equal to K of not. If we can jump off the Kth step.

If not i.e. if we can't cross the kth step as it is broken..

So at max we can reach upto k-1 step

we can start subtracting k with the step starting from n then n-1 and so on. when the value is less then 0, Don't take that step and move to next.

- sanjay.2812 May 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't see how to post a solution. So I post it as a reply. Sorry about that.

Below is the pseudo code. The idea is that just get the optimal case. (step every time.) If it does not step on K, good. That should be the optimal solution.

If it happens to step on Kth stair, the optimal case must be all the steps without the first step(1st step).

Why? Proof below:

Proof :
If we step on Kth stairs, there must be a case without Ith step, we cannot reach K.
We always avoid Kth stair by not stepping the 1st step since K != (K-1).
For an arbitrary I, I >= 1 is always true,
thus SumFrom1ToN - 1 >= SumFrom1ToN - I is always true.

Thus, skipping the 1st step is always optimal.

Solution :

long long sum = 0;
for(int i = 0 ; i < k ; i++)
{
sum += i;
if( sum > K ) {
return SumFrom1ToN(N); //Because this is optimal case. Just stepping every time does happen to step on Kth stair.
}
else if( sum == K ) { // Stepping on K, so we could just not step the first step.
return SumFrom1ToN(N) - 1;
}
}
return -1; // error. impossible to get here.

- taekout June 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the working code and output:

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    private int maxStep(int currentStep, int totalMoves, int brokenStep, int currentMove) {
        if(totalMoves == 0) {
        	return currentStep;
        }
        if(currentMove > totalMoves) {
        	return currentStep;
        }
        if(currentStep + currentMove == brokenStep)
            return maxStep(currentStep, totalMoves, brokenStep, currentMove+1);
        else
            return Math.max(maxStep(currentStep, totalMoves, brokenStep, currentMove+1), maxStep(currentStep+currentMove, totalMoves, brokenStep, currentMove+1));
    }

	public static void main (String[] args) throws java.lang.Exception {
		Ideone one = new Ideone();
		System.out.println(one.maxStep(0, 4, 10, 1));
		System.out.println(one.maxStep(0, 3, 1, 1));
		System.out.println(one.maxStep(0, 3, 2, 1));
	}
}

Success time: 0.09 memory: 320320 signal:0
9
5
6

- abhishek08aug April 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you consider condition, that no step is taken?

General question: why there is a such condition, that at n action, step might or might not be taken?

- Marcello Ghali April 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

return Math.max(maxStep(currentStep, totalMoves, brokenStep, currentMove+1), maxStep(currentStep+currentMove, totalMoves, brokenStep, currentMove+1));

First part is for the case when no step is taken. Steps are not taken when

1) You end up stepping on the broken step.
2) Not taking some particular step could help you taking a later longer step

- abhishek08aug April 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

abishek, maybe I'm missing something or misunderstanding the question.
In the second output how can there be 5 total steps when the broken step is at 1?
Shouldn't the output be the total steps you can take before you reach the broken step? My impression was that you cannot go at or beyond the broken step.

- Alex April 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"totalMoves" is not decremented

- Naveed May 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you write the code for this solution in c

- Codie April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findMaxSteps(int n, int k)
{
	int ans = (n * (n + 1)) >> 1, x = (sqrt(8 * k + 1) - 1) / 2;

	return (x * (x + 1)) >> 1 == k ? ans - 1 : ans;
}

- malinbupt May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't see how to post a solution. So I post it as a reply. Sorry about that.

Below is the pseudo code. The idea is that just get the optimal case. (step every time.) If it does not step on K, good. That should be the optimal solution.

If it happens to step on Kth stair, the optimal case must be all the steps without the first step(1st step).

Why? Proof below:

Proof :
If we step on Kth stairs, there must be a case without Ith step, we cannot reach K.
We always avoid Kth stair by not stepping the 1st step since K != (K-1).
For an arbitrary I, I >= 1 is always true,
thus SumFrom1ToN - 1 >= SumFrom1ToN - I is always true.

Thus, skipping the 1st step is always optimal.

Solution :

long long sum = 0;
for(int i = 0 ; i < k ; i++)
{
	sum += i;
	if( sum > K ) {
		return SumFrom1ToN(N); //Because this is optimal case. Just stepping every time does happen to step on Kth stair.
	}
	else if( sum == K ) { // Stepping on K, so we could just not step the first step.
		return SumFrom1ToN(N) - 1;
	}
}

return -1; // error. impossible to get here.

- taekout June 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also have a dynamic programming solution.
It works for general cases. (multiple Ks).

It runs better than exponential complexity. (K^3)

- taekout June 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

[{(n+1)*n}/2]-k

- AMit February 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Everytime we take a step, we need to ensure that we won't be resting on the 'k'th step which is broken. All other steps we can take. Please check the solution below.

int fnMaxSteps(int n,int k){
int steps = 0;
for (int i=1;i<=n;i++){
	if(steps+i==k)
		continue;
	else
		steps+=i;
}
return steps;
}

- Kiran Vadakath April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider the case with n=4 and k=10.

Your solution will give: 1+2+3+0=6.

However the correct solution is: 0+2+3+4=9.

- abhishek08aug April 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You know that you will reach k by following the pattern 1,2,3,4,... if 1 + 2 + 3 + 4 + 5 +...a = k

What does this remind us of?

1 + 2 + 3 + 4 + 5 +...x = (x)(x + 1)/2


So, we can work from here and see if there's an x such that this case is true. If not, then our answer is (n)(n+1)/2

If so, we do

(x-1)(x)/2 + remaining steps starting from x +1.

remaining steps starting from x + 1 would be (n + 1)(n + 2)/2 - (x)(x+1)/2

So our final answer would be

(x - 1)(x)/2 + (n + 1)(n + 2)/2 - (x)(x+1)/2

public int numSteps(int k, int n) {
	
	if (!integerSolutionExists(k)) {

		return getSum(n);
	}

	int x = (int) solveQuadratic(k);

	return getSum(x - 1) + getSum(n) - getSum(x);
}

public int getSum(int x) {
	
	return (x * (x + 1))/2
}

public boolean integerSolutionExists(int k) {
	
	return(Math.floor(solveQuadratic(k)) == solveQuadratic(k));
}

public double solveQuadratic(int k) {
	
	return (-1 + Math.sqrt(1 - 4 * (-2 * k)))/2;
}

- SK April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The question is to find the maximum steps we can go.
If there exists an integer solution to quadratic equation(as you mentioned), then we can skip the first step to escape on landing kth step.
Then the solution would be something like follows.
1+2+...x = k --> solve this, if there exists integer solution, answer would be n(n+1)/2 -1 else, n(n+1)/2

- bharat April 27, 2015 | 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