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

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

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.

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

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

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?

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

``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

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

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.

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

"totalMoves" is not decremented

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

can you write the code for this solution in c

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

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.

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

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

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

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

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

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

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

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

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

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

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

public int getSum(int x) {

return (x * (x + 1))/2
}

public boolean integerSolutionExists(int k) {

}

return (-1 + Math.sqrt(1 - 4 * (-2 * k)))/2;
}``````

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

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.